リード・マラー符号

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

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

${\displaystyle \left(\mathbb {I} _{A}\right)_{j}={\begin{cases}1&(x_{j}\in A)\\0&(x_{j}\notin A)\end{cases}}}$

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

${\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}$

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

${\displaystyle \mathbb {F} _{2}^{m}=\{\,(y_{1},\dotsc ,y_{m})\mid y_{i}\in \mathbb {F} _{2}\,\}}$

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

${\displaystyle v_{0}=\mathbb {I} _{\mathbb {F} _{2}^{m}},\quad v_{i}=\mathbb {I} _{H_{i}}\quad (1\leq i\leq m)}$

ここで、H_i は ${\displaystyle \mathbb {F} _{2}^{m}}$における超平面 ${\displaystyle H_{i}=\{\,y\in \mathbb {F} _{2}^{m}\mid y_{i}=0\,\}}$ である。リード・マラー 符号 R(r, m) とは、長さ n = 2^m、 次数 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\,\}}$

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

Summarize Timeline Top Qs Fact Check

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

${\displaystyle \mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),\ldots ,(1,1,1)\}}$

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

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

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

${\displaystyle \{v_{0},v_{1},v_{2},v_{3}\}\,}$

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

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

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

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

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

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

• m 番目までの v_i がとりうる全ての楔積の集合は、${\displaystyle \mathbb {F} _{2}^{n}}$ の基底である。
• ランクは次の通り^[2]。${\displaystyle \textstyle \sum _{s=0}^{r}{m \choose s}}$
• R (r, m) = R (r, m − 1) | R (r − 1, m − 1) ここで、'|' は2つの符号の bar product を表している。
• 最小距離は 2^{m − r} である^[3]。