DOSEIの日記

技術メモ+日常ログ

中間テスト答案返却。100点だった!!俺すげー(自画自賛)。平均点は91点。満点は7人だった。うーん、簡単すぎないか…でも、難しいよりはいいか。
BCH符号の復号(エラー訂正)の話。送信符号多項式 F(x)、受信符号多項式 Y(x)、誤り多項式 E(x) とすると、
Y(x) = F(x) + E(x)
である。原始根 α、最大訂正可能ビット数 t、生成多項式 G(x) とすると、
G(α1) = G(α2) = … = G(α2t) = 0
また F(x) = G(x)Q(x) なので、
Si := Y(αi) = E(αi)
となり、これがシンドロームになる。これを満たす E(αi) を求めればいい。
たとえば G(x) = 1+x+x3, Y(x) = 1+x で、 (i+1) ビット目に誤りがある場合、E(x) = xi であるので、
S1 = E(α) = αi
S2 = E(α2) = α2i
また、
S1 = Y(α) = 1+α
S2 = Y(α2) = 1+α2
この2式を満たす i を求めると3。ゆえに4ビット目が誤りと分かる。
複数ビットになった場合も、E(x) を適切に定めて解けばいいが、かなり大変である。しかも、簡単な解法が特にないらしい。うーむ。それに誤りの個数を特定する方法はなんなんだろう…。どこにも載ってない。