シンドローム２倍加計画は達成不可能である
バーレカンプ・マッシー法に対する検査行列の構造を以下のように書くことが出来る。
\begin{pmatrix}
\frac{1}{f(x_i)},\frac{x_i}{f(x_i)},...,\frac{x^k_i}{f(x_i)}\end{pmatrix}^T
=
\begin{pmatrix}
\frac{1}{f(a_1)},\frac{1}{f(a_2)},...,\frac{1}{f(a_n)}\\
\frac{a_1}{f(a_1)},\frac{a_2}{f(a_2)},...,\frac{a_n}{f(a_n)}\\
\frac{a^2_1}{f(a_1)},\frac{a^2_2}{f(a_2)},...,\frac{a^2_n}{f(a_n)}\\
... \\
\frac{a^k_1}{f(a_1)},\frac{a^k_2}{f(a_2)},...,\frac{a^k_n}{f(a_n)}
\end{pmatrix}
=
\begin{pmatrix}
a^0_1,a^0_2,...,a^0_n\\
a_1,a_2,...,a_n\\
a^2_1,a^2_2,...,a^2_n\\
...\\
a^k_1,a^k_2,...,a^k_n\\
\end{pmatrix}
\cdot
\begin{pmatrix}
\frac{1}{f(a_1)},0,0,...,0\\
0,\frac{1}{f(a_2)},0,...,0\\
0,0,\frac{1}{f(a_3)},...,0\\
...\\
0,0,...,0,\frac{1}{f(a_n)}
\end{pmatrix}\\
=\\
V\cdot F
=
(a^i,a^{2i},a^{3i},...,a^{ki})
\cdot
\begin{pmatrix}
\frac{1}{f(a_1)},0,0,...,0\\
0,\frac{1}{f(a_2)},0,...,0\\
0,0,\frac{1}{f(a_3)},...,0\\
...\\
0,0,...,0,\frac{1}{f(a_n)}
\end{pmatrix}\\
\cdot
(e_0,e_1,e_2,...,e_n)^T
=(\frac{a_1^i}{f(a_1)},\frac{a_2^{2i}}{f(a_2)},...,\frac{a_n^{ki}}{f(a_n)})
\cdot
(e_1,e_2,...,e_n)^T
ここで行列$V$はVandermonde行列である。
シンドロームが２倍化できないことの例
GF(16)の生成多項式を、$x^4+x^3+1$とする。
今、リードソロモン符号の検査行列を次のように書く。
$$(2^i,2^{2i},2^{3i},2^{4i},2^{5i},2^{6i})^T$$
すると、最初の３列を抜き出してみると、
\begin{pmatrix}
1 & 2 & 4 \\
1 & 4 & 9 \\
1 & 8 & 15 \\
1 & 9 & 14 \\
1 & 11 & 10 \\
1 & 15 & 3
\end{pmatrix}
となる。このとき符号の０番目、１番目、２番目に値１のエラーが発生した場合のシンドロームを計算すると、
$$(7,12,6,6,0,13)$$
である。
もし２倍化によってシンドロームが伸長できたとすると、このシンドロームの最初の３要素から後半が計算できるはずであるが、この要素の掛け算からは計算できないような０の値が出てきてしまうので、そのような２倍化は不可能であることが分かる。
よって、シンドローム２倍化計画は達成不可能である。
どうやら私は２乗してから足すことと、足してから２乗することの違いを理解していないようだ。