CRC(Cyclic Redundancy Check)

16장 이더넷 프레임에서 FCS(4바이트) 필드가 CRC 값을 담는다고 짧게 언급했는데, 이 글은 그 CRC가 실제로 어떻게 계산되고 왜 오류를 잡아내는지를 수식과 예제로 풀어본다.

CRC의 기본 아이디어

송신 측은 전송할 데이터(M)를 생성 다항식(Generator Polynomial, P)으로 나눈 나머지(R)를 구해 데이터 뒤에 붙여 보낸다. 수신 측은 받은 데이터 전체를 같은 P로 다시 나눠보고, 나머지가 0이 아니면 오류가 있었다고 판단한다. 이 나눗셈은 일반적인 뺄셈이 아니라 Modulo-2 연산(XOR)으로 수행되는데, 덧셈과 뺄셈이 똑같이 XOR로 처리되어 자리올림(carry)을 신경 쓸 필요가 없어 회로/코드로 구현하기 쉽다.

계산 과정

송신 측

  1. 데이터(M) 준비
  2. 데이터 뒤에 P(x)의 차수(n)만큼 0을 붙임: T = M × 2ⁿ
  3. Modulo-2 나눗셈: T ÷ P(x) = Q(몫), R(나머지) — 이 R이 CRC 값(FCS)
  4. 전송 데이터 생성: T* = T + R (XOR로 결합)

수신 측

  1. T*를 같은 P(x)로 나눈다: T* ÷ P(x) = Q', R'
  2. R' = 0이면 오류 없음, R' ≠ 0이면 오류 발생

직접 계산해보기: M=1101011011, P=10011

생성 다항식 P = 10011 (차수 n=4)이라 하면, M 뒤에 0을 4개 붙여 T = 11010110110000(14비트)을 만든다. 이제 T를 P로 Modulo-2(XOR) 나눗셈한다 — 일반 나눗셈처럼 몫의 자리를 맞춰가되, 뺄셈 대신 XOR을 쓴다는 점만 다르다. 계산 규칙은 단순하다: 현재 보고 있는 구간의 맨 앞 비트가 1이면 P와 XOR하고, 0이면 그대로 한 자리를 내려서 다음 구간으로 넘어간다. 이 과정을 T의 마지막 비트까지 반복하면 된다.

T=11010110110000, P=10011로 실제 계산해보면 나머지 R=1110이 나온다. 즉 전송 데이터는 T* = T + R = 11010110111110이 된다(원래 데이터 뒤에 붙였던 0000 자리가 CRC 값 1110으로 바뀐 것). 수신 측은 이 T* 전체를 다시 P로 나눠보고, 나머지가 0이면 통과, 0이 아니면 오류로 판정한다.

이 단순 반복(맨 앞 비트가 1이면 XOR, 아니면 넘어가기) 덕분에 CRC는 소프트웨어보다 오히려 하드웨어(시프트 레지스터 + XOR 게이트)로 구현했을 때 더 빠르다.

왜 오류를 잡아낼 수 있는가

전송 중 1비트가 뒤집히는 오류를 오류 다항식 E(x) = xᵏ로 표현할 수 있다. 송신자가 만든 T는 설계상 P(x)로 나누어떨어지므로(나머지 0), 오류가 섞인 T’ = T* + E(x)를 다시 나누면 다음이 성립한다.

T*' ÷ P(x) = (T* ÷ P(x)) + (E(x) ÷ P(x)) = 0 + (E(x) ÷ P(x))

E(x)는 단일항이라 P(x)로 나누어떨어지지 않는 한(즉 P(x)가 xᵏ의 인수가 아닌 한) 나머지가 0이 아니게 되고, 그래서 단일 비트 오류는 CRC로 100% 검출된다. 2비트·3비트 오류나 연속된 비트가 깨지는 Burst Error의 검출률은 P(x)를 어떻게 설계하느냐에 달려 있는데, 표준 CRC 다항식들은 이런 성질을 수학적으로 분석해 채택된 것들이다.

종류 다항식
CRC-4 x⁴ + x + 1 (0b10011)
CRC-8 x⁸ + x² + x + 1 (0x07)
CRC-16 x¹⁶ + x¹² + x⁵ + 1 (0x1021)
CRC-32 x³² + … + 1 (0x04C11DB7)

만약 P(x)가 1(x⁰)이라면 어떤 데이터를 나눠도 나머지가 항상 0이 되어 오류 검출이 아예 불가능해진다 — 그래서 CRC 설계에서는 반드시 차수 1 이상인 다항식을 쓴다.

핵심 정리

  • CRC는 “나눗셈의 나머지가 0인가”만으로 오류를 판별하는 단순한 아이디어지만, XOR 기반 Modulo-2 연산 덕분에 하드웨어로도 소프트웨어로도 빠르게 구현할 수 있다.
  • 단일 비트 오류는 항상 검출되고, 다중 비트·Burst 오류의 검출률은 생성 다항식의 설계에 좌우된다 — 이더넷의 CRC-32처럼 표준화된 다항식을 쓰는 이유가 여기에 있다.
  • CRC는 “오류를 고치는” 기술이 아니라 “오류가 있었다는 것만 알려주는” 기술이다. 오류가 감지되면 상위 계층(LLC/TCP)이 재전송을 요청하는 방식으로 복구가 이루어진다.