통신을 할 때, 데이터가 수신이 완전히 이루어 졌는가? 에러는 없는가? 는 중요한 요소이다. 이것을 하는 방법은 다양하게 개발되었다.
- Parity bit : UART - 한비트의 데이터로 1의 갯수가 짝수인가 홀수인가를 나타낸다.
- Check-sum : CPU 실행 파일의 포맷 - 모든 데이터를 더하여 보수를 취하면 된다.
- CRC : 가장 안전하게 체크할 수 있지만 복잡하다. 다양한 비트수가 있다.
순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.
데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.
CRC는 가환환(commutative ring)의 나눗셈에 기반한다. 여기서 쓰이는 환은 법 2 (modulo 2) 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 비트의 계수를 갖는 다항식의 집합이고, 이 다항식들간의 사칙연산은 다시 계수들을 가장 아래 비트만 따도록 정의하여 한 비트 계수의 다항식으로 표현하도록 정의된다. 예를 들면:
- (x3 + x) + (x + 1) = x3 + 2x + 1 = x3 + 1
위 식에서 2는 이진수로 10이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자리수는 버린다. 다음은 곱셈의 예이다:
- (x2 + x)(x + 1) = x3 + 2x2 + x = x3 + x
더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, x3 + x2 + x 를 x + 1 로 나눈다고 해 보자.
- x3 + x2 + x = (x + 1)(x2 + 1) − 1 = (x + 1)(x2 + 1) + 1.
으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 x2 + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.
모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번자리가 1, 1번자리가 0, 2번자리가 1이므로, 다항식 x2 + 1에 해당한다고 볼 수 있다. CRC 값은, 정해진 특정 다항식으로 데이터 스트링으로 주어진 다항식을 나누어 그 나머지를 나타내는 특정 길이의 비트 스트링이 된다. 이 나머지를 구하는 간단하고 빠른 알고리즘은 잘 알려져 있다. CRC는 종종 체크섬(checksum)으로 불리는데, 엄밀히 말하면 나눗셈을 통해 얻어지는 CRC 값에는 옳지 않은 이름이다.
댓글