線形コード入門：理論、主要手法、実践的応用まで詳解

線形コードとは何か

線形コード（linear code）は、有限体 F_q 上のベクトル空間の部分空間として定義される誤り訂正符号の一種です。特に二元（q=2）の場合はバイナリ線形コードと呼ばれ、電気通信やデータストレージで広く用いられます。線形性により数学的取り扱いが容易になり、符号設計や復号アルゴリズムの効率化が可能になります。

基本的な定義と記法

長さ n、次元 k の q-進線形コードは一般に [n,k,d]_q と表記されることが多く、ここで d は最小ハミング距離です。コードは k 次元部分空間なので、符号語は長さ n のベクトルで、全コード語の数は q^k です。

• 生成行列 G： k×n 行列で、情報ベクトル u (長さ k) に対し符号語 c = uG が得られる。
• 検査行列 H： (n−k)×n 行列で、任意符号語 c は Hc^T = 0 を満たす（つまり H の行空間の直交補空間がコード）。
• 最小距離 d：0 でない符号語の最小ハミング重み（非ゼロシンボルの個数）。訂正能力 t = floor((d−1)/2)。

生成行列と検査行列の関係

生成行列 G と検査行列 H は GH^T = 0 を満たします。任意の線形コードはガウスの消去法によって標準形（例：G = [I_k | P]）に変形でき、対応する検査行列は H = [−P^T | I_{n−k}] と表されます。この標準形は符号化（エンコード）やシンドローム計算を単純化します。

シンドロームと復号の基本

受信ベクトル r = c + e（c は送信符号語、e は誤りベクトル）に対してシンドローム s = Hr^T = He^T が得られます。シンドロームは誤りの同値類を示す情報で、同じシンドロームを持つ誤りは同じ方法で訂正されます。シンドローム復号では事前にシンドローム表（誤りパターンと最小重み代表の対応表）を作成し、受信時に対応する誤りを引くことで復号します（標準配列法）。

主要な線形コードの例

• ハミング符号：最小距離 d=3 を持つ単純で効率的な単一誤り訂正符号。パリティ検査行列は全非ゼロ列を並べたものになる（長さ n = 2^m − 1）。
• 単純符号（Repetition）とパリティ検査符号：構造が簡単で誤り検出や繰り返しに使用。
• リード＝ソロモン符号（RS符号）：非バイナリ（q が大きい有限体）で最大距離分離（MDS）符号の代表。ブロック長 n ≤ q−1、情報長 k に対し d = n−k+1 を達成する。多くのストレージや光学メディア、CD、QRコードで使用。
• 低密度パリティ検査符号（LDPC）：パリティ検査行列が疎で、反復ベリーフプロパゲーション（メッセージパッシング）で高性能な復号が可能。近年の通信規格で採用。

最小距離と誤り検出・訂正能力

最小距離 d は符号の性能指標で、(d−1) 個の誤りを検出でき、floor((d−1)/2) 個の誤りを必ず訂正できます。最小距離の解析には重み分布（重み列挙多項式）が重要で、これにより符号の誤り発生確率や性能評価が可能になります。

重要な不等式と限界

線形符号設計ではいくつかの理論的限界が設けられており、設計目標の妥当性を評価するために用いられます。

• ハミング界（Hamming bound）：任意の符号語が占める球の体積の和が全空間の体積を超えない条件。
• シングルトン界（Singleton bound）：d ≤ n−k+1、リード＝ソロモン符号はこの界を満たす（MDS 符号）。
• Gilbert–Varshamov bound：存在可能な符号の下限を与え、実用的な探索目標となる。

復号アルゴリズムの概要

復号は符号の種類により手法が異なり、計算量と性能のトレードオフがあります。

• シンドローム復号（標準配列、表探索）：短いコードや小さい誤り重みに対して有効。
• 最大尤度復号（ML）：理論上最良だが計算量が指数的。小規模コードで使われる。
• 代数的復号（例：リード＝ソロモンに対するBerlekamp–Massey、Euclid 法）：有限体上の多項式操作に基づく効率的アルゴリズム。
• 反復復号・確率的手法（例：LDPCのベルリーフ・プロパゲーション、タービン符号の双方向反復法）：高い実用性能と線形時間近傍の計算量。

双対コードとその役割

ある線形コード C の双対 C^⊥ は、C と直交する全ベクトルからなるコードで、検査行列 H の行空間はそのまま C^⊥ を生成します。双対コードの性質は符号設計や暗号（例：McEliece 暗号の基礎理論）などで重要です。また自己双対符号や等距離性の議論にも登場します。

実践での設計課題と実装上の注意点

実システムに線形コードを組み込む際は、以下の点に注意する必要があります。

• 符号率（k/n）と耐誤り性のバランス。高い符号率は効率的だが耐誤り性は低下する。
• 復号アルゴリズムの計算量と遅延。リアルタイム通信では遅延制約が重要。
• 有限体演算（特に非バイナリ符号）に関連する実装コスト。ハードウェアでの最適化が鍵。
• 乱れやチャネル特性に適した符号選択（フェージング、バースト誤り対策など）。特定用途では畳み込み符号やターボ、LDPC と RS の組み合わせが使われる。

応用事例

• データストレージ：RAID、分散ストレージシステムではリード＝ソロモン符号やローカル再構成符号（LRC）が使われる。
• 通信：衛星通信、深宇宙通信、モバイル通信規格では誤り制御符号が不可欠。LDPC とターボ符号はブロードバンド無線で採用。
• バーコードや光学メディア：CD、DVD、QR コードに RS や畳み込み符号が使用。

最近の動向

近年は低復号複雑度で高性能を実現する符号（LDPC、Polar 符号など）や、分散ストレージ向けの局所復旧特性を持つ符号、量子誤り訂正符号の研究が活発です。線形コード理論は新しいチャネルモデルや実装技術の発展に伴い進化を続けています。

まとめ

線形コードは数学的に美しく、実装可能性と理論性能が高い誤り訂正符号の基本です。生成行列と検査行列、シンドローム復号、最小距離の概念を理解することで、さまざまな符号設計や復号アルゴリズムの選択が可能になります。用途に応じた符号の選定（例：リアルタイム通信向けは低遅延の反復符号、長期保存向けはMDS系のRS符号）は実務上重要です。

参考文献

• Linear code - Wikipedia
• Hamming code - Wikipedia
• Reed–Solomon error correction - Wikipedia
• Low-density parity-check code - Wikipedia
• Shu Lin, Daniel J. Costello, Jr., "Error Control Coding: Fundamentals and Applications" (Pearson)
• J. H. van Lint, "Introduction to Coding Theory" (Springer)

投稿者プロフィール

エバープレイ編集部

最新の投稿

• 書籍・コミック2025.12.16推理小説の魅力と技法──歴史・ジャンル・読み方・書き方を徹底解説
• 用語2025.12.16イヤモニ完全ガイド：種類・選び方・安全な使い方とプロの活用法
• 用語2025.12.16曲管理ソフト完全ガイド：機能・選び方・おすすめと運用のコツ
• 用語2025.12.16オーディオ機材徹底ガイド：機器選び・設置・音質改善のすべて