暗号絡みで誤り訂正がホットな時期を迎えていますが、動くコードが見つからなかったので自作。
洋書にアルゴリズムが書いてあったのに、誤植がひどくて動かなかった。
さんざん探し回った挙句、フランスのリヨン大学の論文が見つかって、そこからアルゴリズムを抜き出しました。
タイトル：Comparison of Different Decoding Algorithms for Binary Goppa Codes
Rayan Safieddine and Amund Desmarais
ここでは主にリードソロモン符号に特化して復号します。
もちろんGoppa符号でもできるはずです。
この論文がなければ、おそらく動くコードは作れなかったと思います。
とは言っても、この論文で検索しても全く出てこなかったり、そればかりかサイトにリンクを貼ることさえできないので、ここで疑似コードも交えながら説明していきたいと思います。
// Input:符号の次元をKとすると、K個のシンドロームを要素として持つ配列ｓ
// Output:誤り位置決定多項式（この多項式が０になる値を探すことでエラーの位置を求める）
vec bma(unsigned short s[]) //sはシンドロームの値
{
int L = 0, m = -1, d[K] = {0}, k = 0, i, e;
vec f = {0}, g = {0}, h, v;
f.x[0] = g.x[0] = 1;
while (k <= (2 * T - 1))
{
e = 0;
for (i = 0; i < L; i++)
e ^= gf[mlt(fg[f.x[i]], fg[s[k - i]])];
d[k] = gf[mlt(fg[f.x[i]], fg[s[k - i]])] ^ e;
if (d[k] > 0)
{
h = f;
memset(v.x, 0, sizeof(v.x));
v.x[k - m] = 1;
unsigned short a;
a = (m < 0) ? 1 : oinv(d[m]);
f = vadd(f, vmul(kof2(gf[mlt(fg[d[k]], a)], g), v));
if (L <= k / 2)
{
L = k + 1 - L;
m = k;
g = h;
}
}
k++;
}
return f;
}
動くコードの全体はこちらにあります。
make
手前味噌の恥ずかしいコードですが動いているように見えます。
これをNTLやSageMathに移植するのもやってみようかと思います。
でもアプリの使い方を覚えるより、自分で１から書いたほうが楽なので書きました。
今後さらに、基礎体が２以外の拡大体上で動くように一般化する予定です。
以下にアルゴリズムの疑似コードを書きます。
ほぼこのままプログラムすれば、リードソロモン符号の誤り位置を決定することは簡単にできます。
Berlekamp-Massey Algorithm
Inputs:シンドローム多項式:S(x)をｋ次の項の係数としてS[k]とする。
Outputs:エラー位置多項式をf(x)とする。
1.L=0
2.m= -1
2.f(x)=1
4.g(x)=1
5.d[m]=1
6.for k = 0 to k=2t-1 do
7. d[k]=S[k]+$\sigma_{i=1}^L f_iS_{k-i}$
8. if $d[k] \neq 0$ then
9. h(x)=f(x)
10. f(x)=f(x)+$\frac {d_[k]}{d[m]} g(x)x^{k-m}$
11. if L<= k/2 then
12. L=k+1-L
13. m=k
14. g(x)=h(x)
15. end if
16. end if
17. k=k+1
18.end for
19.return f(x)
バーレカンプ・マッシー アルゴリズムと言うと、誤り訂正符号をしている人にはとても有名な計算方法として知られているのですが、有名な割に本にも載ってないし、わかりやすい解説もなかったりするので、今回実装に成功した記念になにか書いてみようと思います。（英語版のウィキにもわかりにくく書いてある程度ですｗ）
今回実装したプログラムも、これと計算例から実装したもので、コーディング自体はそんなに難しくありませんでした。まだ動作原理は調査中ですが、疑似コードに計算例を追加して実装可能な状態にしていきます。そしてLSFRの最小多項式の決定と、代数的符号の復号問題のつながりについて考察したいと思います。
（続くｗ）
20230120（追記）
スッキリした方には０番目の位置にエラーがあると訂正できないというバグがあり、今日一日じゃ取り切れなかった。
昔のなんだかよくわからないけど正しいコードをベクトル型多項式に統一したのを移植。
なんとか動くけど理解してないので解説すらできない。
期待してた人はいないと思うけど、いたらもうしばらくお待ちください。
あるいは０番目の位置にエラーは入らないという前提でこのまま推し進めることもできるけど、じゃあなぜ０番目だけダメなのか、ということはやはりアルゴリズムの理解が足りないということなのでもう少し勉強します。
とりあえず０なんか無視してもいいから動くコードがほしいというなら、符号の０列目は全部０とみなして、１列目から符号が始まることにすればきれいなコードのまま動かすことができます。
モダンなマックエリスではランダムにトレースを選ぶのでそういう選択肢も十分あります。
なので動くは正義という方にとっては、疑似コードを見ながら何らかのライブラリを使って、手頃に実装できそうな難易度ではあると思います。
（逃げ）
続きはこちら。