임베디드 스터디 - CRC 코드

이번 글 참고자료:
한빛아카데미, 디지털 논리회로4판
ElectronicsTutorials

GitHub - hneemann/Digital: A digital logic designer and circuit simulator.

A digital logic designer and circuit simulator. Contribute to hneemann/Digital development by creating an account on GitHub.

github.com

CRC (Cyclic Redundancy Check)

• CRC 코드는 에러 검출 코드로, 데이터에 특정 이진수를 Modulo-2 나눗셈, 다시 말해 다항식 나눗셈으로 나눈 나머지를 에러 검출 코드로 사용하는 방법이다.
  • Modulo-2 나눗셈 (XOR)은 다른 Modulo-2 연산에 비해 데이터 전송 간 연속적으로 발생하는 오류(Burst Error)에 효과적이다.
• CRC 코드의 크기에 따라 CRC-4, CRC-8, CRC-16 등 8비트 단위로 코드를 사용할 수 있으며, 코드의 크기에 따라 에러를 검출할 수 있는 데이터의 크기가 다르다.

Polynomial

• 다항식은 CRC 코드의 연산 기준이 되는 수식이다. Polynomial를 정하는데 자주 사용하는 수식은 있으나 정해져있는 규칙은 없다. 사용자의 선호에 따라 수식을 설정해서 사용하면 된다.

• EX) CRC-8/Wire의 Polynomial 다항식 $X^8 + X^2 + x + 1 = 100000111$ 이 때, 일반적인 다항식 나눗셈과 같이 나머지가 최고차항의 밑 차항까지의 값이 나오므로 다항식 $X^8$은 생략하여 Polynomial을 $0X07$ 으로도 표기한다.

CRC-8 연산 예제

• 데이터: 10110011 (8bit)
• 생성 다항식 (CRC-8): $G(x) = x^{8}+x^{2}+x+1$ → 100000111

1. 데이터 뒤에 8bit 0 추가

    10110011 00000000  (16bit)
   

2. XOR 나눗셈

    1011001100000000   ← 데이터 + 8bit 0
    100000111          ← 생성 다항식 (MSB=1인 위치에 정렬)
    ─────────
    0011000010000000   ← XOR 결과, 앞 0 제거 후 다음 1 탐색
   
   
    11000010000000     ← MSB=1 위치 탐색
    100000111
    ─────────
    01000001100000     ← XOR 결과
   
    1000001100000       ← MSB=1 위치 탐색
    100000111
    ─────────
    0000000010000      ← XOR 결과
   
            10000   ← 나머지 비트 < 생성 다항식 비트 수(9bit) → 종료
   

3. 나머지 = CRC-8

    CRC-8 = 00010000  (0x10)
   

   LFSR (Linear Feedback Shift Register)

• 시프트 레지스터에서 특정 FF의 비트를 XOR로 연결하여 출력된 값을 다시 레지스터의 입력 신호로 사용하는 회로.
  • 연결된 FF의 비트에 따라 나온 출력을 특성 방정식으로 표현할 수 있다.
• 일반적으로 난수 생성기에 자주 사용되며, 특정 방정식의 Modulo-2 나눗셈 연산의 기능으로도 사용 가능하기에 CRC 연산에도 활용된다.

CRC 활용

• CRC-4 Polynomial 연산을 바탕으로 LFSR 회로를 이용한 CRC 연산을 확인해보자.

• 데이터: 1011 (4bit)
• 생성 다항식 (CRC-4): $G(x) = x^{4}+x+1$ → 10011

  1 0 1 1 0 0 0 0   ← 피제수 (1011 + 0000)
  ⊕ 1 0 0 1 1         ← 제수 G(x), MSB 정렬
  ─────────────────
  0 0 1 0 1 0 0 0   ← MSB=0이므로 두 칸 앞으로
  
      1 0 1 0 0 0
  ⊕   1 0 0 1 1     ← 제수 정렬
    ─────────────
      0 0 1 1 1 0
  

  나머지 = 1110 → CRC = 1110

LFSR의 입력에 1011 0000을 입력하여 CRC 값이 도출되는 것을 확인할 수 있다.

| CLK | 입력 | r3 | r2 | r1 | r0 |
|:---:|:----:|:--:|:--:|:--:|:--:|
| 초기 | — | 0 | 0 | 0 | 0 |
| 0 | 1 (d1) | 0 | 0 | 0 | 1 |
| 1 | 0 (d2) | 0 | 0 | 1 | 0 |
| 2 | 1 (d3) | 0 | 1 | 0 | 1 |
| 3 | 1 (d4) | 1 | 0 | 1 | 1 |
| 4 | 0 (패딩1) | 0 | 1 | 0 | 1 |
| 5 | 0 (패딩2) | 1 | 0 | 1 | 0 |
| 6 | 0 (패딩3) | 0 | 1 | 1 | 1 |
| 7 | 0 (패딩4) | 1 | 1 | 1 | 0 |

Look-up table

• CRC 연산은 결국 다항식 나눗셈의 나머지로 연산되는 값이므로, 입력하는 데이터에 따라 규칙적인 패턴을 보인다. 이를 Precomputable이라고 한다. LFSR 회로와 같이 1비트 씩 입력을 하게되면 연산이 느리기에, 입력 데이터의 전처리 후, 룩업테이블에서 CRC 코드를 빠르게 출력하여 연산속도를 줄인다.

static const uint8_t crc4_lut[16] = {
    0x00, 0x03, 0x06, 0x05, 0x0C, 0x0F, 0x0A, 0x09,
    0x0B, 0x08, 0x0D, 0x0E, 0x07, 0x04, 0x01, 0x02
}; // CRC-4 Look up table

uint8_t data    = 0xB;           // 1011
uint8_t crc     = crc4_lut[data]; // 0xE = 1110