순환중복검사(CRC)

1. 순환중복검사(CRC)

---

  CRC(Cyclic Redundancy Check)는 파일 전송, 네트워크 통신 프로토콜, 데이터 저장 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크 값을 결정하는 방식을 말한다. CRC는 다항식 코드를 사용하여 오류를 검출하고, 집단 오류를 검출하는 능력이 탁월하다. 또한, 구현이 단순하여 현재 통신 프로토콜에서 가장 많이 사용하는 오류 검출 기법이다.

 

  CRC 기법의 동작 과정은 그림 1과 같다.

그림 1. CRC 기법 상세 원리

  CRC는 데이터 전송 시 오류를 검출하기 위한 기술로, 전송하고자 하는 데이터에 n 비트 길이의 CRC 검증 코드를 추가하는 방식이다. CRC 값을 계산하기 위해, n+1 비트 길이의 고정된 다항식, Divisor(생성 다항식)를 사용한다. 이 Divisor는 오류 검출의 민감도를 결정하며, CRC 표준에 따라 미리 정해진 값이다.

 

  송신 측에서는 원본 데이터 끝에 n 개의 '0'을 추가하여 확장된 데이터를 만든 뒤, 이 확장된 데이터를 Divisor로 나눈다. 이 나눗셈은 일반적인 수학적 나눗셈과 다르게 이진 나눗셈을 의미하며, XOR 연산을 기반으로 한다. 나눗셈의 결과로 얻어진 나머지가 CRC 값이 된다. 이렇게 계산된 CRC 값은 원본 데이터 뒤에 추가되어 수신 측으로 전송된다.

 

  수신 측에서는 전송받은 데이터 패킷(원본 데이터 + CRC)을 검증한다. 송신 측과 동일한 Divisor를 사용하여, 전체 데이터 패킷을 나눈다. 만약 데이터가 정확하게 전송되었다면, 이 나눗셈의 결과로 나오는 나머지는 '0'이 된다. 즉, (Data + CRC) / Divisor의 계산 결과가 '0'이라면 오류 없이 데이터가 전송된 것이다.

 

  나머지가 '0'인 경우, 수신 측은 데이터 패킷을 정상적으로 수락한다. 반면, 나머지가 '0'이 아닌 경우에는 오류가 발생했다고 판단하여 데이터 패킷을 거부한다. 이 과정을 통해, 송신 측과 수신 측은 데이터 전송 중에 발생할 수 있는 오류를 효과적으로 검출하고, 데이터의 무결성을 확보할 수 있다.

 

2. CRC 계산 예제

---

  CRC 계산 과정은 XOR (Exclusive OR) 연산을 기반으로 수행한다. XOR 연산은 두 비트가 다를 경우 '1'을 반환하고, 두 비트가 같을 경우 '0'을 반환한다.

 

  CRC 발생 코드 P(x)를 그림 2와 같이 설정한다.

그림 2. CRC 발생 코드

  CRC 발생 코드는 다항식 형태나 이진수 형태로 제공될 수 있다. 다항식 형태로 주어졌을 경우, 이를 이진수 형태로 변환해야 한다. 그림 2와 같이 P(x) = x^3 + x^2 + 1 다항식은 이진수 '1101'로 변환된다. 변환된 이진수의 최상위 비트(최고 차수)는 CRC 검증 코드의 길이를 결정한다.

 

  예를 들어, 전송할 데이터가 '110010'이라면, CRC 발생 코드의 최고 차수인 3에 따라 데이터 끝에 '000'을 추가하여 확장된 데이터 '110010000'을 만든다. 이 확장된 데이터에 대해 CRC 발생 코드 '1101'을 사용하여 XOR 기반의 이진 나눗셈을 수행한다. 이 과정을 통해 얻어진 나머지가 최종적인 CRC 값이 되며, 이 값을 원본 데이터의 뒤에 추가하여 전송한다.

 

  그림 3과 같이 나머지 비트 수는 CRC 발생 코드의 최고 차수와 일치하며, 전송할 데이터 '110010'에 CRC 값 '100'을 붙인 '110010100'이 오류 검출을 위해 전송되는 최종 데이터이다.

그림 3. CRC 계산

  다음은 수신 된 코드  '110010100'에 오류가 있는지 확인해 보자!

 

  그림 4와 같이 수신된 코드 '110010100'을 CRC 발생 코드인 '1101'을 사용하여 XOR 기반 이진 나눗셈을 수행한다. 계산 결과 나머지가 '0'이므로 전송 데이터에는 오류가 없음을 확인할 수 있다.

그림 4. 수신 측에서 전송 데이터 오류 검증

 

---

참고 자료 및 출처

순환중복검사 (CRC, Cyclic Redundancy Check) < 도리의 디지털라이프

25. 오류검출코드 (CRC : Cyclic redundancy check)