⛳

CRC-16よくばりセット

2022/02/22に公開

crc

組み込み

巡回符号

チェックサム

tech

概要

CRC-16は誤り検出符号のひとつで、ファイルコンテナやデータ転送におけるデータの誤りや破損を検出するために使われています。私が経験してきた限りでは組み込みプログラミングで頻繁に利用されていました。

組み込み機器は外部機器との通信でRS-232CやRS-485といった規格を使用することが多いのですが、信号の減衰やノイズの影響を受けることが多々あるので、少しでも信頼性を上げるために送信側では送信データ全体のチェックサムを取り送信データに付加します。受信側ではチェックサムを確認し、合っていれば正しいデータとして受け取り、間違っていれば破棄するか、送信側に再送要求をします。

チェックサムの候補としては、送信データのバイト値を足し合わせたり、XORを取ったりといった単純なものもありますし、複雑なものになると今回取り上げるCRC-16だったりします。

CRC-16の計算方法

CRC-16の計算アルゴリズムはどのバリエーションも同じものを使用していますが、5つのパラメータが異なります。

生成多項式 (poly)
初期値 (init)
反転入力 (refin)
反転出力 (refout)
排他的論理和出力 (xorout)

これらの値によってCRC-16の計算結果が変わって来ます。よく使われているパラメータには名前がつけられていて、Catalogue of parametrised CRC algorithms with 16bitsには有名なものが列挙されています。

パラメータ

よく「生成多項式は x^16+x^12+x^5+1」のように書かれていますが、実際には数式で提示されるだけの生成多項式では情報が足りずCRC-16の計算ができません。前述の5つのパラメータである生成多項式(poly), 初期値(init), 反転入力(refin), 反転出力(refout), 排他的論理和出力(xorout)が必要です。

Catalogue of parametrised CRC algorithms with 16bitsにはそれぞれの名前と計算に使用するパラメータが書かれています。例えばCRC-16/CCITT-FALSEは

width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 residue=0x0000 name="CRC-16/CCITT-FALSE"

であり「長さ16、多項式(poly)0x1021、初期値(init)0xffff、反転入力(refin)しない、反転出力(refout)しない、排他的論理和出力(xorout)0x0000」となっています。

そしてこのパラメータを使ってバイト列123456789のCRC-16を計算すると、チェックサム(check)が0x29b1になるとしています。

仮に今使用しているCRC-16がどのパラメータによるものかわからなくても、このチェックサムと突き合わせてみれば何を使用しているかわかります。今からでも仕様書にCRC-16の名前とパラメータを書きましょう。きっと後世の役に立つはずです。

Pythonによる実装

ではCRC-16の計算方法はというと、これはA Painless Guide to CRC Error Detection Algorithmsの実装が参考になります。この文献では古いCによる実装例が示されていますが、わかりやすく現代風にPythonで書き直すとこうなります。

class CRC16:
    ARC          = lambda: CRC16(0x8005, 0x0000,  True,  True, 0x0000)
    AUG_CCITT    = lambda: CRC16(0x1021, 0x1d0f, False, False, 0x0000)
    BUYPASS      = lambda: CRC16(0x8005, 0x0000, False, False, 0x0000)
    CCITT_FALSE  = lambda: CRC16(0x1021, 0xffff, False, False, 0x0000)
    CDMA2000     = lambda: CRC16(0xc867, 0xffff, False, False, 0x0000)
    CMS          = lambda: CRC16(0x8005, 0xffff, False, False, 0x0000)
    DDS_110      = lambda: CRC16(0x8005, 0x800d, False, False, 0x0000)
    DECT_R       = lambda: CRC16(0x0589, 0x0000, False, False, 0x0001)
    DECT_X       = lambda: CRC16(0x0589, 0x0000, False, False, 0x0000)
    DNP          = lambda: CRC16(0x3d65, 0x0000,  True,  True, 0xffff)
    EN_13757     = lambda: CRC16(0x3d65, 0x0000, False, False, 0xffff)
    GENIBUS      = lambda: CRC16(0x1021, 0xffff, False, False, 0xffff)
    GSM          = lambda: CRC16(0x1021, 0x0000, False, False, 0xffff)
    LJ1200       = lambda: CRC16(0x6f63, 0x0000, False, False, 0x0000)
    MAXIM        = lambda: CRC16(0x8005, 0x0000,  True,  True, 0xffff)
    MCRF4XX      = lambda: CRC16(0x1021, 0xffff,  True,  True, 0x0000)
    OPENSAFETY_A = lambda: CRC16(0x5935, 0x0000, False, False, 0x0000)
    OPENSAFETY_B = lambda: CRC16(0x755b, 0x0000, False, False, 0x0000)
    PROFIBUS     = lambda: CRC16(0x1dcf, 0xffff, False, False, 0xffff)
    RIELLO       = lambda: CRC16(0x1021, 0x554d,  True,  True, 0x0000)
    T10_DIF      = lambda: CRC16(0x8bb7, 0x0000, False, False, 0x0000)
    TELEDISK     = lambda: CRC16(0xa097, 0x0000, False, False, 0x0000)
    TMS37157     = lambda: CRC16(0x1021, 0x3791,  True,  True, 0x0000)
    USB          = lambda: CRC16(0x8005, 0xffff,  True,  True, 0xffff)
    CRC_A        = lambda: CRC16(0x1021, 0x6363,  True,  True, 0x0000)
    KERMIT       = lambda: CRC16(0x1021, 0x0000,  True,  True, 0x0000)
    MODBUS       = lambda: CRC16(0x8005, 0xffff,  True,  True, 0x0000)
    NRSC_5       = lambda: CRC16(0x080b, 0xffff,  True,  True, 0x0000)
    X_25         = lambda: CRC16(0x1021, 0xffff,  True,  True, 0xffff)
    XMODEM       = lambda: CRC16(0x1021, 0x0000, False, False, 0x0000)

    def __init__(self, poly, init, refin, refout, xorout):
        self.poly = poly
        self.init = init
        self.refin = refin
        self.refout = refout
        self.xorout = xorout
        if self.refin:
            self.init = self.__reflect(init, 16)

    def __reflect(self, x, bits):
        r = 0
        for i in range(bits):
            r = (r << 1) | ((x >> i) & 1)
        return r

    def update(self, data):
        for x in data:
            self.init ^= (self.__reflect(x, 8) if self.refin else x) << 8
            for _ in range(8):
                if self.init & 0x8000:
                    self.init = ((self.init << 1) ^ self.poly) & 0xffff
                else:
                    self.init = (self.init << 1) & 0xffff

    def digest(self, data=b''):
        self.update(data)
        x = self.init
        if self.refout:
            x = self.__reflect(x, 16)
        return x ^ self.xorout

CRC-16の性質

CRCの計算はSHAのような汎用ハッシュアルゴリズムと同様に、データをいくつかに分割して入力することができる性質を持っています。大量のメモリを確保できない場合やストリームによって分割されたデータが手に入るなど一度にすべてのデータを入力できない場合であっても、小分けにしてチェックサムを計算できるということです。

このPythonコードではCRC16のインスタンスを作り、update()を0回以上呼び出したのち、digest()を呼び出せばCRC-16のチェックサムを得られる様になっています。

a = CRC16.CCITT_FALSE()
a.update(b'12345')
a.update(b'6789')
a.digest()                # 0x29b1

b = CRC16.CCITT_FALSE()
b.digest(b'123456789')    # 0x29b1

概要

CRC-16の計算方法

パラメータ

Pythonによる実装

CRC-16の性質

Discussion