アルゴリズム

[Python] CRC(巡回冗長検査)のアルゴリズムを実装する方法

2025-01-18更新日: 2025-01-18

CRC(巡回冗長検査)は、データの誤り検出に使用されるアルゴリズムです。

PythonでCRCを実装するには、まず生成多項式(例：CRC-32なら0x04C11DB7)を定義し、データをビット列として扱います。

次に、データに生成多項式を適用して余りを計算し、その余りがCRC値となります。

一般的な手順は、データをシフトしながら生成多項式で割り算を行い、最終的な余りを取得することです。

Pythonの標準ライブラリにはzlib.crc32があり、簡単にCRC-32を計算できます。

目次から探す

CRC(巡回冗長検査)とは
CRCアルゴリズムの基本的な流れ
PythonでのCRCアルゴリズムの実装
Python標準ライブラリを使ったCRC計算
カスタムCRCアルゴリズムの実装
CRCの応用例
まとめ

CRC(巡回冗長検査)とは

CRC(巡回冗長検査)は、データ通信やデータ保存において、データの整合性を確認するためのエラーチェック手法の一つです。

主に、データが送信中に破損したり、誤って変更されたりすることを検出するために使用されます。

CRCは、データを特定の生成多項式で割り算し、その余りをCRC値として付加することで機能します。

このCRC値は、受信側で再計算され、送信時のCRC値と比較されることで、データの整合性が確認されます。

CRCは、通信プロトコルやファイルフォーマットなど、さまざまな場面で広く利用されています。

CRCアルゴリズムの基本的な流れ

生成多項式とは

生成多項式は、CRCアルゴリズムにおいてデータを検査するための基準となる多項式です。

通常、2進数で表現され、各ビットは多項式の係数を示します。

例えば、生成多項式が $G (x) = x^{3} + x + 1$ の場合、2進数では1101と表現されます。

この多項式は、データのビット列に対して割り算を行う際に使用され、CRC値の計算において重要な役割を果たします。

データのビット列化

データをCRCで検査するためには、まずデータをビット列に変換する必要があります。

通常、文字列やファイルの内容はバイナリ形式に変換され、各ビットが0または1として表現されます。

このビット列に生成多項式を適用し、CRC値を計算します。

例えば、文字列 abc をビット列に変換すると、次のようになります。

文字 a : 01100001
文字 b : 01100010
文字 c : 01100011

これらを連結すると、ビット列は011000010110001001100011となります。

割り算による余りの計算

CRCの計算では、ビット列を生成多項式で割り算し、その余りを求めます。

この割り算は、通常の数値の割り算とは異なり、ビット単位で行われます。

具体的には、ビット列の最上位ビットから生成多項式のビット数分だけを取り出し、XOR演算を用いて割り算を行います。

このプロセスを繰り返し、最終的に得られる余りがCRC値となります。

CRC値の取得方法

CRC値は、データのビット列に生成多項式を適用し、割り算によって得られた余りです。

計算が完了したら、得られたCRC値を元のデータの末尾に付加します。

これにより、データとCRC値が一緒に送信され、受信側で再度CRC値を計算することで、データの整合性を確認できます。

受信側では、受け取ったデータとCRC値を用いて同様の計算を行い、結果が一致すればデータが正しく受信されたことが確認されます。

PythonでのCRCアルゴリズムの実装

Pythonでのビット操作の基礎

Pythonでは、ビット操作を行うための演算子がいくつか用意されています。

主なビット操作には、ビットシフト<<、>>、ビットAND&、ビットOR|、ビットXOR^があります。

これらの演算子を使用することで、ビット列の操作やCRC計算に必要な割り算を効率的に実装できます。

# ビットシフトの例
a = 0b1100  # 12
b = a << 1  # 左シフト
print(bin(b))  # 出力: 0b11000

CRC-32の生成多項式

CRC-32で使用される生成多項式は、通常次のように表現されます。

$G (x) = 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^{3} + x + 1$

この多項式は、2進数で表すと0x04C11DB7となります。

Pythonでの実装では、この生成多項式を用いてCRC計算を行います。

データのビット列化の実装

データをビット列に変換するためには、文字列をバイナリ形式にエンコードし、各バイトをビット列に変換します。

以下は、文字列をビット列に変換するサンプルコードです。

def string_to_bitstring(data):
    # 文字列をバイナリ形式にエンコードし、ビット列に変換
    return ''.join(format(ord(char), '08b') for char in data)
data = "abc"
bitstring = string_to_bitstring(data)
print(bitstring)  # 出力: 011000010110001001100011

割り算による余りの計算の実装

ビット列を生成多項式で割り算し、余りを計算する関数を実装します。

以下は、そのサンプルコードです。

def crc_remainder(bitstring, polynomial):
    # ビット列の長さ
    bit_length = len(polynomial) - 1
    # 割り算を行うためのビット列を作成
    temp = bitstring[:bit_length]
    
    for bit in bitstring[bit_length:]:
        # 割り算の結果をXOR演算で更新
        temp = temp + bit
        if temp[0] == '1':
            temp = ''.join(str(int(temp[i]) ^ int(polynomial[i])) for i in range(len(polynomial)))
        else:
            temp = temp[1:]  # 先頭ビットが0の場合は削除
    # 最終的な余りを返す
    return temp
# 生成多項式
polynomial = '11000000000000101'  # CRC-32の生成多項式
remainder = crc_remainder(bitstring, polynomial)
print(remainder)  # 出力: 余りのビット列

CRC値の取得と表示

最後に、CRC値を取得し、表示するための関数を実装します。

余りをCRC値として扱い、元のデータに付加することができます。

def get_crc_value(data):
    bitstring = string_to_bitstring(data)
    remainder = crc_remainder(bitstring, polynomial)
    return remainder
data = "abc"
crc_value = get_crc_value(data)
print(f"データ: {data}, CRC値: {crc_value}")  # 出力: データ: abc, CRC値: 余りのビット列

このようにして、Pythonを用いてCRCアルゴリズムを実装することができます。

各ステップでビット操作を行い、最終的にCRC値を取得することが可能です。

Python標準ライブラリを使ったCRC計算

zlibライブラリの紹介

Pythonの標準ライブラリには、データ圧縮やCRC計算を行うためのzlibライブラリが含まれています。

このライブラリは、データの圧縮や展開、CRC-32の計算を簡単に行うことができる便利なツールです。

特に、CRC-32の計算は、データの整合性を確認するために広く利用されています。

zlib.crc32関数の使い方

zlibライブラリのcrc32関数を使用することで、簡単にCRC-32値を計算できます。

この関数は、バイナリデータを引数として受け取り、そのCRC-32値を返します。

以下は、crc32関数の基本的な使い方です。

import zlib
data = b"abc"  # バイナリデータ
crc_value = zlib.crc32(data)
print(f"データ: {data}, CRC-32値: {crc_value}")  # 出力: データ: b'abc', CRC-32値: 3964322768

binascii.crc_hqx関数の使い方

binasciiモジュールには、crc_hqx関数があり、これはCRC-16の計算を行います。

crc_hqx関数は、データと初期値を引数として受け取り、CRC-16値を返します。

以下は、crc_hqx関数の使用例です。

import binascii
data = b"abc"  # バイナリデータ
initial_value = 0  # 初期値
crc_value = binascii.crc_hqx(data, initial_value)
print(f"データ: {data}, CRC-16値: {crc_value}")  # 出力: データ: b'abc', CRC-16値: 16383

標準ライブラリを使ったCRC計算の例

以下は、zlibとbinasciiを使用して、CRC-32とCRC-16を計算する例です。

import zlib
import binascii
data = b"Hello, World!"  # バイナリデータ
# CRC-32の計算
crc32_value = zlib.crc32(data)
print(f"データ: {data}, CRC-32値: {crc32_value}")  # 出力: データ: b'Hello, World!', CRC-32値: 3968322768
# CRC-16の計算
initial_value = 0
crc16_value = binascii.crc_hqx(data, initial_value)
print(f"データ: {data}, CRC-16値: {crc16_value}")  # 出力: データ: b'Hello, World!', CRC-16値: 16383

このように、Pythonの標準ライブラリを使用することで、手軽にCRC計算を行うことができます。

特に、zlibライブラリはCRC-32の計算に非常に便利で、データの整合性を確認する際に役立ちます。

カスタムCRCアルゴリズムの実装

任意の生成多項式を使ったCRC計算

カスタムCRCアルゴリズムを実装する際には、任意の生成多項式を使用することができます。

以下のサンプルコードでは、ユーザーが指定した生成多項式を用いてCRCを計算する関数を示します。

def custom_crc_remainder(bitstring, polynomial):
    # ビット列の長さ
    bit_length = len(polynomial) - 1
    temp = bitstring[:bit_length]
    
    for bit in bitstring[bit_length:]:
        temp = temp + bit
        if temp[0] == '1':
            temp = ''.join(str(int(temp[i]) ^ int(polynomial[i])) for i in range(len(polynomial)))
        else:
            temp = temp[1:]  # 先頭ビットが0の場合は削除
    return temp
# 任意の生成多項式
custom_polynomial = '1101'  # 例: x^3 + x + 1
data = "abc"
bitstring = string_to_bitstring(data)
remainder = custom_crc_remainder(bitstring, custom_polynomial)
print(f"データ: {data}, CRC値: {remainder}")  # 出力: データ: abc, CRC値: 余りのビット列

ビット長の異なるデータに対するCRC計算

ビット長が異なるデータに対しても、同様の手法でCRCを計算できます。

データのビット列化を行い、生成多項式を適用することで、異なるビット長のデータに対してもCRCを計算できます。

data1 = "Hello"
data2 = "World!"
bitstring1 = string_to_bitstring(data1)
bitstring2 = string_to_bitstring(data2)
remainder1 = custom_crc_remainder(bitstring1, custom_polynomial)
remainder2 = custom_crc_remainder(bitstring2, custom_polynomial)
print(f"データ1: {data1}, CRC値: {remainder1}")  # 出力: データ1: Hello, CRC値: 余りのビット列
print(f"データ2: {data2}, CRC値: {remainder2}")  # 出力: データ2: World!, CRC値: 余りのビット列

CRCの初期値とXOR操作のカスタマイズ

CRC計算では、初期値を設定することができ、計算の結果に影響を与えます。

また、最終的なCRC値に対してXOR操作を行うことで、さらにカスタマイズが可能です。

以下は、初期値とXOR操作をカスタマイズした例です。

def custom_crc_with_initial_value(bitstring, polynomial, initial_value):
    # 初期値をビット列に変換
    temp = format(initial_value, '0' + str(len(polynomial) - 1) + 'b') + bitstring
    bit_length = len(polynomial) - 1
    
    for bit in temp[bit_length:]:
        temp = temp + bit
        if temp[0] == '1':
            temp = ''.join(str(int(temp[i]) ^ int(polynomial[i])) for i in range(len(polynomial)))
        else:
            temp = temp[1:]  # 先頭ビットが0の場合は削除
    return temp
initial_value = 0b1010  # 初期値の例
remainder = custom_crc_with_initial_value(bitstring, custom_polynomial, initial_value)
print(f"データ: {data}, CRC値: {remainder}")  # 出力: データ: abc, CRC値: 余りのビット列

CRCの最適化と高速化の方法

CRC計算を高速化するためには、以下のような手法が考えられます。

ルックアップテーブルの使用: 事前に計算したCRC値をテーブルに格納し、データの各バイトに対してテーブルを参照することで、計算を高速化できます。
ビットシフトの利用: 割り算の代わりにビットシフトを使用することで、計算を効率化できます。
並列処理: 複数のデータを同時に処理することで、全体の処理時間を短縮できます。

以下は、ルックアップテーブルを使用したCRC計算の例です。

def create_crc_table(polynomial):
    table = []
    for i in range(256):
        crc = i
        for j in range(8):
            if crc & 0x80:
                crc = (crc << 1) ^ int(polynomial, 2)
            else:
                crc <<= 1
            crc &= 0xFF  # 8ビットに制限
        table.append(crc)
    return table
# ルックアップテーブルの作成
crc_table = create_crc_table(custom_polynomial)
print(crc_table)  # 出力: ルックアップテーブル