この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "リード・マラー符号" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2015年11月）

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

符号 R(0, m) は反復符号[1]、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。.mw-parser-output .toclimit-2 .toclevel-1 ul,.mw-parser-output .toclimit-3 .toclevel-2 ul,.mw-parser-output .toclimit-4 .toclevel-3 ul,.mw-parser-output .toclimit-5 .toclevel-4 ul,.mw-parser-output .toclimit-6 .toclevel-5 ul,.mw-parser-output .toclimit-7 .toclevel-6 ul{display:none}
構成

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

まず F 2 m = { x 1 , … , x n } {\displaystyle \mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{n}\}} とおく。このとき、部分集合 A ⊂ F 2 m {\displaystyle A\subset \mathbb {F} _{2}^{m}} に対して、指示ベクトル I A ∈ F 2 n {\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{n}} を次で定義する。 ( I A ) j = { 1 ( x j ∈ A ) 0 ( x j ∉ A ) {\displaystyle \left(\mathbb {I} _{A}\right)_{j}={\begin{cases}1&(x_{j}\in A)\\0&(x_{j}\notin A)\end{cases}}}

また F 2 n {\displaystyle \mathbb {F} _{2}^{n}} における次の二項演算を「楔積; wedge product」と呼ぶ。 w ∧ z = ( w 1 × z 1 , … , w n × z n ) {\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}

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

F 2 m = { ( y 1 , … , y m ) ∣ y i ∈ F 2 } {\displaystyle \mathbb {F} _{2}^{m}=\{\,(y_{1},\dotsc ,y_{m})\mid y_{i}\in \mathbb {F} _{2}\,\}}

このとき、n-次元空間 F 2 n {\displaystyle \mathbb {F} _{2}^{n}} において次のベクトルを定義する。 v 0 = I F 2 m , v i = I H i ( 1 ≤ i ≤ m ) {\displaystyle v_{0}=\mathbb {I} _{\mathbb {F} _{2}^{m}},\quad v_{i}=\mathbb {I} _{H_{i}}\quad (1\leq i\leq m)}

ここで、Hi は F 2 m {\displaystyle \mathbb {F} _{2}^{m}} における超平面 H i = { y ∈ F 2 m ∣ y i = 0 } {\displaystyle H_{i}=\{\,y\in \mathbb {F} _{2}^{m}\mid y_{i}=0\,\}} である。リード・マラー 符号 R(r, m) とは、長さ n = 2m、 次数 0 ≤ r ≤ m であり、 { v 0 } ∪ { v i 1 ∧ ⋯ ∧ v i p ∣ 1 ≤ i 1 < ⋯ < i p ≤ m , p ≤ r } {\displaystyle \{v_{0}\}\cup \{\,v_{i_{1}}\wedge \dotsb \wedge v_{i_{p}}\mid 1\leq i_{1}<\dotsb <i_{p}\leq m,\quad p\leq r\,\}}

によって生成される符号のことである。
例

m = 3 とする。すると n = 8 であり、次のようになる。 F 2 3 = { ( 0 , 0 , 0 ) , ( 0 , 0 , 1 ) , … , ( 1 , 1 , 1 ) } {\displaystyle \mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),\ldots ,(1,1,1)\}}

そして、上の構成と同様に、次のようにおく。 v 0 = ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) v 1 = ( 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 ) v 2 = ( 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 ) v 3 = ( 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 ) {\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\v_{1}&=(1,0,1,0,1,0,1,0)\\v_{2}&=(1,1,0,0,1,1,0,0)\\v_{3}&=(1,1,1,1,0,0,0,0)\end{aligned}}}
R(1, 3)

r = 1 とすると、符号 R(1, 3) は次の集合から生成される。 { v 0 , v 1 , v 2 , v 3 } {\displaystyle \{v_{0},v_{1},v_{2},v_{3}\}\,}

あるいは、次の行列を生成行列とする符号である。 ( 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 ) {\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\\end{pmatrix}}}