주기적 용장성 검사

CRC(Cyclic Redundancy Check)는 디지털 네트워크 및 스토리지 장치에서 디지털 데이터의 우발적인 변화를 감지하기 위해 일반적으로 사용되는 오류 감지 코드입니다.이들 시스템에 들어가는 데이터 블록은 그 내용의 다항식 분할의 나머지에 근거해 짧은 체크치를 부가한다.검색 시 계산을 반복하여 체크 값이 일치하지 않을 경우 데이터 파손에 대한 시정 조치를 취할 수 있습니다.CRC는 오류 수정에 사용할 수 있습니다(비트 필터 ^[1]참조).

CRC는 체크(데이터 검증) 값이 용장성(정보를 추가하지 않고 메시지를 확장)이며 알고리즘이 순환 코드에 기반하기 때문에 호출됩니다.CRC는 바이너리 하드웨어로 구현이 간단하고 수학적으로 분석하기 쉬우며 특히 전송 채널의 노이즈로 인한 일반적인 오류를 검출하는 데 능숙하기 때문에 인기가 있습니다.체크 값은 길이가 고정되어 있기 때문에 이를 생성하는 함수가 해시 함수로 사용되는 경우가 있습니다.

서론

CRC는 주기적 오류 수정 코드 이론에 기초합니다.통신 네트워크에서의 에러 검출을 목적으로, 고정 길이 체크치를 추가해 메시지를 부호화하는 체계적 순환 코드의 사용은, W에 의해서 최초로 제안되었습니다. 웨슬리 ^[2]피터슨 1961년사이클릭 코드는 구현이 간단할 뿐만 아니라 버스트오류 검출에 특히 적합하다는 장점이 있습니다.메시지 내의 오류 데이터 기호의 연속 시퀀스입니다.버스트 에러는 자기 및 광학 스토리지 디바이스를 포함한 많은 통신 채널에서 일반적인 전송 에러이기 때문에 이것은 중요합니다.일반적으로 임의의 길이의 데이터 블록에 적용되는n비트 CRC는 n비트 이하의 단일 오류 버스트를 검출합니다.검출되는 모든 긴 오류 버스트의 비율은 (1 - 2⁻ⁿ)입니다.

CRC 코드를 지정하려면 이른바 생성기 다항식의 정의가 필요합니다.이 다항식은 다항식 긴 나눗셈에서 제수가 되고, 이 다항식은 메시지를 배당금으로 받아들이고 몫이 폐기되고 나머지가 결과가 됩니다.중요한 경고는 다항식 계수가 유한 필드의 산술에 따라 계산되므로 추가 연산은 항상 비트 병렬로 수행될 수 있다는 것입니다(숫자 간 자리 이동은 없습니다).

실제로 일반적으로 사용되는 모든 CRC는 GF(2)라는 두 요소의 갈로아 필드 또는 더 간단히 유한 필드를 사용합니다.이 두 요소는 보통 0과 1로 불리며 컴퓨터 아키텍처와 잘 어울립니다.

CRC는 체크값이 n비트 길이일 때 n비트 CRC라고 불립니다.주어진 n에 대해 각각 다른 다항식을 갖는 여러 CRC가 가능합니다.이러한 다항식은 차수 n이 가장 높으며, 즉 n + 1 항을 가집니다.즉, 다항식의 길이는 n + 1이며 인코딩에는 n + 1비트가 필요합니다.MSB 또는 LSB는 항상 1이므로 대부분의 다항식 사양은 MSB 또는 LSB를 폐기합니다.CRC 및 관련 다항식은 일반적으로 아래 표와 같이 CRC-n-XXX 형식의 이름을 가집니다.

가장 간단한 오류 감지 시스템인 패리티 비트는 사실 1비트 CRC입니다. 생성기 다항식 x + 1(2개 항)^[3]을 사용하며 CRC-1이라는 이름을 가집니다.

어플

CRC 대응 장치는 송신 또는 저장되는 데이터의 각 블록에 대해 체크값 또는 CRC로 알려진 짧은 고정 길이의 이진 시퀀스를 계산하여 코드워드를 형성하여 데이터에 부가한다.

코드워드를 수신 또는 읽었을 때, 디바이스는 체크값을 데이터 블록으로부터 새롭게 계산한 값과 비교하거나, 또는 동등하게 코드워드 전체에 대해 CRC를 실행하고, 그 체크값을 기대 잔차 상수와 비교한다.

CRC 값이 일치하지 않으면 블록에 데이터 오류가 포함되어 있습니다.

디바이스는 블록을 다시 읽거나 다시 전송하도록 요청하는 등의 수정 작업을 수행할 수 있습니다.그렇지 않으면 데이터에는 오류가 없는 것으로 간주됩니다(다만, 검출되지 않은 에러가 포함되어 있을 가능성이 있습니다.이것은 에러 ^[4]체크의 본질입니다).

데이터 무결성

CRC는 통신 채널에서 흔히 볼 수 있는 유형의 오류로부터 보호하기 위해 특별히 설계되었으며, 이를 통해 전달되는 메시지의 무결성을 신속하고 합리적으로 보장할 수 있습니다.단, 데이터의 의도적인 변경에 대한 보호에는 적합하지 않습니다.

우선 인증이 없기 때문에 공격자는 치환을 검출하지 않고 메시지를 편집하여 CRC를 재계산할 수 있습니다.데이터와 함께 저장되는 CRC 및 암호화 해시 함수 자체는 의도적인 데이터 수정으로부터 보호되지 않습니다.이러한 공격에 대한 보호가 필요한 응용 프로그램에서는 메시지 인증 코드나 디지털 서명(일반적으로 암호화 해시 함수에 기반함) 등의 암호화 인증 메커니즘을 사용해야 합니다.

둘째, 암호화 해시함수와 달리 CRC는 쉽게 되돌릴 수 있는 함수로 디지털 ^[5]서명에 적합하지 않습니다.

셋째, CRC는 선형 함수(또는 더 정확히는 아핀 함수)^[6]와 유사한 관계를 만족합니다.

$\displaystyle \operatorname {CRC}(x\oplus y)=\operatorname {CRC}(x)\oplus\operatorname {CRC}(y)\oplus c}$

$여기$서 c$\displaystyle$c는$$ x$\$$displaystyle$ $x{\displaystyle }$\와 y$$$\backslash$$displaystyle$y의 $길이$에 따라 달라집니다.이것은 다음과 같이 나타낼 수도 있습니다. 여기서$x{\displaystyle }$ {\$displaystyle$x$\},$$y{\displaystyle }$ {\$displaystyle$ y$}$ $및$ z {\$displaystyle$ z$}$의 길이는 동일합니다.

$\displaystyle \operatorname {CRC}(x\oplus y\oplus z)=\operatorname {CRC}(x)\oplus \operatorname {CRC}(z);}$

그 결과 CRC가 XOR을 결합 조작(또는 OFB나 CFB와 같이 효과적으로 스트림 암호로 변환하는 블록 암호 모드)으로 암호화되어 있어도 메시지와 관련된 CRC는 암호화 키를 인식하지 않고 조작할 수 있습니다.이것은 잘 알려진 설계상의 결함 중 하나입니다.Wired Equivalent Privacy(WEP) 프로토콜.^[7]

계수

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2016년 7월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

n비트 바이너리 CRC를 계산하려면 입력을 나타내는 비트를 행에 나열하고 CRC의 제수('폴리노미얼'이라고 함)를 나타내는 (n + 1)비트 패턴을 행의 왼쪽 끝에 배치합니다.

이 예에서는 메시지의 14비트를 3비트 CRC, 다항식³ x + x + 1로 부호화합니다.다항식은 계수로 2진수로 작성됩니다. 3차 다항식은 4개의 계수(1x³ + 0x² + 1x + 1)를 가집니다.이 경우 계수는 1, 0, 1, 1입니다.계산 결과는 3비트 길이이므로 3비트 CRC라고 합니다.그러나 다항식을 명시적으로 기술하려면 4비트가 필요합니다.

부호화할 메시지로 시작합니다.

11010011101100 

이것은 처음에 CRC의 비트 길이n에 대응하는 제로로 채워집니다.이것은 결과 코드 워드가 체계적인 형식이 되도록 하기 위해 수행됩니다.3비트 CRC를 계산하기 위한 첫 번째 계산은 다음과 같습니다.

1101001100000 <--- 3비트1011로 오른쪽 패딩된 입력 <--- 1011> = x420 + x + 1 ------------------------------------------------------------------------------------------- 결과

알고리즘은 각 단계에서 제수 바로 위의 비트에 작용합니다.이 반복의 결과는 위의 비트가 있는 다항식 제수의 비트 단위 XOR입니다.제수 위에 없는 비트는 해당 단계에서 바로 아래에 복사됩니다.그런 다음 제수가 입력에서 가장 높은 나머지 1비트와 정렬되도록 오른쪽으로 이동하고 제수가 입력 행의 오른쪽 끝에 도달할 때까지 이 과정을 반복합니다.전체 계산은 다음과 같습니다.

11010011101100 000<>-입력 바로 3비트 천억개의 신경 세포라<>로 부풀린 것이며,-제수 01100011101100 000<>-결과(첫 4비트는들의 XOR은 제수 beneath과 비트의 휴식이 변화하지 않습니다에 유의하세요)천억개의 신경 세포라<>-제수..00111011101100 000천억개의 신경 세포라 00010111101100 000천억개의 신경 세포라 00000001101100 000<>-노트 정확그 제수용 모자(그 스텝의 몫이 제로이므로) 1011 (즉, 1회마다 1비트를 이동할 필요는 없습니다)00000011000000000000101010101010110000000000101010101010101011000000101101101 ----------------------------------------------- 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100 <---나머지(3비트).배당이 0이므로 나눗셈 알고리즘은 여기서 멈춥니다. 

맨 왼쪽 제수 비트가 터치한 모든 입력 비트를 제로로 설정했기 때문에 이 프로세스가 종료되었을 때 입력 행에서 0이 아닌 비트는 행 오른쪽 끝에 있는n비트뿐이에요이 n비트는 나눗셈 스텝의 나머지 부분이며 CRC 함수의 값이 되기도 합니다(선택한 CRC 사양에 따라 일부 후처리가 필요하지 않은 경우).

수신된 메시지의 유효성은, 상기의 계산을 재차 실시해, 이번에는 체크치를 0이 아니고 추가해 간단하게 확인할 수 있습니다.검출 가능한 에러가 없는 경우는, 나머지가 0이 됩니다.

110100111000 100 <--- 체크값 1011을 가진 입력 <---divisor 0110001100 100 <--- 결과 1011 <---divisor ... 00111011101 100 1011 000000101 100 101 1 --------------------- 00000000000000000000000000000000000000000000000000000000000000 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 1 ---------------not 00000000000000000000000000000000000000

다음 Python 코드는 선택한 입력 및 다항식의 초기 CRC 나머지를 반환하는 함수의 개요를 나타내고 있으며, 초기 패딩은 1 또는 0입니다.이 코드는 미가공 번호가 아닌 문자열 입력으로 동작합니다.

def crc_remainder(input_bitstring, 다항식_bitstring, initial_filler): "선택한 다항식을 사용하여 문자열의 나머지 CRC를 계산합니다.    initial_array는 '1' 또는 '0'이어야 합니다. "" 다항식_bitstring = 다항식_bitstring.lripa0") len_input = len(input_bitstring) initial_array = (len(len(input_bitial_bitstring) - 1) * initial_initial input_array = listing) input_array = list(input_array = listing)1')의 i 범위(len(input_bitstring)의 경우: input_disput_array[cur_shift + i] \ = str(int(input_bitstring [i]!= input_disput_array[cur_shift + i])를 반환합니다.mial."" 다항식_bitstring = 다항식_bitstring.lstrip0") len_input = len(input_bitstring) initial_array = list(input_bitstring + initial_array = list(input_bitstring_input_input_inut_input_inut_inut_inut_input_inut_inut_inut_inut_inut_inut_inut_inut_inut_inut_i] \ = str(int(interial_bitstring[i] != input_bitstring[cur_shift + i]) 반환('.'에 없음(input_bitstring)[len_input:]) 

>>>crc_module('11010011101100', '1011', '0') '100' >>>crc_체크('11010011101100', '1011', '100') 진실의 

CRC-32 알고리즘

이것은 ^[8]CRC-32 배리언트의 실용적인 알고리즘입니다.CRCTable은 메시지의 각 바이트에 대해 반복해야 하는 계산을 메모화한 것입니다(Computation of cyclic redundancy checks multi Multi-bit computation ） 。

    함수 CRC32 입력: 데이터: 바이트 // 바이트 배열출력: crc32: UInt32 // 32비트 부호 없는 CRC-32 값
 // CRC-32를 시작값 crc32 ← 0xFFFFFF로 초기화합니다.
 데이터의 각 바이트에 대해 nLookup을 수행합니다.인덱스 ← (120032 xor 바이트) 및 0xFF crc32 ← (120032 shr 8) xor CRCTable[nLookup]Index] // CRCTable은 256개의 32비트 상수 배열입니다.
 // 모든 비트 crc32 ← crc32 x 또는 0xFFFFFF 반환 crc32를 반전하여 CRC-32 값을 완성합니다.

C의 알고리즘은 다음과 같습니다.

#실패하다 <int types >h>// uint32_t, uint8_t  uint32_t CRC32(const uint8_t 데이터.[], size_t data_length) {  uint32_t crc32 = 0xFFFFFFU;    위해서 (size_t i = 0; i < > data_length; i++) {   const uint32_t lookup Index(룩업 인덱스) = (crc32 ^ 데이터.[i]) & 0xff;   crc32 = (crc32 >> 8) ^ CRCTable[lookup Index(룩업 인덱스)];  // CRCTable은 256개의 32비트 상수 배열입니다.  }    // 모든 비트를 반전시켜 CRC-32 값을 완성합니다.  crc32 ^= 0xFFFFFFU;  돌아가다 crc32; } 

수학

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2016년 7월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

이 나눗셈과 같은 과정을 수학적으로 분석하면 양호한 오차 검출 특성을 보장하는 제수를 선택하는 방법을 알 수 있습니다.이 분석에서 비트 문자열의 자릿수는 일부 변수 x- 유한 필드 GF(2)의 요소인 계수(정수 모듈로 2, 즉 0 또는 1)에서 보다 친숙한 숫자 대신 다항식의 계수로 받아들여진다.이항 다항식의 집합은 수학환이다.

다항식 설계

생성기 다항식의 선택은 CRC 알고리즘을 구현하는 데 있어 가장 중요한 부분입니다.전체 충돌 확률을 최소화하면서 오류 탐지 기능을 최대화하려면 다항식을 선택해야 합니다.

계산된 체크 값의 길이에 직접적인 영향을 미치기 때문에 다항식의 가장 중요한 속성은 다항식의 길이(다항식의 한 항 중 가장 큰 정도(exponent) +1)이다.

가장 일반적으로 사용되는 다항식 길이는 9비트(CRC-8), 17비트(CRC-16), 33비트(CRC-32) 및 65비트(CRC-64)^[3]입니다.

체크값이 n비트일 경우 CRC는 n비트 CRC라고 불립니다.주어진 n에 대해 각각 다른 다항식을 갖는 여러 CRC가 가능합니다.이러한 다항식은 차수가 n이 가장 높으므로 n + 1 항(다항식의 길이는 n + 1)입니다.나머지는 길이 n입니다.CRC에는 CRC-n-XX 형식의 이름이 있습니다.

CRC 다항식의 설계는 보호할 블록의 최대 총 길이(데이터 + CRC 비트), 원하는 오류 보호 기능, CRC 구현을 위한 리소스 유형 및 원하는 성능에 따라 달라집니다.일반적인 오해는 "최상의" CRC 다항식이 환원 불가능한 다항식 또는 환원 불가능한 다항식에 계수 1 + x를 곱한 값에서 파생된다는 것입니다. 이 값은 코드에 홀수 ^[9]비트에 영향을 미치는 모든 오류를 탐지하는 기능을 추가합니다.실제로는 위에서 설명한 모든 요인이 다항식의 선택에 들어가야 하며, 환원성 다항식으로 이어질 수 있습니다.그러나 환산 가능한 다항식을 선택하면 몫 링의 제수가 0이기 때문에 특정 비율의 누락 오차가 발생합니다.

원시 다항식을 CRC 코드의 생성기로 선택하는 이점은 결과 코드가 그 블록 길이 내의 모든 1비트 오류가 다른 나머지(신드롬이라고도 함)를 가지고 있다는 점에서 최대 총 블록 길이를 가지기 때문에 나머지 부분은 블록의 선형 함수이므로 코드는 모든 2비트 e를 검출할 수 있다는 것입니다.그 블록 길이 내에서 rrors가 표시됩니다.r$${\$displaystyle$ r$}$이 원시 발생기 다항식의 정도일 $경우{\displaystyle }$ 최대 총 ${\displaystyle {블록}^{}}$ 길이는 2 ${\displaystyle \mathrm{r}{}^{}}$-$$1 {\$displaystyle 2^{r$}-1$\}$이며 관련 코드는 싱글비트 또는 더블비트 오류를 ^[10]검출할 수 있습니다.우리는 이 상황을 개선할 수 있다.$제너레이터$ $다항식{\displaystyle }$g (${\displaystyle x}$)${\displaystyle =p}$ ( ${\displaystyle \mathrm{x}}$)${\displaystyle }$( 1 + $x$) { $displaystyle$g ( x )$= p$ ( 1 +$x$ )$$} ($여기$서$$p { $displaystyle$ p$}$는 r${\displaystyle }$-$$ (\displaystyle $r-1$의 기본 다항식이며, 최대 총 블록 $길이$는 2$$ -${\displaystyle {}^{}1}$ - 1$$- 1 (\$displaystyle r-1$ 및 code )입니다.홀수 개수의 에러입니다.

최대 총 블록 길이와 원하는 오류 검출 파워의 균형을 맞추기 위해 다른 인수 분해를 허용하는 $다항식{\displaystyle }$ g$)$ {$display$ g$(x)}$을 선택할 수 있다.BCH 코드는 그러한 다항식의 강력한 클래스입니다.위의 두 가지 예를 제시합니다.생성기 다항식 r의 환원성 속성에 관계없이, 만약 그것이 "+1" 항을 포함한다면, 코드는 r개의 연속 비트 창으로 제한되는 오류 패턴을 검출할 수 있을 것이다.이러한 패턴을 「에러 버스트」라고 부릅니다.

사양

실장자 또는 표준위원회가 CRC를 사용하여 실용적인 시스템을 설계할 경우 CRC의 오류 검출 코드라는 개념은 복잡해집니다.다음은 몇 가지 복잡한 문제입니다.

• 실장에서는 체크하는 비트스트림에 고정 비트패턴이 프리픽스 되는 경우가 있습니다.이는 클로킹 오류가 메시지 앞에 0비트를 삽입할 경우 유용합니다.그 이외의 경우 체크 값은 변경되지 않습니다.
• 통상, 항상은 아니지만, 실장은 다항식 나눗셈이 발생하기 전에 체크할 비트스트림에 n개의 0비트(n은 CRC 크기)를 추가합니다.이러한 추가 사항은 CRC 계산 기사에 명시되어 있습니다.이렇게 하면 체크 값이 추가된 원래 비트스트림의 나머지 부분이 정확히 0이므로 수신된 비트스트림에서 다항식 나눗셈을 수행하고 나머지를 0과 비교하는 것만으로 CRC를 확인할 수 있습니다.그 exclusive-or 작업의 가환 연상 속성 때문에, 실용적인 테이블에 의해 주도되는 구현을 명시적으로 어떤 영이 첨부 없이, 스트림은 CRCreg에서 이동하는 것과 함께 메시지를 bitstream가 equivalent,[9]더 빠른 알고리즘을 이용해 결과 수치 zero-appending에 해당하는 얻을 수 있다.는ter.
• 구현 배타적 비트 패턴을 다항식 나눗셈의 나머지 부분에 OR하는 경우가 있습니다.
• 비트 순서:일부 체계는 각 바이트의 하위 비트를 "첫 번째"로 보고 다항식 나눗셈 중에 "가장 왼쪽"을 의미하며, 이는 "저차"에 대한 우리의 관습적 이해와 반대됩니다.이 표기법은 시리얼 포트 전송이 하드웨어에서 CRC 체크되었을 때 의미가 있습니다.이는 널리 보급되어 있는 시리얼 포트 전송 표기법 중 일부는 최하위 비트를 먼저 전송하기 때문입니다.
• 바이트 순서:멀티바이트 CRC에서는 최초로 전송된 바이트(또는 메모리의 최저 주소 바이트에 저장됨)가 최하위 바이트(LSB)인지 최상위 바이트(MSB)인지에 대해 혼동이 발생할 수 있습니다.예를 들어 일부 16비트 CRC 방식은 체크 값의 바이트를 스왑합니다.
• 제수 다항식의 상위 비트 누락:상위 비트는 항상 1이고, n비트 CRC는 n비트 레지스터를 오버플로하는 (n + 1)비트 제수에 의해 정의되어야 하므로 일부 기록자는 제수의 상위 비트를 언급할 필요가 없다고 가정합니다.
• 제수 다항식의 하위 비트 누락:하위 비트는 항상 1이므로 Philip Koopman과 같은 저자는 상위 비트는 그대로 유지하되 하위 비트(${\displaystyle {x\mathrm{}}^{}}$ 0$${\$style$ x$^{0}}$ 또는$$ 1항)는 포함하지 않은 다항식을 나타냅니다.이 규칙은 하나의 정수로 완성되는 다항식을 부호화합니다.

이러한 복잡성은 다항식을 정수로 표현하기 위한 세 가지 일반적인 방법이 있다는 것을 의미합니다. 2진법에서 발견된 거울 이미지인 첫 번째 두 가지는 코드에서 발견된 상수이고, 세 번째는 Koopman의 논문에서 발견된 숫자입니다.두 경우 모두 하나의 항이 생략됩니다.따라서 $다항식{\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$4 +${\displaystyle x}$ + $({displaystyle$ x$^{4}+x+1})$은 다음과 같이 표기할 수 있습니다.

• 0x3 = 0b0011 (${\displaystyle {x4\mathrm{}}^{}}$+ (${\displaystyle {0\mathrm{}}^{}}$ x${\displaystyle {}^{}}$3 + ${\displaystyle {}^{}}$ x${\displaystyle {}^{}{2\mathrm{}}^{}}$ + ${\displaystyle 1}$ ${\displaystyle {x\mathrm{}}^{}}$ 1${\displaystyle {}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$0 )$$({$displaystyle$ x$^{4}$ + ($0x^{3}+1x^{0}))$ (MSB 최초 코드)
• 0xC = 0b1100${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$0 + ${\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$1 + ${\displaystyle 0}$ ${\displaystyle {x\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {x\mathrm{}}^{}}$ 3${\displaystyle }$) + x$$ ($1x$ style $(1x^{0}$ + $0x^{1}$ + $0x^{3})$ + $x^{4}$ (LSB 첫 번째 코드)
• 0x9 = 0b1001${\displaystyle }$(${\displaystyle {}^{}}$ x${\displaystyle {}^{}{4\mathrm{}}^{}}$ + ${\displaystyle 0}$ ${\displaystyle {}^{}{3\mathrm{}}^{}}$ + ${\displaystyle {}^{}}$ x${\displaystyle {}^{}{2\mathrm{}}^{}}$ + ${\displaystyle {}^{}}$ x${\displaystyle {}^{}{1\mathrm{}}^{}}$) + ${\displaystyle {x\mathrm{}}^{}}$ 0$$\ $displaystyle (1x^{4}$ + $0x^{3$} + $0x^{$2} + $1x^{1$} +$x^{0})$ (Koopman 표기법)

다음 표에 다음과 같이 표시됩니다.

난독화

독점 프로토콜의 CRC는 중요하지 않은 초기 값과 최종 XOR을 사용하여 난독화될 수 있지만, 이러한 기술은 알고리즘에 암호화 강도를 추가하지 않고 간단한 ^[11]방법을 사용하여 역설계할 수 있습니다.

표준 및 일반적인 용도

다양한 주기적 중복성 검사가 기술 표준에 통합되었습니다.하나의 알고리즘 또는 각 정도의 알고리즘이 모든 목적에 적합한 것은 아닙니다. Koopman과 Chakravarty는 애플리케이션 요건과 메시지 ^[12]길이의 예상 분포에 따라 다항식을 선택할 것을 권장합니다.사용 중인 CRC의 개수로 인해 개발자들이 혼란스러워하고 있으며, 저자들은 이 상황을 ^[9]해결하려고 노력했습니다.CRC-12에는 ^[12]3개의 다항식, CRC-16에는 22개의 모순되는 정의, CRC-32에는 ^[13]7개의 다항식이 보고되어 있습니다.

일반적으로 적용되는 다항식은 가능한 가장 효율적인 다항식이 아닙니다.1993년 이후, Koopman, Castagnoli과 다른 사람들 3,64비트 사이의 이전 프로토콜의 다항식보다 훨씬 더 좋은 성능(Hamming 거리의 주어진 메시지 크기를 위한 측면에서)이 있size,[12][14][15][16]을 찾는 예에, 및 오류 드의 개선을 목적으로 그 중에 최고의 출판 다항식의 공간 조사하고 있다.tectioncapacit미래 ^[15]표준의 y.특히 iSCSI와 SCTP는 이 연구의 결과 중 하나인 CRC-32C(Castagnoli) 다항식을 채택했다.

표준 기관인 CRC-32-IEEE가 가장 일반적으로 사용하는 32비트 다항식의 설계는 조지아 공과대학의 조셉 해먼드, 제임스 브라운, 샨샹 류, 미트레이어(Kenneth Brayer)가 로마 연구소와 공군 전자 시스템 부서를 위해 공동으로 노력한 결과였다.32비트 다항식의 가장 오래된 등장은 1975년 출판물에서 볼 수 있다.Brayer for Mitre의 기술 보고서 2956은 1월에 발행되어 ^[17]8월에 DTIC를 통해 일반에 배포되었으며, Hammond, Brown 및 Liu는 ^[18]5월에 발행된 로마 연구소에 대한 보고서입니다.두 보고서 모두 다른 팀의 기여가 포함되어 있었다.1975년 12월, 브레이어와 해몬드는 IEEE National Telecommunications Conference에서 그들의 연구를 발표했다. IEEE CRC-32 다항식은 해밍 코드의 생성 다항식이며 오류 감지 ^[19]성능으로 선정되었다.이 경우에도 iSCSI 또는 SCTP에서 사용되는 Castagnoli CRC-32C 다항식은 58비트부터131kbit의 메시지 퍼포먼스와 일치하며 가장 일반적인2개의 인터넷패킷 ^[15]사이즈를 포함한 몇 가지 사이즈 범위에서 퍼포먼스를 웃돌고 있습니다.ITU-T G.hn 규격에서도 CRC-32C를 사용하여 페이로드 내의 오류를 검출하고 있습니다(단, PHY 헤더에는 CRC-16-CCITT를 사용합니다).

CRC-32C 계산 하드웨어에서 수술을(으로 구현됩니다.CRC32 인텔 프로세서의 Nehalem 마이크로아키텍처(architecture)에 최초로 도입된 SSE4.2 명령어 세트).또한 ARMAArch64 아키텍처는 CRC-32와 CRC-32C의 양쪽 운용에 하드웨어 액셀러레이션을 제공합니다.

순환 중복성 검사의 다항식 표현

아래 표에는 사용 중인 다양한 알고리즘의 다항식만 나와 있습니다.특정 프로토콜의 변형은 위에서 설명한 바와 같이 사전 반전, 사후 반전 및 역 비트 순서를 부과할 수 있습니다.예를 들어 Gzip과 Bzip2에서 사용되는 CRC32는 동일한 다항식을 사용하지만 Gzip은 역비트 순서를 사용하는 반면 Bzip2는 사용하지 않습니다.^[13]도수가 1보다 큰 GF(2)의 패리티 다항식도 결코 원시적이지 않습니다.이 표에서 원시 다항식으로 표시된 짝수 패리티 다항식은 원시 다항식에${\displaystyle }$(${\displaystyle x}$ ${\displaystyle +1}$)$${$displaystyle \left(x+1\right$를 곱한 값을 나타냅니다.다항식의 최상위 비트는 항상 1이며 16진수 표현에는 표시되지 않습니다.

이름.	사용하다	다항식 표현				패리티[20]	원시적인[21]	해밍[22][15][21] 거리에 의한 페이로드의 최대 비트
		보통의	반전	호혜적	역호수			≥ 16	15	14	13	12	11	10	9	8	7	6	5	4	3	2개[23]
CRC-1	대부분의 하드웨어, 패리티 비트라고도 합니다.	0x1	0x1	0x1	0x1	심지어.
		${\displaystyle x+1}$
CRC-3-GSM	모바일[24] 네트워크	0x3	0x6	0x5	0x5	이상한	네	–	–	–	–	–	–	–	–	–	–	–	–	–	4	∞
		${\displaystyle x^{3}+x+1}$
CRC-4-ITU	ITU-T G.704, 페이지 12	0x3	0xC	0x9	0x9	이상한
		${\displaystyle x^{4}+x+1}$
CRC-5-EPC	2세대 RFID[26]	0x09	0x12	0x05	0x14	이상한
		${\displaystyle x^{5}+x^{3}+1}$
CRC-5-ITU	ITU-T G.704, 9페이지	0x15	0x15	0x0B	0x1A	심지어.
		${\displaystyle x^{5}+x^{4}+x^{2}+1}$
CRC-5-USB	USB 토큰 패킷	0x05	0x14	0x09	0x12	이상한
		${\displaystyle x^{5}+x^{2}+1}$
CRC-6-CDMA2000-A	모바일[27] 네트워크	0x27	0x39	0x33	0x33	이상한
CRC-6-CDMA2000-B	모바일[27] 네트워크	0x07	0x38	0x31	0x23	심지어.
CRC-6-DARC	데이터 라디오 채널[28]	0x19	0x26	0x0D	0x2C	심지어.
CRC-6-GSM	모바일[24] 네트워크	0x2F	0x3D	0x3B	0x37	심지어.	네	–	–	–	–	–	–	–	–	–	–	1	1	25	25	∞
		${\displaystyle x^{6}+x^{5}+x^{3}+x^{2}+x+1}$
CRC-6-ITU	ITU-T G.704, 페이지 3	0x03	0x30	0x21	0x21	이상한
		${\displaystyle x^{6}+x+1}$
CRC-7	텔레콤 시스템, ITU-T G.707, ITU-T G.832, MMC, SD	0x09	0x48	0x11	0x44	이상한
		${\displaystyle x^{7}+x^{3}+1}$
CRC-7-MVB	열차 통신 네트워크, IEC 60870-5[30]	0x65	0x53	0x27	0x72	이상한
CRC-8	DVB-S2[31]	0xD5	0xAB	0x57	0xEA[12]	심지어.	없다	–	–	–	–	–	–	–	–	–	–	2	2	85	85	∞
		${\displaystyle x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+1}$
CRC-8-AUTOSAR	자동차[34] 통합,[33] OpenSafety	0x2F	0xF4	0xE9	0x97[12]	심지어.	네	–	–	–	–	–	–	–	–	–	–	3	3	119	119	∞
		${\displaystyle x^{8}+x^{5}+x^{3}+x^{2}+x+1}$
CRC-8-블루투스	무선 접속[35]	0xA7	0xE5	0xCB	0xD3	심지어.
		${\displaystyle x^{8}+x^{7}+x^{5}+x^{2}+x+1}$
CRC-8-CCITT	ITU-T I.432.1 (02/99); ATM HEC, ISDN HEC 및 셀 표시, SMBus PEC	0x07	0xE0	0xC1	0x83	심지어.
		${\displaystyle x^{8}+x^{2}+x+1}$
CRC-8-Dallas/Maxim	1-와이어 버스[36]	0x31	0x8C	0x19	0x98	심지어.
		${\displaystyle x^{8}+x^{5}+x^{4}+1}$
CRC-8-DARC	데이터 라디오 채널[28]	0x39	0x9C	0x39	0x9C	이상한
		${\displaystyle x^{8}+x^{5}+x^{4}+x^{3}+1}$
CRC-8-GSM-B	모바일[24] 네트워크	0x49	0x92	0x25	0xA4	심지어.
		${\displaystyle x^{8}+x^{6}+x^{3}+1}$
CRC-8-SAE J1850	AES3, OBD	0x1D	0xB8	0x71	0x8E	이상한
		${\displaystyle x^{8}+x^{4}+x^{3}+x^{2}+1}$
CRC-8-WCDMA	모바일[27][37] 네트워크	0x9B	0xD9	0xB3	0xCD[12]	심지어.
		${\displaystyle x^{8}+x^{7}+x^{4}+x^{3}+x+1}$
CRC-10	ATM, ITU-T I.610	0x233	0x331	0x263	0x319	심지어.
		${\displaystyle x^{10}+x^{9}}+x^{5}+x^{4}+x+1}$
CRC-10-CDMA2000	모바일[27] 네트워크	0x3D9	0x26F	0x0DF	0x3EC	심지어.
CRC-10-GSM	모바일[24] 네트워크	0x175	0x2BA	0x175	0x2BA	이상한
CRC-11	FlexRay[38]	0x385	0x50E	0x21D	0x5C2	심지어.
		${\displaystyle x^{11}+x^{9}}+x^{8}+x^{7}+x^{2}+1}$
CRC-12	통신[39][40] 시스템	0x80F	0xF01	0xE03	0xC07[12]	심지어.
		${\displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-12-CDMA2000	모바일[27] 네트워크	0xF13	0xC8F	0x91F	0xF89	심지어.
CRC-12-GSM	모바일[24] 네트워크	0xD31	0x8CB	0x197	0xE98	이상한
CRC-13-BBC	시간 신호, 무선 텔레스위치[41][42]	0x1CF5	0x15E7	0x0BCF	0x1E7A	심지어.
		${\displaystyle x^{13}+x^{12}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1}$
CRC-14-DARC	데이터 라디오 채널[28]	0x0805	0x2804	0x1009	0x2402	심지어.
CRC-14-GSM	모바일[24] 네트워크	0x202D	0x2D01	0x1A03	0x3016	심지어.
CRC-15-CAN		0xC599[43][44]	0x4CD1	0x19A3	0x62CC	심지어.
		${\displaystyle x^{15}+x^{14}+x^{10}+x^{8}+x^{7}+x^{4}+x^{3}+1}$
CRC-15-MPT1327	[45]	0x6815	0x540B	0x2817	0x740A	이상한
CRC-16-차크라바티	64비트 이하의 페이로드에[30] 최적	0x2F15	0xA8F4	0x51E9	0x978A	이상한
CRC-16-ARINC	ACARS 어플리케이션[46]	0xA02B	0xD405	0xA80B	0xD015	이상한
CRC-16-CCIT	X.25, V.41, HDLC FCS, XMODEM, Bluetooth, PACTOR, SD, DigRF, 기타 다수의 CRC-CCITT	0x1021	0x8408	0x811	0x8810[12]	심지어.
		${\displaystyle x^{16}+x^{12}+x^{5}+1}$
CRC-16-CDMA2000	모바일[27] 네트워크	0xC867	0xE613	0xCC27	0xE433	이상한
CRC-16-DECT	무선 전화[47]	0x0589	0x91A0	0x2341	0x82C4	심지어.
		${\displaystyle x^{16}+x^{10}+x^{8}+x^{7}+x^{3}+1}$
CRC-16-T10-차이	SCSI DIF	0x8BB7[48]	0xEDD1	0xDBA3	0xC5DB	이상한
		${\displaystyle x^{16}+x^{15}+x^{11}+x^{9}}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$
CRC-16-DNP	DNP, IEC 870, M 버스	0x3D65	0xA6BC	0x4D79	0x9EB2	심지어.
		${\displaystyle x^{16}+x^{13}+x^{11}+x^{10}+x^{8}+x^{6}+x^{5}+x^{2}+1}$
CRC-16-IBM	Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, 기타 다수, CRC-16 및 CRC-16-ANSI라고도 함	0x8005	0xA001	0x4003	0xC002	심지어.
		${\displaystyle x^{16}+x^{15}+x^{2}+1}$
CRC-16-Open Safety-A	안전[34] 필드버스	0x5935	0xAC9A	0x5935	0xAC9A[12]	이상한
CRC-16-Open Safety-B	안전[34] 필드버스	0x755B	0xDAAE	0xB55D	0xBAAD[12]	이상한
CRC-16-Profibus	필드버스[49] 네트워크	0x1DCF	0xF3B8	0xE771	0x8EE7	이상한
플레처-16	애들러-32 A&B 체크섬에서 사용	종종 CRC로 혼동되지만 실제로는 체크섬입니다. Fletcher의 체크섬을 참조하십시오.
CRC-17-CAN	CAN FD[50]	0x1685B	0x1B42D	0x1685B	0x1B42D	심지어.
CRC-21-CAN	CAN FD[50]	0x102899	0x132281	0x064503	0x18144C	심지어.
CRC-24	FlexRay[38]	0x5D6DCB	0xD3B6BA	0xA76D75	0xAEB6E5	심지어.
		${\displaystyle x^{24}+x^{22}+x^{19}+x^{18}+x^{16}+x^{13}+x^{11}+x^{10}+x^{8}+x^{7}+x^{6}+x^{3}+x1}$
CRC-24-Radix-64	OpenPGP, RTCM104v3	0x864CFB	0xDF3261	0xBE64C3	0xC3267D	심지어.
		${\displaystyle x^{24}+x^{23}+x^{17}+x^{14}+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x+x^{1}$
CRC-24-WCDMA	OS-9 RTOS에서 사용됩니다.잔류물 = 0x800FE3.[51]	0x800063	0xC60001	0x8C0003	0xC00031	심지어.	네[52]	–	–	–	–	–	–	–	–	–	–	4	4	8388583	8388583	∞
		${\displaystyle x^{24}+x^{23}+x^{6}+x^{5}+x+1}$
CRC-30	CDMA	0x2030B9C7	0x38E74301	0x31CE8603	0x30185CE3	심지어.
		${\displaystyle x^{30}+x^{29}+x^{20}+x^{15}+x^{13}+x^{12}+x^{11}+x^{8}+x^{7}+x^{6}+x^{2}+x^{1}$
CRC-32	ISO 3309(HDLC), ANSI X3.66(ADCCP), FIPS PUB 71, FED-STD-1003, ITU-T V.42, ISO/IEC/IEEE 802-3(이더넷), SATA, MPEG-2, PKZIP, CZIP, POSIX	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB[15]	이상한	네.	–	10	–	–	12	21	34	57	91	171	268	2974	91607	4294967263	∞
		${{displaystyle x^{32}+x^{26}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+x+x+1}$
CRC-32C(Castagnoli)	iSCSI, SCTP, G.hn 페이로드, SSE4.2, Btrfs, ext4, Ceph	0x1EDC6F41	0x82F63B78	0x05EC76F1	0x8F6E37A0[15]	심지어.	네.	6	–	8	–	20	–	47	–	177	–	5243	–	2147483615	–	∞
		${\displaystyle x^{32}+x^{28}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^9}}+x^{8}+x^{6}+1}$
CRC-32K(Koopman {1,3,28})	이더넷 프레임 길이, 긴 파일 사용 시 성능 저하	0x741B8CD7	0xEB31D82E	0xD663B05D	0xBA0DC66B[15]	심지어.	아니요.	2	–	4	–	16	–	18	–	152	–	16360	–	114663	–	∞
		${\displaystyle x^{32}+x^{30}+x^{28}+x^{26}+x^{20}+x^{19}+x^{17}+x^{16}+x^{15}+x^{11}+x^{10}+x^{7}+x^6}+x^2}+x^2}$
CRC-32K2(Koopman {1,1,30})	이더넷 프레임 길이, 긴 파일 사용 시 성능 저하	0x32583499	0x992C1A4C	0x32583499	0x992C1A4C[15]	심지어.	아니요.	–	–	3	–	16	–	26	–	134	–	32738	–	65506	–	∞
CRC-32Q	항공[55], AIXM	0x814141AB	0xD5828281	0xAB050503	0xC0A0A0D5	심지어.
		${\displaystyle x^{32}+x^{31}+x^{24}+x^{22}+x^{16}+x^{14}+x^{8}+x^{7}+x^{3}+x+1}$
애들러-32		CRC로 혼동되는 경우가 많지만 실제로는 체크섬입니다.Adler-32 참조
CRC-40-GSM	GSM 컨트롤[56][57][58] 채널	0x0004820009	0x9000412000	0x2000824001	0x8002410004	심지어.
		$({displaystyle x^{40}+x^{26}+x^{17}+x^{3}+1=(x^{23}+1)(x^{17}+x^{3}+1)})$
CRC-64-ECMA	ECMA-182 페이지 51, XZ 유틸리티	0x42F0E1EBA9EA3693	0xC96C5795D7870F42	0x92D8AF2BAF0E1E85	0xA17870F5D4F51B49	심지어.
		$({displaystyle x^{64}+x^{62)+x^{55}+x^{52)+x^{47}+x^{46)+x^{45}+x^{40}+x^{39}+x^{38}+x^{35}+x^{5}+x^{5})$ ${\displaystyle x^{32}+x^{31}+x^{27}+x^{24}+x^{23}+x^{22}+x^{21)+x^{17}+x^{13}+x^{12}+x^{10}+x^{9}}+x^{7}+x^{4}+x+1}$
CRC-64-ISO	ISO 3309(HDLC), Swiss-Prot/TrEMBL, 해시에[59] 약한 것으로 간주	0x000000000000001B	0xD800000000000000	0xB000000000000001	0x800000000000000D	이상한
		${\displaystyle x^{64}+x^{4}+x^{3}+x+1}$

실장

• GNU Radio에서의 CRC32 구현(최대 3.6.1) (2012년 경)
• CRC 체크섬 계산용 C클래스 코드(다양한 CRC 선택 가능)

CRC 카탈로그

• 파라미터화된 CRC 알고리즘 카탈로그
• CRC 다항식 동물원

「 」를 참조해 주세요.

• 순환 용장성 검사 수학
• 주기적 용장성 검사 계산
• 해시 함수 목록
• 체크섬 알고리즘 목록
• 정보 보안
• 간단한 파일 확인
• LRC

레퍼런스

추가 정보

• Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8.

외부 링크

• ISO/IEC 13239:2002:정보기술 -시스템간 전기통신 및 정보교환 -고레벨 데이터링크제어(HDLC) 절차
• CRC32-Castagnoli Linux 라이브러리