순환 중복 검사

위키백과 ― 우리 모두의 백과사전.

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

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

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

[편집] 개요

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

(x 2 + x) + (x + 1) = x 2 + 2 x + 1 = (x + 1) 2

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

(x 2 + x)(x + 1) = x 3 + 2 x 2 + x = x 3 + x

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

x 3 + x 2 + x = (x + 1)(x 2 + 1) - 1 = (x + 1)(x 2 + 1) + 1.

으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 x² + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.

모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번자리가 1, 1번자리가 0, 2번자리가 1이므로, 다항식 $x 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
}

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

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

shiftRegister를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트한다. 이 경우 polynomial의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
shiftRegister의 한 비트와 bitString의 한 비트를 xor하는 대신에, shiftRegister와 bitString에서 polynomial에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결과를 shiftRegister에 더한다. polynomial을 적당히 고치면 같은 나머지를 얻을 수 있다. 이 방법은 소프트웨어에서 구현하기는 힘들지만 하드웨어 구현에서는 종종 사용되며, CRC와 깊은 관련이 있는 선형 피드백 쉬프트 레지스터를 설명하는 데 자주 사용된다.

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

[편집] CRC 다항식들과 종류들

여기에 표시하지는 않았지만 더 많은 CRC 종류들이 있다.

적어도 다섯 종류의 서로 다른 CRC-16, CRC-32, CRC-64가 존재하고 널리 사용된다.
CRC-64, CRC-128, CRC-256도 존재하고 표준화되어 있지만 널리 사용되지는 않는다.

다음은 ITU-IEEE 문법으로 쓴 다양한 CRC 다항식들이다.

CRC-1	$x + 1$ (하드웨어에서 사용되며 패리티 비트로 알려져 있음)
CRC-5	$x 5 + x 2 + 1$ (USB 토큰 패킷에서 사용됨)
CRC-7	$x 7 + x 3 + 1$ (몇몇 통신 체계에서 사용됨)
CRC-8-Fletcher	A := A + D[i], B := B + A
CRC-8	$x 8 + x 2 + x + 1$
CRC-12	$x 12 + x 11 + x 3 + x 2 + x + 1$ (통신 체계에서 사용됨)
CRC-16-Fletcher	(CRC-16 Adler의 기반)
CRC-16-Adler_A	[A = 1 + D₁ + D₂ + ... + D_n (mod 65521)]
CRC-16-Adler_B	[B = n×D₁ + (n-1)×D₂ + (n-2)×D₃ + ... + D_n + n (mod 65521)]
CRC-16-CCITT	$x 16 + x 12 + x 5 + 1$
CRC-16-IBM	$x 16 + x 15 + x 2 + 1$
CRC-32-Adler	[Adler-32(D) = B × 65536 + A]
CRC-32-IEEE 802.3	$x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1$
CRC-32C (Castagnoli)	$x 32 + x 28 + x 27 + x 26 + x 25 + x 23 + x 22 + x 20 + x 19 + x 18 + x 14 + x 13 + x 11 + x 10 + x 9 + x 8 + x 6 + 1$
CRC-64-ISO	$x 64 + x 4 + x 3 + x + 1$ (ISO 3309)
CRC-64-ECMA-182	$x 64 + x 62 + x 57 + x 55 + x 54 + x 53 + x 52 + x 47 + x 46 + x 45 + x 40 + x 39 + x 38 + x 37 + x 35 + x 33 + x 32 + x 31 + x 29 + x 27 + x 24 + x 23 + x 22 + x 21 + x 19 + x 17 + x 13 + x 12 + x 10 + x 9 + x 7 + x 4 + x + 1$ (ECMA-182 p.63)
CRC-128	(IEEE? / ITU?)