[Network] Parity Bit, Checksum, CRC

오늘은 Parity Bit, Check-Sum, CRC에 대해서 Survey한 것을 정리해보고자 합니다.

다음 순서로 내용을 정리하고자 합니다.

*Parity bit

*Check-sum

*CRC (Cyclic Redundancy Check)

*Glossary & Reference

이미 많은 사람들이 책의 내용 혹은 강의 혹은 자신의 이해 정도를 작성해서 internet에 잘 정리해 놓은 것을 저 역시 참조한 것이며, 개인적 이해를 위해서 적어 놓은 겁니다.

이들 survey로 찾은 주제 용어들 parity bit, check-sum, CRC는

데이터는 전송 중에 변경될 수 있으며, 신뢰성 있는 통신을 위해 오류들은 검출 및 정정되어야 한다라는 목적으로부터 사람들이 생각하게 된 방법들 입니다.

이러한 오류를 수정하기 검출 및 정정하기 위해서 원래의 data에 추가로 data를 할당/추가하게 됩니다. 그것을 redundant bits or extra bits이라고 합니다.

여기서 설명하는 parity bit, check-sum code, CRC code는 오류를 검출하기 위해서 원래의 data에 추가되는 정보들 입니다.

물론 소개 되는 parity bit, check-sum, CRC는 오류 검출이며, 오류 검출 및 오류에 대한 수정까지 가능한 hamming code도 있지만, 여기서 다루려는 범주에서 벗어납니다.

하지만 이러한 전체적인 오류 검출 및 정정에서 대해서 다음 reference와 Wikipedia에서 소개 되고 있으니, 그것을 참고 하시면 될 것 같습니다.

관련 내용 및 범주는 통신이론, 정보 이론, Shannon Theorem을 기초하고 있습니다.

Parity Bit 란?

http://ko.wikipedia.org/wiki/%ED%8C%A8%EB%A6%AC%ED%8B%B0_%EB%B9%84%ED%8A%B8

Wikipedia에서 한글로 작성 된 내용이며, 쉽게 잘 설명을 해 놓았네요.

Parity bit은 정보전달 과정에서 오류가 생겼는지를 검사하기 위해서 추가한 bit입니다.

정해진 bit stream에서 1bit을 추가하여 전송하게 되는데 방법에 따라서

종류는 크게 2가지가 있습니다. Even과 odd parity입니다.

*even parity : 전체 bits stream에서 1의 개수가 짝수가 되도록 parity bit를 정하며,

*odd parity : 전체 bits stream에서 1의 개수가 홀수가 되도록 parity bit을 정합니다.

이해를 돕기 위한 예를 wikipedia에서 소개된 예를 가지고

아래 4개의 7bits에 대해서 각각 even parity로 encoding/decoding을 해본다고 하지요.

000_0000,

101_0001,

110_1001,

111_1111

http://ko.wikipedia.org/wiki/%ED%8C%A8%EB%A6%AC%ED%8B%B0_%EB%B9%84%ED%8A%B8

*Encoding을 해보면,

Even parity를 사용하면,

000_0000 에서 1의 개수는 0이므로 짝수입니다. 그래서 parity bit으로 0을 추가합니다.

101_0001 에서 1의 개수는 3개이므로 홀수입니다 그래서 parity bit으로 1을 추가합니다.

110_1001 에서 1의 개수는 0이므로 짝수입니다. 그래서 parity bit으로 1을 추가합니다.

111_1111 에서 1의 개수는 7이므로 홀수입니다. 그래서 parity bit으로 0을 추가합니다.

*Decoding

Encoding했던 방법을 사용을 그대로 거꾸로 보면 됩니다.

0000_0000 에서 parity bit이 0이기 때문에 1의 개수가 짝수개인지를 확인합니다.

Even parity의 경우, parity bit을 포함해서 각각을 XOR operation을 해서 결과가 0이면 error가 없는 겄이고, 1이면 error가 있습니다.

0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 XOR 0 = 0

1 XOR 1 XOR 0 XOR 1 XOR 0 XOR 0 XOR 0 XOR 1 = 0

*문제점

Single bit 혹은 동시에 홀수개의 bits에 error가 발생할 경우는 error 검출이 되지만,

만약 한꺼번에 짝수개의 bit (2bit, 4bit, …)이 동시에 바뀌게 되는 error에 대해서는 검출하지 못합니다.

Parity bit은 Encoding/decoding이 가장 간단하다는 장점이 있지만, error의 검출 능력은 떨어진다는 단점이 있겠습니다.

2. Check-sum 이란 ?

앞의 parity bit의 오류 검출능력을 향상시키기 위해서 개발된 방법입니다.

Check-sum의 알고리즘을 간단히 설명하면, 다음과 같습니다.

송신측에서는 보내려는 data를 모두 더한 값이 SUM이라고 하면, -1을 곱한 -SUM값을 check-sum code을 계산해서 얻게 되고, 원래 data와 check-sum code를 전송하게 됩니다.

그러면 수신측에서 원래 data와 check-sum code인 –SUM을 모두 더한 결과가 0이 나오면 error가 없는 것이고, 0이 아니면 error가 있는 거에요.

물론 여기서 더한 값 SUM에서 carry값이 제거한 값이고,

-SUM에 대한 구현은 2의 보수(two’s complement)에 의해서 SUM을 -SUM으로 만듭니다.

예를 들어 보겠습니다. 아래 link의 있는 예에 대한 내용입니다.

http://ko.wikipedia.org/wiki/%EC%B2%B4%ED%81%AC%EC%84%AC

예를 들어 다음 4bytes의 전송할 data가 있다고 가정하겠습니다.

0x25, 0x62, 0x35, 0x52

* 송신측 Encoding

(1)앞의 모든 bytes를 더합니다.

0x25 + 0x62 + 0x35 + 0x52 = 0x118이 됩니다.

(2)Carry Nibble을 버려서 0x118에서 0x18이 됩니다.

(3) 0x18(=1_1000)의 2의 보수를 취해서 0xE8(=1110_1000) 이 됩니다.

2의 보수 계산 :

먼저 각 bit을 inverting 합니다.

0001_1000(=0x18)의 각 bit을 invert 하면,

1110_0111(=0xE8)

Inversion한 값에 +1 을 합니다.

1110_0111 + 1 = 1110_1000 (=0xEB)

(4) 따라서 원래 4개의 bytes와 check-sum 1개 byte 추가해서 모두 5개의 bytes를 보냅니다.

0x25, 0x62, 0x35, 0x52, 0xEB를 보냅니다.

*수신측 Decoding

(1) 원래 data byte와 check-sum을 모두 더하면 0x118 + 0xE8 = 0x200 입니다.

(2) 역시 carry nibble을 버리면, 0x00이 되고, 값이 0이기 때문에 오류가 없다는 의미가 됩니다.

*문제점.

다음 예를 들어서 이러한 경우는 어떻게 될까요 ?

( A, B, C, D, Check-Sum ) 인 값이 있는데,

오류로 인해서 값이 (A+1,B-1,C,D, Check-Sum) 이 된다고 하면,

수신쪽에서 모두 값을 더했을 때, 0가 되겠지요.. 이런 경우는 오류가 있음에도 검출하지 못합니다.

Parity bit가 비교해보면, encoding/decoding 계산이 조금 복잡해 졌지만, 오류검출 확률은 높아졌습니다. 하지만 아직까지도 검출확률을 더 높일 필요성이 요구됩니다.

3.CRC란 ?

(1)CRC (Cyclic Redundancy Check)는 위의 2가지 방법보다 높은 신뢰도를 확보하며, Error 검출에 대한 overhead가 적고, random error나 burst error를 포함한 error검출에도 용이하다고 합니다.

(2)또 다른 reference에서는 이렇게 쓰고 있습니다.

CRC is a technique for detecting data transmission errors based on generator polynomial.

(3)또 다른 reference (Wikipedia)에서의 CRC는

A cyclic redundancy check (CRC) is an error-detecting code designed to detect accidental changes to raw computer data, and is commonly used in digital networks and storage devices such as hard disk drives. Blocks of data entering these systems get a short check value attached, derived from the remainder of a polynomial division of their contents; on retrieval the calculation is repeated, and corrective action can be taken against presumed data corruption if the check values do not match.

CRCs are so called because the check (data verification) value is a redundancy (it adds zero information to the message) and the algorithm is based on cyclic codes. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.

As the check value has a fixed length, the function that generates it is occasionally used as a hash function.

The CRC was invented by W. Wesley Peterson in 1961; the 32-bit polynomial used in the CRC function of Ethernet and many other standards is the work of several researchers and was published in 1975.

사실 CRC-16이라는 것을 공부하려고 survey를 하다 보니, parity bit도 찾아보게 되고, check-sum도 찾아보게 되었습니다.

CRC라고 하는 것이 단순히 몇 시간만 투자해서 모두 이해할 수 있는 영역이 아니기에,

또한 내가 CRC를 전공한 사람이 아니고, 앞으로 관련해서 study를 깊게 할 분야가 아니어서,

오늘까지 찾아본 내용만을 정리하고자 합니다.

먼저 남에게 가장 간단하게 CRC 알고리즘을 설명하라고 하면, 아래 내용으로 설명하고자 할 것 같습니다. 사실 아래 내용도 남의 blog에 친절히 설명이 되어있고, 다른 설명들도 상당히 많은데, 개인적으로는 이렇게 이해 하는 것이 오랜 시간 개념을 기억할 수 있을 것 같더군요.

먼저 더 쉬운 이해를 돕기 위해 미리 이해해야 할 background가 있습니다.

Modulo-2(=mod 2) 덧셈(addition) 연산

Modulo-2(=mod 2) 뺄셈(subtraction) 연산

Modulo-2(=mod 2) 곱셈(multiplication) 연산

Modulo-2 란 ?

http://blog.bagesoft.com/858

*송신측 Encoding에서는

전송해야 할 P(X)가 N bits 있다고 가정하고,

송신/수신에서 사용할 약속된 G(X)가 K+1 bits으로 있다고 가정하면,

전송할 P(X)에 X^K곱해서, 약속된 G(x)로 나누게 되면, 몫으로 Q(x)가 생기고, 나머지 R(x)가 생기게 됩니다.

수식으로는 다음처럼 X^K *P(x) = G(x) * Q(x) +/- R(x) 가 됩니다.

그러면 P(x)와 R(x)를 붙여서 보내게 됩니다.

여기서 R(x)를 CRC Code라고 합니다.

*Decoding

받은 P(x)에 X^K를 곱하고, R(x)를 더해서, 약속된 G(x)로 나누게 되면, 전송 중에 P(X),R(X)가 특별히 error가 발생하지 않는다면, 0이 되게 됩니다.

수식적으로 표현하면, X^K *P(x) + R(x) = G(x) * Q(x) 이 되기 때문 입니다.

다음 예를 들어 보겠습니다.

*가정 (1) 원래 data (message 혹은 dataword라고도 합니다)가 1001 이 있습니다. 그렇다면, Message Polynomial P(X) = 1*X3 + 0*X2 + 0*X1 + 1*X0 가 됩니다. (2) 그리고 약속된 Divisor ( Generator라고 합니다)가 1011 입니다. 그렇다면, Generator Polynomial G(X) = 1*X3 + 0*X2 + 1*X1 +1*X0 이 약속된 divisor는 송신측과 수신측에서 미리 이 divisor를 사용할 것을 약속한 상태입니다. *송신측 Encoding (1) 먼저 dataword에 3bit의 000을 LSB쪽에 추가해서 넣습니다. 3bits인 이유는 divisor가 4bits이기 때문에 4-1=3bits인 것이고, 000을 오른쪽에 넣는 이유는 XK*P(X) 한 것이기 때문입니다. 즉 message polynomial P(X) = 1*X3 + 0*X2 + 0*X1 + 1*X0 였다면, 000을 오른쪽 LSB쪽에 넣으면, k=3이므로, X3 * P(X) = 1 * X6 + 0 * X5 + 0 * X4 + 1 * X3 가 되지요. (2) 그 다음부터 나눗셈을 진행합니다. 나눗셈 진행에서 mod-2 뺄셈과 mod-2 곱셈 연산을 사용하게 됩니다. 다시 한번 mod-2 뺄셈을 정리하면, 1-0=1, 1-1=0, 0-0=0, 0–1=1 마치 XOR logical operation하고 같습니다. division하는 중간 과정에서 계속 사용됩니다. 다시 한번 mod-2 곱셈을 정리하면, 1 * 0 = 0 0 * 1 = 0 1 * 1 = 1 마치 AND logical operation과 같습니다. Divisor와 quotient(몫)에서의 곱셈에서 사용됩니다. (3) 나눗셈을 정리하면, 3bit의 R(X)= 1*X2 + 1*X1 + 0*X0 를 얻게 됩니다. 즉 110의 code를 얻게 되는 거지요. (반듯이 3bits이어야 하지 더 클 수 없습니다. Divisor가 4bit이기 때문에) 110이 CRC Code가 되겠습니다. (4) 원래 code (=dataword) 와 remainder (=CRC Code or FCS )를 합친 codeword를 전송합니다. *수신측 decoding (1) 수산한 codeword = 1001110에 대해서 약속된 divisor로(1011)로 나눗셈을 하게 됩니다. (2) 아래 왼쪽 그림처럼 remainder = 0이게 되면, 수신된 codeword가 error가 아닌 것이고, 만약 오른쪽 그림처럼 remainder가 0이 아니게 되면, 수신된 codeword는 오류가 있는겁니다.

CRC의 종류

앞서 설명했던 송신/수신에서 약속해서 사용하는 divisor or generator polynomial에 따라서 다양한 CRC의 종류가 있으며, generator polynomial의 최고승의 숫자를 가지고 와서,

CRC- XX라고 합니다.

CRC-16과 비슷하게

CRC-CCITT가 있습니다. X¹⁶ + X¹⁵ + X² + 1 입니다.

CRC-CCITT도 상당히 많이 사용됩니다.

IBM 8-inch floppy disk에서 사용되었고, XMODEM에서도 transmission protocol로 사용되었습니다.

CRC-8은 ATM 기계에서 사용되고, CRC-16은 HDL에서 사용되는 application이라고 하네요.

CRC-32의 경우 LAN의 사용되는 standard라고 하네요.. TCP-IP의 7 layers에서 physical layer에 있는 건가요 ?

CRC 구현( implementation)

이러한 CRC 구현법에는 상당히 많은 방법이 있는 것으로 알고 있습니다.

제가 survey한 것으로는

앞에서 설명한 mod-2 나눗셈 연산에 관해서 shift 방법을 이용해서

Hardware로 구현하는 방법과 software로 구현하는 방법이 있습니다.

하지만 이렇게 하면 시간이 올래 걸리게 되어서, table을 사용하는 방법이 있는데요.

하지만 여기서는 table을 다루는 방법에 대해서는 나중에 시간이 되면 추가 update하도록 하고,

지금은 다루지 않을 예정입니다.

앞에서 예제로 사용한 내용을 다시 한번 구현해 보도록 하겠습니다. 먼저 위의 내용을 diagram으로 표현하면, 각 수행되는 과정에 대해서 다음과 같이 도식화 할 수 있겠죠.. 이것을 간단하게 표현할 수 있는데, 바로 Feedback을 사용하면 됩니다.

Hardware로 구현하는 방법.

사실 이 부분을 구현하기 위해서 애초의 이것저것을 찾으면서 오게 되었는데요…

참 어렵네요.. 여기까지 오기도 어려웠고, 지금도..

일단 Hardware를 구현은 LFSR (Linear Feedback Shift Register)를 이용하는 방법입니다.

http://ishaksuleiman.tripod.com/00000.pdf // Verilog code -> CRC Module crc3 (clk, clr, data_in, data_out); input clk, clr; input data_in; reg [2:0] data_out; always @(posedge clk) begin if (!clr) data_out=0; else data_out = { data_out[1], (data_out[2]^data_out[0]), (data_out[2]^data_in) }; end endmodule 구현하는 방법에 따라서 Serial architecture 혹은 Parallel architecture로 구현할 수도 있습니다. 위의 HDL code는 1 clock당 1bit 씩 처리하는 serial architecture방식이고, 1 clock당 여러 bits 예를 들어 1byte을 처리하는 parallel architecture방식도 있습니다. parallel architecture에 대한 coding 기본적으로 앞의 serial architecture는 여러 clock으로 동작을 시켜야 하기 때문에 고속동작에서는 사용할 수 없겠지요. 아래 reference에 parallel architecture관련해서 많이 검색해 보았는데, 잘 이해가 안되더군요.. 그러다 다음 reference 의 table을 보고 있자니 감이 오는구요. 들어올 입력을 미리 정해 놓고서, 정해진 clock 만큼 계산을 해주면 앞의 serial architecture를 돌려보면, 아래 표처럼 정리가 됩니다. 그래서 앞의 예였던 1001000 값을 넣으면, 1 clock 만에 110의 값을 얻을 수 있습니다. Serial architecutre와 비교해보면 알겠지만 많은 수의 XOR gate가 필요하겠네요. 세상에는 공짜가 없는 법이니, 빠른 속도를 얻는 만큼, area는 손해를 봅니다. 참고로, CRC-16에 대해서 serial 과 parallel에 대한 Verilog code 입니다. [9] http://ishaksuleiman.tripod.com/00000.pdf CRC-CITT Serial Architecture CRC-CITT Parallel Architecutre Parallel에서 왜 저렇게 XOR operation을 하는지를 Excel로 정리 해보았습니다.

Software 구현하는 방법

http://blog.naver.com/truemonpark?Redirect=Log&logNo=40014936647 the main portion of the algorithm can be expressed in psedocode as follows function crc (bit array bitString[ 1 .. len ], int polynomial) { shiftRegister := initial value // commonly all 0 bits or all 1 bits for I from 1 to len { if MSB (most significant bit) of shiftRegister XOR bitString [i] = 1 shiftRegister := (shftRegister left shift 1) XOR polynomial else shiftRegister := shiftRegister left shift 1 } Return shiftRegister } C / C++ version 추후 update 예정!! http://www.netrino.com/Embedded-Systems/How-To/CRC-Calculation-C-Code Perl version 추후 update 예정!!

Table을 사용해서

Glossary

FCS (Frame Check Sequence)

데이터 전송시, 송신측에서 CRC를 검사하기 위해서 각 data frame마다, 전송된 frame의 error를 검출할 수 있는 여분의 FCS를 포함해서 전송하도록 합니다.

Burst Error

Data의 부분이 2개 또는 그 이상의 bits가 변경되는 경우를 말합니다.

Codeword

We add redundant bits to each block to make the length n =k + r.

The resulting n-bit blocks are called codewords.

Dataword

In blocking coding, we divide our message into blocks, each of k bits, called datawords.

Divisor

나눗셈 계산에서 나누는 놈입니다.

10/2라고 하면, 2가 divisor가 됩니다.

divisor에서 or라는 접미사가 붙은 것이 능동적인 의미이지요 ?

Dividend

나눗셈 계산에서 나눠지는 피연산자 입니다.

10/2 라고 하면, 10이 dividend가 됩니다.

Polynomial

A polynomial is a value expressed in a particular algebraic form

Message polynomial

Generator polynomial or Polynomial generator

Remainder

나눗셈 계산에서의 나머지 입니다.

Single-Bit Error

데이터에서 한 개 bit만 변경된 경우를 말합니다.

Cyclic Code

Cyclic code are special linear block codes with one extra property.

In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword

Reference

[1] “Data Communications and Networking” Fourth Edition, Forouzan [2] 위의 책[1] 내용을 강의한 http://www.ssyeo.net/의 여상수 교수님의 강의 파일 “Chapter 10. 오류 발견과 교정 (Error Detection and Correction)”을 down 받을 수 있습니다. [3] “오류 검출 및 정정”에 대한 Wikipedia 한글 http://ko.wikipedia.org/wiki/%EC%98%A4%EB%A5%98_%EA%B2%80%EC%B6%9C_%EC%A0%95%EC%A0%95 [4] Aram Perez “Byte-wise CRC Calculations” IEEE Micro, June 1983, pp.40-50. [5] Ramabadran T.V., Gaitonde S.S., “A tutorial on CRC computations” IEEE Micro, [6] CRC Implementation Code in C http://www.netrino.com/Embedded-Systems/How-To/CRC-Calculation-C-Code [7] A Practical Parallel CRC Generation Method http://outputlogic.com/my-stuff/circuit-cellar-january-2010-crc.pdf [8] Parallel CRC Realization http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.387&rep=rep1&type=pdf [9] Algorithms for Cyclic Redundancy Code (CRC) Computation http://ishaksuleiman.tripod.com/00000.pdf