1. CRC 생성 다항식 이란?
ㅇ CRC : 순환 중복 검사용
ㅇ 생성 다항식 : 입력 데이터 비트열로부터 유효 부호어를 생성시킬 수 있는 다항식 형태
- 例) BCH 생성 다항식, CRC 생성 다항식
ㅇ CRC 생성 다항식 : 메시지 비트열을 나누어 CRC 나머지(검사용 비트열)를 생성하는 기준 다항식
- 송신측에서는, 메세지 비트열,생성 다항식으로부터, CRC를 생성하고, 덧붙여 전송함
- 수신측에서는, 수신 비트열을, 동일한 생성 다항식으로 나누어, 오류 여부를 검사
2. CRC 생성 다항식의 표현 구조
ㅇ 표현 방식
- 입력에 의해 출력이 결정되는 `조합 논리`의 표현을,
- `부울 대수`가 아닌 `추상 대수`의 대수적 표현(다항식 환)에 의함
. 이에의해, 나눗셈,나머지 연산 같은 대수적 성질을,
. 그대로 오류 검출 능력 분석에 활용 가능하게 됨
ㅇ 표현 항목
- 계수 : {0,1}
. 유한체 GF(2) 위에서 정의되며, 계수는 {0,1}뿐임
- 차수 (degree) : 생성 다항식의 차수 r은, 그대로 부가되는 CRC 비트 수 (r = n − k)
. 즉, r차 생성다항식은, r 비트 CRC를 만듬
- 전송 비트 길이 : 차수(r) + 1 = (n - k) + 1 bits
- 연산 : XOR 연산
. 다항식 덧셈,뺄셈은 모두 XOR과 동일 (GF(2)에서는 −1 = +1)
3. CRC 생성 다항식의 CRC 부호어 조건
※ (메시지 다항식 : M(X), 생성 다항식 : g(X), 생성된 CRC : R(X), 생성 다항식의 차수 : r)
ㅇ 송신측에서는, {#R(X)=\bigl(M(X)X^r\bigr)\bmod g(X)#}를 계산하여 CRC를 생성
ㅇ 전송되는 부호어(Codeword)는, {#T(X)=M(X)X^r+R(X)#}이며,
- 이는, {#T(X)\bmod g(X)=0#}을 항상 만족하도록 구성됨
ㅇ 수신측에서는, 동일한 생성 다항식으로, {#T(X)\bmod g(X)#}를 계산하여,
- 나머지가 0 이면, 정상 (오류가 검출되지 않음)
- 나머지가 0 이 아니면, 오류 발생 으로 판단함
4. CRC 생성 다항식 종류 : 각 차수별 대표적인 CRC 생성다항식 g(X) 例)
※ CRC 생성 다항식 형태는, 오류 검출 성능을 결정함
- 같은 차수의 동일한 비트 수의 CRC 이라도,
. 어떤 것은 짧은 버스트 오류 검출에 강하고,
. 어떤 것은 긴 프레임에서 우수하는 등
- 특정 산업 표준 마다 적절하게 채택됨
ㅇ CRC-8 (비트 길이 : 8 + 1 = n - k + 1 bits)
- 생성 다항식 : g(X) = X8 + X2 + X1 + 1 (8 차수)
- 이진 표현 : 1000 0011 1 (9 비트)
- 사용 例) : ATM HEC, SMBus 등
ㅇ CRC-10 (비트 길이 : 10 + 1 = n - k + 1 bits)
- 생성 다항식 : g(X) = X10 + X9 + X5 + X4 + X1 + 1 (10 차수)
- 이진 표현 : 1100 0011 001 (11 비트)
- 사용 例) : ATM HEC 등
ㅇ CRC-12 (비트 길이 : 12 + 1 = n - k + 1 bits)
- 생성 다항식 : g(X) = X12 + X11 + X3 + X2 + X + 1 (12 차수)
- 이진 표현 : 1100 0000 1111 (13 비트)
- 사용 例) : 전송 시스템, 케이블 모뎀 DOCSIS 등
ㅇ CRC-16 (비트 길이 : 16 + 1 = n - k + 1 bits)
- 생성 다항식 : g(X) = X16 + X15 + X2 + 1 (16 차수)
- 이진 표현 : 1100 0000 0000 0101 (17 비트)
- 사용 例) : IBM SDLC, ANSI X3.28
ㅇ CRC-16-CCITT (비트 길이 : 16 + 1 = n - k + 1 bits)
- 생성 다항식 : g(X) = X16 + X12 + X5 + 1 (16 차수)
- 이진 표현 : 1000 1000 0000 1001 (17 비트)
- 사용 例) : X.25, HDLC, Bluetooth, PPP
ㅇ CRC-32 (비트 길이 : 32 + 1 = n - k + 1 bits) : IEEE 802.3-2008
- 생성 다항식 : g(X) = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5
+ X4 + X2 + X + 1 (32 차수)
- 이진 표현 : 1000 0100 1100 0001 0001 1101 1011 0111 (33 비트)
- 사용 例) : Ethernet (IEEE 802.3), ZIP, PNG, SCTP, MPEG-2