|
|
| 1行目: |
1行目: |
| − | {{出典の明記|date=2015年11月}} | + | {{テンプレート:20180815sk}} |
| − | '''リード・マラー符号'''（{{lang-en-short|Reed–Muller code}}）は、通信で使われる[[線型符号|線型]]な[[前方誤り訂正|誤り訂正符号]]の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(''r'', ''m'') で表され、''r'' は符号の次数、''m'' は符号語の長さ ''n'' = 2<sup>''m''</sup> である。リード・マラー符号は、元が {0, 1} である[[有限体]] GF(2<sup>''m''</sup>) における[[バイナリ関数]]に関連する。
| |
| − | | |
| − | 符号 R(0, ''m'') は[[反復符号]]{{sfn|Roman|1992|loc={{google books quote|id=v7EwMbbTvr4C|page=273|Theorem 6.2.4}}}}、符号 R(1, ''m'') は[[アダマール符号]]、符号 R(''m'' − 1, ''m'') は[[パリティチェック符号]]である。リード・マラー符号は直交性があるために興味深い特性を持ち、[[ブール関数]]空間と見なせる。
| |
| − | | |
| − | {{toclimit|limit=2}}
| |
| − | | |
| − | == 構成 ==
| |
| − | 長さ ''n'' = 2<sup>''m''</sup> のリード・マラー符号は以下のように構成される。
| |
| − | | |
| − | まず
| |
| − | <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>
| |
| − | | |
| − | ここで、''H''<sub>''i''</sub> は <math>\mathbb{F}_2^m</math>における[[超平面]]
| |
| − | <math>H_i = \{\, y \in \mathbb{F}_2^m \mid y_i = 0 \,\} </math>
| |
| − | である。'''リード・マラー 符号''' R(''r'', ''m'') とは、長さ ''n'' = 2<sup>''m''</sup>、 次数 0 ≤ ''r'' ≤ ''m'' であり、
| |
| − | :<math> \{ v_0 \} \cup \{\, v_{i_1} \wedge \dotsb \wedge v_{i_p} \mid 1 \le i_1 < \dotsb < 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'' 番目までの ''v''<sub>''i''</sub> がとりうる全ての楔積の集合は、<math>\mathbb{F}_2^n</math> の基底である。<!-- i.e. R(m, m) = F_2^n? -->
| |
| − | * ランクは次の通り<ref>{{oeis|A008949}}</ref>。<math>\textstyle \sum_{s=0}^r {m \choose s} </math>
| |
| − | * R (''r'', ''m'') = R (''r'', ''m'' − 1) | R (''r'' − 1, ''m'' − 1) ここで、'|' は2つの符号の [[:en:bar product (coding theory)|bar product]] を表している。
| |
| − | * 最小[[ハミング距離|距離]]は 2<sup>''m'' − ''r''</sup> である{{sfn|van Lint|1999|loc={{google books quote|id=tvQhRUFh7EwC|page=58|Theorem 4.5.7}}}}。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{reflist|2}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | * {{cite book
| |
| − | |last1 = Roman
| |
| − | |first1 = Steven
| |
| − | |year = 1992
| |
| − | |title = Coding and Information Theory
| |
| − | |series = Graduate Texts in Mathematics
| |
| − | |volume = 134
| |
| − | |url = {{google books|v7EwMbbTvr4C|plainurl=yes}}
| |
| − | |publisher = Springer-Verlag
| |
| − | |isbn = 0-387-97812-7
| |
| − | |mr = 1168212
| |
| − | |zbl = 0752.94001
| |
| − | |ref = harv
| |
| − | }}
| |
| − | * {{cite book
| |
| − | |last1 = van Lint
| |
| − | |first1 = J. H.
| |
| − | |year = 1999
| |
| − | |title = Introduction to Coding Theory
| |
| − | |edition = Third
| |
| − | |series = Graduate Texts in Mathematics
| |
| − | |volume = 86
| |
| − | |url = {{google books|tvQhRUFh7EwC|plainurl=yes}}
| |
| − | |publisher = Springer-Verlag
| |
| − | |isbn = 3-540-64133-5
| |
| − | |mr = 1664228
| |
| − | |zbl = 0936.94014
| |
| − | |ref = harv
| |
| − | }}
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[リード・ソロモン符号]]
| |
| − | | |
| − | {{DEFAULTSORT:りとまらふこう}}
| |
| − | [[Category:符号理論]]
| |
| − | [[Category:誤り検出訂正]]
| |
| − | [[Category:数学に関する記事]]
| |