Skip to main content Link Search Menu Expand Document (external link) Copy Copied
MainLogo

CRC 구현 방법

작성일 : 2023년 04월 02일 (Sunday)

Table of contents
  1. CRC 16 CCITT FALSE
  2. CRC 4 ITU

CRC는 Cyclic Redundancy Check의 줄임말이다. CRC는 정확하게 정해진 알고리즘은 없다고 봐도 무방하다. 수신과 송신측이 동일한 로직을 적용해서 주고받은 데이터의 정합성에 대해 검증하는 값으로 CRC는 통신뿐만 아니라 여러가지 데이터들을 인터넷이나 서버를 통해서 내려받는 경우에도 사용되곤 한다. 아래는 CRC 16 CCITT FALSE, CRC 4 ITU 알고리즘을 코드로 구현하여 간단하게 표현해 보았다. 처음 보면 어렵지만 이해하면 쉽다.
CreateMap 함수는 매번 반복되는 계산을 미리 한번 해둬서 매번 계산을 반복하지 않도록 도와주는 기능을 하고, Compute_CRC는 적당한 크기로 데이터를 끊어서 연산하고 쉬프트해서 마지막 데이터까지 반복해서 CRC를 계산하는 함수이다.

기다란 데이터를 나눈다고 생각해보자.

=============================================0000

위 =의 개수를 헤아릴 필요는 없다. 단순히 그냥 예시를 위해 나도 개수를 세보지 않고 의미없이 길게 썼다. 대신 =는 계산을 CRC 계산이 필요한 데이터이지만 그 값은 모두 0이라고 해보자. 간단하게 설명하면 CRC는 계속해서 쉬프팅하며 계산을 계속해나가는 것이다. 예를 들어, CRC4를 계산한다고 생각하고 아래를 봐보자.

CRC4는 다항식 0xF를 사용한다. 이 것은 무슨 의미일까? 0xF는 이진수로 0b0011이 된다. 이를 다항식으로 표현하면 $x^4 + x + 1$이 된다. 이 다항식이라는 것은 도대체 무엇인지 모르겠다면 이전 포스팅 인코딩 을 참고하길 바란다.

Data   =======1===============1===============1======0000  
Poly 1        10011  
XOR  1 =======00011===========1===============1======0000  
Poly 2           10011  
XOR  2 =======00001011========1===============1======0000  
...
Final  ==============================================0101  

CRC = 0b0101 = 0x5

사실 위에서 실제로 CRC가 5로 나오는지 검증해보지는 않았다. 흐름만 알면 된다. 컴퓨터에서 코드로 CRC를 구현할 때에는 직접 계산할 위치를 옮겨가며 다항식과 XOR를 수행하고 또 오른쪽으로 옮겨가서 XOR을 수행하는 것이 불가능할 것이기에 비트 쉬프트 연산자를 이용하여 왼쪽으로 당겨가며 계산하는 것이라고 보면된다. 이 관점에서 아래 코드를 분석해보면 이해에 도움이 될 것이다.

CRC의 종류는 굉장히 다양하다. 알려진 알고리즘만 하더라도 굉장히 많다. 이력, 다른 알고리즘의 종류 등을 참고하려면 위키피디아를 참고해보자. 알고리즘 구현방법까지는 나와있는 편은 아니지만 종류나 이력만큼은 확인하기 좋다.

CRC 16 CCITT FALSE

Initial Value : 0xFFFF Final XOR : 0x0000

public static class Crc16
{
    public static UInt16[] Crc16Tbl = new UInt16[256];

    public static void CreateMap()
    {
        Array.Clear(Crc16Tbl, 0, 256);

        const ushort generator = 0x1021;

        for (int divident = 0; divident < 256; divident++)
        {
            ushort curByte = (ushort)(divident << 8);

            for (byte bit = 0; bit < 8; bit++)
            {
                if ((curByte & 0x8000) != 0)
                {
                    curByte <<= 1;
                    curByte ^= generator;
                }
                else
                {
                    curByte <<= 1;
                }
            }

            Crc16Tbl[divident] = curByte;
        }
    }

    public static ushort Compute_CRC(byte[] bytes)
    {
        ushort crc = 0xFFFF; // Initial Value
        foreach (byte b in bytes)
        {
            byte pos = (byte)((crc >> 8) ^ b);
            crc = (ushort)((crc << 8) ^ (ushort)(Crc16Tbl[pos]));
        }
        crc = (ushort)(crc ^ 0x0000); // Final XOR
        return crc;
    }
}

CRC 4 ITU

Initial Value : 0xF Final XOR : 0x0

public static class Crc4
{
    public static byte Shift4Bits(byte data)
    {
        return (byte)(data << 4);
    }
    public static byte[] Crc4Tbl = new byte[16];
    public static void CreateMap()
    {
        Array.Clear(Crc4Tbl, 0, 16);

        byte generator = 0x03;
        byte poly = (byte)(generator << 4);

        for (int divident = 0; divident < 16; divident++)
        {
            byte curByte = (byte)(divident << 4);
            curByte &= 0x00FF;

            for (byte bit = 0; bit < 4; bit++)
            {
                if ((curByte & 0x80) != 0)
                {
                    curByte <<= 1;
                    curByte ^= poly;
                }
                else
                {
                    curByte <<= 1;
                }
            }

            curByte &= 0xFF;
            curByte = (byte)(curByte >> 4);
            Crc4Tbl[divident] = (byte)curByte;
        }
    }
    public static byte Compute_CRC(byte[] bytes)
    {
        byte initialValue = 0x0F; // Initial Value
        byte curByte = initialValue;

        foreach (byte b in bytes)
        {
            byte upper4Bits = (byte)((b & 0xF0) >> 4);
            byte below4Bits = (byte)(b & 0x0F);
            // upper4Bits 부터
            byte pos = (byte)((curByte >> 4) ^ upper4Bits);
            curByte = (byte)((curByte << 4) ^ (byte)(Crc4Tbl[pos]));
            // below4Bits 이어서
            pos = (byte)((curByte >> 4) ^ below4Bits);
            curByte = (byte)((curByte << 4) ^ (byte)(Crc4Tbl[pos]));
        }
        // 마지막 남은 1번 처리
        pos = (byte)((curByte & 0xF0) >> 4);
        curByte = (byte)((curByte & 0x0F) ^ (byte)(Crc4Tbl[pos]));
        
        curByte ^= 0x00; // Final XOR
        return (byte)(curByte);
    }
}