[Tech, etc.] CRC32 (Cyclic Redundancy Check 32-bit) - 예

3비트 checksum을 생성하는 CRC3이라는 작은 버전을 사용해 CRC가 어떻게 작동하는지 알아보자. 예시에서는 간단한 4비트 입력 메시지와 4비트 다항식을 사용한다. 원리는 CRC32와 동일하지만 규모만 더 작을 뿐이다.

 

1. 다항식 선택
   : 먼저 CRC3 계산을 위해 4비트 다항식을 선택한다 0xB(2진수로는 1011)을 사용한다. 선행 비트는 항상 1로 가정하며 명시적으로 기록하지 않는다.
2. 입력 데이터 준비
   : 입력 데이터가 1101(4비트 메시지)라고 가정하자. CRC3을 수행하려면 이 메시지를 CRC 비트 수(이 경우 3)만큼 환장한다. 메시지 끝에 0을 세 개 추가해 1101 000을 만들면 된다.
3. 나누기
   : 이제 2진수의 긴 나눗셈과 유사한 XOR 연산을 사용해 확장된 메시지를 다항식으로 나눈다. 몫은 버려지고 나머지는 CRC 값이 된다.
   (1) 초기 설정
   - 확장 데이터: 1101 000
   - 다항식: 1011
   (2) 나누기 단계
   - 다항식의 MSB를 확장 데이터의 첫 번째 1과 정렬한다.
   - 확장된 데이터의 처음 네 비트와 다항식 사이에 XOR을 수행한다: 1101 XOR 1011 = 0110
   - 결과의 다음 1과 일치하도록 다항식을 이동하고 XOR 연산을 반복한다. 결과가 0110이므로 시프트할 필요가 없다(MSB는 이미 1에 정렬돼 있다.)
   - XOR 실행: 0110 XOR 1011 = 1101
   - 처리할 비트가 4비트 미만이므로(101) 나눗셈을 완료했다. 나머지는 101
4. CRC 값
   : 나눗셈의 마지막 단계에서 남은 부분은 CRC 값이다. 따라서 입력 데이터 1101의 경우 CRC3 checksum은 101이다.
5. 데이터에 CRC 추가
   : CRC가 포함된 메시지를 작성하려면 원본 데이터에 CRC 값을 추가한다: 1101 101

메시지가 올바른지 확인하기 위해 CRC가 추가된 메시지에 대해 동일한 분할 프로세스를 수행한다. 오류가 없으면 나머지는 000이 된다. 나머지가 000이 아닌 경우 전송 오류가 발생했을을 나타낸다.