04-04. Channel Coding and Error Control

4.4 순환 덧붙임 검사(CRC: Cyclic Redundancy Check)

---

개념

• 데이터 통신 시스템과 기타 여러 직렬 데이터 전송시스템에서 쓰이는 error cehck code
• 송신기는 각각 프레임마다 여분의 n bit 수열을 추가하여 전송
  • 이렇게 추가된 bit 수열을 프레임 검사 수열(FCS, Frame Checksum)이라고 부름
• FCS는 수신기에서 수신한 프레임에 포함된 오류의 검출을 도와주는 여분의 정보를 가지고 있음
• CRC는 모듈로 연산에 사용한 다항식 처리과정을 기초로 수행

Theorem

기본 정의

• 한 블록의 입력 bit를 다항식의 계수 집합으로 간주
  • 예를들어 이진수 10100이 입력되면 다음과 같은 다항식으로 표현 됨
    $$
    0\cdot x^4 + 0\cdot x^3 + 1\cdot x^2 + 0\cdot x + 1\cdot x^0
    $$
  • 가장 지수가 큰 자리가 가장 마지막 자리로 표현 됨
  • 이진수 10100의 가장 오른쪽이 최소 중요도 비트(LSB, Least Significant Bit)
    • 숫자 값의 크기에 가장 영향을 덜 미치는 유효 숫자
  • 이진수 10100의 가장 왼쪽이 최대 중요도 비트(MSB, Most Significant Bit)
    • 숫자 값의 크기에 가장 크게 영향을 미치는 유효 숫자
• 일정 계수를 가진 두 번째 다항식을 생성 다항식으로 부름
• 생성 다항식으로 메시지 다항식을 나누어 몫과 나머지를 생성
• 나머지의 계수들을 비트로 환산한 것이 최종 CRC bit 수열이 됨
• 변수들 정의
  • Q: k bit 비트 길이의 전송 프레임
  • F: Q에 추가될 n - k 비트의 FCS
  • J: Q와 F를 연결하여서 만든 수열
  • P: CRC 생성 다항식

연산 과정

• CRC 알고리즘에 의하면 J는 P로 정확하게 나누어 떨어져야 함
  $$
  J = Q\cdot x^{n-k}+F
  $$
• 이 관계에 의하면 Q(k bit의 길이)는 좌측으로 n - k bit만큼 이동되며, 그 뒤에 F(n - k bit 의 길이)가 추가됨
• Qx^n-k를 P로 나누면 아래와 같은 관계를 얻을 수 있음
  $$
  \frac{Q\cdot x^{n-k}}{P}=Q+\frac{R}{P}
  $$
  아래 식에서의 R은 위에서 얻은 나머지로 표현
  $$
  J = Q\cdot x^{n-k}+R
  $$
• 이 J 값은 J/P 연산을 할 경우 나머지가 0이 됨
  • 참고) XRO 연산에서는 A + A = 0

자주 사용되는 CRC 형식

CRC 종류	다항식
CRC-12	x^12 + x^11 + x^3 + x^2 + x + 1
CRC-16	x^16 + x^15 + x^2 + 1
CRC-CCITT	x^16 + x^12 + x^5 + 1
CRC-32	x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1