1972年、NASAの惑星探査機マリナー9号は火星の表面写真を地球へ送り届けました。火星と地球のあいだは数億キロメートル離れており、探査機の送信電力はわずか数十ワットしかありません。電波は宇宙空間を旅するあいだに薄まり、地球に届くころにはノイズに埋もれかけています。それでも鮮明な白黒写真が再構成できたのは、画像データを Reed-Muller符号 で守っていたからです。マリナー9号が使ったのは RM(1, 5) という符号で、6ビットの情報を32ビットに膨らませて送ることで、受信側でビットが多少化けても元の画像を正しく復元できました。
なぜこんなことが可能なのでしょうか。鍵は「冗長性を賢く設計する」ことにあります。ただやみくもにビットを増やすのではなく、ブール多項式という数学的な構造を使って符号語を作ると、復号のときに 多数決 という驚くほど単純で頑健な手続きで誤りを訂正できるのです。Reedの多数決復号は、各情報ビットを「多くの独立した投票」から推定するため、いくつかの票が誤りで汚れても、過半数が正しければ正解にたどり着けます。
Reed-Muller符号を学ぶと、次のような場面で役立つ知識が手に入ります。
- 深宇宙通信・衛星通信: 送信電力が極端に制限される環境で、低い符号化率でも確実にデータを守る設計の考え方
- 計算量理論・組合せ論: ブール関数の次数と誤り訂正能力の関係は、局所復号可能符号（locally decodable codes）や確率的検証（PCP定理）など現代の理論計算機科学の基礎にもつながります
本記事の内容
- Reed-Muller符号 RM(r, m) をブール多項式の評価ベクトルとして構成する直感と定義
- 符号長 $2^m$・次元 $\sum_{i=0}^{r}\binom{m}{i}$・最小距離 $2^{m-r}$ の導出（省略なし）
- RM(1, 3) が拡張ハミング符号の双対であることなどの具体例
- Reedの多数決復号アルゴリズムのPythonスクラッチ実装と、誤りを注入した受信語が訂正される様子の検証
この記事の全体像を1枚にまとめたのが上の図です。情報ビット（多項式の係数 $c_S$）から次数 $r$ 以下のブール多項式を作り、それを $\mathbb{F}_2^m$ の全 $2^m$ 点で評価して符号語にします。次数を $r$ に制限することが「符号語どうしを遠ざけ、多数決で誤りを直せる」という性質の源になっている、という流れを押さえておいてください。
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 誤り訂正符号とは？仕組みをわかりやすく解説 — 冗長性で誤りを直すという発想の出発点
- 線形ブロック符号の理論 — 生成行列・パリティ検査行列・最小距離・符号化率の基礎
- ハミング符号の理論 — 最小距離と訂正能力の関係、シンドローム復号の具体例
線形代数（特に $\mathbb{F}_2$ 上のベクトル空間と行列）と、ブール代数の基礎（AND・XOR）を知っていると読みやすくなります。
Reed-Muller符号とは — 「真理値表を符号語にする」
いきなり定義を出す前に、Reed-Muller符号がどんな発想で作られているかをイメージしましょう。
私たちはふだん、ブール関数を「真理値表」で表します。たとえば3変数の関数 $f(x_1, x_2, x_3)$ なら、$(x_1, x_2, x_3)$ が取りうる8通りの入力それぞれに対して、出力が0か1かを並べた長さ8の表になります。この 出力を並べた長さ8の列ベクトル こそが、Reed-Muller符号の符号語です。
ここがポイントです。Reed-Muller符号は「あるブール関数の真理値表まるごと」を1つの符号語と見なします。そして、どんなブール関数を許すかに制限をかけることで、符号としての性質をコントロールします。具体的には、多項式の次数を $r$ 以下に制限 します。
なぜ次数を制限すると誤り訂正ができるのでしょうか。直感的には、低次の多項式は「なめらか」で、ところどころのビットが化けても全体の形からそれが見抜けるからです。たとえば1次多項式（平面）は、空間に広く広がった単純な形なので、数点が外れていても「本来の平面」を推定できます。逆に、高次多項式は複雑にうねるので、誤りと本来の値の区別がつきにくくなります。次数 $r$ を小さくするほど符号語どうしが「遠く」なり、たくさんの誤りを訂正できる——これが後で導く最小距離 $2^{m-r}$ の正体です。
もう少し丁寧に言葉で定義します。変数の個数を $m$、許す多項式の最大次数を $r$ とするとき、$r$ 次以下の $m$ 変数ブール多項式すべての評価ベクトルの集合 が Reed-Muller符号 $\mathrm{RM}(r, m)$ です。ここで「評価ベクトル」とは、その多項式を $\mathbb{F}_2^m$ のすべての点（$2^m$ 個）で評価して並べたものを指します。
この「多項式 ↔ 真理値表（評価ベクトル）」という対応をしっかり押さえると、あとの導出はすべて見通しよく進みます。次の節では、この対応を数式できちんと定義していきましょう。
ブール多項式と評価ベクトルの定義
まず、扱う多項式の世界をきちんと決めます。変数は $x_1, x_2, \dots, x_m$ で、それぞれ $\mathbb{F}_2 = \{0, 1\}$ の値を取ります。$\mathbb{F}_2$ では加算は XOR（$1+1=0$）、乗算は AND です。
$\mathbb{F}_2$ では $x^2 = x$ が常に成り立ちます（$0^2=0$, $1^2=1$）。ですから、同じ変数を2回以上掛けても意味がなく、各変数は「掛けるか掛けないか」の2択だけです。したがって意味のある 単項式（モノミアル） は、変数の部分集合 $S \subseteq \{1, \dots, m\}$ を選んで
$$ \begin{equation} x_S = \prod_{i \in S} x_i \end{equation} $$
と書けるものに限られます。空集合 $S = \emptyset$ のときは積が空なので $x_\emptyset = 1$（定数項）と約束します。
単項式 $x_S$ の 次数 は、掛けている変数の個数 $|S|$ です。次数が $d$ の単項式は $\binom{m}{d}$ 個あります（$m$ 個から $d$ 個を選ぶ選び方）。
任意のブール多項式は、これらの単項式の $\mathbb{F}_2$ 上の線形結合（係数が0か1）で一意に書けます。
$$ \begin{equation} f(\bm{x}) = \sum_{S \subseteq \{1,\dots,m\}} c_S \, x_S, \qquad c_S \in \{0, 1\} \end{equation} $$
この表現を 代数正規形（Algebraic Normal Form, ANF） と呼びます。$m$ 変数では部分集合が $2^m$ 個あるので、係数 $c_S$ も $2^m$ 個あり、これがすべてのブール関数（$2^{2^m}$ 通り）を尽くします。
評価ベクトル
次に、多項式を「数列」に変換します。$\mathbb{F}_2^m$ の点をある決まった順序で $\bm{p}_0, \bm{p}_1, \dots, \bm{p}_{2^m – 1}$ と並べておきます（後の実装では $j$ の2進表現を点 $\bm{p}_j$ とします）。多項式 $f$ の 評価ベクトル を
$$ \begin{equation} \mathrm{ev}(f) = \big( f(\bm{p}_0),\ f(\bm{p}_1),\ \dots,\ f(\bm{p}_{2^m – 1}) \big) \in \mathbb{F}_2^{2^m} \end{equation} $$
と定義します。これは長さ $2^m$ のビット列、すなわち先ほど言った「真理値表」そのものです。
特に重要なのが、各変数 $x_i$ そのものの評価ベクトルです。$x_i$ の評価ベクトルは「$i$ 番目の座標が1である点で1、それ以外で0」というビット列になります。たとえば $m=3$ で点を $000, 001, 010, \dots, 111$ の順に並べると、$x_1$（最上位ビット）の評価ベクトルは
$$ \mathrm{ev}(x_1) = (0,0,0,0,1,1,1,1) $$
となります。同様に $\mathrm{ev}(x_2) = (0,0,1,1,0,0,1,1)$、$\mathrm{ev}(x_3) = (0,1,0,1,0,1,0,1)$ です。そして単項式 $x_S$ の評価ベクトルは、含まれる変数の評価ベクトルの 成分ごとの積（AND） で得られます。
$$ \begin{equation} \mathrm{ev}(x_S) = \bigodot_{i \in S} \mathrm{ev}(x_i) \end{equation} $$
ここで $\bigodot$ は成分ごとの積を表します。たとえば $\mathrm{ev}(x_1 x_2) = \mathrm{ev}(x_1) \odot \mathrm{ev}(x_2)$ です。
この「単項式 → 評価ベクトル」という写像が、生成行列の各行をそのまま与えてくれます。次の節で、$\mathrm{RM}(r,m)$ の生成行列を正式に組み立てましょう。
RM(r, m) の生成行列
線形符号は生成行列 $\bm{G}$ で完全に決まります。$\bm{G}$ の各行が「基底となる符号語」であり、情報ベクトル $\bm{u}$ を符号語 $\bm{c} = \bm{u}\bm{G}$ に写します。
Reed-Muller符号 $\mathrm{RM}(r, m)$ の生成行列は、次数 $r$ 以下のすべての単項式の評価ベクトルを行として並べたもの です。
$$ \begin{equation} \bm{G}_{\mathrm{RM}(r,m)} = \begin{bmatrix} \mathrm{ev}(x_S) \end{bmatrix}_{|S| \le r} \end{equation} $$
行は慣例として次数の低い順に並べます。すなわち、
- 次数0: $\mathrm{ev}(1)$ — 全成分1の行（1行）
- 次数1: $\mathrm{ev}(x_1), \dots, \mathrm{ev}(x_m)$（$m$ 行）
- 次数2: $\mathrm{ev}(x_i x_j)$（$\binom{m}{2}$ 行）
- $\vdots$
- 次数 $r$: $\mathrm{ev}(x_S)$, $|S| = r$（$\binom{m}{r}$ 行）
の順です。
行の総数、つまり符号の 次元 $k$ は、次数0から $r$ までの単項式の個数を足したものです。
$$ \begin{equation} k = \dim \mathrm{RM}(r, m) = \sum_{i=0}^{r} \binom{m}{i} \end{equation} $$
そして列数（評価する点の個数）が 符号長
$$ \begin{equation} n = 2^m \end{equation} $$
です。情報ベクトル $\bm{u} = (c_\emptyset, c_{\{1\}}, \dots)$ は各単項式の係数 $c_S$ を並べたものになります。符号化 $\bm{c} = \bm{u}\bm{G}$ は、まさに多項式 $f = \sum_S c_S x_S$ を作って全点で評価する操作にほかなりません。
ここで生成行列の各行が一次独立であることを確認しておきましょう。これがないと「次元が $k$」と言い切れません。異なる単項式の評価ベクトルは $\mathbb{F}_2$ 上で一次独立です。理由は、もし非自明な線形結合がゼロベクトルになれば、その結合に対応する非ゼロ多項式がすべての点で0となり「恒等的に0の多項式」になりますが、ANFは一意なので非ゼロ多項式が恒等的に0になることはなく、矛盾するからです。よって行は一次独立で、ランクは確かに $k$ です。
生成行列が決まったので、次は符号の最も重要な性能指標である 最小距離 を導出します。
最小距離 2^{m-r} の導出
線形符号では、最小距離 $d$ は「ゼロでない符号語の最小ハミング重み（1の個数）」に等しいことが知られています（線形ブロック符号の理論 参照）。符号語は多項式の評価ベクトルなので、
$$ d = \min_{f \ne 0,\ \deg f \le r} \mathrm{wt}\big(\mathrm{ev}(f)\big) $$
を求めればよいわけです。ここで $\mathrm{wt}$ は評価ベクトルの中の1の個数、つまり $f(\bm{x}) = 1$ となる点の個数 です。
主張は次の通りです。
$$ \begin{equation} d = 2^{m-r} \end{equation} $$
これを2段階で示します。まず「重み $2^{m-r}$ の符号語が存在する」こと（上界）、次に「ゼロでない符号語の重みは必ず $2^{m-r}$ 以上」であること（下界）です。
ステップ1: 重み 2^{m-r} の符号語が存在する
次数ちょうど $r$ の単項式 $f = x_1 x_2 \cdots x_r$ を考えます。これは $r$ 個の変数の積です。$f(\bm{x}) = 1$ となるのは、$x_1 = x_2 = \dots = x_r = 1$ のときだけです。
このとき残りの変数 $x_{r+1}, \dots, x_m$（$m – r$ 個）は自由に0か1を取れるので、$f = 1$ となる点は $2^{m-r}$ 個あります。よって
$$ \mathrm{wt}(\mathrm{ev}(x_1 \cdots x_r)) = 2^{m-r} $$
これで重み $2^{m-r}$ の符号語が確かに存在することがわかりました。つまり最小距離は $2^{m-r}$ 以下です。
ステップ2: ゼロでない符号語の重みは 2^{m-r} 以上
下界の証明には、変数の数 $m$ についての 数学的帰納法 を使います。$\deg f \le r$ かつ $f \not\equiv 0$ なら $\mathrm{wt}(\mathrm{ev}(f)) \ge 2^{m-r}$ を示します。
まず基礎となるケースを押さえます。$r = 0$ のとき、$f$ は定数0か1で、$f \ne 0$ なら $f \equiv 1$、重みは $2^m = 2^{m-0}$ ですからちょうど一致します。また $r \ge m$ のときは $2^{m-r} \le 1$ で、$f \ne 0$ なら少なくとも1点で1なので重み $\ge 1$ となり成立します。これらの端のケースを除いて、$1 \le r < m$ で考えます。
ここで、$f$ を最後の変数 $x_m$ について整理します。$\mathbb{F}_2$ では $x_m^2 = x_m$ なので、$f$ は $x_m$ について高々1次です。よって
$$ \begin{equation} f(x_1, \dots, x_m) = g(x_1, \dots, x_{m-1}) + x_m \, h(x_1, \dots, x_{m-1}) \end{equation} $$
と一意に分解できます。$g$ は $x_m$ を含まない項を集めたもの、$h$ は $x_m$ が掛かっている項から $x_m$ を外したものです。次数について、$\deg g \le r$、そして $x_m h$ の次数が $r$ 以下なので $\deg h \le r – 1$ が成り立ちます。
評価ベクトルを $x_m = 0$ の半分と $x_m = 1$ の半分に分けて考えます。
- $x_m = 0$ の $2^{m-1}$ 点では $f = g$
- $x_m = 1$ の $2^{m-1}$ 点では $f = g + h$
したがって全体の重みは2つの部分の和です。
$$ \begin{equation} \mathrm{wt}(\mathrm{ev}(f)) = \mathrm{wt}(\mathrm{ev}(g)) + \mathrm{wt}(\mathrm{ev}(g + h)) \end{equation} $$
ここで場合分けをします。
ケースA: $h \equiv 0$ のとき。 このとき $f = g$ で、$g$ は $m-1$ 変数の次数 $\le r$ の非ゼロ多項式です。$x_m=0$ 側と $x_m=1$ 側の両方で $f=g$ となり、重みは $g$ の重みの2倍です。帰納法の仮定（$m-1$ 変数で成立）より $\mathrm{wt}(\mathrm{ev}(g)) \ge 2^{(m-1)-r}$ なので、
$$ \mathrm{wt}(\mathrm{ev}(f)) = 2\,\mathrm{wt}(\mathrm{ev}(g)) \ge 2 \cdot 2^{m-1-r} = 2^{m-r} $$
ケースB: $h \not\equiv 0$ のとき。 $h$ は $m-1$ 変数の次数 $\le r-1$ の非ゼロ多項式です。帰納法の仮定より $\mathrm{wt}(\mathrm{ev}(h)) \ge 2^{(m-1)-(r-1)} = 2^{m-r}$ です。ここで、ハミング重みに対する三角不等式（$\mathbb{F}_2$ では $\mathrm{wt}(a) + \mathrm{wt}(a+b) \ge \mathrm{wt}(b)$ が成り立つ）を $a = \mathrm{ev}(g)$, $b = \mathrm{ev}(h)$ に適用します。実際 $a + (a+b) = b$ なので、両者の重みの和は $b$ の重み以上です。これを上の重みの分解式に当てはめると、
$$ \mathrm{wt}(\mathrm{ev}(f)) = \mathrm{wt}(\mathrm{ev}(g)) + \mathrm{wt}(\mathrm{ev}(g+h)) \ge \mathrm{wt}(\mathrm{ev}(h)) \ge 2^{m-r} $$
どちらのケースでも $\mathrm{wt}(\mathrm{ev}(f)) \ge 2^{m-r}$ が示せました。帰納法により、すべての $m$ で下界が成立します。
ステップ1とステップ2を合わせると、最小距離はちょうど $d = 2^{m-r}$ です。最小距離が $d$ の符号は $t = \lfloor (d-1)/2 \rfloor$ 個までの誤りを訂正できるので、$\mathrm{RM}(r,m)$ は
$$ \begin{equation} t = \left\lfloor \frac{2^{m-r} – 1}{2} \right\rfloor = 2^{m-r-1} – 1 \end{equation} $$
個までの誤りを訂正できます（$r < m$ のとき）。
導出が完了しました。これで $\mathrm{RM}(r,m)$ は $[n, k, d] = [2^m,\ \sum_{i=0}^r \binom{m}{i},\ 2^{m-r}]$ という3つの基本パラメータを持つことがわかりました。次に、具体的な小さい符号でこれらの数値を確かめ、RM(1,3) が拡張ハミング符号の双対であることを見ていきます。
具体例: RM(1, 3) と双対関係
数値を入れて感覚を掴みましょう。$m = 3$、$r = 1$ の $\mathrm{RM}(1, 3)$ を作ります。
- 符号長: $n = 2^3 = 8$
- 次元: $k = \binom{3}{0} + \binom{3}{1} = 1 + 3 = 4$
- 最小距離: $d = 2^{3-1} = 4$
つまり $[8, 4, 4]$ 符号で、$t = 2^{3-1-1} – 1 = 1$ 個の誤りを訂正できます。生成行列は次数0と次数1の単項式の評価ベクトルからなる4行です。
$$ \bm{G}_{\mathrm{RM}(1,3)} = \begin{bmatrix} \mathrm{ev}(1) \\ \mathrm{ev}(x_1) \\ \mathrm{ev}(x_2) \\ \mathrm{ev}(x_3) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix} $$
上の図は、実際に rm_generator(1, 3) で構成した生成行列 $\bm{G}$ を色分けしたものです。各列は評価点 $x_1x_2x_3$ の2進表現に対応し、1行目が全成分1（定数項 $\mathrm{ev}(1)$）、2〜4行目が各変数 $x_1, x_2, x_3$ の評価ベクトルになっていることが見て取れます。手で書いた行列とビット単位で完全に一致しています。
この $[8,4,4]$ 符号は 拡張ハミング符号 と呼ばれるものと同じです。元の $[7,4,3]$ ハミング符号（ハミング符号の理論 参照）に全体パリティビットを1つ追加すると、最小距離が3から4へ上がり $[8,4,4]$ になります。$\mathrm{RM}(1,3)$ はこの拡張ハミング符号と等価なのです。
さらに美しい性質として、双対関係 があります。一般に $\mathrm{RM}(r, m)$ の双対符号は $\mathrm{RM}(m – r – 1, m)$ です。
$$ \begin{equation} \mathrm{RM}(r, m)^\perp = \mathrm{RM}(m – r – 1, m) \end{equation} $$
$m = 3$, $r = 1$ では双対は $\mathrm{RM}(3 – 1 – 1, 3) = \mathrm{RM}(1, 3)$ となり、自己双対 です。一方 $\mathrm{RM}(1, 3)$ を「拡張ハミング符号」と見ると、その双対は「拡張ハミング符号の双対 = 第1次のシンプレックス符号に全1行を足したもの」と一致し、これも $\mathrm{RM}(1,3)$ に戻ります。双対の次元は $n – k = 8 – 4 = 4$ で、$\mathrm{RM}(1,3)$ の次元4と一致するので、自己双対であることが次元からも確認できます。
念のため次元の足し算も確認しておきましょう。$\dim \mathrm{RM}(r,m) + \dim \mathrm{RM}(m-r-1, m) = n$ が成り立つはずです。$\sum_{i=0}^{r}\binom{m}{i} + \sum_{i=0}^{m-r-1}\binom{m}{i}$ を考えると、後者は $\binom{m}{i} = \binom{m}{m-i}$ を使って $\sum_{i=r+1}^{m}\binom{m}{i}$ と書き直せます。両者を足すと $\sum_{i=0}^{m}\binom{m}{i} = 2^m = n$ となり、確かに双対の次元の和が符号長に一致します。
もう一つ、有名な符号を挙げておきます。$\mathrm{RM}(1, 5)$ は $[32, 6, 16]$ 符号で、6ビットの情報を32ビットにし、最小距離16なので $t = 2^{5-1-1}-1 = 7$ 個の誤りを訂正できます。これが冒頭で触れたマリナー探査機の符号です。32ビット中7ビットまで化けても画像が復元できる、という強力さがパラメータから読み取れます。
導出した最小距離の式 $d = 2^{m-r}$ が本当に正しいか、いくつかの符号で全符号語を総当たり探索して確かめてみましょう。
灰色が理論値 $2^{m-r}$、青が全符号語を生成して求めた実測の最小重みです。RM(1,3)=4、RM(1,4)=8、RM(2,4)=4、RM(1,5)=16、RM(2,5)=8 と、すべての符号で理論値と実測値がぴったり一致しています。帰納法で導いた下界と最高次単項式による上界が、確かに最小距離 $d=2^{m-r}$ を与えていることが数値でも裏づけられました。
具体例で数値感覚がついたところで、いよいよ本題の 多数決復号 に進みます。なぜ多数決で復号できるのか、その仕組みを丁寧に見ていきましょう。
Reedの多数決復号の原理
復号の目標は、ノイズで一部のビットが反転した受信語 $\bm{y}$ から、元の係数 $c_S$ をすべて当てることです。Reedが考えた方法は、高次の係数から順に、独立した多数の手がかりで各係数を多数決で決める というものです。
直感をつかむために、まず1つの係数 $c_S$（$|S| = r$、最高次）に注目します。多項式は
$$ f(\bm{x}) = c_S\, x_S + (\text{次数 } < r \text{ の項を含む } S \text{ 以外の全項}) $$
と書けます。ここで巧妙なトリックを使います。$x_S = \prod_{i\in S} x_i$ に着目し、$S$ に含まれない変数 $\{x_j : j \notin S\}$ の値を固定して、$S$ に含まれる変数 $\{x_i : i \in S\}$ だけを全パターン動かした点を集めるのです。
$S$ に含まれる変数は $r$ 個なので、その全パターンは $2^r$ 通り。これら $2^r$ 個の点での $f$ の値を XOR で足し合わせる と、驚くべきことに $c_S$ だけが残ります。
$$ \begin{equation} \bigoplus_{\bm{x}_S \in \mathbb{F}_2^r} f(\bm{x}) = c_S \end{equation} $$
なぜでしょうか。ある単項式 $x_T$（$T \neq S$, $|T| \le r$）を $\{x_i : i\in S\}$ の全パターンで足し合わせると0になることを示せば十分です。$T \ne S$ かつ $|T| \le r = |S|$ なら、$T$ には「$S$ に属さない添字」が含まれるか、または「$S$ に属するが $T$ に属さない添字」が存在します。いずれの場合も、固定していない変数のうち少なくとも1つは $x_T$ の積に 現れない。その現れない変数を $x_a$ とすると、$x_a = 0$ の場合と $x_a = 1$ の場合で $x_T$ の値はまったく同じになり、ペアで打ち消し合って和が0になります。一方 $T = S$ のときだけ、$x_S = 1$ となるのは全変数が1の1点のみで、和は $c_S$ になります。こうして $c_S$ だけが生き残るのです。
ここまでは「誤りがない」場合の話です。本番では受信語 $\bm{y}$ にノイズが乗っているので、上の和を1回計算しただけでは信用できません。そこで 多数決 が登場します。
固定する変数 $\{x_j : j \notin S\}$ は $m – r$ 個あり、その値の選び方は $2^{m-r}$ 通りあります。それぞれの選び方について、上の「$2^r$ 点のXOR和」を計算すると、$c_S$ の推定値が $2^{m-r}$ 個得られます。これらは互いに 重ならない（disjoint な）点集合 から計算されるので、独立した投票になっています。誤りが少なければ、過半数の投票が正しい $c_S$ を指すので、多数決で確定できます。
この「$2^{m-r}$ 個の独立投票」という数が、最小距離 $2^{m-r}$ と一致しているのは偶然ではありません。$t = 2^{m-r-1}-1$ 個までの誤りなら、各投票ブロックに高々1個の誤りしか入らない（鳩の巣原理）か、誤りが過半数に届かないため、多数決が必ず正しい答えを返します。
実際に RM(1,4)（投票ブロック数 $2^{m-r}=8$）で、誤りを増やしながら「正しい係数 $c_S$ を指す票の割合」を実測してみると、次のようになります。
誤りが0個のときは全票（割合1.0）が正しい値を指し、誤りが1個増えるごとに正票の割合がなだらかに下がっていきます。それでも誤り5個までは割合が0.5（多数決の境界、赤破線）を上回っており、過半数が正しい答えを保っていることがわかります。誤りがさらに増えて正票が0.5を割ると、多数決が誤った値に倒れ始めます。
最高次の係数 $\{c_S : |S| = r\}$ がすべて決まったら、それらの寄与を受信語から 引き算（XOR） して取り除きます。すると残りは次数 $r-1$ 以下の多項式になり、まったく同じ手続きが $\mathrm{RM}(r-1, m)$ に対して使えます。これを次数0まで繰り返せば全係数が求まります。これが「高次から順に多数決で決め、部分除去する」アルゴリズムの全体像です。
アルゴリズムの骨格が見えたので、ステップとして整理しましょう。
多数決復号アルゴリズムの手順
入力は受信語 $\bm{y} \in \mathbb{F}_2^{2^m}$、出力は推定した係数ベクトル $\hat{\bm{u}} = (\hat{c}_S)$ です。
- 作業用ベクトルを初期化: $\bm{r} \leftarrow \bm{y}$ とする。これは「まだ説明できていない残差」を表します。
- 次数を高い方から走査: $d = r, r-1, \dots, 0$ の順に以下を行う。
- その次数の各単項式 $S$（$|S| = d$）について多数決: – $S$ に含まれない変数の値の全パターン（$2^{m-d}$ 通り）それぞれについて、$S$ の変数を全パターン動かした $2^d$ 点での $\bm{r}$ の値を XOR して投票を作る。 – $2^{m-d}$ 個の投票の多数決で $\hat{c}_S \in \{0,1\}$ を決める。
- 部分除去: 次数 $d$ の係数がすべて決まったら、$\sum_{|S|=d} \hat{c}_S\, \mathrm{ev}(x_S)$ を作って $\bm{r}$ から XOR で引く。これで残差は次数 $d-1$ 以下の符号語（＋誤り）になる。
- 次の次数へ: $d \leftarrow d-1$ として手順3へ戻る。
- $d = 0$ まで終えたら、全係数 $\hat{\bm{u}}$ が揃う。符号語は $\hat{\bm{c}} = \hat{\bm{u}}\bm{G}$ で再構成できる。
ここで重要なのは「なぜ高次から処理するのか」です。多数決のトリック（XOR和で1つの係数だけ残す）は、対象の係数が その時点で最高次 のときにのみ正しく機能します。低次の係数を先に消そうとすると、まだ残っている高次の項が和に混ざってしまい、投票が汚れます。高次から順に確定して取り除けば、各段階で常に「最高次の係数を多数決」という同じ構造を保てるのです。
この「段階的に係数を確定して残差から取り除く」様子を、RM(2,4) に1ビット誤りを入れて追跡したのが次の図です。
受信語（残差）の重みは9で始まり、次数2・次数1・次数0の係数を順に確定して除去していくと、最終的に重み1まで落ちます。途中で重みが一時的に増える段階があるのは、推定した高次の符号語をXORで差し引いた結果ですが、復号は正しく成功しています（情報ビットが完全一致）。最後に残った重み1は、まさに注入した1ビットの誤りパターンそのもので、これは符号語ではないため残差として残りますが、情報ビットの推定には影響しません。
手順が明確になったので、Pythonで実装し、誤りを注入した受信語が本当に訂正されるかを検証しましょう。
Pythonでの実装
まず、生成行列の構成・符号化・パラメータ確認を行います。日本語フォントの設定もしておきます。
import numpy as np
import matplotlib, matplotlib.pyplot as plt
from itertools import combinations
# 日本語フォント設定
for cand in ["Hiragino Sans", "Yu Gothic", "Noto Sans CJK JP", "IPAexGothic", "Meiryo"]:
if any(cand == f.name for f in matplotlib.font_manager.fontManager.ttflist):
plt.rcParams["font.family"] = cand
break
plt.rcParams["axes.unicode_minus"] = False
def monomial_eval(S, m):
"""変数集合Sの単項式 x_S の評価ベクトル（長さ2^m）を返す"""
n = 2 ** m
vec = np.ones(n, dtype=int)
for j in range(n):
# 点 p_j は j の2進表現（最上位ビットが x_1）
bits = [(j >> (m - 1 - i)) & 1 for i in range(m)]
prod = 1
for i in S:
prod &= bits[i] # AND（積）
vec[j] = prod
return vec
def rm_monomials(r, m):
"""次数0からrまでの単項式（変数集合）を低次順に列挙"""
monos = []
for d in range(r + 1):
for S in combinations(range(m), d):
monos.append(S)
return monos
def rm_generator(r, m):
"""RM(r,m)の生成行列を構成して返す"""
monos = rm_monomials(r, m)
G = np.array([monomial_eval(S, m) for S in monos], dtype=int)
return G, monos
monomial_eval は、点 $\bm{p}_j$ を整数 $j$ の2進表現として扱い、$S$ に含まれる変数ビットの AND を計算しています。rm_generator は次数の低い単項式から順に評価ベクトルを並べ、生成行列を組み立てます。これで定義どおりの $\bm{G}$ が手に入ります。
実際に $\mathrm{RM}(1,3)$ の生成行列とパラメータを確認します。
r, m = 1, 3
G, monos = rm_generator(r, m)
n = 2 ** m
k = G.shape[0]
# 最小距離（ゼロでない全符号語の最小重み）を全探索で確認
min_wt = n
for u_int in range(1, 2 ** k):
u = np.array([(u_int >> i) & 1 for i in range(k)], dtype=int)
c = (u @ G) % 2
w = c.sum()
if 0 < w < min_wt:
min_wt = w
k_theory = sum(len(list(combinations(range(m), i))) for i in range(r + 1))
print("RM(%d,%d): n=%d, k=%d, d=%d" % (r, m, n, k, min_wt))
print("理論値: n=2^m=%d, k=ΣC(m,i)=%d, d=2^(m-r)=%d"
% (2 ** m, k_theory, 2 ** (m - r)))
print("生成行列 G =")
print(G)
このコードを実行すると次の出力が得られます。
RM(1,3): n=8, k=4, d=4
理論値: n=2^m=8, k=ΣC(m,i)=4, d=2^(m-r)=4
生成行列 G =
[[1 1 1 1 1 1 1 1]
[0 0 0 0 1 1 1 1]
[0 0 1 1 0 0 1 1]
[0 1 0 1 0 1 0 1]]
出力から、全符号語を総当たりで調べた最小距離が4となり、理論値 $2^{m-r} = 2^{3-1} = 4$ と一致することが確認できます。生成行列も先ほど手で書いたものと完全に同じで、1行目が全1（定数項）、2〜4行目が各変数の評価ベクトルになっています。次元 $k=4$ も $\binom{3}{0}+\binom{3}{1}=4$ と合っています。
同じ要領で、もう少し大きい RM(1,4)（$[16,5,8]$）の全32符号語の重み（1の個数）を数えて分布にすると、次のようになります。
重みは0（全ゼロ符号語）、8、16 の3種類しか現れず、特に重み8の符号語が30個と大半を占めます。最小距離はゼロでない符号語の最小重みなので $d=8$（赤破線）であり、これは理論値 $2^{4-1}=8$ と一致します。重み分布がこれほど集中するのはReed-Muller符号やその親戚に特徴的な美しい性質で、符号語が「ちょうど半分の点で1になる」一次関数の評価ベクトルに対応していることの現れです。
次に、多数決復号の核心である「投票点の生成」を実装します。
def voting_blocks(S, m):
"""単項式Sについて、多数決の投票ブロックを列挙する。
各ブロックは、Sに含まれない変数を固定しSの変数を全パターン動かした
2^|S|個の点インデックスの集合。"""
S = set(S)
free = [i for i in range(m) if i not in S] # 固定する変数（S以外）
in_S = sorted(S) # 動かす変数
blocks = []
# 固定変数の全パターン（2^(m-|S|)通り）
for fixed_int in range(2 ** len(free)):
idxs = []
# 動かす変数の全パターン（2^|S|通り）
for move_int in range(2 ** len(in_S)):
bits = [0] * m
for b, i in enumerate(free):
bits[i] = (fixed_int >> b) & 1
for b, i in enumerate(in_S):
bits[i] = (move_int >> b) & 1
# ビット列を点インデックスjに変換（x_1が最上位）
j = sum(bits[i] << (m - 1 - i) for i in range(m))
idxs.append(j)
blocks.append(idxs)
return blocks
voting_blocks は、固定変数の各パターンに対して1つの投票ブロック（$2^{|S|}$ 個の点インデックス）を作ります。ブロックの個数は $2^{m-|S|}$ で、これが多数決の票数になります。各ブロックは互いに点を共有しない（disjoint な）ので、独立した投票として機能します。
このブロックを使って、多数決復号の本体を書きます。
def reed_decode(y, r, m):
"""Reedの多数決復号。受信語yから係数ベクトルを推定する"""
res = y.copy() % 2 # 残差（作業用）
monos = rm_monomials(r, m)
coeff = {} # 推定係数 c_S
# 次数の高い方から処理
for d in range(r, -1, -1):
for S in [s for s in monos if len(s) == d]:
blocks = voting_blocks(S, m)
votes = []
for blk in blocks:
# ブロック内の残差をXORして1票を作る
votes.append(int(np.bitwise_xor.reduce(res[blk])))
# 多数決
coeff[S] = 1 if sum(votes) * 2 > len(votes) else 0
# この次数の寄与を残差から除去（部分除去）
for S in [s for s in monos if len(s) == d]:
if coeff[S] == 1:
res = (res + monomial_eval(S, m)) % 2
# 係数を生成行列の行順（低次→高次）に並べて返す
u_hat = np.array([coeff[S] for S in monos], dtype=int)
return u_hat
reed_decode は手順どおり、次数の高い方から各単項式について投票を集め多数決で係数を決め、決まった係数の寄与を残差 res から XOR で取り除いていきます。np.bitwise_xor.reduce がブロック内の点を一気にXORして1票を作る部分です。最後に係数を生成行列の行順に並べた情報ベクトル u_hat を返します。
それでは、誤りを注入して訂正できるかを検証します。$\mathrm{RM}(1,3)$（$t=1$ 個訂正）でランダムな情報を符号化し、1ビット誤りを入れて復号します。
np.random.seed(0)
r, m = 1, 3
G, monos = rm_generator(r, m)
n, k = 2 ** m, G.shape[0]
# ランダムな情報ベクトルを符号化
u = np.random.randint(0, 2, size=k)
c = (u @ G) % 2
# 1ビット誤りを注入
y = c.copy()
err_pos = np.random.randint(0, n)
y[err_pos] ^= 1
# 復号
u_hat = reed_decode(y, r, m)
c_hat = (u_hat @ G) % 2
print("送信情報 u =", u)
print("符号語 c =", c)
print("受信語 y =", y, " (誤り位置 %d)" % err_pos)
print("復号情報 u^ =", u_hat)
print("復号符号 c^ =", c_hat)
print("情報ビット復元成功:", np.array_equal(u, u_hat))
print("符号語復元成功:", np.array_equal(c, c_hat))
実行すると次のような出力になります。
送信情報 u = [0 1 1 0]
符号語 c = [0 0 1 1 1 1 0 0]
受信語 y = [0 0 1 0 1 1 0 0] (誤り位置 3)
復号情報 u^ = [0 1 1 0]
復号符号 c^ = [0 0 1 1 1 1 0 0]
情報ビット復元成功: True
符号語復元成功: True
受信語 y は符号語 c の3番目のビットが反転していますが、復号後の情報ベクトル u^ と符号語 c^ は送信したものと完全に一致しています。1ビットの誤りが多数決によって正しく訂正されたことが確認できます。多数決の各ブロックには高々1個の誤りしか入らないため、過半数が正しい票を投じ、誤りに引きずられないのです。
1回だけでは偶然かもしれないので、多数の試行で誤り数と訂正成功率の関係を調べ、図にします。より訂正能力の高い $\mathrm{RM}(1,4)$（$[16,5,8]$, $t=3$）を使います。
def simulate(r, m, max_err, trials=2000):
"""誤りビット数を変えて訂正成功率を測定する"""
G, monos = rm_generator(r, m)
n, k = 2 ** m, G.shape[0]
rng = np.random.default_rng(1)
rates = []
for e in range(max_err + 1):
ok = 0
for _ in range(trials):
u = rng.integers(0, 2, size=k)
c = (u @ G) % 2
y = c.copy()
if e > 0:
pos = rng.choice(n, size=e, replace=False)
y[pos] ^= 1
u_hat = reed_decode(y, r, m)
if np.array_equal(u, u_hat):
ok += 1
rates.append(ok / trials)
return np.array(rates)
r, m, max_err = 1, 4, 6
rates = simulate(r, m, max_err)
t = 2 ** (m - r - 1) - 1 # 理論上の訂正可能数
plt.figure(figsize=(8, 5))
plt.plot(range(max_err + 1), rates, "o-", color="#0077b6", label="訂正成功率")
plt.axvline(t, color="#d00000", linestyle="--", label="理論訂正限界 t=%d" % t)
plt.xlabel("注入した誤りビット数")
plt.ylabel("情報ビット復元成功率")
plt.title("RM(1,4) [16,5,8] の多数決復号 誤り数 vs 成功率")
plt.ylim(-0.05, 1.05)
plt.grid(True, alpha=0.3)
plt.legend()
plt.tight_layout()
plt.savefig("/tmp/rm14_success.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、誤りビット数が理論訂正限界 $t = 3$ 以下のときは成功率がほぼ1.0（100%）であり、$t$ を超えると急激に成功率が落ちることが読み取れます。実測でも誤り3個までは成功率1.000、4個で0.224、5個で0.082と崖のように下がりました。これは $\mathrm{RM}(1,4)$ の最小距離 $d=8$ から導かれる $t = \lfloor (8-1)/2 \rfloor = 3$ という理論限界とぴったり一致しています。符号の保証どおり、3ビットまでなら確実に訂正でき、4ビット以上では多数決の票が過半数を割って訂正に失敗しはじめるのです。
複数の符号で同じ実験を行い、訂正能力を見比べると、最小距離の違いが耐性の違いとして現れます。
RM(1,4)（$d=8$, $t=3$、緑）は3ビットまで完璧に訂正し最も粘り強く、RM(1,3)（$d=4$, $t=1$、青）は1ビットまで、RM(2,4)（$d=4$, $t=1$、橙）も1ビットまでと、いずれも理論上の訂正可能数 $t$ の地点まで成功率1.0を保ち、その先で落ちます。同じ符号長16でも RM(1,4) と RM(2,4) で耐性が大きく違うのは、次数を上げて情報を詰め込んだ RM(2,4) の最小距離が小さいためで、これが次に見るトレードオフの正体です。
最後に、最小距離が次数 $r$ でどう変わるかを可視化し、設計上のトレードオフを確認します。
m = 5
rs = list(range(0, m))
ds = [2 ** (m - r) for r in rs]
ks = [sum(len(list(combinations(range(m), i))) for i in range(r + 1)) for r in rs]
ts = [2 ** (m - r - 1) - 1 for r in rs]
fig, ax1 = plt.subplots(figsize=(8, 5))
ax1.plot(rs, ds, "o-", color="#d00000", label="最小距離 d=2^(m-r)")
ax1.plot(rs, ts, "s--", color="#9d0208", label="訂正可能数 t")
ax1.set_xlabel("次数 r")
ax1.set_ylabel("距離・訂正数", color="#d00000")
ax1.tick_params(axis="y", labelcolor="#d00000")
ax2 = ax1.twinx()
ax2.plot(rs, ks, "^-", color="#0077b6", label="次元 k")
ax2.set_ylabel("次元 k（情報ビット数）", color="#0077b6")
ax2.tick_params(axis="y", labelcolor="#0077b6")
ax1.set_title("RM(r,5): 次数rによる距離と次元のトレードオフ")
ax1.grid(True, alpha=0.3)
fig.legend(loc="upper center", ncol=3, bbox_to_anchor=(0.5, 0.98))
plt.tight_layout()
plt.savefig("/tmp/rm_tradeoff.png", dpi=150, bbox_inches="tight")
plt.show()
このグラフから、次数 $r$ を小さくすると最小距離 $d$（赤）と訂正可能数 $t$ は指数的に大きくなる一方、運べる情報ビット数 $k$（青）は減ることがわかります。$r$ を上げれば多くの情報を詰め込めますが誤り訂正能力は下がる——この「強さ（距離）と効率（次元）のトレードオフ」が、Reed-Muller符号の設計で最も重要な調整つまみです。深宇宙通信のようにノイズが厳しい環境では $r=1$ のような低次数を選び、効率より頑健さを優先するわけです。
最後に、このトレードオフが実際の通信路でどう効いてくるかを、雑音そのものに対する性能として確かめます。各符号語のビットを確率 $p$ で独立に反転させる二元対称通信路（BSC）で、ワード単位の復号失敗率を実測しました。
誤り確率 $p$ が小さい領域では、最小距離の大きい RM(1,4)（緑）が最も低い失敗率を示し、裸の5ビットをそのまま送る参照（黒破線）を大きく下回ります。一方、次数を上げて高レートにした RM(2,4)（橙）は最小距離が4と小さいため、ほぼ全域で参照より失敗率が高く、「冗長性を増やしても距離が足りなければ守れない」ことが見て取れます。符号化はやみくもにビットを増やすことではなく、距離を稼ぐ設計だという点が重要です。
最後に、情報ビット単位での誤り低減効果を見ます。横軸を生のビット誤り率、縦軸を復号後のビット誤り率にとり、「何も符号化しない場合」を対角線と比較します。
青い実測曲線が対角線（符号化しない場合）より下にある領域（緑の塗り）では、復号後のビット誤り率が生の誤り率を下回っており、確かに誤りが減っています。実測では境界がおよそ $p \approx 0.26$ にあり、それより誤りが少ない通信路なら符号化が役立ち、誤りが多すぎると（多数決の票が汚れすぎて）かえって悪化することがわかります。低雑音側で誤り率を一桁以上下げられるのが、低レートReed-Muller符号の強みです。
まとめ
本記事では、Reed-Muller符号の理論と多数決復号を解説しました。
- 構成: $\mathrm{RM}(r,m)$ は、$r$ 次以下の $m$ 変数ブール単項式の評価ベクトルを行に並べた生成行列で定義される線形符号
- パラメータ: 符号長 $n = 2^m$、次元 $k = \sum_{i=0}^{r}\binom{m}{i}$、最小距離 $d = 2^{m-r}$（帰納法で下界、最高次単項式で上界を導出）
- 具体例: $\mathrm{RM}(1,3)$ は $[8,4,4]$ で拡張ハミング符号と等価かつ自己双対。一般に双対は $\mathrm{RM}(m-r-1,m)$
- 多数決復号: 高次の係数から、$2^{m-r}$ 個の独立した投票ブロックのXOR和を多数決し、確定したら部分除去して次数を下げる。$t = 2^{m-r-1}-1$ 個までの誤りを確実に訂正
- Python実装: 1ビット誤りの訂正、誤り数と成功率の関係（理論限界 $t$ で急落）、距離と次元のトレードオフを数値で確認
Reed-Muller符号は、ブール多項式という代数的構造と、多数決という単純で頑健な復号が結びついた美しい例です。次数と距離・次元の関係は、符号理論の中でも特に見通しがよく、より高度な符号を学ぶ足がかりになります。
次のステップとして、以下の記事も参考にしてください。
- 線形ブロック符号の理論 — 生成行列・最小距離・双対符号の一般論
- ハミング符号の理論 — RM(1,3) と関係する最小距離3の符号
- リード・ソロモン符号の理論 — 多項式評価という同じ発想を有限体 $\mathbb{F}_q$ 上で展開した符号
参考文献
- F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977
- I. S. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” IRE Transactions on Information Theory, 1954
- Todd K. Moon, Error Correction Coding: Mathematical Methods and Algorithms, Wiley, 2005