巡回符号の最小距離

BCH限界 巡回符号の最小距離$${d_{min}}$$は、生成多項式がh個の連続根をもつとすると、$${d_{min} \geq h+1}$$である。

連続根 生成多項式$${g(x)}$$の根の中で、べき指数が連続する根のこと。例えば$${g(x) = (x^4+x+1)(x^4+x^3+x^2+x+1)}$$は根が$${\alpha, \alpha^2, \alpha^3, \alpha^4,\alpha^6, \alpha^8,\alpha^9,\alpha^{12} }$$の根をもつ。このうち$${\alpha, \alpha^2, \alpha^3, \alpha^4}$$は連続根だから、4個の連続根を持っている。

証明 符号長nの符号多項式を$${w(x) = w_0 + w_1x + \cdots + w_{n-1}x^{n-1}}$$とおく。生成多項式$${g(x)}$$のh個の連続根$${\alpha^a, \alpha^{a+1},\cdots, \alpha^{a+h-1}}$$を代入すると

$$
w(\alpha^a) = w_0 + w_1\alpha^a + \cdots + w_{n-1}\alpha^{(n-1)a} \\
w(\alpha^{a+1}) = w_0 + w_1\alpha^{a+1} + \cdots + w_{n-1}\alpha^{(n-1)(a+1)} \\
\cdots \\
w(\alpha^{a+h-1}) = w_0 + w_1\alpha^{a+h-1} + \cdots + w_{n-1}\alpha^{(n-1)(a+h-1)} \\
$$

より行列としてかける

$$
\boldsymbol{w}H^T=0 \\
\boldsymbol{w} = (w_0, w_1 , \cdots,w_{n-1}) \\
H =
\begin{pmatrix}
1 & \alpha^a & \alpha^{2a} & \cdots & \alpha^{(n-1)a} \\
1 & \alpha^{a+1} & \alpha^{2(a+1)} & \cdots & \alpha^{(n-1)(a+1)} \\
\cdots \\
1 & \alpha^{a+h-1} & \alpha^{2(a+h-1)} & \cdots & \alpha^{(n-1)(a+h-1)} \\
\end{pmatrix}
$$

方針としては以降、$${H}$$の任意のh列が一次独立であるならば$${ \boldsymbol{w}}$$には、0ベクトルでない限りは$${h+1}$$以上0でない成分がある　という性質に帰着させ、符号の最小ハミング重みが$${h+1}$$以上だから最小距離$${h+1}$$以上という形で証明する。
というわけで、$${H}$$の任意のh列が一次独立であることを証明するため、ヴァンデルモンドの行列式の形にする。

まず行列$${H}$$の任意のh列をとった行列$${A}$$を次のように表現する。

$$
A =
\begin{pmatrix}
\alpha^{s_1a}                  & \alpha^{s_2a}          & \cdots & \alpha^{s_ha} \\
\alpha^{s_1(a+1)}           & \alpha^{s_2(a+1)}    & \cdots & \alpha^{s_h(a+1)} \\
\cdots \\
\alpha^{s_1(a+h-1)}        & \alpha^{s_2(a+h-1)} & \cdots & \alpha^{s_h(a+h-1)} \\
\end{pmatrix} 
$$

行列式

$$
det A = \alpha^{s_1a} \alpha^{s_2a} \cdots \alpha^{s_ha} det
\begin{pmatrix}
1                  & 1    &      \cdots      & 1 \\
\alpha^{s_1}           & \alpha^{s_2}    & \cdots & \alpha^{s_h} \\
\cdots \\
\alpha^{s_1(h-1)}        & \alpha^{s_2(h-1)} & \cdots & \alpha^{s_h(h-1)} \\
\end{pmatrix}  \\
= \pm \alpha^{s_1a} \alpha^{s_2a} \cdots \alpha^{s_ha} \prod_{1 \leq i< j \leq h} (\alpha^{s_j} - \alpha^{s_i} )
$$

$${\alpha^{s_1} \alpha^{s_2} \cdots \alpha^{s_h}}$$はすべて異なるから、これは0にはならない。したがってHの任意のh列は一次独立。