1. CRC의 핵심 원리
CRC는 송신측과 수신측이 동일한 생성 다항식($G(x)$)을 공유한다는 점을 이용합니다.
- 송신측 : 데이터 비트열을 생성 다항식으로 나누어 나머지를 구합니다. 이 나머지를 FCS(Frame Check Sequence)라고 하며, 원래 데이터 뒤에 붙여서 보냅니다.
- 수신측 : 받은 전체 비트열을 동일한 생성 다항식으로 나눕니다.
- 나머지가 0이면 : 오류 없음 (통과)
- 나머지가 0이 아니면 : 전송 중 오류 발생 (폐기)
2. 오류 검출 vs 오류 정정 비교
CRC를 제대로 이해하려면 오류 검출(Detection)과 오류 정정(Correction)의 메커니즘 차이를 아는 것이 중요합니다.
| 구분 | 오류 검출 (Error Detection) | 오류 정정 (Error Correction) |
| 핵심 목적 | 데이터에 에러가 있는지 여부 확인 | 에러의 위치를 찾아 올바른 값으로 수정 |
| 대표 방식 | CRC, Parity Check, Checksum | Hamming Code, Reed-Solomon |
| 오버헤드 | 상대적으로 적음 (검사 비트 소량 필요) | 매우 큼 (위치 파악을 위해 많은 비트 필요) |
| 후속 조치 | ARQ(재전송 요청)를 통해 해결 | 수신측에서 자체 수정 (FEC, 전진 오류 정정) |
| 효율성 | 에러 발생률이 낮을 때 유리 | 에러 발생률이 높거나 재전송이 힘들 때 유리 |
3. 다른 검출 방식과의 차이점 (CRC vs Checksum vs Parity)
- Parity Check : 가장 단순한 방식. 1비트 에러만 검출 가능하며, 짝수 개의 비트 에러가 동시에 나면 감지하지 못합니다.
- Checksum : 주로 전송 계층(TCP/UDP)이나 네트워크 계층(IP)에서 사용합니다. 데이터를 일정 단위로 나누어 합산한 값을 이용하며, CRC보다 연산 부담은 적지만 검출 능력은 상대적으로 낮습니다.
- CRC : 데이터 링크 계층(L2)에서 주로 사용합니다. 비트 단위의 버스트 에러(Burst Error, 연속된 에러) 검출 능력이 매우 뛰어나 신뢰성이 높습니다.
4. 왜 CRC는 오류 정정을 하지 않을까?
CRC는 "어딘가 잘못되었다"는 것은 확실히 알지만, "몇 번째 비트가 틀렸다"는 위치 정보까지는 제공하지 않습니다. 이론적으로는 가능할 수 있으나, 정정을 위한 계산 복잡도와 추가 비트 소모를 고려할 때, "틀리면 그냥 다시 보내달라고 하자(ARQ)"는 방식이 네트워크 효율성 면에서 더 이득이기 때문입니다.
5. CRC 계산 시 주의할 점
시험에서 CRC 계산 문제를 풀 때는 다음 세 가지만 기억하세요.
- XOR 연산 : CRC 나눗셈은 일반 산술 나눗셈이 아니라 Modulo-2 연산(XOR)을 사용합니다.
즉, 뺄셈 대신 자릿수가 같으면 0, 다르면 1을 씁니다. (내림수가 없음) - 0의 추가 : 데이터 뒤에 붙이는 0의 개수는 생성 다항식의 최고 차수와 같습니다. (예: $x^3 + 1$이면 0을 3개 추가)
- 나머지(FCS)의 길이 : 최종 FCS 비트 수는 생성 다항식의 최고 차수와 일치해야 합니다. (비트열이 부족하면 앞을 0으로 채움)
6. 비트열과 CRC다항식을 상호변환하는 법(시험빈출)
비트열 → CRC 다항식 변환
비트열의 각 자릿수를 오른쪽에서 왼쪽 방향으로 $x^0$부터 시작하여 지수를 부여합니다. 비트가 1인 위치의 항만 남기면 됩니다.
예시 : 비트열 101101
- 자릿수 매칭 : 1(5번 자릿수) 0(4번) 1(3번) 1(2번) 0(1번) 1(0번)
- 지수 할당 : $1 \cdot x^5 + 0 \cdot x^4 + 1 \cdot x^3 + 1 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0$
- 다항식 정리 : $x^5 + x^3 + x^2 + 1$ (0이 곱해진 항은 생략, $x^0 = 1$)
CRC 다항식 → 비트열 변환
다항식에서 가장 높은 차수를 확인하여 전체 비트 길이를 결정한 후, 해당 차수가 존재하면 1, 존재하지 않으면 0을 채웁니다.
예시 : 다항식 $x^4 + x + 1$
- 최고 차수 확인 : 최고 차수가 4이므로, 비트는 $x^4$부터 $x^0$까지 총 5비트가 됩니다.
- 모든 항 나열 : $(1) \cdot x^4 + (0) \cdot x^3 + (0) \cdot x^2 + (1) \cdot x^1 + (1) \cdot x^0$
- 계수만 추출 (비트열 생성) : 1 0 0 1 1
그런데......
이제는 비트열과 다항식을 상호변환하는 것을 넘어 갑자기 하드웨어 회로도를 보여주면서 다항식을 찾으라 합니다.
갑자기 하드웨어 구조도가 나오다니.. 하지만 이 문제는 앞서 공부한 '다항식 변환' 원리만 알면 5초 만에 풀 수 있는 보너스 문제입니다. 복잡해 보이는 회로도를 "다항식의 지도"라고 생각하고 아래 순서대로 따라와 보세요.
7. 회로되에서 다항식 찾기
이 그림에서 딱 두 가지만 기억하세요.
- 사각형($\square$) : 지수(자릿수)를 의미합니다. 오른쪽에서 왼쪽으로 가면서 $x^1, x^2, x^3, x^4...$가 됩니다.
- 더하기 기호($\oplus$) : 이게 바로 XOR 연산자이자, 다항식에서 항이 존재한다(+)는 뜻입니다.
그림을 오른쪽에서 왼쪽 방향으로 훑으면서 XOR($\oplus$) 기호가 어디에 붙어 있는지 확인하면 됩니다.
- 가장 오른쪽 XOR (데이터 입력부) : 이건 무조건 상수항 $1$을 의미합니다. (모든 생성 다항식의 시작점입니다.)
- 사각형 개수 확인 : 사각형이 총 4개죠? 그러면 이 다항식의 최고 차수는 $x^4$입니다. 맨 왼쪽 사각형을 빠져나오는 선이 다시 돌아가므로 $x^4$ 항은 무조건 존재합니다.
- 중간의 XOR 위치 찾기 : 오른쪽에서 두 번째 사각형과 세 번째 사각형 사이에 $\oplus$ 기호가 보이죠? 오른쪽부터 자릿수를 세어보면 $x^1$ 다음인 $x^2$ 자리에 XOR이 있는 것입니다.
- 맨 오른쪽 입력부 (상수항) : $1$
- 중간 XOR 위치 : $x^2$
- 맨 왼쪽 출력 (최고 차수) : $x^4$
- 이걸 다 더하면? $x^4 + x^2 + 1$ 이 됩니다.
따라서 정답은 ①번입니다.
최대항의 지수가 16이므로 총 17자리 이진수여야 한다. 왜냐? 0부터 16까지의 이진수니까.
정답은 ③
이 문제는 CRC(Cyclic Redundancy Check)의 기본 원리와 코드워드(Codeword)의 구성을 이해하면 아주 간단하게 풀 수 있는 문제입니다. 계산 과정을 길게 거칠 필요 없이 정의만 알면 바로 답이 보입니다.
코드워드란?
CRC에서 송신측이 보내는 코드워드는 원래의 데이터에 계산된 나머지 값(FCS, Frame Check Sequence)을 덧붙인 형태입니다.
코드워드(Codeword) = 데이터워드(Dataword) + 나머지(Remainder)
문제에서 주어진 값들은 다음과 같습니다.
- 데이터워드 : 111111
- 제수(Divisor) : 1010
- 몫(Quotient) : 110011
- 나머지(Remainder) : 110
CRC 알고리즘에 따라 코드워드를 구성하면 원래의 데이터워드인 111111을 앞에 둡니다. 그 뒤에 계산된 나머지 값인 110을 그대로 붙입니다. (참고: 나머지의 비트 수는 보통 (제수의 비트 수 - 1)입니다. 여기서는 제수가 4비트이므로 나머지는 3비트인 110이 됩니다.)
따라서 코드워드는 111111 + 110 = 111111110 이 됩니다. 정답은 ③ 111111110