リード・マラー符号

リード・マラー符号（リード・マラーふごう、英: Reed–Muller code）は、通信で使われる線型な誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(r, m) で表され、r は符号の次数、m は符号語の長さ n = 2^m である。リード・マラー符号は、元が {0, 1} である有限体 GF(2^m) におけるバイナリ関数に関連する。

符号 R(0, m) は反復符号^[1]、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。

構成[編集]

長さ n = 2^m のリード・マラー符号は以下のように構成される。

まず $\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{n}\}$ とおく。このとき、部分集合 $A\subset \mathbb {F} _{2}^{m}$ に対して、指示ベクトル $\mathbb {I} _{A}\in \mathbb {F} _{2}^{n}$ を次で定義する。

\left(\mathbb {I} _{A}\right)_{j}={\begin{cases}1&(x_{j}\in A)\\0&(x_{j}\notin A)\end{cases}}

また $\mathbb {F} _{2}^{n}$ における次の二項演算を「楔積; wedge product」と呼ぶ。

w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})

$\mathbb {F} _{2}^{m}$ は、体 $\mathbb {F} _{2}$ 上の m 次元ベクトル空間ゆえ、次のように記述できる。

$\mathbb {F} _{2}^{m}=\{\,(y_{1},\dotsc ,y_{m})\mid y_{i}\in \mathbb {F} _{2}\,\}$

このとき、n-次元空間 $\mathbb {F} _{2}^{n}$ において次のベクトルを定義する。

v_{0}=\mathbb {I} _{\mathbb {F} _{2}^{m}},\quad v_{i}=\mathbb {I} _{H_{i}}\quad (1\leq i\leq m)

ここで、H_i は $\mathbb {F} _{2}^{m}$ における超平面 $H_{i}=\{\,y\in \mathbb {F} _{2}^{m}\mid y_{i}=0\,\}$ である。リード・マラー符号 R(r, m) とは、長さ n = 2^m、次数 0 ≤ r ≤ m であり、