| この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "リード・マラー符号" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2015年11月) |
リード・マラー符号(リード・マラーふごう、英: Reed–Muller code)は、通信で使われる線型な誤り訂正符号の1つの種類である。発見者は Irving S. Reed と D. E. Muller である。リード・マラー符号は、R(r, m) で表され、r は符号の次数、m は符号語の長さ n = 2m である。リード・マラー符号は、元が {0, 1} である有限体 GF(2m) におけるバイナリ関数に関連する。
符号 R(0, m) は反復符号、符号 R(1, m) はアダマール符号、符号 R(m − 1, m) はパリティチェック符号である。リード・マラー符号は直交性があるために興味深い特性を持ち、ブール関数空間と見なせる。
長さ n = 2m のリード・マラー符号は以下のように構成される。
まず
とおく。このとき、部分集合
に対して、指示ベクトル
を次で定義する。
![{\displaystyle \left(\mathbb {I} _{A}\right)_{j}={\begin{cases}1&(x_{j}\in A)\\0&(x_{j}\notin A)\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e085148c20ec305ea07aa1a2d8888ef81f211d)
また
における次の二項演算を「楔積; wedge product」と呼ぶ。
![{\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8cf76d0a89006cb4f9d4b4f9c5850de21871926)
は、体
上の m 次元ベクトル空間ゆえ、次のように記述できる。
このとき、n-次元空間
において次のベクトルを定義する。
![{\displaystyle v_{0}=\mathbb {I} _{\mathbb {F} _{2}^{m}},\quad v_{i}=\mathbb {I} _{H_{i}}\quad (1\leq i\leq m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15bbabed865893ee596273ddb01e3f99496cdb91)
ここで、Hi は
における超平面
である。リード・マラー 符号 R(r, m) とは、長さ n = 2m、 次数 0 ≤ r ≤ m であり、
![{\displaystyle \{v_{0}\}\cup \{\,v_{i_{1}}\wedge \dotsb \wedge v_{i_{p}}\mid 1\leq i_{1}<\dotsb <i_{p}\leq m,\quad p\leq r\,\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc7d98c1b495b2d8612a46786fac71f7bbb58aef)
によって生成される符号のことである。
m = 3 とする。すると n = 8 であり、次のようになる。
![{\displaystyle \mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),\ldots ,(1,1,1)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fea02f5884a644f4858af14f3abdc5669377898)
そして、上の構成と同様に、次のようにおく。
![{\displaystyle {\begin{aligned}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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cda64858fc7f02a20ee30a23a86173e9b9dc31a8)
R(1, 3)[編集]
r = 1 とすると、符号 R(1, 3) は次の集合から生成される。
![{\displaystyle \{v_{0},v_{1},v_{2},v_{3}\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d66b95a3187492d457d269952195374319051f3)
あるいは、次の行列を生成行列とする符号である。
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a521075a2b43b0ca09bb6a4527f73bdee44e8c91)
R(2, 3)[編集]
r = 2 とすると、符号 R(2, 3) は次の集合から生成される。
![{\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1ce1e89b1e50c159d560c29617d41123755d4b2)
あるいは、次の行列を生成行列とする符号である。
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cd9bf0c31131a5cac5b0b87754f009bcdfc8e11)
リード・マラー符号 R (r, m) は次の特性をもつ。
- m 番目までの vi がとりうる全ての楔積の集合は、
の基底である。
- ランクは次の通り[2]。
![{\displaystyle \textstyle \sum _{s=0}^{r}{m \choose s}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a20b6286dc52152646b4d700ef0810e1b52d40a)
- R (r, m) = R (r, m − 1) | R (r − 1, m − 1) ここで、'|' は2つの符号の bar product を表している。
- 最小距離は 2m − r である。
参考文献[編集]
関連項目[編集]