순환 중복 검사 문서 원본 보기

{{위키데이터 속성 추적}}
'''순환 중복 검사'''(巡環重復檢査), '''CRC'''(cyclic redundancy check)는 [[네트워크]] 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.

데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것임을 알 수 있다.

CRC는 [[이진법]] 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 [[데이터 무결성]]을 검사하는 데는 사용될 수 없다. 이런 용도로는 [[MD5]] 등의 함수들이 사용된다.

순환 중복 검사를 계산하는 과정은 하드웨어적 방식과 소프트웨어적 방식을 생각할 수 있다. 하드웨어적 방식을 말할 때, 직렬데이터를 계산하는 것이 단순하다. 통신시스템에서 프로토콜 계층에서 물리층에 가까울수록 하드웨어 접근을 그리고 상위계층에 가까울수록 소프트웨어적인 방식이 적용된다.

통신시스템에서 물리계층에 가까울수록 직렬데이터를 사용하는 경향이 있다. 따라서 하드웨어적 계산방식을 사용한다. 전송라인은 거의 직렬 데이터이기 때문이다. 이런 경우 순환 중복 검사는 비트단위의 입력에 대한 출력을 얻는다. 논리 회로를 만들면 간단해진다. 그러나 높은 계층으로 갈수록 병렬데이터(octet 단위, 8비트)를 사용한다. 이런 경우는 소프트웨어적 접근으로 주로 바이트 단위로 계산한다. 순환 중복 검사는 결국 비트단위 입력에 대한 각 비트별 [[XOR]] 연산이므로 한 바이트 계산도 소프트웨어적 고속계산에 한계가 있다. 이런 경우 주로 미리 계산을 한 테이블 형태를 사용한다<ref>[http://blog.naver.com/dolicom/10070824912 CRC 테이블 생성과 사용법] 정해진 다항식에 따라 한 바이트에 해당하는 직렬데이터를 미리 계산을 하여 테이블화한다. 바이트 단위의 입력데이터를 인덱스로 하여, 다음 CRC 값을 테이블 탐색을 하여 찾는다.</ref>.

== 개요 ==

CRC는 [[가환환]](commutative ring)의 나눗셈(사칙연산의 나눗셈이 아니다. 그냥 Modulo-2의 덧셈-XOR-이다.)에 기반한다. 여기서 쓰이는 환은 법 2 (modulo 2) 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 [[비트 (단위)|비트]]의 계수를 갖는 [[다항식]]의 집합이고, 이 다항식들간의 사칙연산은 다시 계수들을 가장 아래 비트만 따도록 정의하여 한 비트 계수의 다항식으로 표현하도록 정의된다. 예를 들면:
: <math>(x^3 + x) + (x + 1) = x^3 + 2x + 1 = x^3 + 1</math>

위 식에서 2는 [[이진법|이진수]]로 10이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자리수는 버린다. 다음은 곱셈의 예이다:
: <math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x = x^3 + x</math>

더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x''를 ''x'' + 1 로 나눈다고 해 보자.
: <math>x^3 + x^2 + x = (x + 1)(x^2 + 1) - 1 = (x + 1)(x^2 + 1) + 1.</math>
으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 ''x''<sup>2</sup> + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.

모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번자리가 1, 1번자리가 0, 2번자리가 1이므로, 다항식 <math>x^2 + 1</math>에 해당한다고 볼 수 있다. CRC 값은, 정해진 특정 다항식으로 데이터 스트링으로 주어진 다항식을 나누어 그 나머지를 나타내는 특정 길이의 비트 스트링이 된다. 이 나머지를 구하는 간단하고 빠른 [[알고리즘]]은 잘 알려져 있다. CRC는 종종 '''체크섬'''(checksum)으로 불리는데, 엄밀히 말하면 나눗셈을 통해 얻어지는 CRC 값에는 옳지 않은 이름이다.

CRC의 중심을 이루는 알고리즘은 [[의사코드]]로 다음과 같이 쓸 수 있다:

 '''function''' crc(''bit array'' bitString[1..len], ''int'' polynomial) {
     shiftRegister := initial value ''// 보통 00000000 또는 11111111''
     '''for''' i '''from''' 1 '''to''' len {
         '''if''' (shiftRegister의 최상위 비트) [[XOR|xor]] bitString[i] = 1
             shiftRegister := (shiftRegister left shift 1) [[XOR|xor]] polynomial
         '''else'''
             shiftRegister := shiftRegister left shift 1
     }
     '''return''' shiftRegister
 }

(참고: 실제로는 여러 개의 최상위 비트들에 해당하는 <code>shiftRegister</code>의 표를 만들어서 한꺼번에 여러 비트를 처리해 속도를 높이는 방법을 쓰며, 특히 8비트 단위로 처리하는 방법이 많이 사용된다.)

위의 구현은 다음과 같은 두 가지 방법으로 고칠 수 있으며, 따라서 둘 중 하나를 적용하거나 둘 다 적용할 경우 CRC 값을 계산하는 네 가지 동등한 방법이 존재한다:
# <code>shiftRegister</code>를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트한다. 이 경우 <code>polynomial</code>의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
# <code>shiftRegister</code>의 한 비트와 <code>bitString</code>의 한 비트를 xor하는 대신에, <code>shiftRegister</code>와 <code>bitString</code>에서 <code>polynomial</code>에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결과를 <code>shiftRegister</code>에 더한다. <code>polynomial</code>을 적당히 고치면 같은 나머지를 얻을 수 있다. 이 방법은 소프트웨어에서 구현하기는 힘들지만 하드웨어 구현에서는 종종 사용되며, CRC와 깊은 관련이 있는 [[선형 되먹임 시프트 레지스터]]를 설명하는 데 자주 사용된다.

특정한 CRC는 사용되는 다항식으로 정의한다. n비트 CRC를 만드는 데는 <math>x^n + ... + 1</math> 꼴의 n차 다항식이 필요하다. 이 다항식은 기본적으로 (n+1)비트 문자열로 나타낼 수 있지만, 차수가 가장 높은 x<sup>n</sup> 항의 계수는 항상 1이기 때문에 이 항을 빼고 n비트 문자열로 나타낼 수 있다. 예를 들어 CRC-16 표준에 사용되는 다항식인 <math>x^{15} + x^2 + 1</math>은 비트 순서에 따라서 [[십육진수|16진수]] 숫자 0x8005나 0xa001로 나타낼 수 있으며, [[이더넷]], [[FDDI]], [[PKZIP]], [[WinZip]], [[PNG]] 등에서 널리 사용되는 '''CRC-32'''의 경우 0x04C11DB7 또는 0xEDB88320으로 쓸 수 있다.

== CRC 다항식들과 종류들 ==

여기에 표시하지는 않았지만 더 많은 CRC 종류들이 있다.
* 적어도 다섯 종류의 서로 다른 CRC-16, CRC-32, CRC-64가 존재하고 널리 사용된다.
* CRC-128, CRC-256도 존재하고 표준화되어 있지만 널리 사용되지는 않는다.

=== 다항식의 표현 ===

다항식의 표현은 일반적으로 다음과 같이 표현한다.

다항식의 예 :

: <math>x^4 + x + 1</math>

이 다항식은 다음과 같이 3가지 방법의 숫자로 표현할 수 있다:
* 0x3 = 0b0011 : <s><math>x^4 +</math></s><math>0x^3 + 0x^2 + 1x^1 + 1x^0</math> (MSB-우선 코드)
* 0xC = 0b1100 : <math>1x^0 + 1x^1 + 0x^2 + 0x^3</math><s><math>+ x^4</math></s> (LSB-우선 코드)
* 0x9 = 0b1001 : <math>1x^4 + 0x^3 + 0x^2 + 1x^1</math><s><math>+ x^0</math></s> (Koopman 표시)

이 가지를 표로 나타내면:

{| class="wikitable"
! colspan="3" | 다항식(representations)
|-
! 정상(normal)
! 역방향(reversed)
! 역방향의 역수(reversed reciprocal)
|-
| 0x3
| 0xC
| 0x9
|}

=== 정의된 다항식의 사용처 ===
CRC값을 계산하려면 비트수와 다항식을 결정해야 한다. 따라서 정해진 비트수와 함께 다항식을 정하면 입력된 메시지는 오류가 없는 경우 같은 CRC 값이 나온다.

다음은 사용하고 있는 다양한 다항식들이다:

{| class="wikitable"
! rowspan="2" | 이름
! rowspan="2" | 사용
! colspan="3" | 다항식
|-
! 정상
! 역방향
! 역방향의 역수
|-
|CRC-1 || 주로 하드웨어에서 사용되며 [[패리티 비트]]로 알려져 있음
| 0x1
| 0x1
| 0x1
|-
| CRC-4-ITU
| [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]
| 0x3
| 0xC
| 0x9
|-
| CRC-5-EPC
| [[Radio-frequency identification|Gen 2 RFID]]<ref name="gen-2-spec">{{서적 인용|title=Class-1 Generation-2 UHF RFID Protocol|version=1.2.0|publisher=[[EPCglobal]]|url=http://www.gs1.org/gsmp/kc/epcglobal/uhfc1g2/uhfc1g2_1_2_0-standard-20080511.pdf|date=23 October 2008|accessdate=4 July 2012|page=35}} (Table 6.12)</ref>
| 0x09
| 0x12
| 0x14
|-
| CRC-5-ITU
| [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]
| 0x15
| 0x15
| 0x1A
|-
|CRC-5 || [[USB]] 토큰 패킷
| 0x05
| 0x14
| 0x12
|-
| CRC-6-ITU
| [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]
| 0x03
| 0x30
| 0x21
|-
|CRC-7 || |통신 체계, [http://www.itu.int/rec/T-REC-G.707/en G.707], [http://www.itu.int/rec/T-REC-G.832/en G.832], [[MultiMediaCard|MMC]], [[SD 카드]]
| 0x09
| 0x48
| 0x44
|-
| CRC-7-MVB
| [[열차 통신 네트워크]], [[IEC 60870-5]]<ref name="chakravarty-thesis">{{서적 인용|last=Chakravarty|first=Tridib|other=Philip Koopman, advisor|year=2001|month=December|title=Performance of Cyclic Redundancy Codes for Embedded Networks|publisher=Carnegie Mellon University|location=Pittsburgh|url=http://www.ece.cmu.edu/~koopman/thesis/chakravarty.pdf|accessdate=8 July 2013|pages=5,18}}</ref>
| 0x65
| 0x53
| 0x72
|-
<!-- |-
|CRC-8-Fletcher || A := A + D[i], B := B + A
|- --->
| CRC-8-[[CCITT]]
| [http://www.itu.int/rec/T-REC-I.432.1-199902-I/en I.432.1]; ATM [[CRC-based framing|HEC]], [[ISDN]] HEC and cell delineation
| 0x07
| 0xE0
| 0x83
|-
| CRC-8-Dallas/[[Maxim Integrated Products|Maxim]]
| 1-Wire bus
| 0x31
| 0x8C
| 0x98
|-
| CRC-8
| 
| 0xD5
| 0xAB
| 0xEA<ref name=koop04>{{저널 인용|  last = Koopman | first = Philip |  last2 = Chakravarty | first2 = Tridib |  title = Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks |  journal = The International Conference on Dependable Systems and Networks |  year = 2004 | month = June <!-- date from http://www.ece.cmu.edu/~koopman/pubs.html --> |  url = http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf |  accessdate = 14 January 2011 |  pages = 145–154 |  doi = 10.1109/DSN.2004.1311885 |  isbn = 0-7695-2052-9 }}</ref>
|-
| CRC-8-SAE J1850
| [[AES3]]
| 0x1D
| 0xB8
| 0x8E
|-
| CRC-8-[[W-CDMA (UMTS)|WCDMA]]
|<ref name="richardson-wcdma">{{서적 인용|last=Richardson|first=Andrew|title=WCDMA Handbook|location=Cambridge, UK|publisher=Cambridge University Press|date=17 March 2005|isbn=0-521-82815-5|page=223|url=http://books.google.co.uk/books?id=yN5lve5L4vwC&lpg=PA223&dq=&pg=PA223#v=onepage&q&f=false}}</ref>
| 0x9B
| 0xD9
| 0xCD<ref name="koop04" />
|-
| CRC-10
| ATM; [http://www.itu.int/rec/T-REC-I.610/en I.610]
| 0x233
| 0x331
| 0x319
|-
| CRC-11
| [[FlexRay]]<ref name="flexray-spec">{{서적 인용|title=FlexRay Protocol Specification|version=3.0.1|publisher=Flexray Consortium|date=October 2010|page=114}} (4.2.8 Header CRC (11 bits))</ref>
| 0x385
| 0x50E
| 0x5C2
|-
| CRC-12
| 통신 체계<ref>{{저널 인용| last = Perez | first = A. | coauthors = Wismer & Becker | title =  Byte-Wise CRC Calculations | journal = IEEE Micro | volume = 3 | issue = 3 | pages = 40–50 | year = 1983 | doi = 10.1109/MM.1983.291120}}</ref><ref>{{저널 인용| last = Ramabadran | first =  T.V. | last2 = Gaitonde | first2 = S.S. | title = A tutorial on CRC computations | journal = IEEE Micro | volume = 8 | issue = 4 | year = 1988 | pages = 62–75 | doi = 10.1109/40.7773 }}</ref>
| 0x80F
| 0xF01
| 0xC07<ref name="koop04" />
|-
| CRC-15-CAN(Controller Area Network)
| 
| 0x4599
| 0x4CD1
| 0x62CC
|-
| CRC-15-[[MPT1327]]
|<ref name="mpt1327">{{서적 인용|year=1997 |month=June |title=A signalling standard for trunked private land mobile radio systems (MPT 1327) |edition=3rd |publisher=[[Ofcom]] |page=3-3 |url=http://www.ofcom.org.uk/static/archive/ra/publication/mpt/mpt_pdf/mpt1327.pdf |accessdate=16 July 2012}} (3.2.3 Encoding and error checking)</ref>
| 0x6815
| 0x540B
| 0x740A
|-
| CRC-16-[[IBM]]
| Bisync(Binary Synchronous Communications), [[Modbus]], USB, [[ANSI]] [https://web.archive.org/web/20091001172850/http://www.incits.org/press/1997/pr97020.htm X3.28], SIA DC-07, 기타. ''CRC-16'' 또는 ''CRC-16-ANSI''로 알려짐.
| 0x8005
| 0xA001
| 0xC002
|-
| CRC-16-CCITT
| [[X.25]], [[V.41]], [[HDLC]] ''FCS'', [[XMODEM]], [[Bluetooth]], [[PACTOR]], [[SD 카드]],기타. ''CRC-CCITT''라고도 함.
| 0x1021
| 0x8408
| 0x8810<ref name="koop04" />
|-
| CRC-16-T10-DIF
| [[SCSI]] DIF
| 0x8BB7<ref name="thaler-t10-selection">{{저널 인용|last=Thaler|first=Pat|title=16-bit CRC polynomial selection|publisher=INCITS T10|date=28 August 2003|url=http://www.t10.org/ftp/t10/document.03/03-290r0.pdf|accessdate=11 August 2009}}</ref>
| 0xEDD1
| 0xC5DB
|-
| CRC-16-[[DNP]]
| DNP, [[IEC 60870-5|IEC 870]], M-Bus
| 0x3D65
| 0xA6BC
| 0x9EB2
|-
| CRC-16-DECT
| 무선전화<ref name="en-300-175-3">{{저널 인용|title=ETSI EN 300 175-3|version=V2.2.1|date=November 2008|publisher=European Telecommunications Standards Institute|location=Sophia Antipolis, France}}</ref>
| 0x0589
| 0x91A0
| 0x82C4
|-
| CRC-16-[[ARINC]]
|  ACARS 응용<ref name="rehmann-acars">{{저널 인용 | url=http://ntl.bts.gov/lib/1000/1200/1290/tn95_66.pdf | title=Air Ground Data Link VHF Airline Communications and Reporting System (ACARS) Preliminary Test Report | year=1995 | month=February | page=5 | last1=Rehmann | first1=Albert | last2=Mestre | first2=José D. | publisher=Federal Aviation Authority Technical Center | accessdate=7 July 2012 | archive-date=2012-08-02 | archive-url=https://web.archive.org/web/20120802065800/http://ntl.bts.gov/lib/1000/1200/1290/tn95_66.pdf }}</ref>
| 0xA02B
| 0xD405
| 0xD015
|-
<!--| Chakravarty
| optimal for payloads ≤64 bits<ref name="chakravarty-thesis"/>
| 0x2F15
| 0xA8F4
| 0x978A
|-
|CRC-16-Fletcher || (CRC-16 Adler의 기반)
|-
|CRC-16-Adler_A || [''A'' = 1 + ''D''<sub>1</sub> + ''D''<sub>2</sub> + ... + ''D''<sub>''n''</sub> (mod 65521)]
|-
|CRC-16-Adler_B || [''B'' = ''n''×''D''<sub>1</sub> + (''n''-1)×''D''<sub>2</sub> + (''n''-2)×''D''<sub>3</sub> + ... + ''D''<sub>''n''</sub> + ''n'' (mod 65521)]
|-
|CRC-32-Adler || [''Adler-32''(''D'') = ''B'' × 65536 + ''A'']
|---->
| Fletcher
| [[Adler-32]]에서 사용; A & B CRCs
| colspan="3" align="center" | ''[[Fletcher's checksum]]에 언급''
|-
| CRC-17-CAN
| CAN FD<ref name="can-fd-spec">{{서적 인용|title=CAN with Flexible Data-Rate Specification|version=1.0|publisher=Robert Bosch GmbH|date=April 17th, 2012|page=13|url=http://www.bosch-semiconductors.de/media/pdf_1/canliteratur/can_fd_spec.pdf|확인날짜=2013년 4월 2일|보존url=https://web.archive.org/web/20130822124728/http://www.bosch-semiconductors.de/media/pdf_1/canliteratur/can_fd_spec.pdf|보존날짜=2013년 8월 22일|url-status=dead}} (3.2.1 DATA FRAME)</ref>
| 0x1685B
| 0x1B42D
| 0x1B42D
|-
| CRC-21-CAN
| CAN FD<ref name="can-fd-spec"/>
| 0x102899
| 0x132281
| 0x18144C
|-
| CRC-24
| [[FlexRay]]<ref name="flexray-spec" />
| 0x5D6DCB
| 0xD3B6BA
| 0xAEB6E5
|-
| CRC-24-[[Radix-64]]
| [[Pretty Good Privacy#OpenPGP|OpenPGP]], [[RTCM|RTCM104v3]]
| 0x864CFB
| 0xDF3261
| 0xC3267D
|-
| CRC-30
| [[CDMA]]
| 0x2030B9C7
| 0x38E74301
| 0x30185CE3
|-
| Adler-32
| [[Zlib]]
| colspan="3" align="center" | ''[[Adler-32]]에 언급''
|-
<!--
|CRC-32-[[IEEE 802.3]] || <math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7}</math><br /><math>+ x^{5} + x^{4} + x^{2} + x + 1</math>
|-
|CRC-32C (Castagnoli)|| <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18}</math><br /><math>+ x^{14} + x^{13} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + 1</math>
|-
--->
| CRC-32
| [[HDLC]], [[ANSI]] X3.66, ITU-T [[V.42]], [[이더넷]], [[Serial ATA]], [[MPEG-2]], [[PKZIP]], [[Gzip]], [[Bzip2]], [[PNG]],<ref>{{웹 인용| last = Boutell | first = Thomas | last2 = Randers-Pehrson | first2 = Glenn | coauthors = ''et al.'' | date = 14 July 1998 | title = PNG (Portable Network Graphics) Specification, Version 1.2 | url = http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html |publisher=Libpng.org | accessdate = 3 February 2011 }}</ref> many others
| 0x04C11DB7
| 0xEDB88320
| 0x82608EDB<ref name="koop02">{{저널 인용|  last = Koopman | first = Philip |  title = 32-Bit Cyclic Redundancy Codes for Internet Applications |  journal = The International Conference on Dependable Systems and Networks |  year = 2002 | month = July <!-- date from http://www.ece.cmu.edu/~koopman/pubs.html --> |  url = http://www.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf |  accessdate = 14 January 2011 |  pages = 459–468 |  doi = 10.1109/DSN.2002.1028931 |  isbn = 0-7695-1597-5 }}</ref>
|-
| CRC-32C (Castagnoli)
| [[iSCSI]], [[SCTP]], [[G.hn]] payload, [[SSE4#SSE4.2|SSE4.2]], [[Btrfs]], [[ext4]]
| 0x1EDC6F41
| 0x82F63B78
| 0x8F6E37A0<ref name="koop02" />
|-
| CRC-32K (Koopman)
| 
| 0x741B8CD7
| 0xEB31D82E
| 0xBA0DC66B<ref name="koop02" />
|-
| CRC-32Q
| aviation; [[AIXM]]<ref name="aixm-primer">{{서적 인용|title=AIXM Primer|url=http://www.eurocontrol.int/sites/default/files/content/documents/information-management/20060320-aixm-primer.pdf|version=4.5|publisher=[[European Organisation for the Safety of Air Navigation]]|date=20 March 2006|accessdate=4 July 2012|보존url=https://web.archive.org/web/20131031175623/http://www.eurocontrol.int/sites/default/files/content/documents/information-management/20060320-aixm-primer.pdf|보존날짜=2013년 10월 31일|url-status=dead}}</ref>
| 0x814141AB
| 0xD5828281
| 0xC0A0A0D5
|-
<!---
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math> (ISO 3309)
|-
|CRC-64-[[ECMA 인터내셔널|ECMA]]-182 || <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45}</math><br /><math> + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} + x^{31} + x^{29} + x^{27}</math><br /><math>+ x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9</math><br /><math> + x^7 + x^4 + x + 1</math><br />([http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] p.63)
|-
|CRC-128 || (IEEE? / ITU?)
|-
--->
| CRC-40-[[GSM]]
| GSM control channel<ref name="gammel">{{서적 인용|last=Gammel|first=Berndt M.|date=31 October 2005|title=Matpack documentation: Crypto - Codes <!-- |unusedurl=http://users.physik.tu-muenchen.de/gammel/matpack/html/LibDoc/Crypto/MpCRC.html long-time home, gone--> |url=http://www.matpack.de/index.html#DOWNLOAD |publisher=Matpack.de |accessdate=21 April 2013}} (Note: MpCRC.html is included with the Matpack compressed software source code, under /html/LibDoc/Crypto)</ref><ref name="geremia">{{저널 인용|last=Geremia|first=Patrick|year=1999|month=April|title=Cyclic redundancy check computation: an implementation using the TMS320C54x|issue=SPRA530|publisher=Texas Instruments|page=5|url=http://www.ti.com/lit/an/spra530/spra530.pdf|accessdate=4 July 2012}}</ref>
| 0x0004820009
| 0x9000412000
| 0x8002410004
|-
| CRC-64-ISO
| [[High-Level Data Link Control|HDLC]], [[Swiss-Prot]]/[[TrEMBL]]; considered weak for hashing<ref name="jones-improved64">{{저널 인용|last=Jones|first=David T.|title=An Improved 64-bit Cyclic Redundancy Check for Protein Sequences|publisher=University College London|url=http://www.cs.ucl.ac.uk/staff/d.jones/crcnote.pdf|accessdate=15 December 2009}}<!-- date of PDF=1 Dec 2009; date of referenced C file=2 Mar 2006; date in C file comments=28 Sep 2002 --></ref>
| 0x000000000000001B
| 0xD800000000000000
| 0x800000000000000D
|-
| CRC-64-[[Ecma International|ECMA]]-182
| [http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182], [[XZ Utils]]
| 0x42F0E1EBA9EA3693
| 0xC96C5795D7870F42
| 0xA17870F5D4F51B49
|}

<!---
{| class="wikitable"
! 이름 !! 다항식
|-
|CRC-1 || <math>x + 1</math> (하드웨어에서 사용되며 [[패리티 비트]]로 알려져 있음)
|-
|CRC-5 || <math>x^{5} + x^{2} + 1</math> ([[USB]] 토큰 패킷에서 사용됨)
|-
|CRC-7 || <math>x^{7} + x^{3} + 1</math> (몇몇 통신 체계에서 사용됨)
|-
|CRC-8-Fletcher || A := A + D[i], B := B + A
|-
|CRC-8 || <math>x^{8} + x^{2} + x + 1</math>
|-
|CRC-12 || <math>x^{12} + x^{11} + x^3 + x^2 + x + 1</math> (통신 체계에서 사용됨)
|-
|CRC-16-Fletcher || (CRC-16 Adler의 기반)
|-
|CRC-16-Adler_A || [''A'' = 1 + ''D''<sub>1</sub> + ''D''<sub>2</sub> + ... + ''D''<sub>''n''</sub> (mod 65521)]
|-
|CRC-16-Adler_B || [''B'' = ''n''×''D''<sub>1</sub> + (''n''-1)×''D''<sub>2</sub> + (''n''-2)×''D''<sub>3</sub> + ... + ''D''<sub>''n''</sub> + ''n'' (mod 65521)]
|-
|CRC-16-CCITT || <math>x^{16} + x^{12} + x^{5} + 1</math>
|-
|CRC-16-[[IBM]] || <math>x^{16} + x^{15} + x^{2} + 1</math>
|-
|CRC-32-Adler || [''Adler-32''(''D'') = ''B'' × 65536 + ''A'']
|-
|CRC-32-[[IEEE 802.3]] || <math>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7}</math><br /><math>+ x^{5} + x^{4} + x^{2} + x + 1</math>
|-
|CRC-32C (Castagnoli)|| <math>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18}</math><br /><math>+ x^{14} + x^{13} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + 1</math>
|-
|CRC-64-ISO || <math>x^{64} + x^4 + x^3 + x + 1</math> (ISO 3309)
|-
|CRC-64-[[ECMA 인터내셔널|ECMA]]-182 || <math>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45}</math><br /><math> + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} + x^{32} + x^{31} + x^{29} + x^{27}</math><br /><math>+ x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9</math><br /><math> + x^7 + x^4 + x + 1</math><br />([http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] p.63)
|-
|CRC-128 || (IEEE? / ITU?)
|-
|}
--->

== CRC 계산 예 ==

''n''-bit 이진 CRC 계산을 위해서는 [[다항식]](polynomial) (''n''+1)-비트 패턴의 제수(divisor)를 만든다.
{| class="wikitable"
! 다항식 !! 제수 !! 비트수 !! CRC
|-
| <math>x^3 + x + 1</math> || <math>1011</math> || 4비트 || 3비트
|}

다항식의 각 자릿수 별로 표현하면:

<math>1 x^3 + 0 x^2 + 1 x + 1  => 1011</math>

메시지 데이터는:

<pre>
11010011101100
</pre>

3비트 CRC를 계산하기 첫 번째로 나누면 :

<pre>
          1
     ---------------------
1011 ) 11010011101100 000    <--- 오른쪽으로 3비트 후부터
       1011                  <--- 제수(divisor) 4비트 <= x³+x+1
------------------
       01100011101100 000    <--- 결과
</pre>

나누는 과정에서 각 비트별로 [[XOR]]로 행한다. 일반적인 나누기에서의 뺄셈과는 다르다. 연산결과 첫 번째 비트가 0으로 소거되도록 몫의 비트를 정한다. 메시지 첫 번째 비트가 1이므로 몫의 1로 하여 XOR-나누기를 한다. 이렇게 되면 첫 번째 비트가 0으로 된다.

 1101 XOR 1011 => 0 110

이제 전체를 계산하며:

<pre>
   11110001111 100   <--- 몫은 별로 의미가 없는 중간 과정이다.
-------------------
11010011101100 000   <--- 오른쪽으로 3비트 후부터
1011                 <--- 제수
01100011101100 000   <--- 결과
 1011                <--- 제수 ...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000
    0000             <--- 0인 경우 위의 계산결과가 바뀌지 않는다. 그대로 넘겨도 된다.
00000001101100 000
     0000
00000001101100 000
      0000
00000001101100 000
       1011
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000
           101 1
00000000000000 100   <--- 왼쪽이 모두 0이면 여기서 끝내도 된다. 뒤에 오는 것은 0은 계산에 영향이 없다.
            00 00
00000000000000 100
             0 000
-----------------
00000000000000 100 <--- 나머지(remainder) 3비트, 앞에는 모두 0이 되고 뒤에 3비트가 최종 결론이다.
</pre>

왼쪽의 나머지가 모두 0이 되도록 계속 나눈다. 최대로 입력 비트수 만큼 나누면 모두 0이 된다.

이제 위의 계산결과로부터 검증을 하면 입력 메시지 다음에 CRC 결과를 붙여 나누면 나머지가 0이 된다.:

<pre>
11010011101100 100 <--- 입력과 CRC 체크값을 붙이고
1011               <--- 나누고
01100011101100 100 <--- 결과
 1011              <--- 나누고 ...
00111011101100 100

......

00000000001110 100
          1011
00000000000101 100
           101 1
------------------
                 0 <--- 나머지
</pre>

== 하드웨어 구현 ==

구현은 하드웨어적 방법과 소프트웨어적 방법이 있다. 보통 CRC가 통신시스템등에 많이 사용되는데, 하드웨어적인 접근방법도 많이 사용한다.

위의 예:
 <math>x^3 + x + 1</math>

는 다음과 같은 구성으로 표현할 수 있다.

[[파일:Crc3.jpg|프레임|가운데|CRC 직렬 논리회로, <math>x^3 + x + 1</math>.]]

직렬 비트데이터가 들어오면 매 비트마다 논리회로에 의해 계산된다.

=== [[논리 회로]]에 의한 하드웨어 구현 ===
D-FF을 사용하여 [[논리 회로]]를 그리면 다음과 같다:
[[파일:CRC3 Circuit.png|섬네일|가운데|600px|다항식 <math>x^3 + x + 1</math>에 대해 CRC 계산 논리회로, RESET은 회로에서 생략함.]]

입력은 한클럭 동안 하나의 비트를 입력하고, 출력은 O<sub>2</sub> O<sub>1</sub> O<sub>0</sub>로 3비트이다. 직렬입력에 대해 매 클럭마다 CRC값이 출력된다.

디지털통신에서 물리계층으로 갈수록 직렬비트의 데이터 형태로 입력되어 처리되는 경향이 있다. 따라서 보통 위와같은 회로를 사용하여 CRC을 계산할 수 있다.

=== 병렬비트 입력 하드웨어 계산 예 ===

직렬이 아니고 병렬로 입력되어 여러비트를 한클럭에 계산할 필요가 있다면, 위의 예에서의 회로를 층구조로 쌓아 만들면 된다.

예를 들어 4비트를 동시에 계산하는 하드웨어를 구성하면 다음과 같은 예로 만들수 있다.
4비트 입력 b3:b2:b1:b0를 한클럭에 계산하려면 다음과 같은 회로로 구성할 수 있다:

[[파일:CRC ParInput-ProcCircuit.png|섬네일|가운데|600px|병렬 4비트 입력을 한클럭에 CRC 계산하는 회로. 다항식은 <math>x^3 + x + 1</math>.]]

입력 b[3:0]에 대해 계산된 CRC출력은 C[2:0]이다. 여기서 b0가 가장먼저 입력되고, 다음이 b1의 순으로 입력되는 경우이다.

고속 클럭에서 동작하는 회로에서는 XOR가 여러단 전파하면서 생기는 시간지연은 상황에 따라 고려하여 설계하여야 한다.

위에서 예로 들은 메시지 입력:
  1101 0011 1011 0000

에 대해 계산을 하면 다음과 같이 4비트 단위로 나눌 수 있다.

여기서 회로의 입력순서는
 1101 = b0 b1 b2 b3 = b[0:3]
으로 표시 하였다.

* 1 clock - 입력 1101 = b0 b1 b2 b3 = b[0:3]
<PRE>
000       <-- 처음 RESET에 의해 000으로 플립플롭을 초기화
1101 000  <-- 입력 1101이 동시에 들어 온다.
----
1101 000  <-- 우선 이전의 CRC와 현재 입력을 XOR 한다. 초기에 000으로 설정되면 입력이 변하지 않는다.
1011      <-- 첫 번째 XOR 실행
----
0110 000
 101 1
----
 011 100
  10 11
----
  01 010
   1 011
----
   0 001   <-- 첫 번째 CRC 결과 C[2:0] = 001
</PRE>

* 2 clock - 입력 0011 = b0 b1 b2 b3
<PRE>
001        <-- 첫 번째 클럭에 의해 계산된 001이 반영된다.
0011 000   <-- 입력
----
0001 000   <-- 우선 이전의 CRC와 현재 입력을 XOR 한다.
0000
----
 001 000
 000 0
----
 001 000
   1 011
----
0000 011   <-- 두 번째 CRC 결과 C[2:0] = 011
</PRE>

* 3 clock - 입력 1011 = b0 b1 b2 b3
<PRE>
011
1011 000
1011
----
0110 000
 101 1
----
  11 100
  10 11
----
   1 010
   1 011
----
   0 001   <-- 세 번째 CRC 결과 C[2:0] = 001
</PRE>

* 4 clock - 입력 0000 = b0 b1 b2 b3
<PRE>
001
0000 000
0000
----
0010 000
  10 11
----
  00 110  <-- 네 번째 CRC 결과 C[2:0] = 110
</PRE>

최종 CRC 결과 C[2:0] = 110로 4클럭으로 계산 할 수 있다.

== 소프트웨어 구현 ==

보통 CRC을 적용할 때 바이트(Octet) 단위로 구현한다. 많은 통신시스템에서 OCTET 단위가 기본이기 때문이다. 비트단위로 계산해야 하는 경우 속도등의 문제로 오히려 CRC 테이블 기법을 많이 사용한다.

OCT단위로 입력되는 데이터를 계산해야 하는데, 루프를 실행해야 하므로 속도등에 문제가 발생할 수 있다. 특히 CRC의 비트수가 많을 수록 더욱 문제가 된다.

위의 예를 기반으로 소프트웨어 접근법을 위한 코드를 작성 하면:
# CRC 테이블을 만들어 변수화 한다.
# 데이터가 들어오면 OCTET 단위로 테이블 탐색을 통해 CRC을 결정 한다.

=== CRC 테이블을 위한 코드 예 ===

우선 모든 OCT 단위로 입력을 미리 계산한다.

<syntaxhighlight lang="cpp">

//#define CRC_SHIFT_5

static unsigned char crctable[256];

/// CRC 테이블 만들기 /////////////////////////////

//   Generate a table for a byte-wise 3-bit CRC calculation on the polynomial:
//   x^3 + x + 1

void make_crc_table( void )
{
    int cnt, bcnt;
    unsigned short poly, c;

    // terms of polynomial defining this crc (except x^3):
    static const char p[] = {0,1};

    // make exclusive-or pattern from polynomial
    poly = 0;
    for ( cnt = 0; cnt < sizeof(p)/sizeof(p[0]); cnt++ ) {
        poly |= 1 << p[cnt];
    }
    poly <<= 5;

    for ( cnt = 0; cnt < 256; cnt++ ) {
        c = cnt;
        for ( bcnt = 0; bcnt < 8; bcnt++ ) {
            c = ( c & 0x80 ) ? poly ^ ( c << 1 ) : ( c << 1 );
        }
       #ifdef CRC_SHIFT_5
	crctable[cnt] = (unsigned char) (c>>5) & 0x07;
       #else
        crctable[cnt] = (unsigned char) (c & 0xE0);
       #endif
    }
}

int main(int argc, char* argv[])
{
    int cnt;
    unsigned char crc;

    make_crc_table();

    FILE *fout;

    if ( (fout = fopen("crc3table.h", "wt")) == NULL)
       return -1;

    fprintf(fout,
      "#ifndef _CRC3TABLE_H\n"
      "#define _CRC3TABLE_H\n"
      "\nextern const unsigned char crctable[];\n"
    );

   #ifdef CRC_SHIFT_5
    fprintf(fout, "\n#define CRC_SHIFT_5\n");
   #endif

    fprintf(fout, "\n#endif\n");
    fclose(fout);

    if ( (fout = fopen("crc3table.c", "wt")) == NULL)
       return -1;

    fprintf(fout, "\nconst unsigned char crctable[256] = {\n   ");
    for ( cnt = 0; cnt < 256; cnt++ ) {
        if (cnt == 255) {
            fprintf(fout, "0x%02X\n", crctable[cnt] );
            break;
        } else
            fprintf(fout,"0x%02X,", crctable[cnt] );
            if ( (cnt % 8) == 7)
                fprintf(fout,"\n   ");
            else
                fprintf(fout," ");
    }
    fprintf(fout,"};\n");
    fclose(fout);

    return 0;
}
</syntaxhighlight>

실행결과 :
<pre>
const unsigned char crctable[256] = {
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60
};
</pre>

변수 crctable[]이 바이트 단위로 모두 계산한다. 이것을 프로그램 파일로 만들어 CRC 계산하는데 사용한다.

이 파일이름을 crc3table.c라고 하면 다음에 이것을 사용하여 코딩한다.

=== CRC 테이블을 탐색을 통해 CRC 결정 ===

<syntaxhighlight lang="cpp">
// File : crc3.h //////////////////////////////////////////
#ifndef _CRC3_H
#define _CRC3_H

#include "crc3table.h"

#define CRC3_INIT_VALUE   0x0000

unsigned char crc3_CalcChecksum(const unsigned char icrc, const void *data, int length );
#endif

// File : crc3.c //////////////////////////////////////////
//
#include "crc3.h"

/// CRC 테이블 사용하기 //////////////
#include "crc3table.c"  // 위의 예에서 미리계산한 CRC 테이블 코드를 사용한다.

unsigned char crc3_CalcChecksum(const unsigned char icrc, const void *data, int length )
{
    unsigned char crc;
    const unsigned char *buf = (const unsigned char *) data;

    crc = icrc;
    while (length--) {
       #ifdef CRC_SHIFT_5
        crc = crctable[(crc<<5) ^ *buf++];
       #else
        crc = crctable[crc ^ *buf++];
       #endif
    }
    return crc;
}

// File : testcrc3main.c //////////////////////////////////////////
//
#include <stdio.h>
#include "crc3.h"

int main(int argc, char* argv[])
{
   int cnt;
   unsigned char crc;

    unsigned char data[8] = { 0xD3, 0xB0 };
   #define SZ_MSGDATA 2

    crc = crc3_CalcChecksum(CRC3_INIT_VALUE, (void *)data, SZ_MSGDATA);
    printf("Input Data : ");
    for (cnt = 0;cnt < SZ_MSGDATA;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif

    int sz = SZ_MSGDATA;
    data[sz++] = 0xCB;
    data[sz++] = 0x0D;
    crc = crc3_CalcChecksum(crc, &data[SZ_MSGDATA], sz-SZ_MSGDATA);
    printf("Input Data : ");
    for (cnt = 0;cnt < sz;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif

    crc = crc3_CalcChecksum(CRC3_INIT_VALUE, (void *)data, sz);
    printf("다시 계산 : ");
    for (cnt = 0;cnt < sz;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif
    return 0;
}
</syntaxhighlight>

실행결과:
 Input Data : 0xD3 0xB0  : CRC = 0xC0 [6]
 Input Data : 0xD3 0xB0 0xCB 0x0D  : CRC = 0x20 [1]
 다시 계산 : 0xD3 0xB0 0xCB 0x0D  : CRC = 0x20 [1]

2바이트의 3비트 CRC는 6으로 결정되었다.

== 각주 ==
<references />

== 같이 보기 ==
* [[오류 정정 부호]]
* [[Adler-32]]

== 외부 링크 ==
* [https://web.archive.org/web/20051204020946/http://www.ross.net/crc/ ''The CRC Pitstop'']
* [https://web.archive.org/web/20060927004051/http://www.repairfaq.org/filipg/LINK/F_crc_v3.html ''A Painless Guide to CRC Error Detection Algorithms'']
* [https://web.archive.org/web/20050408104838/http://www.4d.com/docs/CMU/CMU79909.HTM ''Understanding Cyclic Redundancy Check'']
* [https://web.archive.org/web/20060702231245/http://serversniff.net/hash.php Serversniff.net] 널리 쓰이는 CRC들(CRC-8/16/32/64)을 계산하는 도구
* Online [http://www.zorc.breitbandkatze.de/crc.html CRC calculator]
* Online [http://www.easics.com/webtools/crctool CRC Tool: Generator of synthesizable CRC functions] {{웹아카이브|url=https://web.archive.org/web/20051125113717/http://www.easics.com/webtools/crctool}}

[[분류:체크섬 알고리즘]]
[[분류:통신공학]]
[[분류:통신]]
[[분류:디지털 전자공학]]
[[분류:유한체]]