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 :-
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
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 :-
Code:
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.
I've got no idea what section (b) above is doing to the process though.... could someone explain this to me?
Regards,
Paul
Comment