リード・マラー符号

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

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

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

構築[編集]

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

 X = \mathbb{F}_2^d = \{ x_1, \ldots, x_{2^d} \}

ここで、部分集合  A \subset X について、n-次元空間 \mathbb{F}_2^n における指示ベクトル \mathbb{I}_A \in \mathbb{F}_2^n を次のように定義する。

\left( \mathbb{I}_A \right)_i = \begin{cases} 1 & \mbox{ if } x_i \in A \\ 0 & \mbox{ otherwise} \\ \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^d は、 \mathbb{F}_2 における d-次元ベクトル空間である。従って、次のように記述できる。

(\mathbb{F}_2)^d = \{ (y_d, \ldots , y_1) | y_i \in \mathbb{F}_2 \}

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

 v_i = \mathbb{I}_{ H_i }

このとき、Hi(\mathbb{F}_2)^d(次元が 2d −1)における超平面である。

H_i = \{ y \in ( \mathbb{F}_2 ) ^d \mid y_i = 0 \}

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

例 1[編集]

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

 X = \mathbb{F}_2^3 = \{ (0,0,0), (0,0,1),  \ldots, (1,1,1) \}

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


\begin{matrix}
v_0 & = & (1,1,1,1,1,1,1,1) \\[2pt]
v_1 & = & (1,0,1,0,1,0,1,0) \\[2pt]
v_2 & = & (1,1,0,0,1,1,0,0) \\[2pt]
v_3 & = & (1,1,1,1,0,0,0,0) \\
\end{matrix}

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

 \{ v_0, v_1, v_2, v_3 \}\,

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


\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}

例 2[編集]

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

 \{ v_0, v_1, v_2, v_3, v_1 \wedge v_2, v_1 \wedge v_3, v_2 \wedge v_3 \}

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


\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}

特性[編集]

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

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

関連項目[編集]