Reed–Muller符号の理論と応用：定義・構成・復号・実装ガイド
エバープレイ編集部導入 — Reed–Muller符号とは何か
Reed–Muller符号（以下RM符号）は、1950年代にD. E. MullerとI. S. Reedによって独立に提案された線形ブロック符号の一群で、ブール多項式の全域評価を基礎に持ちます。パラメータが明示的に表現でき、再帰的な構成と復号アルゴリズムが存在するため、理論的解析と実装の両面で重要な役割を果たしてきました。長さや次元・距離を簡潔に定式化でき、古典的アルゴリズム（多数決復号、プロットキン構成）から近年のリスト復号や極性化（polar）符号との関連研究まで幅広い研究分野につながります。
基本定義とパラメータ
RM符号は2つの整数 r,m（0 ≤ r ≤ m）で指定され、記号でRM(r,m)と書きます。主なパラメータは次の通りです。
- 符号長 n = 2^m
- 次元 k = Σ_{i=0}^r C(m,i)（m個の変数について次数 ≤ r のブール多項式のモノミアル数）
- 最小距離 d = 2^{m-r}
いくつかの特別な場合は直観的に理解できます。例えばRM(0,m)は全ての座標が同じ1次元反復符号（繰り返し符号）、RM(m,m)は全空間（無検査符号）です。RM(1,m)はHadamard符号に対応し、次元はm+1、最小距離は2^{m-1}となります。
構成（ブール多項式の評価）
RM符号はブール多項式の評価ベクトルとして定義されます。具体的には、x_1,…,x_mをGF(2)上の変数とし、次数≤rの全てのモノミアルを考えます。各モノミアルは長さ2^mの評価ベクトル（GF(2)^m上の全ての入力点での値）を与え、これらを生成ベクトルとして線形結合することでRM(r,m)の全コード語が得られます。つまり、任意の次数≤rの多項式 f(x_1,…,x_m) に対して、コード語は (f(a))_{a ∈ GF(2)^m} です。
生成行列の行はモノミアルに対応し、順序付けは任意ですが、しばしば辞書式や次数別に並べます。この視点はエンコードを明確にし、また対称性（全座標に対する二項群の作用）を示します。
再帰的構成：Plotkin（u,u+v）構成
RM符号はPlotkin構成によって自然に再帰的に作れます。具体的には
RM(r,m) = { (u, u+v) | u ∈ RM(r,m-1), v ∈ RM(r-1,m-1) }
が成り立ちます。ここで左半分が u、右半分が u+v を表します。この表現は復号アルゴリズムを再帰的に設計する基盤になり、効率的なソフト／ハード的実装に適しています。初期条件はRM(r,0)やRM(0,m)の自明な符号です。
エンコード
エンコードはブール多項式の評価を計算することと同値です。生成行列による線形変換を使えば標準的に行えますが、より効率的には高速Walsh–Hadamard変換（FWHT）を用いた方法が有効です。計算量は直感的にはO(nk)ですが、構造を利用するとO(n log n)に近い実装が可能です（特にRM(1,m)などでFWHTが使える場合）。
復号アルゴリズム
RM符号は複数の復号法が存在します。主要なものを概説します。
- 多数決復号（majority-logic decoding）: 特にRM(1,m)などで歴史的に重要。局所的な多数決規則を繰り返すことでビットを決定する方式で、ハードウェア実装が容易です。
- 再帰復号（Plotkin再帰）: RM(r,m)をRM(r,m-1)とRM(r-1,m-1)に分け、両方を復号して組み合わせる。ソフト情報を扱うバージョンもあり、実際的な性能が良い。
- 最大事後確率(MAP)復号や最大尤度(ML)復号: 最良性能を出せるが計算コストが高い。小さなmやList decodingと組み合わせる場合に利用。
- リスト復号やソフト出力復号: 近年の研究でSCL（Successive Cancellation List）に類似の手法や、信頼度情報を使った改良アルゴリズムが示されています。RMと極性化（polar）符号の類似性から、類似したデコーダ設計が可能です。
誤り訂正能力は最小距離dから得られる整数訂正量 t = ⌊(d-1)/2⌋ が理論的限界の一つです。ただし実際の復号アルゴリズムはこの限界より悪くなることがあり、リスト化やソフト復号で補うことが多いです。
双対符号と恒等関係
RM符号の重要な代数的性質として双対性の閉じた形が知られています。
RM(r,m)⊥ = RM(m-r-1,m)
この関係は多項式的性質と評価の直交性から導かれ、RM符号が自己相補的な階層構造を持つことを示しています。特殊ケースとしてRM(m-1,m)は単一パリティチェック（全体で偶奇）に関連します。
性能と限界
RM符号は構造化された距離と次元を持つため、最低距離解析や重み分布の理論的評価が可能です。組合せ的解析により重み分布が部分的に明らかになりますが、一般のr,mに対する完全な閉形式は難しい場合があります。現実的な通信系では、符号率と誤り率（FER/BER）を見て復号アルゴリズムを選ぶことになります。
応用例・最新動向
RM符号は以下のような分野で使われます。
- 組み込みシステム・初期の通信ハードウェアでの多数決復号実装。
- 理論情報工学：局所性、自己同形性、古典的符号理論の研究対象。
- 近年の研究：RM符号とpolar符号の関係（極性化順序の調整で性能が近づくこと）、リスト復号性能の解析、漸近的性能に関する理論研究など。
- 暗号や秘密分散、テスト理論など数学的性質を活かした応用研究。
注意点として、RM符号は構造が強いため最適（ML）復号を行えば非常に良好な性能を示すことが多い一方で、計算量の面で実用的な制約があり、低レート・中レートで有利に働くことが多いです。
実装上の注意点
実装時は次の点に注意してください。
- 効率的なエンコードはFWHTを活用できる場合がある（特に一次RMなど）。
- 再帰復号はスタック／再帰深度に注意。メモリ管理やソフト信頼度の格納形式が実装効率に影響する。
- リスト復号や軟判定を行う場合、候補数（リストサイズ）と計算負荷のトレードオフを設計する必要がある。
- パラメータ選定（r,m）は目的の符号率と誤り耐性から決める。設計時にn=2^mなので長さ調整は2のべき乗単位になる。
簡単な例（m=3, r=1）
RM(1,3)は n=8, k=C(3,0)+C(3,1)=1+3=4, d=2^{3-1}=4 を持ちます。生成多項式集合は {1, x1, x2, x3} に対応し、評価により4行×8列の生成行列が得られます。これはHadamard行列を基にした符号であり、相関復号（Walsh変換に基づく）で効率よく復号できます。
まとめ
Reed–Muller符号はブール多項式の評価に基づく明快な構造、再帰的なPlotkin構成、明確なパラメータ式（n=2^m, k=ΣC(m,i), d=2^{m-r}）を備えた古典かつ現在でも研究が盛んな符号です。実用面では復号アルゴリズム選択と計算資源の制約が重要になりますが、理論面では双対性や極性化符号との関係など多くの興味深い性質があります。最新の研究動向では、復号性能の向上やpolar符号との橋渡し、リスト復号とソフト復号の手法が進展しています。
参考文献
以下はRM符号の理解・実装に役立つ参考資料です。
- Reed–Muller code — Wikipedia
- Reed–Muller codes (lecture notes)
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes
- J. H. van Lint, Introduction to Coding Theory
- I. Dumer, Recursive decoding and its performance for Reed–Muller codes (IEEE Trans. on Information Theory)
- Walsh–Hadamard transform — Wikipedia
投稿者プロフィール
