ISDN CRC Calculation Problem

[Paul Thrower]

Hi Folks.

I'm having trouble coding a CRC16 routine to check the message payload of an ISDN message.

Despite much browsing of the forums and the WWW, I cannot come up with an algorythm to re-produce a known good checksum.

For example, an Primary-rate ISDN 'SABME' message appears as '0x00 0x01 0x7F 0x64 0x54'.
The "00 01 7F" bit is the 'SABME' message, and the "64 54" bit is the CRC16, which *should* be correct, since this comes from a known good bit of test equipment.
(The bitstream appears LSB first on the wire, in other words |00000000|10000000|11111110|00100110|00101010|)

No matter what I do with my code,(tinkering with Augmentation, Reflection of poly and data etc.) I cannot get a CRC of "64 54" in response to a message of "00 01 7F".

Quoting the ITU's Q.921 specification, we see :-

"
2.7 Frame Check Sequence (FCS) field
The FCS field shall be a 16-bit sequence. It shall be the ones complement of the sum (modulo 2) of:

(a) the remainder of xk (x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1) divided (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, where k is the number of bits in the frame existing between, but not including, the final bit of the opening flag and the first bit of the FCS, excluding bits inserted for transparency; and

(b) the remainder of the division (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, of the product of x16 by the content of the frame existing between, but not including, the final bit of the opening flag and the first bit of the FCS, excluding bits inserted for transparency.

As a typical implementation at the transmitter, the initial content of the register of the device computing the remainder of the division is preset to all 1s and is then modified by division by the generator polynomial (as described above) on the address, control and information fields; the ones complement of the resulting remainder is transmitted as the 16-bit FCS.

As a typical implementation at the receiver, the initial content of the register of the device computing the remainder is preset to all 1s. The final remainder, after multiplication by x16 and then division (modulo 2) by the generator polynomial x16 + x12 + x5 + 1 of the serial incoming protected bits and the FCS, will be 0001110100001111 (x15 through x0, respectively) in the absence of transmission errors.
"

This leads me to believe that the 'poly' needed is 0x01021 [ See (a) above ], the 'seed' value is 0xFFFF, and that the final CRC-16 is inverted [ "the ones complement" ] after calculation.

In pseudocode, what I'm doing at the moment is :-

1)  load LFSR with all "1"s
2)  while not end of message
2a)   shift the LFSR left by 1
2b)   read the next data bit into the LFSR at b0
2c)   if a 1 popped out at the top of the LFSR, then XOR LFSR with the 'poly'
2)  end while 
3)  invert the LFSR
4)  return LFSR as the result.

It's worth noting that the simple slow (Non-table based!) code I've done seems to pass a suggested test, meaning that a string of "123456789" ends up with a CRC16 of 0x0E5CC ok....

I've got no idea what section (b) above is doing to the process though.... could someone explain this to me?

Regards,

Paul

[Peter Lameijn]

Are you sure the sample code you have is ok? I assume it's a normal CCITT CRC-16?
This code is known to be good and gives a different result:

#Compile Exe
#Dim All
'
#Include "win32api.inc"
   
%POLY_CRC16  = &H11021
  
Function Crc_16(dStr As String) As Word
  Local Cnt As Long, Buff As String, Crc As Word, dwTemp As Dword
  Buff = String$(16, "1")
  For Cnt = 1 To Len(dStr)
    Buff = Buff & Bin$(Asc(dStr, Cnt), 8)
  Next
  Buff = Buff & String$(16, "0")
  dwTemp = Val ("&b" & Mid$(Buff, 1, 16))
  For Cnt = 17 To Len(Buff)
    Shift Left dwTemp, 1
    Bit Calc dwTemp, 0, (Mid$(Buff,Cnt,1) = "1")
    If Bit (dwTemp, 16) Then dwTemp = dwTemp Xor %POLY_CRC16
  Next
  Function = dwTemp
End Function
 
'===============================
Function PBMain () As Long
  MsgBox "CRC-16 of string 0x00, 0x01, 0x7F is:   0x" & Hex$(Crc_16(Chr$(&h00,&h01,&h7F)),4),,"Result:"
End Function

[Paul Thrower]

Thanks for the reply, Peter.

I'm not sure that it actually is a CCITT-CRC16, thats the problem :-)
I think that Section 2.7(b) (see above) does something over and above the normal CCITT method. Remember, I don't speak enough 'pure math' to confirm or deny this :-)

I'll check out your example and see if it matches what I've managed so far when I get back to the salt mine in a week or so :-)

Regard,

Paul

[Peter Lameijn]

I never used low level ISDN programming (mostly use API that comes with ISDN device), but shouldn't a packet be longer as 5 bytes? Found this:

[Paul Thrower]

Hi Peter.

IMHO, The shortest possible frame for an ISDN message in this case is 3 octets of 'message' and 2 octets of FCS\CRC (The FCS octets are usually stripped off before sending to the next layer up in the stack).

This 'SABME' message is a link-maintenance message, not an information-bearing message so it doesn't have any 'informational payload' associated with it, meaning the I-Field is null/zero length. I can't supply a reference as I'm out and about without my Laptop at the moment, but if you're curious you can have a look at the ITU's Q.921.

The 5 byte example I use above is valid - this is just a 'SABME' frame, which has 2 octets of "Address", and one octet of "Control", as all ISDN frames do.
The 'extra' 2 bytes are just the (usually unseen) FCS. Unfortunately, I'm looking at the bitstream on the wire here, meaning the FCS octets are visible in the trace.
If you're used to using the API's of ISDN devices, you'll probably know this 'SABME' frame as an MDL-ESTABLISH-IND or MDL-ESTABLISH-REQ event/indication.