CRCによる誤り検出をPythonで実装｜通信・ストレージの"見張り番"

USB、Ethernet、ストレージ、QRコード——データが化けていないか見張るのに広く使われるのが CRC（巡回冗長検査） です。単純な合計より強力に誤りを見つけます。この記事ではPythonで実装し、そのしくみを理解します。ハミング符号が"訂正"なら、CRCは高速な"検出"担当です。

しくみ：多項式の割り算

CRCは、データを大きな2進数とみなして、決められた生成多項式で割った余りを検査値にします。データと一緒にこの余りを送り、受信側で同じ割り算をして余りが0かを確認する——シンプルながら強力です。

準備

Python標準機能だけ。

① CRCを計算する

XORによる多項式除算で余りを求めます。

def crc_remainder(data_bits, poly_bits):
    # data_bits, poly_bits は 0/1 のリスト
    d = data_bits + [0] * (len(poly_bits) - 1)   # 余り桁を確保
    for i in range(len(data_bits)):
        if d[i] == 1:                             # 先頭が1なら割る
            for j in range(len(poly_bits)):
                d[i + j] ^= poly_bits[j]          # XORで引き算
    return d[len(data_bits):]                     # 余り＝CRC

data = [1, 0, 1, 1, 0, 1]
poly = [1, 0, 1, 1]                # 生成多項式 x³+x+1
crc = crc_remainder(data, poly)
print("CRC:", crc)

② 送信と検証

CRCを付けて送り、受信側で割り算して余りが0かを確認します。

def transmit(data, poly):
    crc = crc_remainder(data, poly)
    return data + crc              # データ＋CRCを送る

def check(received, poly):
    return crc_remainder(received, poly) == [0] * (len(poly) - 1)

sent = transmit(data, poly)
print("正常受信:", check(sent, poly))          # True

# 途中で1ビット化けさせる
corrupted = sent.copy(); corrupted[2] ^= 1
print("改ざん受信:", check(corrupted, poly))    # False

出力は正常なら True、1ビット化けると False。CRCは誤りを確実に検出しました。

③ なぜ単純な合計より強いのか

# 単純な合計（パリティ）だと2ビット誤りを見逃すことがある
def simple_parity(bits): return sum(bits) % 2

original = [1, 1, 0, 0]
# 2ビット反転しても合計の偶奇は変わらない → 見逃す
flipped = [0, 0, 0, 0]
print("パリティは同じ？:", simple_parity(original) == simple_parity(flipped))  # True=見逃す

単純なパリティは2ビット誤りを見逃すことがあります。CRCは多項式のおかげで、連続した誤り（バースト誤り）にも強い。通信で実際に起きる誤りに効く設計です。

🌱

ハードで超高速

CRCはシフトとXORだけなので、専用回路で猛烈に速く計算できます。だから通信チップやストレージコントローラに組み込まれ、全データを流れるように検査しています。ソフトでも軽く、用途が非常に広い符号です。

⚠️

検出はできても訂正はできない

CRCは「化けたことに気づく」だけで、直せません。誤りを見つけたら再送を要求する使い方が基本。訂正まで必要ならハミング符号などのECCを使います。役割分担です。

まとめ

CRCはデータを生成多項式で割った余りを検査値にする
受信側で同じ割り算をして余り0かを確認する
単純なパリティより強く、バースト誤りにも強い
検出専用（訂正は不可）。ハードで高速に計算できる

もう少し詳しく（背景と理論）

CRC（巡回冗長検査）は、データを多項式とみなし、生成多項式で割った余りを検査ビットとして付ける誤り検出方式です。数学的には有限体 GF(2) 上の多項式除算で、XOR とシフトだけで高速に計算できます¹。適切な生成多項式を選ぶと、単一ビット誤り・2ビット誤り・奇数個の誤り・生成多項式の次数までのバースト誤りを確実に検出できるのが強みです²。CRC-32 などは通信（Ethernet）やストレージで広く使われます。ただし CRC は誤り検出専用で訂正はできず、また意図的な改ざんには弱い（線形性を突かれる）ため、セキュリティ用途ではハッシュや HMAC とは役割が異なる点に注意が必要です³。

次の一歩 🌸

訂正までするハミング符号、2進数の基礎は2進数と2の補数、論理演算はブール代数をPythonでへどうぞ。

CRC は GF(2) 上の多項式除算の余り。ハードウェアではシフトレジスタとXORで実装でき、高速・低コスト。Peterson & Brown (1961) が理論を整理。 ↩
生成多項式の設計により、単一・二重・奇数個・次数以下のバースト誤りを保証検出できる。CRC-32 は Ethernet 等で標準採用。 ↩
CRC は誤り検出専用で訂正不可。線形なので改ざん検出（セキュリティ）には不適。悪意ある改ざんには暗号学的ハッシュ/MACを使う。 ↩