線型誤り訂正符号とは何か──理論・実装・応用を深堀する
エバープレイ編集部導入：線型誤り訂正符号の位置付け
線型誤り訂正符号（linear error-correcting codes）は、デジタル通信やデータストレージにおける誤り検出・訂正の基盤を成す数学的構造です。特に「線型符号」は、符号語集合が有限体上の線型部分空間をなすという性質を持ち、代数的手法により設計・解析・実装が行いやすいことから広く用いられています。本コラムでは、数学的定義から代表的な符号族、符号の設計・復号アルゴリズム、理論的限界、実務上の応用と実装上の注意点までを詳しく解説します。
数学的定義と基本概念
長さ n、情報長 k の線型符号 C は、有限体 GF(q) 上の k 次元部分空間として定義されます。しばしばパラメータを (n,k,d) として表し、d は符号の最小ハミング距離です。符号率は R=k/n で、誤り訂正能力は ⌊(d-1)/2⌋ ビット誤りまでの訂正が保証されます。
線型符号は次の二つの行列表現で扱うのが基本です。
- 生成行列 G（k×n）：任意の情報ベクトル u∈GF(q)^k に対して符号語 c=uG で与えられる。
- 検査行列（パリティ検査行列）H（(n-k)×n）：符号語 c は Hc^T=0 を満たす（全ての符号語が H の零空間）。
系統符号化（systematic encoding）では G を [I_k | P] の形に変換し、符号語は元の情報ビットをそのまま含む形で生成されます。パリティ検査行列は一般に H=[-P^T | I_{n-k}]（有限体上での演算）となります。
代表的な線型符号の種類
- ハミング符号（Hamming codes）：短距離（通常 d=3）ながら単一誤りを検出・訂正するための古典的かつ構造が単純な線型符号。n=2^m-1, k=n-m の形を取る。
- BCH符号：任意の設計最小距離 d を達成できる可変長の二項または多項体上の巡回符号で、代数的復号アルゴリズムが存在する。
- リード・ソロモン符号（Reed–Solomon, RS）：GF(q) 上の多項式評価符号で、シンボル誤り（バースト誤り）に強い。BCH 同様、代数的復号アルゴリズム（Berlekamp–Massey、Euclid）が適用可能。
- 畳み込み符号やターボ符号、LDPC符号：畳み込み形式や疎パリティを利用し、反復復号や確率的復号（BPアルゴリズム）で近似的に良好な誤り率を実現する近代的手法。
復号アルゴリズムの基本
復号は大きく最尤復号（ML decoding）と近似復号に分かれます。一般に、最尤復号は計算量が指数的であり（一般線形符号の復号は NP-困難と知られる）、実用的には代数的復号や反復復号（belief propagation）などの多項式時間アルゴリズムが用いられます。
- シンドローム復号：受信語 r に対して syndrome s=Hr^T を計算し、s に基づいて誤りパターンを特定する方法。ハミング符号や一般的な線型符号の基本手法。
- 代数的復号（BCH/RS 用）：受信信号から誤り位置多項式や誤り評価多項式を求める。代表的手法に Berlekamp–Massey アルゴリズムや拡張ユークリッド法、Chien 検査がある。
- 反復復号（LDPC、ターボ）：グラフ表現（因子グラフ）上で確率的メッセージパッシングを行い、近似的に高性能な復号を達成する。
実際の応用では、チャネル特性に応じてハード判定（ビット単位の 0/1）やソフト判定（信頼度を用いた復号）を選択します。ソフト判定を使うと、同じ符号でも性能が大きく改善します。
理論的限界と評価指標
符号設計では «符号率 R»、«最小距離 d»、«復号複雑度» のトレードオフが常に存在します。いくつかの重要な限界と不等式：
- ハミング界（Hamming bound）：単一・複数誤り訂正に対する球被覆の限界。
- Singleton 不等式：d ≤ n − k + 1（最大距離分離符号, MDS 符号は等号を満たす。RS 符号は MDS の代表）。
- ギルバート–ヴァルシャノフ境界（Gilbert–Varshamov bound）：一定のパラメータ範囲で存在保証を与える下界。
さらに、重み分布（weight enumerator）や MacWilliams 恒等式は、符号とその双対符号の性質を結び付け、誤り率解析や性能評価に有益です。
実用的な設計と実装上の注意点
システムに組み込む際の主要な考慮点：
- チャネル特性の理解：ビット誤り率（BER）やバースト誤りの有無により適切な符号（BSC/BEC 向け、バースト耐性が必要なら RS 等）を選ぶ。
- パラメータ選定：必要な誤り訂正能力と透過レートのバランスを取り、計算リソース（CPU、メモリ、遅延）に応じた復号アルゴリズムを決める。
- ハードウェア実装：FPGA や ASIC での実装では、多項式演算や有限体乗算の効率化、パイプライン化、並列度の最適化が鍵となる。ソフト実装ではメモリ局所性やSIMD命令の活用が重要。
- 誤り検出との組合せ：CRC と組み合わせることで、残存エラー検出能力を補完し、誤り伝搬の検出やフレーム破棄判断を行う。
現実世界での応用例
- データストレージ：RAID、SSD 内部、磁気ディスク・光ディスク（CD、DVD）では BCH や RS が広く使用される。
- 通信：衛星通信や携帯通信、無線LAN などでは LDPC やターボ符号が採用され、スペクトル効率を高める。
- バーコード・QRコード：誤り訂正機能（RS 系）により汚損や欠損に強い。
- 深宇宙通信：極めて低い信号対雑音比の環境下で、高性能な符号（LDPC, RS など）と軟判定復号を用いる。
例：符号化とシンドローム復号の概念（概略）
系統符号化の一般的な流れは、情報ベクトル u を生成行列 G で符号語 c=uG に変換して送信し、受信側で r を受け取り s=Hr^T を計算して誤りパターン e を推定することです。もし s=0 なら誤りなし（または誤りが符号空間に属する）と判断します。シンドロームマップ（s→e）を事前にテーブル化しておけば高速復号が可能ですが、n が大きいと現実的ではありません。
高度な話題（概観）
符号理論は符号設計だけでなく、暗号（暗号学的ハードネスを利用した McEliece 暗号など）、圧縮、分散保存（分散ストレージの符号化）、ネットワーク符号化といった分野へも拡張されます。さらに、有限体の代数的構造やグロースマン束縛、有限幾何を用いた符号構成の研究も活発です。
まとめと設計アドバイス
線型誤り訂正符号は理論的にも実用的にも奥が深く、適切な符号選択と復号アルゴリズムの組合せによってシステム性能が大きく変わります。設計時はまずチャネル特性と要求性能（許容エラー率、遅延、計算資源）を明確にし、標準化された符号（RS、BCH、LDPC、ターボなど）を候補に実測評価を行うことが近道です。
参考文献
- Linear code - Wikipedia
- Hamming code - Wikipedia
- Reed–Solomon error correction - Wikipedia
- BCH code - Wikipedia
- Vardy, A., "The intractability of computing the minimum distance of a code" (1997)
- F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes"（参考書）
- S. Lin and D. J. Costello, "Error Control Coding"（教科書）
投稿者プロフィール
