リード・マラー符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

リード・マラー符号: Reed–Muller code)は、通信で使われる線型誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。一次リード・マラー符号はアダマール符号と等価である。リード・マラー符号は、RM(r,m) で表され、r は符号の次数、m は符号語の長さ である。リード・マラー符号は、元が {0,1} である におけるバイナリ関数に関連する。

RM(0,m) 符号は反復符号、RM(m-1,m) 符号はパリティチェック符号である。RM符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。

構築[編集]

長さ n = 2d のリード・マラー符号の生成行列を次のように記述する。

ここで、部分集合 について、n-次元空間 における指示ベクトル を次のように定義する。

また、同様に における次の二項関係を「楔積; wedge product」と呼ぶ。

は、 における d-次元ベクトル空間である。従って、次のように記述できる。

ここで、n-次元空間 における長さ n のベクトル v0 = (1, 1, 1, 1, 1, 1, 1, 1) および、次のベクトルを定義する。

このとき、Hi(次元が 2d −1)における超平面である。

リード・マラー RM(d, r) 符号は、次数 r、長さ n = 2d で、v0vir 番目までの楔積によって生成される。

例 1[編集]

d = 3 とする。すると n = 8 であり、次のようになる。

そして、次のようにする。

RM(3,1)符号は次の集合から生成される。

あるいは、より明確に示せば、次の行列の行から生成される。

例 2[編集]

RM(3,2)符号は次の集合から生成される。

あるいは、より明示的に示せば、次の行列の行から生成される。

特性[編集]

リード・マラー符号は次のような特性を持つ。

  • d 番目までの vi がとりうる全ての楔積の集合は、 の基底を形成する。
  • RM (d, r) のランクは次の通り。
  • RM (d, r) = RM (d − 1, r) | RM (d − 1, r − 1) ここで、'|' は2つの符号の bar product を表している。
  • RM (d, r) の最小ハミング重みは 2dr である。

関連項目[編集]