CCITT CRC-16
디지탈 데이터를 송수신하는 과정에서 데이터가 오류없이 정상적으로 수신되었는지 확인하기 위해 흔히 CRC(Cyclic Redundancy Code)를 사용한다. CRC에는 다양한 종류가 있는데, 대표적인 것이 CCITT CRC-16이다. 이것은 전송데이터를 특정 다항식을 이용하여 나눗셈을 수행하고 남은 나머지 16비트를 전송데이터의 뒷부분에 추가적으로 전송하는 것을 의미한다. 수신측에서는 동일한 다항식으로 나눗셈을 수행하여 나머지가 특정값이면 수신데이터에 오류가 없다고 추정하는 것이다. CCITT CRC-16의 다항식은 다음과 같다. 또는 0x1021 위 다항식의 좌측을 이진수로 표시하면 b’10001000000100001로 표기할 수 있으며, 우측은 이를 16진수로 표기한 것으로 MSB는 항상 1이기 때문에 이를 생략하고 16비트만 표기한 것이다. CRC의 계산은 전송하고자 하는 2진 데이터에 을 곱하고, 즉 b’10000000000000000을 곱하고 이를 위의 다항식으로 나누어서 나머지를 데이터에 이어서 전송하는 것이다. 수신측에서는 수신한 데이터를 위의 다항식으로 나누어 나머지가 0이면 수신데이터에 오류가 없는 것이고 0이 아니면 데이터에 오류가 발생하였다는 것을 의미한다. 나누는 과정에서는 일반적인 산술 나누기와 달리 각 비트 간에 xor을 수행한다. 이 과정을 간단하게 설명하기 위해 3비트의 CRC를 계산하는 과정을 살펴보면 다음과 같다. 우선 다항식을 b’011로 하고 전송하고자 하는 데이터를 b’11010011101100 라고 한다면 송수신부의 CRC 계산 과정은 다음과 같다. - 송신부 - 수신부(오류가 없는 경우) - 수신부(오류 포함) 그런데, 위의 CRC를 계산하는 과정은 shift register를 이용하여 다음과 같이 쉽게 구현할 수 있다. 여기서 + 는 modulo 2 더하기를 의미한다. 즉 2 비트를 xor을 취하면 된다. 이제 다시 CCITT CRC-16 다항식을 적용하여 보면 회로는 다음과 같이 구성할 수 있다...