CRC   Cyclic Redundancy Checking   순환중복검사

(2021-08-18)

1. 순환 중복 검사 (CRC, Cyclic Redundancy Check)에러검출 능력이 우수한 `순회부호`의 일종


2. CRC 특징에러 유무 만 검출하고, 에러의 위치나 정정은 할 수 없음

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

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

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


3. CRC 생성 및 검사 방법

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

순회 부호
   1. 순회 부호   2. 부호 다항식   3. 생성 다항식   4. CRC(순환중복검사)   5. CRC 생성 다항식 종류   6. BCH 부호   7. RS 부호   8. PN 코드   9. 최장 수열  
에러 검출
   1. 에러검출   2. CRC (순환중복검사)   3. FCS (프레임검사시퀸스)   4. 패리티검사   5. 패리티검사부호   6. 체크섬   7. UDP,TCP 체크섬   8. HEC (헤더오류제어)   9. BEC (후진에러수정)  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"