CRC란?

CRC란?

CRC(Cyclic Redundancy Checking) 순환 중복검사는 에러검출 능력이 우수한 ‘순회부호’의 일종이다. 순회부호란 선형 블록 부호(부호어 집합이 선형 벡터공간을 형성하는 부호)의 일종으로서 주요특징으론 잘 정의된 수학적 구조를 가지고 있고 부호화에 용이하며 매우 효율적인 복호화 기능을 가지고 있다.

 

CRC의 특징

1.     산발 에러(Random Error) 뿐만 아니라, 연집 에러(Burst Error)에서도 검출 능력이 우수하다. 연집에러는 데이터 전송 시 한 무리의 데이터에 집단적으로 오류가 발생하는 것이고, 이와 반대로 여기저기 산발적으로 댄덤하게 나타나는 오류를 산발 에러 라고 부른다.

 

2.     순회부호에 기반한 오류검출부호이다. 송신 측에서 데이터에 대해 특정 다항식으로 나눈 결과를 여분의 FCS에 덧붙여 보내면, 수신측에서 동일한 방법으로 계산한 결과와의 일치성으로 오류검사를 하는 기술이다.

여기서 FCS란(Frame Check Sequence) 프레임 끝 부분에 수신측의 에러검출을 돕기위해 삽입하는 필드이다. 수식측은 자신이 갖고있는 FCS와 전송되어온 프레임의 FCS와 비교하여 에러 여부를 확인 가능하고 에러 확인시에는 해당 프레임을 폐기하고 송신측에 재전송을 요구한다.

 

 

CRC 생성 및 검사 방법

1.    송신단

전송할 원래 데이터 프레임(k bit)에 대해 미리 정의된 CRC다항식으로 나누고 그 나머지 값을 원래의 데이터 프레임 뒤에 FCS(n-k bits)로 붙인다. 이떄, 그 결과 프레임(원래의 데이터 + FCS)이 미리 정의된 CRC 다항식에 의하여 정확히 나누어 떨어질 수 있게 된다.

그 결과 프레임(원래의 데이터 + FCS)(n bits)을 송신한다.

 

2.    수신단

수신된 프레임 (n bits)을 받은 후에 CRC 검사를 하게 되는데, 수신된 전체 데이터를 송신 시와 같은 미리 정의된 CRC 다항식으로 나누어서 나머지를 검사한다.

오류 검출 방법은 수신단에서 잉여분(FCS)을 포함한 전체 데이터를 미리 정의된 CRC 다항식으로 나눌 때 나머지가 0이면 오류가 없는 것이고 나머지가 0이 아닌 수가 되면, 전송 시 오류가 발생한 것이다.

 

다항식의 표현

예로 x4+x+1 이란 다항식을 다음과 같이 세가지 방법의 숫자로 표현할 수 있다.

-        0x3 = 0b0011 : x4+ 0x3+0x2+1x1+1x0 (MSB – 우선코드)

-        0xC = 0b1100 : 1x0+1x1+0x2+0x3+x4 (LSB – 우선코드)

-        0x9 = 0b1001 : 1x4+0x3+0x2+1x1+x0 (Koopman 표시)

-       

다항식(representations)
정상 (normal)	역방향 (reversed)	역방향의 역수 (reversed reciprocla)
0x3	0xC	0x9

 

CRC 계산 방법

- 대상 항목들

원래 데이터 : D(x) (k bits)

잉여 데이터 : F(x) (n-k bits)

전송 데이터 : T(x) (n bits)

미리 정의된 CRC 다항식 (Divisor) : P(x) (n-k+1 bits)

(n–k+1 bits)의 비트 패턴 (생성 다항식)

나눗셈 몫 (Quotient) : Q(x) (k bits)     (버려짐)

나머지 (Reminder) : R(x) (n-k bits)   (덧붙여짐)

 

- 다항식 표현

(원 데이터의 prescale)   D'(x) = xn-kD(x)

원래 데이터에 생성 다항식의 가장 큰 차수를 곱한다.

(즉, 그만큼 0 값을 덧붙이는 것)

 

(이것을 생성다항식으로 나눔) D'(x)/P(x) = xn-kD(x)/P(x)

xn-kD(x)/P(x) = Q(x) + R(x)/P(x)

xn-kD(x) = Q(x)P(x) + R(x)

 

(위에서 xn-kD(x)을 전송)   T(x) = xn-kD(x) + R(x)

T(x) = xn-kD(x) + R(x) = Q(x)P(x)

즉, 전송 비트 패턴 T(x)가 생성다항식 P(x)에 의해 정확히 나누어 떨어진다.

 

-CRC 계산 및 비트 처리 방법

나눗셈 연산은, 캐리(overflow 및 borrow)를 무시하고, XOR (mod-2) 수행한다.

나누는 수인 제수(Divisor)는 미리 정의된 이진 소수(Divisor)에 의해 나눈다.

        이때의 제수의 길이는 `(덧붙이는 비트수 n-k) + 1

나머지(Reminder)는 나눗셈의 나머지(Reminder)를 프레임에 덧붙여 송신한다.

이때의 나머지 길이는 `n-k`이다.

 

계산예시