한양과기고 에듀테크 수업도구 대시보드

CRC 순환 중복 검사 — XOR 나눗셈의 나머지로 오류 잡기

네트워크로 보낸 데이터가 도중에 뒤집혔는지 어떻게 알까? 가장 간단한 방법은 패리티 비트(1의 개수 홀짝)지만, 비트가 2개 뒤집히면 놓친다. CRC는 데이터를 하나의 큰 2진 다항식으로 보고, 약속된 생성 다항식(generator)으로 나눈 나머지를 뒤에 붙여 보낸다. 받는 쪽이 같은 수로 다시 나눠 나머지가 0이 아니면 오류다. 나눗셈은 뺄셈 대신 XOR만 쓴다.

1. CRC 계산 — 나머지 구하기

CRC-3 · 1011 CRC-4 (x⁴+x+1) · 10011 CRC-8 · 100000111 CRC-16 앞부분 예시

메시지 뒤에 0을 (생성다항식 길이 − 1)개 붙이고, 최상위 1이 나올 때마다 생성다항식과 XOR 합니다.

2. 전송 데모 — 비트를 눌러 뒤집어 보기

아래는 데이터 + CRC로 이루어진 실제 전송 프레임(코드워드)입니다. 이 상태로는 나눗셈 나머지가 정확히 0이라 수신기가 "정상"으로 판정합니다. 비트를 클릭해 전송 중 잡음으로 뒤집힌 상황을 만들어 보세요.

데이터 비트 CRC 비트 뒤집힌 비트

3. 핵심 코드 (비트 단위)

# msg, gen 은 0/1 문자열. gen 의 맨 앞은 항상 1 def crc_remainder(msg, gen): n = len(gen) bits = list(msg) + ['0'] * (n - 1) # 0 패딩 for i in range(len(msg)): if bits[i] == '1': # 최상위가 1일 때만 for j in range(n): bits[i+j] = '0' if bits[i+j] == gen[j] else '1' # XOR return ''.join(bits[-(n-1):]) # 마지막 n-1 비트 = CRC # 보낼 때: codeword = msg + crc_remainder(msg, gen) # 받을 때: crc_remainder(codeword, gen) == '000...0' 이면 정상

4. 왜 잘 잡히나 · 어디에 쓰나

버스트 오류에 강함

생성 다항식이 r비트면, 길이 r 이하의 연속된 오류(버스트)는 100% 검출한다. 통신 잡음은 몰려서 생기는 경우가 많아 CRC가 특히 효과적이다.

오류 정정은 못 한다

CRC는 "틀렸다"만 알려주고 어디가 틀렸는지·원본이 뭔지는 모른다. 정정까지 하려면 해밍 코드 같은 별도 방식이 필요하다. 보통은 재전송을 요청한다.

보안용은 아니다

CRC는 우연한 잡음을 잡는 용도다. 공격자가 데이터를 바꾸면서 CRC도 맞춰 다시 계산할 수 있으므로, 위·변조 방지에는 SHA-256·HMAC을 쓴다.

실제 사용처

이더넷 프레임(FCS, CRC-32), Wi-Fi, USB, PNG/ZIP/gzip 파일 무결성, 하드디스크 섹터, QR 코드 등 거의 모든 곳에서 CRC가 쓰인다.