OriginalSource: http://hayanmail.com/jsy/index.html?board=cizblog_zboard3&ln_mode=news_view&upcount=active&id=6&ct_sel=2

CRC-16/32

CRC(Cyclic Redundancy Check)는 시리얼 전송에서 데이타의 신뢰성을 검증하기 위한 에러 검출 방법의 일종이다.

간단한 에러 검출방법으로는 parity 비트에 의한 방법과 check-sum에 의한 에러 검출 방법이 있지만 parity 비트에 의한 방법은 데이타 중에 한꺼번에 2비트나 4비트가 변하게 되면 검출을 할 수 없고, check-sum에 의한 방법은 한 바이트에서 +1, 다른 바이트에서는 -1로 에러가 생기는 경우만 해도 에러는 검출 되지 않는다. 즉, 이들 방법으로는 에러를 검출해 낼 수 있는 확률이 대단히 낮다.

CRC에 의한 방법은 높은 신뢰도를 확보하며 에러 검출을 위한 오버헤드가 적고, 랜덤 에러나 버스트 에러를 포함한 에러 검출에 매우 좋은 성능을 갖는 것을 특징으로 한다.

이러한 CRC 방법으로 보통 2가지 종류가 사용 되는데, 원칩 마이크로 프로세서와 같이 간단한 용도에서는 CRC-16 이 사용되고, 이보다 더욱 정확한 에러 검출이 필요한 경우에는 CRC-32를 사용한다.

ZIP,ARJ,RAR 과 같은 압축 프로그램이나 플로피 디스크 등의 데이터 검증 용도에 널리 사용되고 있다.

* CRC 검증의 에러 확률 p = 2^-k (여기서 k는 CRC 비트수)
예를들어 CRC16의 경우 에러 확율은 p = 2^-16 = 1 / 65536 = 0.0000152587890625 = 0.0015%
반대로 데이터의 신뢰성은 1 - p = 0.9999847412109375 = 99.9984 %

기본 원리

n 비트의 주어진 정보가 있을때, 이를 k 비트 만큼 자리를 올리고 (K bit right shift) 미리 약속한 k 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다. 송신측에서는 원래의 정보 비트를 k 비트 rigth shift 와 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다.
수신측에서는 수신된 n+r 비트의 데이타를 키 값으로 나누어 보고 나머지가 정확히 0 이 되는지를 검사하면 된다.

이 때 k 가 16 비트이면 CRC-16, 32비트이면 CRC-32 가 되고 키 값으로는 수학자 들에 의해 정해진 값을 주로 사용한다.
CRC-16 에는 0x8005, CRC-32 에는 0x04c11db7 이 많이 사용된다. 그리고 r 비트의 나머지를 Frame Check Sequence(FCS)라고 부른다.

다항식 표현 방법을 통해 CRC 계산 방법을 살펴보자.

(1) 2진 다항식으로 표시

예) 비트열 101 --> 다항식 x² + 1

정보 다항식: 데이터 비트열의 다항식으로 P(x) = p_n x^n-1 + ... + p₃x² + p₂x¹ + p₁
CRC 다항식: CRC 생성을 위한 다항식으로 G(x) (미리 정해진 키 값)
몫: Q(x)
나머지: R(x)
전송 데이타: T(x)

(2) CRC 계산 방법

P(x)를 k 비트 만큼 자리를 올리고( P(x)에 x^k를 곱하는 것과 동일) G(x)로 나누면

x^k P(x) = Q(x)*G(x) +/- R(x) 이다.

(k는 CRC 다항식의 최고 차수)

R(x) = d_k x^k-1 + .. + d₂x¹ + d₁ ( R(x)의 최고 차수는 k-1)

비트열 d_k ... d₂ d₁ 을 FCS(Frame Check Sequence) 라 함

위 식에서 x^k P(x) + R(x) 는 Q(x)*G(x) 와 같다.

즉, x^k P(x) + R(x) 는 G(x)의 배수이므로 G(x) 로 나누면 나머지가 0 임을 알 수 있다.

결과적으로 전송되는 데이터 비트열 : p_n ... p₃ p₂ p₁ d_k ... d₂ d₁

즉, 전송 T(x) = x^k P(x) + R(x)

예) 데이터 비트열 110011 즉 P(x) =x⁵+x⁴+x¹+x⁰, CRC 다항식G(x) = x⁴+x³+1, 즉 11001일 경우 FCS와 전송되는 비트열은?

x^kP(x) = x⁴ (x⁵ + x⁴ + x¹ + 1) = x⁹ + x⁸ + x⁵ + x⁴, 비트열로 표시하면 1100110000

                   100001
          ____________
11001 | 1100110000
            11001
          ____________
                     10000
                     11001
          ____________
                       1001    

x^kP(x) = Q(x)G(x) - R(x)에서

Q(x) = x⁵ + x⁰ 이므로,

R(x) = x³ + x⁰, ---> FCS는1001

따라서 전송되는 비트열 1100111001

연산의 최적화

CRC의 계산은 일반 나눗셈 명령을 이용해 구현할 수 없다. 1비씩 shift 하면서 XOR 연산을 통해 나머지를 구해야 한다.
하지만 정보 비트에 대해 하나하나씩 연산을 하는 것에는 분명 속도 개선의 여지가 있다.
실제 계산 시에는 모든 바이트에 대해 CRC 다항식에 대한 CRC값을 계산해 표로 만들어 두고 들어오는 데이타를 인덱스로 삼아 계산값을 바로 얻는 방법을 사용 한다.

CRC-16 C소스 : crc16h.c
CRC-32 C소스 : crc32h.c