リード・マラー符号

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

符号 R(0, m) は反復符号テンプレート:Sfn、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。

テンプレート:Toclimit

構成

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

まず $𝔽_{2}^{m} = {x_{1}, \dots, x_{n}}$ とおく。このとき、部分集合 $A \subset 𝔽_{2}^{m}$ に対して、指示ベクトル $𝕀_{A} \in 𝔽_{2}^{n}$ を次で定義する。

{(𝕀_{A})}_{j} = {\begin{matrix} 1 & (x_{j} \in A) \\ 0 & (x_{j} \notin A) \end{matrix}

また $𝔽_{2}^{n}$ における次の二項演算を「楔積; wedge product」と呼ぶ。

w \land z = (w_{1} \times z_{1}, \dots, w_{n} \times z_{n})

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

$𝔽_{2}^{m} = {(y_{1}, \dots, y_{m}) ∣ y_{i} \in 𝔽_{2}}$

このとき、n-次元空間 $𝔽_{2}^{n}$ において次のベクトルを定義する。

v_{0} = 𝕀_{𝔽_{2}^{m}}, v_{i} = 𝕀_{H_{i}} (1 \leq i \leq m)

ここで、H_i は $𝔽_{2}^{m}$ における超平面 $H_{i} = {y \in 𝔽_{2}^{m} ∣ y_{i} = 0}$ である。リード・マラー符号 R(r, m) とは、長さ n = 2^m、次数 0 ≤ r ≤ m であり、

{v_{0}} \cup {v_{i_{1}} \land \dots \land v_{i_{p}} ∣ 1 \leq i_{1} < \dots < i_{p} \leq m, p \leq r}

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

例

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

𝔽_{2}^{3} = {(0, 0, 0), (0, 0, 1), \dots, (1, 1, 1)}

そして、上の構成と同様に、次のようにおく。

\begin{matrix} 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{matrix}

R(1, 3)

r = 1 とすると、符号 R(1, 3) は次の集合から生成される。

{v_{0}, v_{1}, v_{2}, v_{3}}

あるいは、次の行列を生成行列とする符号である。

(\begin{matrix} 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{matrix})

R(2, 3)

r = 2 とすると、符号 R(2, 3) は次の集合から生成される。

{v_{0}, v_{1}, v_{2}, v_{3}, v_{1} \land v_{2}, v_{1} \land v_{3}, v_{2} \land v_{3}}

あるいは、次の行列を生成行列とする符号である。

(\begin{matrix} 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{matrix})

特性

リード・マラー符号 R (r, m) は次の特性をもつ。

m 番目までの v_i がとりうる全ての楔積の集合は、 $𝔽_{2}^{n}$ の基底である。
ランクは次の通り^[1]。 $\sum_{s = 0}^{r} (\binom{m}{s})$
R (r, m) = R (r, m − 1) | R (r − 1, m − 1) ここで、'|' は2つの符号の bar product を表している。
最小距離は 2^{m − r} であるテンプレート:Sfn。

脚注

テンプレート:Reflist

リード・マラー符号

目次

構成

例

R(1, 3)

R(2, 3)

特性

脚注

参考文献

関連項目

ナビゲーションメニュー

リード・マラー符号

構成

例

R(1, 3)

R(2, 3)

特性

脚注

参考文献

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー