Reed–Muller符号

同義語:Reed-Muller符号Reed–Muller codeReed-Muller code

概要

Reed–Muller符号(Reed–Muller code)とは、$m$ 変数の 2 元の多項式のうち次数が $r$ 以下のものを $\mathbb F_2^m$ の $2^m$ 個の点すべてで評価して得られる 2 元線形符号 $\mathrm{RM}(r,m)$ である。長さ $2^m$、次元 $\sum_{i\le r}\binom mi$、最小距離 $2^{m-r}$ で、双対は $\mathrm{RM}(m-r-1,m)$ であり、1 次の符号と拡大 Hamming 符号を特別な場合に含む。部分立方体の上の和が係数を与えることを使う Reed の多数決復号は、最小距離の半分未満の誤りを必ず直す。生成行列の行は、Polar 符号と同じ Kronecker 積の行から重みの大きいものを選んだものである。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形符号, 有限体, 多項式環

Reed–Muller符号(Reed–Muller code)は、$m$ 個の変数の 2 元の多項式のうち次数が $r$ 以下のものを、$\mathbb F_2^m$ の $2^m$ 個の点すべてで評価して得られる 2 元の 線形符号 である。Muller が 1954 年にスイッチ回路の設計と誤りの検出の文脈で導入し、同じ年に Reed が多数決による効率のよい復号を与えた(GRS25 §9.6, p. 186、ASY21 Sect. V-A)。長さ $2^m$、次元 $\sum_{i\le r}\binom mi$、最小距離 $2^{m-r}$ の符号で、パラメータが $m,r$ の簡単な式で書け、$r$ を動かすと繰り返し符号から全空間まで入れ子の列をなし、双対もまた Reed–Muller 符号になる。拡大 Hamming符号 はその特別な場合である。
この記事では、関数と多項式の対応(lem-rm-evaluation)から出発して、次元(prop-rm-dimension)、$(u\mid u+v)$ 型の再帰(lem-rm-plotkin)、最小距離(thm-rm-distance)、双対(thm-rm-dual)を証明し、主定理として、最小距離の半分未満の誤りを多数決で必ず直す Reed の復号(thm-rm-majority)を証明する。最後に、Polar符号 の生成行列との関係(prop-rm-kronecker)を示す。

設定

以下 $m\ge1$ とし、$[m]:=\{1,\dots,m\}$、$\mathbb F_2=\{0,1\}$ とする。$\mathbb F_2^m$ の点 $x=(x_1,\dots,x_m)$ を、$(x_1,\dots,x_m)$ を 2 進表記とみた辞書式の順($x_1$ が最上位)に並べ、長さ $2^m$ の語の座標をこの順で $\mathbb F_2^m$ の点で番号づける。語の重み $\operatorname{wt}$、最小距離 $d(C)$、双対符号 $C^\perp$ の記法は 線形符号 に従う。
$S\subseteq[m]$ について単項式 $x_S:=\prod_{i\in S}x_i$($x_\emptyset=1$)をおく。$\mathbb F_2$ の上では $a^2=a$ なので、$\mathbb F_2^m$ 上の関数としては、どの多項式も各変数について 1 次以下の多項式
$$ f=\sum_{S\subseteq[m]}a_Sx_S\qquad(a_S\in\mathbb F_2) $$
に書き直せる。これを 多重線形多項式 と呼び、$a_S\ne0$ となる $S$ の元の個数の最大値を $f$ の 次数 $\deg f$ とする($f=0$ の次数は $-\infty$)。$f$ の 評価 を $\mathrm{ev}(f):=(f(x))_{x\in\mathbb F_2^m}\in\mathbb F_2^{2^m}$ とする。$y\in\mathbb F_2^m$ について $x_S(y)=1$ となるのは $S\subseteq\operatorname{supp}(y)$ のときに限る。

関数と多重線形多項式の対応

$\mathbb F_2^m$ 上の任意の関数 $g:\mathbb F_2^m\to\mathbb F_2$ に対し、$\mathrm{ev}(f)=g$ となる多重線形多項式 $f$ がただ一つあり、その係数は
$$ a_S=\sum_{x:\ \operatorname{supp}(x)\subseteq S}g(x)\qquad(S\subseteq[m]) $$
で与えられる。とくに $\{\mathrm{ev}(x_S)\}_{S\subseteq[m]}$ は $\mathbb F_2^{2^m}$ の基底である。

部分集合の上の和をとり直す

$a_S$ を上の式で定め、$f:=\sum_Sa_Sx_S$ とおく。$y\in\mathbb F_2^m$、$Y:=\operatorname{supp}(y)$ とし、$T\subseteq[m]$ の指示ベクトルを $1_T$ と書くと
$$ f(y)=\sum_{S\subseteq Y}a_S=\sum_{S\subseteq Y}\ \sum_{T\subseteq S}g(1_T)=\sum_{T\subseteq Y}g(1_T)\cdot\#\{S\mid T\subseteq S\subseteq Y\}=\sum_{T\subseteq Y}2^{\#(Y\setminus T)}g(1_T). $$
$\mathbb F_2$ では $T\ne Y$ の項が消えるので $f(y)=g(1_Y)=g(y)$。よって $\mathrm{ev}$ は多重線形多項式の全体($2^{2^m}$ 個)から関数の全体($2^{2^m}$ 個)への全射で、元の個数が等しいので全単射である。係数の式は存在の証明で使った $f$ の係数である。$\square$

係数の式は、Möbiusの反転公式 の部分集合の束での形を $\mathbb F_2$ で読んだものである。$a_S$ は、$S$ の外の座標を $0$ に固定した部分立方体の上の $g$ の和であり、この見方が thm-rm-majority の復号の鍵になる。

定義と基本の性質

Reed–Muller 符号

$0\le r\le m$ について、次数 $r$ 以下の多重線形多項式の評価の全体
$$ \mathrm{RM}(r,m):=\{\mathrm{ev}(f)\mid\deg f\le r\}\subseteq\mathbb F_2^{2^m} $$
を $r$ 次の Reed–Muller 符号 という。$r<0$ では $\mathrm{RM}(r,m):=\{0\}$ とする。

$\mathrm{ev}$ は線形なので $\mathrm{RM}(r,m)$ は線形符号で、$\mathrm{RM}(0,m)\subseteq\mathrm{RM}(1,m)\subseteq\cdots\subseteq\mathrm{RM}(m,m)=\mathbb F_2^{2^m}$ である。$\mathrm{RM}(0,m)=\{0\cdots0,\,1\cdots1\}$ は長さ $2^m$ の繰り返し符号である。文献によっては $\mathbb F_q$ 上の版を $\mathrm{RM}(q,m,r)$ と書き(GRS25 Definition 9.1.3, p. 174)、引数の順序が異なるものもある。

次元

$\dim\mathrm{RM}(r,m)=\sum_{i=0}^r\binom mi$。

$\mathrm{RM}(r,m)$ は $\{\mathrm{ev}(x_S)\mid\#S\le r\}$ で張られ、lem-rm-evaluation によりこれらは一次独立である。元の個数は $\#S=i$ の $S$ の個数 $\binom mi$ の和である。$\square$

$(u\mid u+v)$ 型の再帰

$m\ge2$、$0\le r\le m-1$ とする。長さ $2^m$ の語の座標を $x_m=0$ の $2^{m-1}$ 個と $x_m=1$ の $2^{m-1}$ 個に分け、語を $(c',c'')$ と書く(どちらも残りの変数 $(x_1,\dots,x_{m-1})$ の辞書式の順に並べる。これは座標の並べ替えなので、重みは変わらない)。このとき
$$ \mathrm{RM}(r,m)=\{(u,\,u+v)\mid u\in\mathrm{RM}(r,m-1),\ v\in\mathrm{RM}(r-1,m-1)\} $$
である($r=0$ では $\mathrm{RM}(-1,m-1)=\{0\}$ とする)。この形の符号の作り方を Plotkin の構成という(ASY21 Sect. II-B)。

$x_m$ を含む項と含まない項に分ける

多重線形多項式 $f$ は、$x_m$ を含まない多重線形多項式 $g,h$ によって $f=g+x_mh$ とただ一通りに書け、$\deg f\le r$ と「$\deg g\le r$ かつ $\deg h\le r-1$」は同値である。$x_m=0$ の点での値は $g$ の値、$x_m=1$ の点での値は $g+h$ の値なので、$\mathrm{ev}(f)=(\mathrm{ev}(g),\mathrm{ev}(g)+\mathrm{ev}(h))$ となる($\mathrm{ev}(g),\mathrm{ev}(h)$ は $m-1$ 変数での評価)。$\square$

最小距離

$0\le r\le m$ について $d(\mathrm{RM}(r,m))=2^{m-r}$ であり、$\mathrm{ev}(x_1x_2\cdots x_r)$ は重み $2^{m-r}$ の符号語である。従って $\mathrm{RM}(r,m)$ は $\bigl[2^m,\ \sum_{i\le r}\binom mi,\ 2^{m-r}\bigr]$ 符号である。

2 つの半分の重みを足す

$x_1\cdots x_r$ の値が $1$ になるのは $x_1=\dots=x_r=1$ の $2^{m-r}$ 点なので、後半が成り立つ。線形符号 の命題「最小距離と最小の重み」により、$0$ でない符号語の重みが $2^{m-r}$ 以上であることを示せばよい。$m$ についての帰納法による。$r=0$ では $0$ でない符号語は全 $1$ の語で重みは $2^m$、$r=m$ では主張は $\operatorname{wt}\ge1$ で明らかである。とくに $m=1$ では成り立つ。
$m\ge2$、$0< r< m$ とし、$m-1$ では成り立つとする。$0$ でない $c\in\mathrm{RM}(r,m)$ を lem-rm-plotkin で $c=(u,u+v)$ と書く。$v=0$ なら $u\ne0$ で、$u\in\mathrm{RM}(r,m-1)$($r\le m-1$)だから $\operatorname{wt}(c)=2\operatorname{wt}(u)\ge2\cdot2^{m-1-r}=2^{m-r}$。$v\ne0$ なら、各座標で $u_j+(u+v)_j=v_j$ だから $\operatorname{wt}(u)+\operatorname{wt}(u+v)\ge\operatorname{wt}(v)$ で、$v\in\mathrm{RM}(r-1,m-1)$ より
$$ \operatorname{wt}(c)=\operatorname{wt}(u)+\operatorname{wt}(u+v)\ge\operatorname{wt}(v)\ge2^{(m-1)-(r-1)}=2^{m-r}.\qquad\square $$

双対符号

$0\le r\le m-1$ について $\mathrm{RM}(r,m)^\perp=\mathrm{RM}(m-r-1,m)$。

次数 $m-1$ 以下の多項式は全体の和が $0$

まず、$\deg h\le m-1$ の多重線形多項式 $h$ について $\sum_{x\in\mathbb F_2^m}h(x)=0$ を示す。$\#S\le m-1$ なら $x_S$ の値が $1$ になる点は $2^{m-\#S}$ 個で偶数だから $\sum_xx_S(x)=0$ であり、線形性から従う。
$\deg f\le r$、$\deg g\le m-r-1$ とする。積 $fg$ を $a^2=a$ で多重線形に直すと、単項式の積 $x_Sx_T=x_{S\cup T}$ の次数は $\#S+\#T$ 以下なので、次数 $m-1$ 以下の多重線形多項式 $h$ で $h(x)=f(x)g(x)$ となるものがある。よって $\mathrm{ev}(f)\cdot\mathrm{ev}(g)=\sum_xh(x)=0$ で、$\mathrm{RM}(m-r-1,m)\subseteq\mathrm{RM}(r,m)^\perp$。次元は prop-rm-dimension と $\binom mi=\binom m{m-i}$ から
$$ \dim\mathrm{RM}(m-r-1,m)=\sum_{i=0}^{m-r-1}\binom mi=\sum_{j=r+1}^m\binom mj=2^m-\dim\mathrm{RM}(r,m) $$
で、線形符号 の命題「双対符号の次元」により右辺は $\dim\mathrm{RM}(r,m)^\perp$ に等しい。従って等号が成り立つ。$\square$

$m$ が奇数で $r=\frac{m-1}2$ なら $m-r-1=r$ なので、$\mathrm{RM}(r,m)$ は自己双対である。例えば $\mathrm{RM}(1,3)$ は自己双対な $[8,4,4]$ 符号である。

小さい次数と大きい次数の Reed–Muller 符号

$m\ge2$ とする。
(1) $\mathrm{RM}(1,m)$ の符号語は、$0$ と全 $1$ の語と、重みがちょうど $2^{m-1}$ の $2^{m+1}-2$ 個の語からなる。
(2) $\mathrm{RM}(m-1,m)$ は重みが偶数の語の全体である。
(3) $\mathrm{RM}(m-2,m)$ は、$x=0$ の座標を除くと $m$ 次の 2 元 Hamming 符号になり、$\mathrm{RM}(m-2,m)$ 自身は、座標の並べ替えを除いて、その拡大 Hamming 符号(偶奇の検査の座標を付け加えたもの)である。

  1. 定数でない 1 次式 $\ell(x)=b_1x_1+\dots+b_mx_m+b_0$($b\ne0$)は $\mathbb F_2^m\to\mathbb F_2$ の全射なアフィン写像なので、値 $1$ をとる点はちょうど $2^{m-1}$ 個である。1 次以下の式は $2^{m+1}$ 個で、そのうち定数は $2$ 個である。
  2. thm-rm-dual で $r=0$ とすると、$\mathrm{RM}(m-1,m)=\mathrm{RM}(0,m)^\perp$ は全 $1$ の語と直交する語、すなわち重みが偶数の語の全体である。
  3. thm-rm-dual で $r=1$ とすると、$c\in\mathrm{RM}(m-2,m)$ は $c$ が $\mathrm{ev}(1),\mathrm{ev}(x_1),\dots,\mathrm{ev}(x_m)$ と直交すること、すなわち
    $$ \sum_xc_x=0,\qquad\sum_xc_x\,x=0\in\mathbb F_2^m $$
    と同値である。第 2 式で $x=0$ の項は消えるので、$x=0$ の座標を除いた語 $c^\circ$ について、これは「列が $\mathbb F_2^m$ の $0$ でない元すべてである $m\times(2^m-1)$ 行列 $H$ で $Hc^{\circ\mathsf T}=0$」という条件で、Hamming符号 の定義の符号である。第 1 式は $c_0=\sum_{x\ne0}c_x$ を意味し、除いた座標が偶奇の検査の座標であることを表す。$\square$

多数決による復号

lem-rm-evaluation の係数の式を、次数の高い単項式から順に使う。

部分立方体の上の和

$0\le t\le m$、$\#S=t$ とし、$f=\sum_Ta_Tx_T$ を次数 $t$ 以下の多重線形多項式とする。$S$ の外の座標を任意の $b\in\mathbb F_2^{[m]\setminus S}$ に固定した $2^t$ 点の集合(部分立方体)を $Q_{S,b}$ とすると
$$ \sum_{x\in Q_{S,b}}f(x)=a_S. $$

$Q_{S,b}$ の上で $f$ は $S$ の変数だけの多重線形多項式 $f_b$ になる。単項式 $x_T$ は、$T\supseteq S$ なら $\deg f\le t$ より $T=S$ に限られ、そのまま $x_S$ として残る。$T\not\supseteq S$ なら、$S$ の変数のうち $x_T$ に現れないものがあるので、$S$ の外の変数に $b$ を代入した後も $S$ の変数全部の積にはならない。よって $f_b$ の $x_S$ の係数は $a_S$ である。lem-rm-evaluation を $t$ 変数の関数 $f_b$ と $S$ 全体に当てると、$x_S$ の係数は $Q_{S,b}$ 全体の上の和に等しい。$\square$

Reed の多数決復号

受け取った語 $y\in\mathbb F_2^{2^m}$ と $r$ に対し、$P_{r+1}:=0$ とし、$t=r,r-1,\dots,0$ の順に次を行う。$y_t:=y+\mathrm{ev}(P_{t+1})$ とし、$\#S=t$ の各 $S$ について、$2^{m-t}$ 個の部分立方体の和 $\sum_{x\in Q_{S,b}}y_t(x)$($b\in\mathbb F_2^{[m]\setminus S}$)のうち多い方の値を $\hat a_S$ とする(同数なら $0$)。$P_t:=P_{t+1}+\sum_{\#S=t}\hat a_Sx_S$ とする。最後に $\mathrm{ev}(P_0)$ を出力する。

多数決復号は最小距離の半分未満の誤りを直す

$0\le r\le m-1$ とする。$c=\mathrm{ev}(f)\in\mathrm{RM}(r,m)$ と誤り $e$ について、$\operatorname{wt}(e)< 2^{m-r-1}$(最小距離の半分未満)なら、def-rm-majority は $y=c+e$ から $c$ を出力する。手間はビット演算 $O(4^m)$ 回である。

誤りに触れる部分立方体は少数派

$f=\sum_Ta_Tx_T$ とし、$f_{>t}:=\sum_{\#T>t}a_Tx_T$ とおく。$t=r+1,r,\dots,0$ について $P_t=f_{>t-1}$、すなわち $P_t$ は $f$ の次数 $t$ 以上の部分であることを、$t$ についての下向きの帰納法で示す。$t=r+1$ では $\deg f\le r$ より両辺は $0$ である。
$P_{t+1}=f_{>t}$ と仮定する。$y_t=y+\mathrm{ev}(f_{>t})=\mathrm{ev}(f+f_{>t})+e$ で、$g:=f+f_{>t}=\sum_{\#T\le t}a_Tx_T$ は次数 $t$ 以下である。$\#S=t$ を固定する。$b$ を動かした $2^{m-t}$ 個の部分立方体 $Q_{S,b}$ は互いに交わらないので、$e$ の台と交わるものは $\operatorname{wt}(e)$ 個以下である。$e$ の台と交わらない $Q_{S,b}$ では、lem-rm-subcube により
$$ \sum_{x\in Q_{S,b}}y_t(x)=\sum_{x\in Q_{S,b}}g(x)=a_S. $$
$t\le r$ なので $2^{m-t}\ge2^{m-r}>2\operatorname{wt}(e)$ であり、値 $a_S$ を返す部分立方体は過半数を占める。よって $\hat a_S=a_S$ がすべての $\#S=t$ で成り立ち、$P_t=f_{>t}+\sum_{\#S=t}a_Sx_S=f_{>t-1}$。
帰納法により $P_0=f$ で、出力は $\mathrm{ev}(f)=c$ である。手間は、各 $t$ と $\#S=t$ の $S$ について部分立方体の和をとるのが $2^m$ 回の加算、$y_t$ の更新も 1 段あたり $2^m\cdot\#\{S\}$ 回以下なので、全体で $2^m\sum_{t\le r}\binom mt\le4^m$ の定数倍である。$\square$

$2^{m-r}$ は偶数なので、$\operatorname{wt}(e)< 2^{m-r-1}$ は「$\operatorname{wt}(e)\le\lfloor(d-1)/2\rfloor$」と同じであり、線形符号 の定理「訂正できる誤りの個数」の限界まで多数決だけで届く(GRS25 Lemma 13.2.5–Theorem 13.2.6, pp. 279–280、ASY21 Sect. V-A)。符号語を全部比べる最近の符号語の探索では $2^{\dim}$ 個の候補を調べるので、$r$ が大きいと復号の手間の差は大きい。

Kronecker 積と Polar 符号との関係

Kronecker 積の行

$F:=\begin{pmatrix}1&0\\1&1\end{pmatrix}$ とし、$m$ 重の Kronecker積 $F^{\otimes m}$ の行と列を $\mathbb F_2^m$ の辞書式の順で番号づける。行 $i$ は $\mathrm{ev}\bigl(\prod_{j:\ i_j=0}(1+x_j)\bigr)$ で、その重みは $2^{\operatorname{wt}(i)}$ である。とくに、重みが $2^{m-r}$ 以上の行の全体は $\mathrm{RM}(r,m)$ の基底である。

Kronecker 積の定義から $(F^{\otimes m})_{i,x}=\prod_jF_{i_j,x_j}$ で、$F_{0,x}=1+x$、$F_{1,x}=1$ だから前半が成り立つ。$Z(i):=\{j\mid i_j=0\}$ とおくと、$\prod_{j\in Z(i)}(1+x_j)$ の値が $1$ になる点は $Z(i)$ の座標が $0$ の $2^{m-\#Z(i)}=2^{\operatorname{wt}(i)}$ 点である。重みが $2^{m-r}$ 以上の行は $\#Z(i)\le r$ の行で、次数 $r$ 以下の多項式の評価だから $\mathrm{RM}(r,m)$ に入る。その個数は $\sum_{i\le r}\binom mi=\dim\mathrm{RM}(r,m)$ である。$\prod_{j\in Z}(1+x_j)=x_Z+\sum_{T\subsetneq Z}x_T$ だから、$\#Z$ についての帰納法により、$\#Z\le r$ の各 $x_Z$ はこれらの行の評価の一次結合で書ける。よって行は $\mathrm{RM}(r,m)$ を張り、個数が次元に等しいので基底である。$\square$

Polar符号 の生成行列 $G_N$($N=2^m$)は $F^{\otimes m}$ の行を並べ替えたものなので、Reed–Muller 符号は「Polar 変換の行を重みの大きい順に選んだ符号」である。Polar 符号は同じ行の中から合成通信路の良い順に選ぶ。長さ $8$・次元 $4$ で 2 値消失通信路 $\mathrm{BEC}(\frac12)$ の例では両者は一致し $\mathrm{RM}(1,3)$ になるが、長くなると選び方が分かれる(Polar符号 の例「行の重みで選ぶと悪い合成通信路を含む」)。

2 値消失通信路での容量の達成

$R\in(0,1)$ について、次数を $r_m=\max\{\lfloor\frac m2+\frac{\sqrt m}2Q^{-1}(1-R)\rfloor,0\}$($Q(t)$ は標準正規分布で $t$ 以上となる確率)とした Reed–Muller 符号の列は、速さ $\dim\mathrm{RM}(r_m,m)/2^m$ が $R$ に収束し、2 値消失通信路 $\mathrm{BEC}(\varepsilon)$($\varepsilon< 1-R$)で、ブロック全体の最大事後確率復号の誤りの確率が $0$ に近づく(KKMPSU17 Theorem 27、ASY21 Theorem 18)。証明は符号の置換群が 2 重可移であることと単調な Boole 関数のしきい値の現象を使う。この記事では証明しない。消失通信路以外の 2 値入力の対称な無記憶通信路で同じことが成り立つかを、2021 年刊の総説 ASY21 は未解決の問題として挙げている(Sect. I・VI-A)。

$\dim\mathrm{RM}(r,m)/2^m$ は 2 項分布 $\mathrm{Bin}(m,\frac12)$ が $r$ 以下になる確率なので、速さが $R\in(0,1)$ に収束するには $r_m$ が $m/2$ から $\sqrt m$ の定数倍の範囲になければならず(KKMPSU17 Theorem 27 の $v_n$ はこの形である)、このとき相対最小距離 $2^{-r_m}$ は $0$ に近づく。最小距離が符号長に比例しなくても、消失通信路では容量に届くということである。消失通信路で符号語を一様に選んで送るとき、消えていない座標の値と一致する符号語はどれも事後確率が等しいので、ブロック全体の最大事後確率復号はそれらを連立一次方程式の解として Gauss消去法 で求めることに当たり、多項式時間でできる(Polar符号 の逐次除去復号の手間は $O(N\log N)$ である)。

例と反例

$\mathrm{RM}(1,3)$ と 1 個の誤りの復号

$\mathrm{RM}(1,3)$ の生成行列は、$\mathrm{ev}(1),\mathrm{ev}(x_1),\mathrm{ev}(x_2),\mathrm{ev}(x_3)$ を行とする
$$ G=\begin{pmatrix}1&1&1&1&1&1&1&1\\0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix} $$
で、$[8,4,4]$ 符号である。$f=1+x_1+x_3$ を送ると $c=10100101$ で、点 $(0,1,0)$ の座標が化けて $y=10000101$ を受け取ったとする。$x_1$ の係数は、$(x_2,x_3)$ を固定した 4 個の部分立方体(辺)の和 $1,1,0,1$ の多数決で $1$。同様に $x_2$ は $1,0,0,0$ から $0$、$x_3$ は $1,0,1,1$ から $1$。$y+\mathrm{ev}(x_1+x_3)=11011111$ の多数決で定数項は $1$ となり、$1+x_1+x_3$ が復元される。

小さい $m$ のパラメータ

$[n,k,d]$ は次のとおりである。

$r$$0$$1$$2$$3$$4$
$m=3$$[8,1,8]$$[8,4,4]$$[8,7,2]$$[8,8,1]$
$m=4$$[16,1,16]$$[16,5,8]$$[16,11,4]$$[16,15,2]$$[16,16,1]$
$m=5$$[32,1,32]$$[32,6,16]$$[32,16,8]$$[32,26,4]$$[32,31,2]$

$[16,11,4]$ と $[32,26,4]$ は拡大 Hamming 符号(cor-rm-extremes (3))、$[16,5,8]$ と $[32,6,16]$ は 1 次の符号(同 (1))である。

反例:最小距離の半分の誤りは直せない

$\mathrm{RM}(1,3)$($d=4$)で $y=11000000$ を受け取ったとする。$y$ から距離 $1$ 以下の符号語はなく、距離 $2$ の符号語は $00000000$、$11110000$、$11001100$、$11000011$ の 4 個ある。どの復号も、そのうちの 3 個については、送られたものが真の符号語であっても誤る。従って thm-rm-majority の条件 $\operatorname{wt}(e)< 2^{m-r-1}$ は、$2^{m-r-1}$ に緩められない。

反例:最小距離は Singleton の限界から遠い

線形符号 の定理「Singleton の限界」$d\le n-k+1$ は $\mathrm{RM}(1,4)$ で $8\le12$、$\mathrm{RM}(2,5)$ で $8\le17$ で、等号から遠い。$\mathrm{RM}(r,m)$ が等号を満たすのは $r=0$、$r=m-1$、$r=m$ に限る。

計算を開く

$r=0$ では $k=1$、$d=2^m=n$。$r=m-1$ では $k=2^m-1$、$d=2$。$r=m$ では $k=n$、$d=1$。いずれも $d=n-k+1$。$1\le r\le m-2$ では、$n-k+1=1+\sum_{j=1}^{m-r}\binom m{r+j}$ と $d=2^{m-r}=1+\sum_{j=1}^{m-r}\binom{m-r}j$ を項ごとに比べる。$\binom{m-r}j=\binom{m-r}{m-r-j}\le\binom m{m-r-j}=\binom m{r+j}$ で、$j=m-r-1\ (\ge1)$ の項は $\binom{m-r}{m-r-1}=m-r< m=\binom m{m-1}$ なので、$n-k+1-d\ge r>0$。

主張反例満たされない条件
多数決復号は最小距離の半分の誤りまで直せるex-rm-half$\operatorname{wt}(e)< d/2$
Reed–Muller 符号は Singleton の限界を等号で満たす$\mathrm{RM}(1,4)$(ex-rm-singleton)$r\in\{0,m-1,m\}$
行の重みで選ぶ規則と合成通信路の良さで選ぶ規則は一致する長さ $32$・次元 $16$ の $\mathrm{BEC}(\frac12)$ の符号(Polar符号)符号が短いこと(長さ $8$・次元 $4$ の $\mathrm{BEC}(\frac12)$ では一致)

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する