순환 중복 검사
위키백과, 우리 모두의 백과사전.
순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.
데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.
순환 중복 검사를 계산하는 과정은 하드웨어적 방식과 소프트웨어적 방식을 생각할 수 있다. 하드웨어적 방식을 말할 때, 직렬데이터를 계산하는 것이 단순하다. 통신시스템에서 프로토콜 계층에서 물리층에 가까울 수록 하드웨어 접근을 그리고 상위계층에 가까울 수록 소프트웨어적인 방식이 적용된다.
통신시스템에서 물리계층에 가까울수록 직렬데이터를 사용하는 경향이 있다. 따라서 하드웨어적 계산방식을 사용 한다. 전송라인은 거의 직렬 데이터이기 때문이다. 이런 경우 순환 중복 검사는 비트단위의 입력에 대한 출력을 얻는다. 논리 회로를 만들면 간단해 진다. 그러나 높은 계층으로 갈수록 병렬데이터(octet 단위, 8비트)를 사용한다. 이런경우는 소프트웨어적 접근으로 주로 바이트 단위로 계산한다. 순환 중복 검사는 결국 비트단위 입력에 대한 각 비트별 XOR 연산이므로 한바이트 계산도 소프트웨어적 고속계산에 한계가 있다. 이런경우 주로 미리계산을 한 테이블 형태를 사용한다.
 
목차
  [숨기기] 
1개요
2CRC 다항식들과 종류들
2.1다항식의 표현
2.2정의된 다항식의 사용처
3CRC 계산 예
4하드웨어 구현
4.1논리 회로에 의한 하드웨어 구현
4.2병렬비트 입력 하드웨어 계산 예
5소프트웨어 구현
5.1CRC 테이블을 위한 코드 예
5.2CRC 테이블을 탐색을 통해 CRC 결정
6각주
7같이 보기
8바깥 고리
 
개요
 
1
2
3
4
5
6
7
8
9
10
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
}
Colored by Color Scripter
cs
 
(참고: 실제로는 여러 개의 최상위 비트들에 해당하는 shiftRegister의 표를 만들어서 한꺼번에 여러 비트를 처리해 속도를 높이는 방법을 쓰며, 특히 8비트 단위로 처리하는 방법이 많이 사용된다.)
위의 구현은 다음과 같은 두 가지 방법으로 고칠 수 있으며, 따라서 둘 중 하나를 적용하거나 둘 다 적용할 경우 CRC 값을 계산하는 네 가지 동등한 방법이 존재한다:
shiftRegister를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트한다. 이 경우polynomial의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
shiftRegister의 한 비트와 bitString의 한 비트를 xor하는 대신에, shiftRegister와 bitString에서 polynomial에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결과를 shiftRegister에 더한다. polynomial을 적당히 고치면 같은 나머지를 얻을 수 있다. 이 방법은 소프트웨어에서 구현하기는 힘들지만 하드웨어 구현에서는 종종 사용되며, CRC와 깊은 관련이 있는 선형 되먹임 시프트 레지스터를 설명하는 데 자주 사용된다.
 

정의된 다항식의 사용처
CRC값을 계산하려면 비트수와 다항식을 결정해야 한다. 따라서 정해진 비트수와 함께 다항식을 정하면 입력된 메시지는 오류가 없는 경우 같은 CRC 값이 나온다.
다음은 사용하고 있는 다양한 다항식들이다:
 
 

소프트웨어 구현
보통 CRC을 적용할 때 바이트(Octet) 단위로 구현한다. 많은 통신시스템에서 OCTET 단위가 기본이기 때문이다. 비트단위로 계산해야 하는 경우 속도등의 문제로 오히려 CRC 테이블 기법을 많이 사용한다.
OCT단위로 입력되는 데이터를 계산해야 하는데, 루프를 실행해야 하므로 속도등에 문제가 발생할 수 있다. 특히 CRC의 비트수가 많을 수록 더욱 문제가 된다.
위의 예를 기반으로 소프트웨어 접근법을 위한 코드를 작성 하면:
CRC 테이블을 만들어 변수화 한다.
데이터가 들어오면 OCTET 단위로 테이블 탐색을 통해 CRC을 결정 한다.
CRC 테이블을 위한 코드 예
우선 모든 OCT 단위로 입력을 미리 계산한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//#define CRC_SHIFT_5
 
static unsigned char crctable[256];
 
/// CRC 테이블 만들기 /////////////////////////////
 
//   Generate a table for a byte-wise 3-bit CRC calculation on the polynomial:
//   x^3 + x + 1
 
void make_crc_table( void ){
    int cnt, bcnt;
    unsigned short poly, c;
 
    // terms of polynomial defining this crc (except x^3):
    static const char p[] = {0,1};
 
    // make exclusive-or pattern from polynomial
    poly = 0;
    for ( cnt = 0; cnt < sizeof(p)/sizeof(p[0]); cnt++ ) { poly |= 1 << p[cnt]; }
    poly <<= 5;
 
    for ( cnt = 0; cnt < 256; cnt++ ) {
        c = cnt;
        for ( bcnt = 0; bcnt < 8; bcnt++ ) {
            c = ( c & 0x80 ) ? poly ^ ( c << 1 ) : ( c << 1 );
        }
       #ifdef CRC_SHIFT_5
    crctable[cnt] = (unsigned char) (c>>5) & 0x07;
       #else
        crctable[cnt] = (unsigned char) (c & 0xE0);
       #endif
    }
}
 
int main(int argc, char* argv[]){
    int cnt;
    unsigned char crc;
 
    make_crc_table();
 
    FILE *fout;
 
    if ( (fout = fopen("crc3table.h", "wt")) == NULL)return -1;
 
    fprintf(fout,
      "#ifndef _CRC3TABLE_H\n"
      "#define _CRC3TABLE_H\n"
      "\nextern const unsigned char crctable[];\n"
    );
 
   #ifdef CRC_SHIFT_5
    fprintf(fout, "\n#define CRC_SHIFT_5\n");
   #endif
 
    fprintf(fout, "\n#endif\n");
    fclose(fout);
 
    if ( (fout = fopen("crc3table.c", "wt")) == NULL)return -1;
 
    fprintf(fout, "\nconst unsigned char crctable[256] = {\n   ");
    for ( cnt = 0; cnt < 256; cnt++ ) {
        if (cnt == 255) {
            fprintf(fout, "0x%02X\n", crctable[cnt] );
            break;
        } else
            fprintf(fout,"0x%02X,", crctable[cnt] );
            if ( (cnt % 8) == 7)fprintf(fout,"\n   ");
            else                fprintf(fout," ");
    }
    fprintf(fout,"};\n");
    fclose(fout);
 
    return 0;
}
Colored by Color Scripter
cs