色々端折った説明.通信路上でエラーが載るので, そのエラーを訂正するために使われるのが誤り訂正符号である. さて, 符号理論ではエラーのモデルとして以下の二つが考えられる. シャノン 1文字ごとにエラーが付くか付かないかが決まる (また各エラーは独立で…

q : 素数, n, m : 整数 のとき、 を示せ。0 < n < q^m とします。 逆にした方が分かり易いんじゃないでしょうか. 証明 Z/qZ上で, 恒等式が成立すれば題意が言える.まずZ/qZでを示す. これは割と簡単に言えて, の係数は. 0 < a < qについてとなるのでOK. (\bi…

Introduction to Coding Theory作者: Ron Roth出版社/メーカー: Cambridge University Press発売日: 2006/02/23メディア: ハードカバー クリック: 6回この商品を含むブログ (1件) を見る 5章 GRS符号の 5.4まで進んだ. ここは本文の説明は楽なんだが, 問題を…

Guruswami and Vardy “Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard” (SODA 2005). MLDは最尤復号でいいんだったかな. MLD-LinearとはF_q要素のm×n行列とシンドロームsと正整数wを入力として, Hv^t=s^tかつハミング重みがw以下となるn次の…