AN-1251 APPLICATION NOTE One Technology Way • P.O. Box 9106 • Norwood, MA 02062-9106, U.S.A. • Tel: 781.329.4700 • Fax: 781.461.3113 • www.analog.com ADAS1000 Cyclic Redundancy Code by Padraic O’Reilly INTRODUCTION This application note details the ADAS1000 cyclic redundancy code. The aim of error detection is to enable the receiver of a message to determine whether the message has been corrupted. To do this, the ADAS1000 constructs a code (called a checksum) that is a function of the message and appends it to the message. The CRC algorithms simply treat the message as an enormous polynomial, dividing it by another fixed polynomial using Modulo 2 arithmetic for the coefficients, and making the remainder from this division the checksum. Upon receipt of the message, the receiver can perform the same division and compare the remainder with the checksum. This application note describes how the code (checksum) for the ADAS1000 is calculated. Rev. 0 | Page 1 of 8 AN-1251 Application Note TABLE OF CONTENTS Introduction ...................................................................................... 1 Computing the CRC Using the ADAS1000 ...............................3 Revision History ............................................................................... 2 Verifying the CRC on the Receiver Side ....................................5 Cyclic Redundancy Code ................................................................ 3 REVISION HISTORY 3/14—Revision 0: Initial Version Rev. 0 | Page 2 of 8 Application Note AN-1251 CYCLIC REDUNDANCY CODE COMPUTING THE CRC USING THE ADAS1000 For each bit in the message, a series of six steps occurs. 128 kHz Data Rate Example 1. For a 128 kHz data rate, the polynomial used is 2. 3. x16 + x12 + x5 + x0 This is also known as the CRC-16-CCITT polynomial. 4. When translated into hexadecimal, this polynomial reads 0x11021 (polynomial: 10001000000100001). The ADAS1000 presets the CRC register to all ones (0xFFFF) where the CRC register is 1111111111111111. 5. For each data bit (below for 16-bits), the remainder shifts left by one. The MSB of the remainder is XOR’d with the data bit. If the resulting MSB is 1, the remainder is then XOR’d with the polynomial. If the resulting MSB is 0, the remainder is not XOR’d with the polynomial. Repeat Step 1 through Step 4 for each data bit. Note that data bits are shifted MSB first. The result in the CRC register, after all message bits are shifted through the register as described, is the CRC code. For example, when transmitting the header only using the ADAS1000, one expects the header to contain the message: 0x8000 (1000000000000000). 1111111111111111 initial CRC is pre-set all ones < 11111111111111110 shift CRC ^ 1 XOR with data bit 15 = 1111111111111110 CRC after data bit 15 < ^ = ^ = 11111111111111100 0 11111111111111100 10001000000100001 1110111111011101 < ^ = ^ = 11101111110111010 0 11101111110111010 10001000000100001 1100111110011011 < ^ = ^ = 11001111100110110 0 11001111100110110 10001000000100001 1000111100010111 < ^ = ^ = 10001111000101110 0 10001111000101110 10001000000100001 0000111000001111 shift CRC XOR with data bit 14 XOR with poly CRC after data bit 14 shift CRC XOR with data bit 13 XOR with poly CRC after data bit 13 shift CRC XOR with data bit 12 XOR with poly CRC after data bit 12 shift CRC XOR with data bit 11 XOR with poly CRC after data bit 11 < 00001110000011110 shift CRC ^ 0 XOR with data bit 10 = 0001110000011110 CRC after data bit 10 < 00011100000111100 shift CRC ^ 0 XOR with data bit 9 = 0011100000111100 CRC after data bit 9 Rev. 0 | Page 3 of 8 AN-1251 Application Note < 00111000001111000 shift CRC ^ 0 XOR with data bit 8 = 0111000001111000 CRC after data bit 8 < 01110000011110000 shift CRC ^ 0 XOR with data bit 7 = 1110000011110000 CRC after data bit 7 < ^ = ^ = 11100000111100000 0 11100000111100000 10001000000100001 1101000111000001 < ^ = ^ = 11010001110000010 0 11010001110000010 10001000000100001 1011001110100011 < ^ = ^ = 10110011101000110 0 10110011101000110 10001000000100001 0111011101100111 shift CRC XOR with data bit 6 XOR with poly CRC after data bit 6 shift CRC XOR with data bit 5 XOR with poly CRC after data bit 5 shift CRC XOR with data bit 4 XOR with poly CRC after data bit 4 < 01110111011001110 shift CRC ^ 0 XOR with data bit 3 = 1110111011001110 CRC after data bit 3 < ^ = ^ = 11101110110011100 0 11101110110011100 10001000000100001 1100110110111101 < ^ = ^ = 11001101101111010 0 11001101101111010 10001000000100001 1000101101011011 < ^ = ^ = 10001011010110110 0 10001011010110110 10001000000100001 0000011010010111 shift CRC XOR with data bit 2 XOR with poly CRC after data bit 2 shift CRC XOR with data bit 1 XOR with poly CRC after data bit 1 shift CRC XOR with data bit 0 XOR with poly CRC after data bit 0 In this example, the CRC result is 0x0697. The ADAS1000 inverts message 0x0697 (0000011010010111) before transmission, as stated in the data sheet, and the message becomes 0xF968 (1111100101101000). The full transmission should contain 0x8000F968. The message is appended by the CRC. Rev. 0 | Page 4 of 8 Application Note AN-1251 VERIFYING THE CRC ON THE RECEIVER SIDE 128 kHz Data Rate Example To verify that data was correctly received, the software should compute a CRC on both the data and the received checksum. 1111111111111111 The same steps (Step 1 through Step 5 in the Computing the CRC Using the ADAS1000 section) are applied to the each data bit and received checksum 0x8000F968 (10000000000000001111100101101000). initial CRC is pre-set all ones < 11111111111111110 shift CRC ^ 1 XOR with data bit 31 = 1111111111111110 CRC after data bit 31 < ^ = ^ = 11111111111111100 0 11111111111111100 10001000000100001 1110111111011101 shift CRC XOR with data bit 30 < ^ = ^ = 11101111110111010 0 11101111110111010 10001000000100001 1100111110011011 shift CRC XOR with data bit 29 < ^ = ^ = 11001111100110110 0 11001111100110110 10001000000100001 1000111100010111 shift CRC XOR with data bit 28 < ^ = ^ = 10001111000101110 0 10001111000101110 10001000000100001 0000111000001111 XOR with poly CRC after data bit 30 XOR with poly CRC after data bit 29 XOR with poly CRC after data bit 28 shift CRC XOR with data bit 27 XOR with poly CRC after data bit 27 < 00001110000011110 shift CRC ^ 0 XOR with data bit 26 = 0001110000011110 CRC after data bit 26 < 00011100000111100 shift CRC ^ 0 XOR with data bit 25 = 0011100000111100 CRC after data bit 25 < 00111000001111000 shift CRC ^ 0 XOR with data bit 24 = 0111000001111000 CRC after data bit 24 < 01110000011110000 shift CRC ^ 0 XOR with data bit 23 = 1110000011110000 CRC after data bit 23 < ^ = ^ = 11100000111100000 0 11100000111100000 10001000000100001 1101000111000001 shift CRC XOR with data bit 22 XOR with poly CRC after data bit 22 < 11010001110000010 shift CRC Rev. 0 | Page 5 of 8 AN-1251 Application Note ^ 0 XOR with data bit 21 = 11010001110000010 ^ 10001000000100001 XOR with poly = 1011001110100011 CRC after data bit 21 < ^ = ^ = 10110011101000110 0 10110011101000110 10001000000100001 0111011101100111 shift CRC XOR with data bit 20 XOR with poly CRC after data bit 20 < 01110111011001110 shift CRC ^ 0 XOR with data bit 19 = 1110111011001110 CRC after data bit 19 < ^ = ^ = 11101110110011100 0 11101110110011100 10001000000100001 1100110110111101 shift CRC XOR with data bit 18 < ^ = ^ = 11001101101111010 0 11001101101111010 10001000000100001 1000101101011011 shift CRC XOR with data bit 17 < ^ = ^ = 10001011010110110 0 10001011010110110 10001000000100001 0000011010010111 shift CRC XOR with data bit 16 < ^ = ^ = 00000110100101110 1 10000110100101110 10001000000100001 0001110100001111 shift CRC XOR with RX CRC bit 15 < ^ = ^ = 00011101000011110 1 10011101000011110 10001000000100001 0010101000111111 shift CRC XOR with RX CRC bit 14 < ^ = ^ = 00101010001111110 1 10101010001111110 10001000000100001 0100010001011111 shift CRC XOR with RX CRC bit 13 < ^ = ^ = 01000100010111110 1 11000100010111110 10001000000100001 1001100010011111 shift CRC XOR with RX CRC bit 12 XOR with poly CRC after data bit 18 XOR with poly CRC after data bit 17 XOR with poly CRC after data bit 16 XOR with poly CRC after RX CRC bit 15 XOR with poly CRC after RX CRC bit 14 XOR with poly CRC after RX CRC bit 13 XOR with poly CRC after RX CRC bit 12 < 10011000100111110 shift CRC ^ 1 XOR with RX CRC bit 11 = 0011000100111110 CRC after RX CRC bit 11 Rev. 0 | Page 6 of 8 Application Note AN-1251 < 00110001001111100 shift CRC ^ 0 XOR with RX CRC bit 10 = 0110001001111100 CRC after RX CRC bit 10 < 01100010011111000 shift CRC ^ 0 XOR with RX CRC bit 9 = 1100010011111000 CRC after RX CRC bit 9 < 11000100111110000 shift CRC ^ 1 XOR with RX CRC bit 8 = 1000100111110000 CRC after RX CRC bit 8 < ^ = ^ = 10001001111100000 0 10001001111100000 10001000000100001 0000001111000001 shift CRC XOR with RX CRC bit 7 < ^ = ^ = 00000011110000010 1 10000011110000010 10001000000100001 0001011110100011 shift CRC XOR with RX CRC bit 6 < ^ = ^ = 00010111101000110 1 10010111101000110 10001000000100001 0011111101100111 shift CRC XOR with RX CRC bit 5 XOR with poly CRC after RX CRC bit 7 XOR with poly CRC after RX CRC bit 6 XOR with poly CRC after RX CRC bit 5 < 00111111011001110 shift CRC ^ 0 XOR with RX CRC bit 4 = 0111111011001110 CRC after RX CRC bit 4 < ^ = ^ = 01111110110011100 1 11111110110011100 10001000000100001 1110110110111101 shift CRC XOR with RX CRC bit 3 < ^ = ^ = 11101101101111010 0 11101101101111010 10001000000100001 1100101101011011 shift CRC XOR with RX CRC bit 2 < ^ = ^ = 11001011010110110 0 11001011010110110 10001000000100001 1000011010010111 shift CRC XOR with RX CRC bit 1 < ^ = ^ = 10000110100101110 0 10000110100101110 10001000000100001 0001110100001111 shift CRC XOR with RX CRC bit 0 XOR with poly CRC after RX CRC bit 3 XOR with poly CRC after RX CRC bit 2 XOR with poly CRC after RX CRC bit 1 XOR with poly CRC after RX CRC bit 0 If the CRC is correct, the remainder on the receive side equals 0x1D0F, the check constant. Rev. 0 | Page 7 of 8 AN-1251 Application Note 2 kHz and 16 kHz Data Rate Examples For 2 kHz and 16 kHz data rates, the polynomial used is Note that data bits are shifted MSB first. x +x +x +x +x +x +x +x +x +x +x +x + x6 + x3 + x1 + x0 24 22 20 19 18 16 14 13 11 10 8 7 The ADAS1000 inverts message CRC before transmission, as stated in the data sheet, and the message becomes the data and the inverted CRC. This is also known as the 24-bit CRC polynomial. When translated into hexadecimal, this polynomial reads 0x15D6DCB (polynomial: 1010111010110110111001011). The ADAS1000 presets the CRC register to all ones (0xFFFFFF) where the CRC register is 111111111111111111111111. For each bit in the message, a series of steps occurs. 1. 2. 3. 4. 5. The result in the CRC register, after all message bits are shifted through the register as described, is the CRC code. For each data bit, the remainder shifts left by one. The MSB of the remainder is XOR’d with the data bit. If the resulting MSB is 1, the remainder is then XOR’d with the polynomial. If the resulting MSB is 0, the remainder is not XOR’d with the polynomial. Repeat Step 1 through Step 4 for each data bit. To verify that data was correctly received, the software should compute a CRC on both the data and the received checksum. The same steps are applied to each data bit and received checksum and data. If the CRC is correct, the remainder on the receive side equals 0x15A0BA, the check constant. ©2014 Analog Devices, Inc. All rights reserved. Trademarks and registered trademarks are the property of their respective owners. AN11548-0-3/14(0) Rev. 0 | Page 8 of 8