순환 중복 검사

순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.
데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.
순환 중복 검사를 계산하는 과정은 하드웨어적 방식과 소프트웨어적 방식을 생각할 수 있다. 하드웨어적 방식을 말할 때, 직렬데이터를 계산하는 것이 단순하다. 통신시스템에서 프로토콜 계층에서 물리층에 가까울수록 하드웨어 접근을 그리고 상위계층에 가까울 수록 소프트웨어적인 방식이 적용된다.
통신시스템에서 물리계층에 가까울수록 직렬데이터를 사용하는 경향이 있다. 따라서 하드웨어적 계산방식을 사용한다. 전송라인은 거의 직렬 데이터이기 때문이다. 이런 경우 순환 중복 검사는 비트단위의 입력에 대한 출력을 얻는다. 논리 회로를 만들면 간단해진다. 그러나 높은 계층으로 갈수록 병렬데이터(octet 단위, 8비트)를 사용한다. 이런경우는 소프트웨어적 접근으로 주로 바이트 단위로 계산한다. 순환 중복 검사는 결국 비트단위 입력에 대한 각 비트별 XOR 연산이므로 한 바이트 계산도 소프트웨어적 고속계산에 한계가 있다. 이런 경우 주로 미리계산을 한 테이블 형태를 사용한다.

하드웨어 구현

구현은 하드웨어적 방법과 소프트웨어적 방법이 있다. 보통 CRC가 통신시스템등에 많이 사용되는데, 하드웨어적인 접근방법도 많이 사용한다.
위의 예:
는 다음과 같은 구성으로 표현할 수 있다.
직렬 비트데이터가 들어오면 매 비트마다 논리회로에 의해 계산된다.

논리 회로에 의한 하드웨어 구현

D-FF을 사용하여 논리 회로를 그리면 다음과 같다:
입력은 한클럭 동안 하나의 비트를 입력하고, 출력은 O₂ O₁ O₀로 3비트이다. 직렬입력에 대해 매 클럭마다 CRC값이 출력된다.
디지털통신에서 물리계층으로 갈수록 직렬비트의 데이터 형태로 입력되어 처리되는 경향이 있다. 따라서 보통 위와같은 회로를 사용하여 CRC을 계산할 수 있다.

CRC 테이블을 위한 코드 예

우선 모든 OCT 단위로 입력을 미리 계산한다.
//#define CRC_SHIFT_5static unsigned char crctable[256];/// CRC 테이블 만들기 ///////////////////////////////   Generate a table for a byte-wise 3-bit CRC calculation on the polynomial://   x^3 + x + 1void 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;}
실행결과 :
const unsigned char crctable[256] = {
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0xE0, 0x80, 0x20, 0x40, 0x00, 0x60, 0xC0, 0xA0,
   0x40, 0x20, 0x80, 0xE0, 0xA0, 0xC0, 0x60, 0x00,
   0xC0, 0xA0, 0x00, 0x60, 0x20, 0x40, 0xE0, 0x80,
   0x60, 0x00, 0xA0, 0xC0, 0x80, 0xE0, 0x40, 0x20,
   0xA0, 0xC0, 0x60, 0x00, 0x40, 0x20, 0x80, 0xE0,
   0x00, 0x60, 0xC0, 0xA0, 0xE0, 0x80, 0x20, 0x40,
   0x80, 0xE0, 0x40, 0x20, 0x60, 0x00, 0xA0, 0xC0,
   0x20, 0x40, 0xE0, 0x80, 0xC0, 0xA0, 0x00, 0x60
};
변수 crctable[]이 바이트 단위로 모두 계산한다. 이것을 프로그램 파일로 만들어 CRC 계산하는데 사용한다.
이 파일이름을 crc3table.c라고 하면 다음에 이것을 사용하여 코딩한다.

CRC 테이블을 탐색을 통해 CRC 결정

// File : crc3.h //////////////////////////////////////////#ifndef _CRC3_H#define _CRC3_H#include "crc3table.h"#define CRC3_INIT_VALUE   0x0000unsigned char crc3_CalcChecksum(const unsigned char icrc, const void *data, int length );#endif// File : crc3.c ////////////////////////////////////////////#include "crc3.h"/// CRC 테이블 사용하기 //////////////#include "crc3table.c"  // 위의 예에서 미리계산한 CRC 테이블 코드를 사용한다.unsigned char crc3_CalcChecksum(const unsigned char icrc, const void *data, int length ){
    unsigned char crc;
    const unsigned char *buf = (const unsigned char *) data;

    crc = icrc;
    while (length--) {
       #ifdef CRC_SHIFT_5
        crc = crctable[(crc<<5) ^ *buf++];
       #else
        crc = crctable[crc ^ *buf++];
       #endif
    }
    return crc;}// File : testcrc3main.c ////////////////////////////////////////////#include <stdio.h>#include "crc3.h"int main(int argc, char* argv[]){
   int cnt;
   unsigned char crc;

    unsigned char data[8] = { 0xD3, 0xB0 };
   #define SZ_MSGDATA 2

    crc = crc3_CalcChecksum(CRC3_INIT_VALUE, (void *)data, SZ_MSGDATA);
    printf("Input Data : ");
    for (cnt = 0;cnt < SZ_MSGDATA;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif

    int sz = SZ_MSGDATA;
    data[sz++] = 0xCB;
    data[sz++] = 0x0D;
    crc = crc3_CalcChecksum(crc, &data[SZ_MSGDATA], sz-SZ_MSGDATA);
    printf("Input Data : ");
    for (cnt = 0;cnt < sz;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif

    crc = crc3_CalcChecksum(CRC3_INIT_VALUE, (void *)data, sz);
    printf("다시 계산 : ");
    for (cnt = 0;cnt < sz;cnt++)
        printf("0x%02X ", data[cnt] );
   #ifdef CRC_SHIFT_5
    printf(" : CRC = %X\n", crc);
   #else
    printf(" : CRC = 0x%02X [%x]\n", crc, crc >> 5 );
   #endif
    return 0;}
실행결과:
Input Data : 0xD3 0xB0  : CRC = 0xC0 [6]
Input Data : 0xD3 0xB0 0xCB 0x0D  : CRC = 0x20 [1]
다시 계산 : 0xD3 0xB0 0xCB 0x0D  : CRC = 0x20 [1]
2바이트의 3비트 CRC는 6으로 결정되었다.