リード・マラー符号
リード・マラー符号(リード・マラーふごう、英: Reed–Muller code)は、通信で使われる線型な誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(r, m) で表され、r は符号の次数、m は符号語の長さ n = 2 である。リード・マラー符号は、元が {0, 1} である有限体 GF(2) におけるバイナリ関数に関連する。
符号 R(0, m) は反復符号、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。
r = 2 とすると、符号 R(2, 3) は次の集合から生成される。
{ v 0 , v 1 , v 2 , v 3 , v 1 ∧ v 2 , v 1 ∧ v 3 , v 2 ∧ v 3 } {\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge 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 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 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\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}
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}}}