「リード・マラー符号」の版間の差分
ja>ARAKI Satoru (出典に合わせ記号の変更ほか) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:28時点における版
リード・マラー符号(英: Reed–Muller code)は、通信で使われる線型な誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(r, m) で表され、r は符号の次数、m は符号語の長さ n = 2m である。リード・マラー符号は、元が {0, 1} である有限体 GF(2m) におけるバイナリ関数に関連する。
符号 R(0, m) は反復符号[1]、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。
Contents
構成
長さ n = 2m のリード・マラー符号は以下のように構成される。
まず [math] \mathbb{F}_2^m = \{ x_1, \ldots, x_n \} [/math] とおく。このとき、部分集合 [math] A \subset \mathbb{F}_2^m [/math] に対して、指示ベクトル [math]\mathbb{I}_A \in \mathbb{F}_2^n[/math] を次で定義する。
- [math]\left( \mathbb{I}_A \right)_j = \begin{cases} 1 & (x_j \in A) \\ 0 & (x_j \notin A) \end{cases} [/math]
また [math]\mathbb{F}_2^n[/math] における次の二項演算を「楔積; wedge product」と呼ぶ。
- [math] w \wedge z = (w_1 \times z_1, \ldots , w_n \times z_n ) [/math]
[math]\mathbb{F}_2^m[/math] は、体 [math]\mathbb{F}_2[/math] 上の m 次元ベクトル空間ゆえ、次のように記述できる。
[math]\mathbb{F}_2^m = \{\, (y_1, \dotsc , y_m) \mid y_i \in \mathbb{F}_2 \,\} [/math]
このとき、n-次元空間 [math]\mathbb{F}_2^n[/math] において次のベクトルを定義する。
- [math] v_0 = \mathbb{I}_{\mathbb{F}_2^m}, \quad v_i = \mathbb{I}_{ H_i } \quad (1 \le i \le m) [/math]
ここで、Hi は [math]\mathbb{F}_2^m[/math]における超平面 [math]H_i = \{\, y \in \mathbb{F}_2^m \mid y_i = 0 \,\} [/math] である。リード・マラー 符号 R(r, m) とは、長さ n = 2m、 次数 0 ≤ r ≤ m であり、
- [math] \{ v_0 \} \cup \{\, v_{i_1} \wedge \dotsb \wedge v_{i_p} \mid 1 \le i_1 \lt \dotsb \lt i_p \le m, \quad p \le r \,\} [/math]
によって生成される符号のことである。
例
m = 3 とする。すると n = 8 であり、次のようになる。
- [math] \mathbb{F}_2^3 = \{ (0,0,0), (0,0,1), \ldots, (1,1,1) \} [/math]
そして、上の構成と同様に、次のようにおく。
- [math] \begin{align} 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{align} [/math]
R(1, 3)
r = 1 とすると、符号 R(1, 3) は次の集合から生成される。
- [math] \{ v_0, v_1, v_2, v_3 \}\, [/math]
あるいは、次の行列を生成行列とする符号である。
- [math] \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} [/math]
R(2, 3)
r = 2 とすると、符号 R(2, 3) は次の集合から生成される。
- [math] \{ v_0, v_1, v_2, v_3, v_1 \wedge v_2, v_1 \wedge v_3, v_2 \wedge v_3 \} [/math]
あるいは、次の行列を生成行列とする符号である。
- [math] \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} [/math]
特性
リード・マラー符号 R (r, m) は次の特性をもつ。
- m 番目までの vi がとりうる全ての楔積の集合は、[math]\mathbb{F}_2^n[/math] の基底である。
- ランクは次の通り[2]。[math]\textstyle \sum_{s=0}^r {m \choose s} [/math]
- R (r, m) = R (r, m − 1) | R (r − 1, m − 1) ここで、'|' は2つの符号の bar product を表している。
- 最小距離は 2m − r である[3]。
脚注
参考文献
- (1992) Coding and Information Theory, Graduate Texts in Mathematics. Springer-Verlag. ISBN 0-387-97812-7.
- (1999) Introduction to Coding Theory, Third, Graduate Texts in Mathematics, Springer-Verlag. ISBN 3-540-64133-5.