컴퓨터 네트워크 -Cyclic Redundancy Check CRC 자료실 등록

컴퓨터 네트워크 -Cyclic Redundancy Check CRC 자료실 등록

파일.zip

컴퓨터 네트워크 -Cyclic Redundancy Check CRC 자료실

컴퓨터 네트워크 -Cyclic Redundancy Check [CRC]


Cyclic Redundancy Check (CRC)

1. CRC

1.1 What is the error?
트랜지스터를 기반으로 하는 컴퓨터는 모든 데이터 처리를 2진법에 기초한다. high-low voltage동작을 컴퓨터 프로세서는 0과 1로 표현하는 것이다. 우리가 컴퓨터로 사용하는 문서, 음악, 영화 등 모든 데이터는 0과 1로 이루어진 binary 덩어리이다. 마치 영화 ‘매트릭스’의 도입화면에서 나타나는 녹색 줄의 0과1의 무수한 코드처럼 말이다. 그러므로 컴퓨터간의 데이터 전송 시에도 0과 1의 조합이 전송되는 것이다. 문제는 이런 데이터의 이동에 있어서 방해요인이 있다는 것이다. 비록 미미한 정도지만 전송선의 저항이 있을 수도 있고, 혹은 네트워크 내의 오류가 있을 수도 있고, 주변 통신기기의 강력한 전파로 인해 전송에 장애가 올 수도 있는 것이다. 이런 약간의 방해요인으로 0과 1의 조합에 균열이 가면 데이터는 엉망이 되고 만다. 이렇게 sender가 의도하지 않은 전송 중에 일어나는 error를 receiver쪽에서는 전혀 알 수 없으므로 이것을 detecting하고 더 나아가 correcting하기 위한 기술들이 필요하다.

1.2 What is the CRC?
Network는 한 장치에서 다른 장치로 정확하게 데이터를 전송할 수 있어야 한다. 한 장치에서 수신한 데이터가 다른 장치 송신된 데이터와 동일하다고 확신할 수 없는 network는 쓸모가 없다. 그러나 sender에서 receiver로 전송되는 데이터는 전송 중에 변경될 가능성을 항상 가지고 있다. 신뢰성 있는 시스템은 이러한 errors를 Detecting하고 Correcting할 수 있는 기법을 포함하고 있어야 한다.
순환중복검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다. 데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것임을 알 수 있다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.

1.3 Fundamental notion of CRC
CRC는 가환환(commutative ring)의 나눗셈에 기반을 둔다. 여기서 쓰이는 ring은 modulo 2 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 bit의 계수를 갖는 다항식의 집합이고, 이 다항식들 간의 사칙연산은 다시 계수들을 가장 아래 bit만 따도록 정의하여 한 bit 계수의 다항식으로 표현하도록 정의된다. 예를 들면:



위 식에서 2는 이진수로 이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자릿수는 버린다. 다음은 곱셈의 예이다:



더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, 을 로 나눈다고 해 보자.



으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.
모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번 자리가 1, 1번 자리가 0, 2번 자리가 1이므로, 다항식 에 해당한다고 볼 수 있다. 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 bitString[i] = 1
shiftRegister := (shiftRegister left shift 1) xor polynomial
else
shiftRegister := shiftRegister left shift 1
}
return shiftRegister
}

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

위의 구현은 다음과 같은 두 가지 방법으로 고칠 수 있으며, 따라서 둘 중 하나를 적용하거나 둘 다 적용할 경우 CRC 값을 계산하는 네 가지 동등한 방법이 존재한다:

1. shiftRegister를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트 한다. 이 경우 polynomial의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
2. shiftRegister의 한 비트와 bitString의 한 비트를 xor하는 대신에, shiftRegister와 bitString에서 polynomial에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결


자료출처 : http://www.ALLReport.co.kr/search/Detail.asp?pk=11041412&sid=sanghyun7776&key=



[문서정보]

문서분량 : 14 Page
파일종류 : HWP 파일
자료제목 : 컴퓨터 네트워크 -Cyclic Redundancy Check CRC 자료실
파일이름 : 컴퓨터 네트워크 -Cyclic Redundancy Check [CRC].hwp
키워드 : 컴퓨터,네트워크,Cyclic,Redundancy,Check,CRC,자료실
자료No(pk) : 11041412