CRC-16 편집하기

'''CRC-16'''은 Cyclic Redundancy Check (CRC) 방식중의 하나이며 CRC 알고리즘 계산을 추진할 때 CRC16 다항식 (Polynomial) 을 사용한다. CRC는 네트워크 데이터블록 또는 파일 등 데이터에 근거하여 짧고 간단하며 자리수가 고정 된 검증코드를 발생시키는 채널코딩기술 (Channel Coding Techniques) 이며 주로 데이터 전송 또는 저장 후에 발생할 수 있는 오류 등을 감지 또는 검증하는데 사용된다. CRC는 1961년에 미국의 정보와 컴퓨터과학 전문가 [[웨슬리 피터슨]](W. Wesley Peterson)이 발명하였다.

==개요==
CRC-16은 Cyclic Redundancy Check (CRC) 방식중에 CRC16 다항식을 적용하여 검증코드 (체크섬;Checksum) 를 취득하고 이를 통신에 적용하는 채널코딩 기술이다.

적용시 송신자측은 전송하고자 하는 메세지에 산출 된 체크섬을 더하여 전송하고 수신자측은 체크섬 산출 시 사용하였던 다항식을 그대로 적용하여 수신한 메세지에 나누기를 적용하여 산출 된 값이 Zero인지를 판단한다. Zero 이면 데이터 송수신이 정확히 진행되었고 아닐 경우 송수신 오류가 발생하였다고 판단한다.

CRC검증작업에서 실수(검증작업에서 오류를 발견못하는) 할 확률은 1/65536이다. 

CRC-16 다항식은 ANSI표준을 적용할 때 x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup>+1 대응수자 0x18005 이고 CCITT 표준을 적용할 때 x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup>+1 대응수자는 0x11021 이다.

CRC-16 산하에는 적용하는 다항식에 따라 CRC-16 알고리즘군이 구성되어 있으며 넓은 영역에서 사용된다. 구체적으로 아래시트를 참조할 수 있다.<ref>"[https://en.wikipedia.org/wiki/Cyclic_redundancy_check Cyclic redundancy check]", ''Wikipedia''</ref><ref>하늘 가득 비, 〈[https://blog.naver.com/tatara4/221352897546 CRC란 무엇인가?]〉, 《네이버 블로그》, 2018-09-05</ref>
[[파일:CRC16 Family.png|썸네일|850픽셀|가운데|CRC16 Family]]

==CRC 원리==
▷ 다항식과 바이너리 코드

다항식과 바이너리코드사이에는 직접적인 대응관계가 존재한다. X의 최고지수가 바이너리의 최고위와 대응되며 아래 각 항들이 일일이 각 제곱과 대응된다. 지수가 있을 경우는 1로 표시하고 없는 경우에는 0으로 표기한다. X의 최고지수가 R일 경우 R+1 비트 바이너리 코드로 전환할 수 있다. 예를 들면 다항식 G(x)=x4 + x3 + x + 1 은 바이너리 코드 11011로 전환할 수 있다.

▷ 다항식

송수신 양측이 약정하여 메세지 데이터 처리에 사용하는 바이너리 데이터이며 데이터 전송 전반과정에서 불변한다. 다항식은 용도에 따라 상당수 분야에서 과학가들이 이미 정해놓았다.

▷ CRC원리

전송하고자 하는 어떤 데이터에 CRC 알고리즘을 적용하여 k 비트 바이너리 서열이 형성되고 형성된 서열은 다항식 (Pplynomial) 이라 불리우는 바이너리 서열에 나뉜다. 나뉜 뒤, r 비트의 나머지를 체크섬 (Checksum) 이라하며 송신측은 (k + r) 비트의 신규 바이너리 서열을 만들어 전송한다. 

수신측은 접수 한 바이너리 서열 (서열에는 체크섬이 포함되어 있다) 을 송신측에서 사용하였던 다항식으로 나누기를 추진한다. 나눈 결과가 zero 이면 송신은 정확히 진행되었고 아닐 경우 송신오류가 발생하였다고 판단한다.   

여기서 나누기 계산은 산술계산의 나누기가 아니고 Logic 계산 XOR를 가르킨다.

==CRC 검증코드 수동계산 사례==

▶ 작업목표: 
다항식 G(x)=x4 + x3 + 1 일때 바이너리 코드 10110011의 CRC 검증코드를 산출한다. 

▶ 계산내역:

1)다항식의 바이너리 서열 

G(x)=x4 + x3 + 1, 대응되는 바이너리 서열 11001 (설명: x4 는 5비트 바이너리 서열의 최고위치를 가리키고 Logic 값은 1을 나타내며 x3 은 5비트 서열의 그 다음 위치, Logic 값은 1을 나타낸다. x2 는 없기에 3번째 위치를 가리키고 Logic 값은 0을 나타낸다. 이런 식으로 마지막까지 처리하면 위의 바이너리 서열을 얻을 수 있다.)

2)검증코드는 4자리수를 맞추어야 하므로 바이너리 코드 10110011에 0 4개를 첨부하여 신규 서열 1011 0011 0000 을 얻는다.

3)검증코드 산출계산

* 메시지 = 10110011
* 다항식 = 11001
[[파일:caculate.png|섬네일|850픽셀|가운데| CRC 수동계산 사례]]

4)신규 취득 바이너리 서열 

메시지 1011001를 대상으로 CRC 알고리즘 계산 추진 후 신규 서열 1011 0011 0100 이 형성되었으며 이가 나중에 공식적으로 전송하는 발송메세지가 된다.<ref>步孤天,〈[https://www.cnblogs.com/bugutian/p/6221783.html CRC校验码原理、实例、手动计算]〉, 《博客园》</ref>

{{각주}}

==참고자료==
* lcy89815, 〈[https://wenku.baidu.com/view/d69c1351580216fc700afd8c.html crc16检验的多项式是怎么形成的，具体的怎么应用]〉, 《百度文库》, 2018-06-30
* realdani, 〈[https://realdani.blog.me/221494620914 CRC(Cyclic Redundancy Check) 간단 소개와 동작 이론]〉, 《네이버블로그》, 2019-03-22
* 하늘 가득 비, 〈[https://blog.naver.com/tatara4/221352897546 CRC란 무엇인가?]〉, 《네이버블로그》, 2018-09-05
* "[https://ww1.microchip.com/downloads/en/AppNotes/00730a.pdf CRC Generating and Checking]", ''microchip''
* 〈[https://zhidao.baidu.com/question/537597475.html?qbl=relate_question_0 CRC多项式对应的代码是怎么得来的]〉, 《百度知道》, 2017-05-27

==같이 보기==
* [[CRC-32]]

{{암호 알고리즘|검토 필요}}