CRC   Cyclic Redundancy Checking   순환중복검사

1. 순환 중복 검사 (CRC, Cyclic Redundancy Check)

  ㅇ 에러검출 능력이 우수한 `순회부호`의 일종


2. CRC 특징

  ㅇ 에러 유무 만 검출하고, 에러의 위치나 정정은 할 수 없음

  ㅇ 산발 에러(Random Error) 뿐만 아니라, 연집 에러(Burst Error)에서도 검출 능력 우수 함
     - 통상 데이터링크 계층에서 많이 사용되는, 비트 지향적인 에러검출 기술
     - 이 기술은 강력하면서도 하드웨어로 구현하기 쉬움

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

  ㅇ (용도)
     - 비트 에러가 존재할 수 있는 패킷에 대한 신뢰성 제고를 위해,
     - 재전송 기반 에러제어를 하는 프로토콜에 주로 쓰임 


3. CRC 생성 및 검사 방법

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

  ㅇ 수신단
     - 수신된 프레임 (n bits)을 받은 후에 CRC 검사를 하게 되는데, 
        . 수신된 전체 데이터를 송신시 처럼 `미리 정의된 CRC 다항식`으로 나누고, 나머지를 검사함
     - 오류검출 방법
        . 수신단에서 잉여분(FCS)을 포함한 전체 데이터를 `미리 정의된 CRC 다항식`으로 나눌 때,
           .. 나머지가 0 이면, 무 오류
           .. 나머지가 0 이 아닌 수가 되면, 전송시에 오류가 발생한 것임


4. 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)의 비트 패턴 (생성 다항식)  ☞ CRC 생성 다항식 종류 참조
        . P는 T를 나눌 수 있어야 함 (약수 즉, T/P의 나머지는 없음)

  ㅇ 기타 항목들 (계산 중간에 임시적 사용)
     - 나눗셈 몫 (Quotient)             :  Q(x) (k bits)     (버려짐)
     - 나머지 (Reminder)                :  R(x) (n-k bits)   (덧붙여짐)


5. CRC 계산을 위한  다항식 표현

  ㅇ (원 데이터의 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)에 의해 정확히 나누어 떨어짐


6. CRC 계산 방법

  ㅇ CRC 계산 및 비트 처리 방법
     - 나눗셈 연산은, 
        . 캐리(overflow 및 borrow)를 무시하고, XOR (mod-2) 수행
     - 나누는 수(제수,Divisor)는,
        . 미리 정의된 이진 소수(Divisor)에 의해 나눔
        . 이때의 제수 길이는 `(덧붙이는 비트수 n-k) + 1`
     - 나머지(Reminder)는,
        . 나눗셈의 나머지(Reminder)를 프레임에 덧붙여 송신함
        . 이때의 나머지 길이는 `n-k`


7. CRC 계산 例)

    


8. CRC 생성 다항식 例

  ※ 여러가지 CRC 생성다항식 g(X) 例)  ☞ CRC 생성 다항식 종류 참조
     - CRC-8, CRC-10, CRC-12, CRC-16, CRC-32 등