CRC(Cyclic Redundancy Check) : CRC-16, CRC-32에 대한 설명과 구현

 

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

간단한 에러 검출방법으로는

    - Parity 비트에 의한 방법

   - Check-Sum에 의한 에러 검출 방법 

   - CRC에 의한 방법

이 있다.  

 

Parity 비트에 의한 방법은 데이타 중에 한꺼번에 2비트나 4비트가 변하게 되면 검출할 수 없고, Check-Sum에 의한 방법은 한 바이트에서 +1, 다른 바이트에서 -1로 에러가 생기는 경우만 해도 에러가 검출되지 않는다. 즉, 이들 방법으로는 에러를 검출해 낼 수 있는데에 한계가 있다. 이에 반하여, CRC에 의한 방법은 높은 신뢰도를 확보하며 에러 검출을 위한 오버헤드가 적고, 랜덤 에러나 버스트 에러를 포함한 에러 검출에 매우 좋은 성능을 갖는 것을 특징으로 한다.

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

 

 

기본 원리

n 비트의 주어진 정보가 있을때, 이를 k 비트 만큼 자리를 올리고 미리 약속한 k 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다.

송신측에서는 원래의 정보 비트를 k 비트 자리 올린 것에 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다. 수신측에서는 수신된 n+r 비트의 데이타를 서로간에 정해진 키 값을 사용하여 수신받은 data를 나누어 보고 나머지가 정확히 0 이 되는지를 검사하면 된다.

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

 

여기서 CRC 계산에 사용되는 modulo-2 연산(첨부 파일 참조)의 세계를 살펴보자.
    CRC 계산시의 사칙연산은 carry를 고려하지 않는다.
    1 + 1 = 0 (carry는 생각하지 않음)
    0 - 1 = 1
덧셈 연산은 뺄셈 연산과 결과가 같으며 XOR 연산과도 같다.

 

다항식 표현 방법을 통해 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)로 나누면

 

        P(x) * x^k  = 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

 

8051 어셈블리 CRC-8 소스 : 8051crc8.zip
8051 어셈블리 CRC-16 소스 : 8051crc16.zip

 

 

CRC_Modulo-2_Arithmetic.pdf

CRC 연산 방법.pdf

 

동영상 강좌 : http://blog.daum.net/ljj-one/41

 

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

CRC 연산 방법.pdf

0.34MB

CRC_Modulo-2_Arithmetic.pdf

0.04MB