代表的な符号の概観

🎓 レベル：標準　|　重要度：B（重要）

📎 前提：線形符号とハミング符号　|　関連：シャノンの通信路符号化定理

要点（BLUF）

CRC（巡回冗長検査）：生成多項式で割った剰余を付加する誤り検出符号。バースト誤りに強く、Ethernet・ZIP・ストレージで偏在。訂正はしません。
リードソロモン（RS）符号：シンボル単位でバースト誤りを訂正。QR コード・CD/DVD・衛星通信で活躍。Singleton 限界 $d_{\min}\le n-k+1$ を等号で達成する MDS 符号。
容量に迫る符号：ターボ・LDPC・ポーラ符号は、長いブロックでシャノン容量（通信路容量）に肉薄。5G NR ではデータに LDPC、制御にポーラ符号を採用（3GPP TS 38.212）。

1. CRC：高速な誤り検出

CRC はデータビット列を多項式とみなし、生成多項式 $g(x)$ で割った剰余を検査ビットとして付加します。受信側は受信語を再び $g(x)$ で割り、剰余が0なら受理、非0なら誤りと判定。XOR とシフトだけで計算でき、ハードウェアで超高速。バースト誤り（連続したビット誤り）の検出に特に強く、生成多項式の次数 $r$ なら $r$ ビット以下のバーストを確実に検出します。訂正はせず検出のみ——誤りを見つけたら再送を要求するのが典型（ARQ）。

2. リードソロモン符号と Singleton 限界

任意の線形符号は Singleton 限界

d_{\min} \le n - k + 1

を満たします（検査ビット $n-k$ 個で作れる距離の上限）。この等号を達成する符号を MDS（Maximum Distance Separable）符号 と呼び、その代表が リードソロモン符号。RS はビットでなくシンボル（複数ビットのまとまり）単位で扱うため、連続ビット誤り（バースト）が1シンボル内に収まれば1シンボル誤りとして訂正でき、CD の傷や QR コードの汚れに強い。 $(n,k)=(255,223)$ （バイト単位）なら $d_{\min}=33$ で最大16シンボル誤りを訂正、と高い訂正力を持ちます。

3. 容量に迫る現代符号

ハミング符号（線形符号とハミング符号）は教育的ですが容量からは遠い。半世紀かけて、長いブロックでシャノン容量に肉薄する符号が発見されました。

符号	特徴	主な用途
ターボ符号	並列連接＋反復復号で容量に接近（1993）	3G/4G（LTE）
LDPC 符号	疎な検査行列・確率伝播（信念伝播）復号	5G NR データ・Wi-Fi・ストレージ
ポーラ符号	通信路分極で容量達成を理論的に証明（2009）	5G NR 制御

5G NR（3GPP TS 38.212） では、高スループットが要るデータチャネルに LDPC（4G のターボを置換）、短く高信頼が要る制御チャネルに ポーラ符号（4G の畳み込み符号を置換）を採用しています。いずれもシャノンの通信路符号化定理（シャノンの通信路符号化定理）が60年以上前に存在を約束した「容量に迫る符号」の実現です。

4. コード：CRC の検出と Singleton 限界（GF(2)）

CRC-3 でデータに剰余を付け、誤りなしなら剰余0・1ビット誤りで非0を確認し、Singleton 限界を計算します。

import numpy as np
def crc_remainder(data_bits, gen_bits):
    d=list(data_bits)+[0]*(len(gen_bits)-1)   # データに次数-1個の0を付加
    g=list(gen_bits)
    for i in range(len(data_bits)):
        if d[i]==1:                            # GF(2) の多項式除算（XOR）
            for j in range(len(g)):
                d[i+j]^=g[j]
    return d[-(len(gen_bits)-1):]              # 剰余

gen=[1,0,1,1]  # 生成多項式 x^3+x+1 (CRC-3)
data=[1,0,1,1,0,0,1]
rem=crc_remainder(data,gen)
print(f"データ {data} の CRC余り = {rem}")
codeword=list(data)+rem
print(f"送信語(データ+CRC) = {codeword}")
print(f"受信側の検査余り(誤りなし) = {crc_remainder(codeword,gen)}  -> 全0なら受理")
bad=codeword.copy(); bad[2]^=1
print(f"1ビット誤り混入の検査余り = {crc_remainder(bad,gen)}  -> 非0なので誤り検出")
print("-"*46)
# Singleton 限界 d_min <= n-k+1 （MDS=等号、リードソロモン）
for (n,k) in [(7,4),(15,11),(255,223)]:
    print(f"(n={n},k={k}): Singleton限界 d_min <= n-k+1 = {n-k+1}")

出力：

データ [1, 0, 1, 1, 0, 0, 1] の CRC余り = [0, 1, 1]
送信語(データ+CRC) = [1, 0, 1, 1, 0, 0, 1, 0, 1, 1]
受信側の検査余り(誤りなし) = [0, 0, 0]  -> 全0なら受理
1ビット誤り混入の検査余り = [0, 1, 1]  -> 非0なので誤り検出
----------------------------------------------
(n=7,k=4): Singleton限界 d_min <= n-k+1 = 4
(n=15,k=11): Singleton限界 d_min <= n-k+1 = 5
(n=255,k=223): Singleton限界 d_min <= n-k+1 = 33

出力の意味：データの CRC 剰余 $[0,1,1]$ を付けた送信語は、 $g(x)$ で割ると剰余0——正しく「 $g(x)$ の倍数」になっています。受信側で剰余0なら受理。1ビット誤りを混入させると剰余が $[0,1,1]$ と非0になり、誤りが検出されました（ただし位置は分からず訂正はしない）。下段の Singleton 限界は、 $(255,223)$ の RS 符号なら $d_{\min}\le33$ 、すなわち最大16シンボル訂正という設計上限を示します。CRC は軽量な見張り番、RS はバーストに強い訂正役、と役割分担が見えてきます。

5. 数式の直観的意味

符号の世界は「率 $R=k/n$ 」「最小距離 $d_{\min}$ 」「復号の計算量」の三つ巴です。ハミング符号は復号が軽い代わりに容量から遠く、RS はバーストに強く Singleton 限界を達成、LDPC・ポーラは容量に迫る代わりに長いブロックと反復復号が要る。シャノンの存在証明（シャノンの通信路符号化定理）が「容量近くの良い符号は存在する」と言ってから実物が出るまで半世紀かかったのは、「ランダム符号は良いが復号できない、構造を入れると復号できるが容量から離れる」というジレンマの解決が難しかったから。LDPC とポーラ符号はそのジレンマを別々の方法（疎なグラフ／通信路分極）で破り、いま手元のスマホで動いています。

⚠️ よくある誤解

「CRC は誤りを訂正できる」ではない：CRC は検出専用。訂正は再送（ARQ）か別の訂正符号に任せます。
「Singleton 限界はどの符号も達成できる」ではない：等号達成は MDS 符号（RS など）だけ。多くの2元符号は等号に届きません。
「ターボ・LDPC は容量を超える」ではない：あくまで容量に迫るだけ。シャノン限界 $C$ （通信路容量）は越えられません。
「現代は1つの最強符号がある」ではない：用途（スループット重視か低遅延・高信頼か、ブロック長）で最適な符号が違うので、5G でも LDPC とポーラを使い分けています。

対応シミュレーション

本文のコードで CRC の検出と Singleton 限界を実証済み。