リード・マラー符号

リード・マラー符号（リード・マラーふごう、）は、通信で使われる線型な誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R("r", "m") で表され、"r" は符号の次数、"m" は符号語の長さ "n" = 2"m" である。リード・マラー符号は、元が {0, 1} である有限体 GF(2"m") におけるバイナリ関数に関連する。
符号 R(0, "m") は反復符号、符号 R(1, "m") はアダマール符号、符号 R("m" − 1, "m") はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。
構成.
長さ "n" = 2"m" のリード・マラー符号は以下のように構成される。
まず
formula_1
とおく。このとき、部分集合 formula_2 に対して、指示ベクトル formula_3 を次で定義する。
また formula_5 における次の二項演算を「楔積; wedge product」と呼ぶ。
formula_7 は、体 formula_8 上の "m" 次元ベクトル空間ゆえ、次のように記述できる。
formula_9 
このとき、"n"-次元空間 formula_5 において次のベクトルを定義する。
ここで、"H""i" は formula_7における超平面
formula_13
である。リード・マラー 符号 R("r", "m") とは、長さ "n" = 2"m"、 次数 0 ≤ "r" ≤ "m" であり、
によって生成される符号のことである。
例.
"m" = 3 とする。すると "n" = 8 であり、次のようになる。
そして、上の構成と同様に、次のようにおく。
R(1, 3).
"r" = 1 とすると、符号 R(1, 3) は次の集合から生成される。
あるいは、次の行列を生成行列とする符号である。
R(2, 3).
"r" = 2 とすると、符号 R(2, 3) は次の集合から生成される。
あるいは、次の行列を生成行列とする符号である。
特性.
リード・マラー符号 R ("r", "m") は次の特性をもつ。