CRC(Cyclic Redundancy Check)는 순환 부호를 쓰는 오류 제어 방법으로, 주로 오류 검출에 쓴다. 보호할 데이터 블록의 비트를 다항식의 계수로 보고 정해진 생성 다항식으로 모듈로 2 나눗셈을 해, 그 나머지를 블록 검사 시퀀스로 데이터 블록에 붙인다.[1] 이 나머지 값도 CRC라 부른다.[2][3]
CRC는 전송하거나 저장하는 데이터의 오류를 찾아내는 간단한 방법이다.[2][4]
다항식 나눗셈
CRC의 나눗셈은 모듈로 2 산술로 하며, 모듈로 2 덧셈과 뺄셈은 XOR다.[2][4]
생성 다항식의 차수가 이면 송신 측은 데이터 뒤에 0을 개 붙인 비트열을 생성 다항식으로 나누고, 나머지 비트를 데이터 뒤에 붙여 보낸다. 이렇게 만든 비트열은 생성 다항식으로 나누어떨어진다.[3][4]
수신 측은 받은 비트열 전체를 생성 다항식으로 나누어, 나머지가 0이 아니면 오류로 판정한다.[2][4] 받은 데이터로 CRC를 다시 계산해 받은 CRC와 비교하고, 다르면 오류로 판정하기도 한다.[5][6]
ENC28J60은 ERXFCON.CRCEN이 설정되어 있으면 CRC가 틀린 패킷을 버린다.[6] ARQ는 오류 검출 부호로 찾은 오류를 되돌림 통로로 알려, 송신 측이 다시 보내게 한다.[7]
AUTOSAR R25-11 CRC 라이브러리 규격은 32비트 다항식 0xF4ACFB13의 해밍 거리를 CRC를 포함해 4096바이트까지 6으로 제시한다.[3]
생성 다항식이 추가로 대수적 성질을 가지면 오류 위치를 찾아 부호어를 고칠 수도 있다.[3]
하드웨어 구현
하드웨어에서는 CRC를 시프트 레지스터와 XOR로 계산한다. 시프트 레지스터의 비트 수는 생성 다항식의 차수와 같고, 데이터를 한 비트씩 밀어 넣으면서 생성 다항식의 계수가 1인 자리에서 XOR를 한다. 데이터를 모두 넣은 뒤 레지스터에 남은 값이 CRC다.[2][4] 아래 그림은 CAN이 쓰는 생성 다항식으로 그린 예다.
쓰는 곳
CRC는 이더넷 같은 LAN(Local Area Network)에서 쓰인다.[2][4] Microchip 앱노트에 따르면 CRC는 데이터 메모리·프로그램 메모리에 든 데이터가 올바른지 확인하는 데도 흔히 쓰이고[8], CAN과 이더넷을 비롯한 널리 쓰이는 통신 프로토콜 대부분이 CRC로 오류를 검출한다.[9]
CRC는 이웃한 비트들에 몰린 오류인 버스트 오류를 찾아내는 데 쓴다.[2][4] 오류 버스트의 길이는 첫 오류 비트부터 마지막 오류 비트까지의 비트 수다.[10] ITU-T X.141에 따르면 X.25 등의 패킷 전송 절차가 쓰는 16비트 FCS(Frame Check Sequence)는 길이가 16비트를 넘지 않는 오류 버스트를 모두 찾아낸다.[11]
Bosch CAN 2.0 규격은 CAN의 CRC 시퀀스를 15비트로 둔다.[5] 자세한 것은 CAN CRC에서 다룬다.
모뎀의 오류 정정 절차를 정한 ITU-T V.42(03/2002)는 LAPM(Link Access Procedure for Modems)의 32비트 FCS 생성 다항식을 차수가 32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0인 항으로 정한다.[12]
IEEE 802.3-2022는 이더넷 MAC(Medium Access Control) 프레임의 FCS 필드에 32비트 CRC 값을 담도록 하고, 그 생성 다항식을 위와 같은 다항식으로 정한다. CRC 값은 목적지 주소, 출발지 주소, 길이/타입 필드, MAC 클라이언트 데이터, 패드, 곧 FCS를 뺀 모든 필드로 계산한다.[13]
생성 다항식이 같아도 보장되는 해밍 거리는 CRC를 뺀 데이터 워드의 길이에 따라 달라서, 데이터 워드가 길수록 작아진다. 데이터 워드를 비트라 하면, 위 다항식이 보장하는 해밍 거리는 이면 8 이상, 이면 7 이상, 이면 6 이상, 이면 5 이상, 이면 4 이상이다.[14]