순환 중복 검사

CRC, Cyclic Redundancy Check

CRC는 데이터 통신에서 오류를 탐지하는 대표적인 방법으로, 데이터 전송 중 발생한 오류를 효과적으로 검출하기 위해 사용된다. CRC는 주로 네트워크 통신과 디지털 저장 장치에서 데이터 무결성을 검사하는 데 사용된다.

기본 개념

CRC는 생성 다항식(Generator Polynomial)이라는 고정된 값을 사용하여 데이터를 다항식처럼 취급하고, 이를 나눗셈 연산을 통해 오류를 검출한다. 송신 측에서 데이터를 전송할 때, 그 데이터를 생성 다항식으로 나눈 나머지를 함께 전송한다. 수신 측은 동일한 방식으로 계산된 나머지를 확인하여 전송 중 오류가 발생했는지 판단한다.

생성 다항식

Generator Polynomial

생성 다항식은 특정 다항식을 이진수로 표현한 값이다. CRC 계산에서 이 다항식은 송신된 데이터를 나누기 위한 나눗셈의 제수 역할을 한다.

• 다항식의 길이는 사용하는 CRC의 종류에 따라 다르며, 대표적인 생성 다항식에는 CRC-8, CRC-16, CRC-32 등이 있다.

예를 들어, 1011이라는 다항식은 다음과 같이 해석된다.

• 다항식: x³+x+1 → 이진수: 1011
  • 여기서 x³, x, 1에 해당하는 자리에 1이 있고, 나머지 자리는 0으로 채운다.
• n 차 다항식은 xⁿ 부터 x⁰ 까지 n + 1 비트가 된다. CRC-16-CCITT 의 x¹⁶+x¹²+x⁵+1 은 17자리 가운데 16, 12, 5, 0 번째가 1 이므로 1 0001 0000 0010 0001 이다
• 최고차항은 늘 1 이라 이를 빼고 나머지 16비트(0x1021)로 적기도 하고, 비트 순서를 뒤집은 0x8408 로 구현하기도 한다. PPP 의 FCS-16 이 이 다항식을 0x8408 로 계산한다
• 17비트를 16비트에 억지로 맞춘 1000 1000 0001 0001 은 지수가 하나씩 밀린 x¹⁵+x¹¹+x⁴+1 이고, 비트를 뒤집은 0111 0111 1110 1110 류는 다항식 표현이 아니다

CRC 동작 과정

1. 생성 다항식 선택: 송신 및 수신 측에서 동일한 생성 다항식을 미리 정의한다. 예시에서는 생성 다항식으로 1011을 사용한다고 가정한다.
2. 송신 측에서 CRC 코드 생성:
   • 데이터를 이진수로 표현한 후, 생성 다항식을 사용해 나눗셈을 수행한다.
   • 데이터를 전송하기 전에 데이터 뒤에 생성 다항식의 길이에 해당하는 0을 붙여 나머지를 구한다.
   • 나머지가 CRC 코드가 되며, 이 코드를 데이터 뒤에 덧붙여 전송한다.
3. 수신 측에서 오류 검출:
   • 수신된 데이터에 대해 동일한 생성 다항식으로 나눗셈을 수행한다.
   • 그 결과가 0이면 오류 없이 정확하게 전송된 것으로 간주하고, 0이 아니면 오류가 발생한 것으로 판단한다.

CRC 예시

데이터: 1101, 생성 다항식: 1011

1. 데이터 뒤에 3개의 0 추가
   • 데이터 길이가 4비트, 생성 다항식이 4비트(다항식 차수 + 1)이므로, 데이터 뒤에 000을 추가한다.
   • 데이터는 이제 1101000이 된다.
2. 데이터를 생성 다항식으로 나눗셈
   • 데이터를 생성 다항식으로 나눗셈하여 나머지를 구한다. XOR 연산을 사용하여 수행한다.
   • 최종 나머지 값은 100이다.
3. 나머지를 데이터에 추가
   • 계산된 나머지인 100을 원래 데이터인 1101 뒤에 붙여 1101100을 전송한다.

수신 측에서 검증

1. 수신 측에서는 1101100을 받는다.
2. 동일한 생성 다항식 1011으로 나눗셈을 수행하여 나머지를 계산한다.
   • 나머지가 0이면 오류 없이 정확히 전송된 것으로 간주된다.

CRC의 특징

• 오류 검출률: CRC는 단일 비트 오류, 두 비트 오류, 연속적인 비트 오류 등을 감지할 수 있으며, 높은 오류 검출 확률을 가지고 있다.
• 빠른 계산: XOR 연산을 사용하여 연산 속도가 빠르고, 하드웨어 및 소프트웨어에서 효율적으로 구현 가능하다.
• 오류 수정 불가: CRC는 오류 탐지에 특화되어 있으며, 오류를 수정할 수는 없다. 오류가 발견되면 데이터를 재전송하는 방식으로 대응한다.

시프트 레지스터 구현

하드웨어 CRC 는 나눗셈을 시프트 레지스터와 XOR 게이트로 한다. 레지스터 칸 수는 생성 다항식의 차수(최고차항의 지수)와 같고, 비트를 하나씩 밀어 넣다가 맨 끝 칸에서 1 이 밀려 나오면 레지스터에 생성 다항식을 XOR 한다. 그래서 회로를 보면 생성 다항식을 거꾸로 읽어 낼 수 있다.

• 레지스터가 n 칸이면 최고차항은 xⁿ 이다. 맨 끝 칸의 출력이 되먹임선이 된다
• 데이터가 들어오는 입구에서 되먹임과 XOR 하는 게이트는 상수항 1(x⁰)이다
• k 번째 칸 앞(입구에서 k 칸 지난 자리)에 되먹임 XOR 이 있으면 x^k 항의 계수가 1 이고, XOR 이 없는 자리는 계수가 0 이다

예를 들어 레지스터 4칸에 입구의 XOR 과 둘째·셋째 칸 사이의 XOR 이 있으면 계수는 x⁴=1, x³=0, x²=1, x¹=0, x⁰=1 이므로 생성 다항식은 x⁴+x²+1(이진수 10101)이다. 칸 수가 다르면 차수가 맞지 않고, 입구 XOR 이 없으면 상수항이 빠진 다른 다항식이 된다.