CRC 기초

작성자: Jeremy Purcell, 마지막 수정일: 2012년 6월 22일

특징

  • CRC에 대한 기본적인 설명(0 추가 방식)
  • CRC의 무차별 대입 컴퓨팅에 관한 간략한 설명
  • CRC 합계 계산 예시
  • 간단한 CRC 실행을 위한 C 코드

소개

CRC(Cyclic Redundancy Check)는 전송되는 데이터가 전송 중 손상되지 않았는지 확인하는 검증 방식입니다. CRC는 디지털 데이터를 전송하는 WiFi 및 이더넷과 같은 통신 매체에 흔히 사용됩니다. 기술 발전을 통해 임베디드 시스템이 대용량의 데이터 패킷을 더 빠르고 복잡한 방식으로 생성하고 전송할 수 있게 됨에 따라, 이러한 임베디드 시스템에 통신 오류가 없는지 확인해야 합니다. 본 응용 노트에서는 CRC를 계산하고 검증하는 방법을 알아봅니다.

배경

CRC 알고리즘은 CRC 알고리즘을 통해 전송되는 각 특정 데이터 세트에 대한 체크섬을 계산합니다. 이 알고리즘은 다항식 키와 전송된 데이터를 사용합니다.

전송을 실행하는 시스템은 확인 또는 검증 코드를 계산하여 이를 전송되는 메시지에 추가합니다. 수신받는 측에서도 데이터가 동일한 프로세스를 거칩니다. 수신 측에서 생성된 CRC가 전송된 CRC와 일치하지 않으면 데이터 손상의 가능성이 있음을 의미합니다. 수신 측에서는 데이터 재전송을 요청하거나 데이터를 무시할 수 있습니다. CRC가 수신된 버전과 일치하면 데이터 손상이 없음을 의미합니다.

CRC를 실행하는 방법은 다음과 같이 두 가지입니다. 전수 공격법에는 더 많은 컴퓨팅 리소스가 필요하며 더 많은 시간이 소요될 수 있습니다. 조회 테이블 방식에는 더 많은 메모리 리소스가 필요하며 정의되었거나 반복적인 데이터 세트에 적합합니다.

응용 분야

본 응용 노트에서는 전수 공격법을 사용한 CRC 계산에 대해 알아봅니다. 소프트웨어에서 데이터 또는 다항식 키를 시프트한 다음 계산을 수행하여 CRC를 계산할 수 있습니다. CRC 체크섬을 계산하는 방법은 다양합니다.

CRC 다항식

다항식 키는 CRC의 중요한 부분입니다. 키는 단순히 무작위 다항식이 아닙니다. 일련의 수학 공식을 사용하여 생성되며 CRC 프로세스에서 식별하는 오류의 수를 증가시키는 것을 목적으로 합니다. 다항식은 보통 네트워크 프로토콜 또는 외부 장치에서 정의됩니다. 이미 잘 구축되어 있는 일련의 키를 사용할 수 있으므로, 여기에서는 키를 정의하는 프로세스를 다루지 않습니다.

다항식 키는 이진법 표현식으로 변환됩니다. 다항식을 확장한 다음 계수를 적용하는 방식으로 변환됩니다. 다항식의 이진 변환 예시는 다음과 같습니다.

다항식 키: image

확장된 다항식 키: image

다항식 계수: 100110001

여기에서 다항식의 가장 높은 제곱수는 8이므로 이 다항식은 8비트 CRC이며, 이를 보통 CRC-8이라고 합니다. CRC에서 매우 일반적으로 사용되는 다항식 크기는 4, 8, 16, 32비트입니다.

CRC 체크섬 계산

전송 장치는 데이터에 올바른 수의 0을 더해 CRC를 계산합니다. 그런 다음 이진법을 사용하여 데이터를 처리하고 통신 채널을 통해 전송합니다. 이러한 방식이 그림 1의 “0 추가” 방식입니다. 부록의 예시 1은 이 방식을 보여줍니다.

우선 전체 데이터 패킷에 0이 추가됩니다. 다항식을 데이터의 가장 왼쪽에 있는 1에 일치시킵니다. 다항식을 데이터에 XOR 연산 수행합니다. 이 결과가 새로운 데이터입니다. 다시 한번 다항식을 데이터의 가장 왼쪽에 있는 1에 일치시킵니다. 데이터가 다항식보다 작아질 때까지 이 과정을 반복합니다. 이 CRC를 데이터 스트림에 추가한 다음 전송합니다.


그림 1. 0 추가 알고리즘

CRC 검증

시스템의 수신부에서 CRC 검증을 위한 두 가지 방법, 즉 “0 추가” 방식과 “0 결과” 방식에 대해 알아보겠습니다.

“0 추가” 방식에서는 CRC를 제거하고 데이터에 n개의 0이 추가되며, n은 다항식에서 가장 높은 제곱수입니다. CRC-8에서는 데이터 끝부분에 8개의 0이 추가됩니다. 그런 다음 그림 1과 같이 CRC를 계산하여 수신된 CRC 값과 비교합니다.

“0 결과” 방식에서는, 그림 1과 같이 이와 유사한 과정을 따르지만, 0이 추가되지 않고 데이터에 수신된 CRC가 포함되어 있다는 점이 다릅니다. 이 프로세스가 완료되면 데이터가 CRC에 일치하는 경우 결과는 0이 됩니다. 부록의 예시 2는 이 방식을 보여줍니다.

수많은 응용 분야에서 더 적은 컴퓨팅 리소스가 필요한 조회 테이블 방식을 사용합니다. 이러한 조회 테이블에는 특정 데이터 세트에 해당하는 CRC 값이 포함되어 있습니다. 이러한 방식은 데이터 전송이 정의되어 있거나 반복적인 경우의 응용 분야에 적합합니다.

고려사항

엔디언은 데이터의 바이트 순서를 나타내는 용어입니다. 빅-엔디언은 데이터가 최상위 비트(MSB)부터 전송됨을 의미합니다. 반대로 리틀-엔디언은 최하위 비트(LSB)부터 전송됨을 의미합니다. 바이트가 MSB 우선에서 LSB우선으로 반전되면 CRC가 변경되기 때문에 엔디언은 중요합니다. 일반적으로 엔디언은 전송되는 데이터 유형에 따라 달라집니다.

결론

CRC는 잡음이 많은 매체를 통해 전송되는 데이터에 오류가 있는지 확인하기 위한 간단하면서도 효과적인 방법입니다. 본 응용 노트에서는 CRC의 원리를 알아보고 CRC를 계산하고 검증하는 방식에 대해 살펴보았습니다. CRC는 대부분의 임베디드 시스템에 손쉽게 적용할 수 있습니다.

부록: 사례

예시 1: 0 추가 방식

수신되는 데이터는 MSB 우선으로 01101010 10101111(2바이트)입니다. 본 예시에서 사용하는 다항식 키는 x8 + x2 + x1 + 1 또는 100000111입니다. 8비트인 CRC-8의 경우 키는 실제로는 9비트입니다.

011010101010111100000000 데이터에 8개의 0 추가
100000111 다항식 키 우측 이동
011010101010111100000000
 100000111 키와 XOR 연산 및 우측 이동
 01010110110111100000000
  100000111 XOR 연산 및 우측 이동
  0010111000111100000000
   100000111 우측 이동
   010111000111100000000
    100000111 XOR 연산 및 우측 이동
    00111011011100000000
     100000111 우측 이동
     0111011011100000000
      100000111 XOR 연산 및 우측 이동
      011011100100000000
       100000111 XOR 연산 및 우측 이동
       0101111100000000
        100000111 XOR 연산 및 우측 이동
        0011110110000000
         100000111 우측 이동
         011110110000000
          100000111 XOR 연산 및 우측 이동
          01110101100000
           100000111 XOR 연산 및 우측 이동
           0110100010000
            100000111 XOR 연산 및 우측 이동
            010100101000
             100000111 XOR 연산 및 우측 이동
             00100110100
              100000111 우측 이동
              0100110100
               100000111 XOR 연산
               000110011 결과 < 다항식 키

데이터 0x6AAF에 대한 CRC 결과는 0x33입니다. 본 예시에서 송신기의 데이터 스트림(HEX)은 34 (xx) 6A AF 33입니다. 앞의 바이트(들)은 전송 프로토콜, 그 다음 두 개의 바이트는 데이터, 그리고 마지막 바이트가 CRC입니다.

예시 2: 0 결과 방식

먼저 수신되는 데이터 MSB는 01101010 10101111(2바이트)입니다. 본 예시에서 사용하는 다항식 키는 x8 + x2 + x1 + 1 또는 100000111입니다. 8비트인 CRC-8의 경우 키는 실제로 9비트입니다.

011010101010111100110011 데이터 및 CRC 수신
100000111 다항식 키 우측 이동
011010101010111100110011
 100000111 키와 XOR 연산 및 우측 이동
 01010110110111100110011
  100000111 XOR 연산 및 우측 이동
  0010111000111100110011
   100000111 우측 이동
   010111000111100110011
    100000111 XOR 연산 및 우측 이동
    00111011011100110011
     100000111 우측 이동
     0111011011100110011
      100000111 XOR 연산 및 우측 이동
      011011100100110011
       100000111 XOR 연산 및 우측 이동
       01011111000110011
        100000111 XOR 연산 및 우측 이동
         0011110110110011
          100000111 우측 이동
          011110110110011
           100000111 XOR 연산 및 우측 이동
           01110101010011
            100000111 XOR 연산 및 우측 이동
            0110100100011
             100000111 XOR 연산 및 우측 이동
             010100011011
              100000111 XOR 연산 및 우측 이동
              00100000111
               100000111 우측 이동
               0100000111
                100000111 XOR 연산
                000000000 결과 < 다항식 키

"0 결과 방식"을 사용한 0x6AAF에 대한 CRC 결과는 0x00으로, 정확한 데이터가 수신되었음을 의미합니다.

질문/의견

질문이나 의견이 있다면 Digi-Key의 TechForum을 방문해 보십시오.



영문 원본: CRC Basics