패킷 통신 - CRC

통신에 있어서 데이터를 수신하는 측에서는 수신한 데이터가 오류없이 제대로 들어왔는지 궁금할 때가 있다.  전송 선로의 길이가 길거나, 아니면 아예 선이 없는 무선 통신의 경우에는 더더욱 수신된 데이터에 대한 신뢰가 떨어지게 된다.

이러한 이유로 다양한 방법을 사용해서 수신된 데이터에 오류가 발생했는지 여부를 확인할 수 있게 한다.  쉽게 사용할 수 있는 방법이 체크섬(check sum)이다.

이 방법은 8비트 혹은 16비트 단위로 모든 데이터를 더해서 그 마지막 결과값을 추가로 데이터에 덧붙여 보내주면, 수신측에서 동일한 계산을 하여 check sum값이 같은지 비교해서 수신한 데이터의 오류를 판단할 수 있게 하는것이다.  그러나 단순한 덧셈 연산이기 때문에 어떤 데이터에 1이 더한 값이 전달되고, 다른 데이터는 1 적은 값이 수신되었을 때에는 check sum은 같은 값으로 계산이 되어 실제로는 오류가 두개가 발생했음에도 불구하고 수신측에서는 데이터에 오류가 없다고 판단하게 된다.

Check sum 보다 좀더 오류에 대한 신뢰성 있는 검사 방법이 CRC를 이용하는 것이다.

CRC는 간단히 얘기해서 수신된 데이터를 특정 패턴으로 나누기를 수행하여 최종 나머지 값을 데이터에 덧붙여 보내는 방법이다.  나누기 계산이기 때문에 한 비트라도 데이터에 오류가 있으면 나머지 값이 완전히 달라지기 때문에 훨씬 높은 신뢰성을 보장한다고 볼 수 있다.

앞의 글에서 나온 HDLC 패킷의 Stop flag 바로 앞에 있는 FCS가 바로 CRC에 해당되는 필드이다.

CRC 구하는 방법도 굉장히 많지만 HDLC에서 사용하는 CRC16-CCITT를 이용하여 CRC 계산을 수행하도록 하겠다.

CRC를 계산 하는 방법은 입문 과정의 LED 온도계 2에서 설명하였듯이 매번 수신된 데이터에 대하여 CRC 공식을 적용해서 계산할 수도 있고, 아니면, 처음부터 CRC 테이블을 만들어 놓고 이 테이블에서 각 데이터에 따른 값을 불러와서 CRC를 계산할 수도 있다.

이 블로그에서는 테이블 방식을 이용해서 CRC를 계산하도록 하겠다.

#include <stdint.h> #include <avr/pgmspace.h> static const uint16_t crc16_tab[] PROGMEM = { 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0, }; uint16_t crc16(uint8_t *buf, int len) { int i; uint16_t crc; crc = 0; for (i = 0; i < len; i++) { crc = pgm_read_word(&(crc16_tab[((crc>>8) ^ *buf++) & 0xFF])) ^ (crc << 8); } return crc; }

테이블 방식의 CRC 계산의 단점은 CRC 테이블이 많은 양의 SRAM 메모리를 점유하게 된다는 것이다.  위의 코드에 나오는 crc16_tab[]의 크기는 512바이트이다.  이 크기는 ATmega328의 전체 SRAM 메모리 크기인 2Kbyte의 1/4에 해당하는 크기이다.  결코 작은 크기가 아닌것을 알 수 있다.

CRC 테이블은 읽기 전용 데이터이므로 굳이 SRAM 메모리에 위치시킬 필요가 없고, 플래쉬메모리 영역에 위치시켜도 된다.  이를 위하여 crc16_tab[] 다음에 PROGMEM이라는 것을 추가하여 program memory space에 위치 시키도록 한다.

Program memory에 있는 데이터를 읽어 올때는 그냥 읽어 올수가 없고 pgm_read_word()라는 함수를 사용하여야 한다.

extern uint16_t crc16(const uint8_t *buf, int len); static void send_packet(const uint8_t *pkt, uint8_t len) { uint16_t crc = crc16(pkt, len); uint8_t data; int i; uart_tx(HDLC_FLAG); for (i=0; i<len; i++) { data = *pkt++; if (data == HDLC_FLAG || data == ESC_FLAG) { uart_tx(ESC_FLAG); uart_tx(data ^ ESC_CHAR); } else { uart_tx(data); } } data = (crc >> 8) & 0xFF; if (data == HDLC_FLAG || data == ESC_FLAG) { uart_tx(ESC_FLAG); uart_tx(data ^ ESC_CHAR); } else { uart_tx(data); } data = crc & 0xFF; if (data == HDLC_FLAG || data == ESC_FLAG) { uart_tx(ESC_FLAG); uart_tx(data ^ ESC_CHAR); } else { uart_tx(data); } uart_tx(HDLC_FLAG); }

send_packet() 함수에서는 일단 데이터 부분에 대해서 CRC값을 먼저 구한다.  그 이후 데이터 부분을 UART로 내 보낸후 뒤이어 CRC값을 내 보낸다.  물론 데이터와 CRC 앞뒤에 Start/Stop flag를 보내어 패킷의 시작과 끝을 알려줘야 한다.

컴퓨터에서 crc를 포함한 데이터가 수신되는지 확인한다.

빨간색 박스 부분이 crc값에 해당되는 것이다.  그럼 이 값이 제대로된 CRC값인지 컴퓨터 프로그램에서 CRC검사를 하여 같은 값이 나오는지 확인해 보도록 하겠다.

참고로 수신측에서는 CRC값까지 포함하여 CRC검사를 하면 항상 0이 나와야 한다.  0이 아닌값이 나오면 데이터에 오류가 있다고 판단할 수 있다.

def crc16(data, crc=0): for byte in data: crc = ((crc<<8)&0xff00) ^ crc16_tab[((crc>>8)&0xff)^byte] return crc & 0xffff def processInPacket(self): data_index = self.data_index self.started = False self.data_index = 0 buf = array.array('B') escaped = False index = 0 for i in range(data_index): data = self.data_buf[i] if data == ESC_FLAG: escaped = True else: if escaped: buf.append(data ^ ESC_CHAR) escaped = False else: buf.append(data) self.parent.processPacket(buf, crc16(buf)) def processPacket(self,packet,crc): msg = 'Packet: ' for i in packet: msg += '0x%02X ' % i msg += 'CRC[0x%04X] ' % crc self.dbgBox.AppendText(msg+'\n')

CRC 검사를 수행한 결과는 다음과 같다.

CRC 계산을 한 결과값이 모두 0이 됨을 볼 수 있다.  그렇다는 얘기는 데이터에 에러가 발생하지 않았다고 판단할 수 있는 것이다.

crc16.cpacket.cSerialPacket.py

심화 과정 목차