やや実用、研究的な話題

巡回符号
シャノンの通信路符号化定理
新しいタイプの誤り訂正符号

「実用的な」線形符号の模索
- 符号化、誤り検出、訂正は行列演算によって実行可能
- 性能を向上させるためには、符号長を大きくすると有利
規模の大きい線形符号が必要
- 生成行列、検査行列が大きくなる(符号長の2乗オーダー)
- 組み合わせ回路の面積が大きくなると、遅延、消費電力etcなどで扱いにくくなる
もっと扱いやすい線形符号はないか => 巡回符号(CDとかで使われているらしい)

巡回符号
- 線形符号の一種で、符号化器や復号気のハードウェア実現が簡単
  - 組み合わせ回路ではなく、"シフトレジスタ"を利用してこれらを構成する

シャノンの通信路符号化定理と通信路容量

シャノンの情報源符号化定理
- 情報源符号化の限界と可能性を示唆した定理
- 圧縮しようと思ったらそのエントロピーまで行ける
- ハフマン符号を持ってきて、そのブロック長を長くすれば理論的限界まで行ける
- 理論的限界とそれに到達する方法まで示されている
シャノンの通信路符号化定理
- 通信路符号化の限界と可能性を示唆した定理
- どうやったらそこに辿りつけるかについては未だに分かっていない

入力記号Xの確率分布をPxとし、出力記号をYとする。このとき、Yを知ることでXに関するあいまいさが減少すると考えられる。あいまいさがどれくらい減少したかの度合いは相互情報量I(X;Y)で考えることができる。

このようにYが手元ある状況で、最もそれらしい入力記号の分布を考えたりしたい。ここで、そのような入力分布が分かったとしたときに達成されるものを通信路容量Cという( $C = \mbox{max}_P_X I(X;Y)$ )。同じ入力Xでも、その分布Pxが異なると相互情報量は変化する。つまり、その通信路で得意な入力分布や苦手な入力分布が存在する、ということ。通信路容量というのは、その中でも一番得意な入力分布を持ってきたときの相互情報量である。

通信路符号化定理

符号語の長さに占める符号語の個数の割合のことを符号化率Rと定義(この辺もうちょっとちゃんと書いたほうがいい)
- (n, k)組織符号の場合、R = k / n
- kがnに近づくほど、余分な情報が付いてなくてユーザーとしてはうれしい

シャノンの通信路符号化定理では、通信路容量をCとしたときに

R <= Cならば、復号誤り率が限りなく0に近い符号が存在
- 通信路容量より符号化率を下げれば(余分な情報を付けてやる)、通信の途中でどんなエラーが発生しても誤りを訂正できる
- ただし、それをどのように作るかについては示されていない!
- ついでにCも具体的に分かるわけではないから、どれくらい付ければいいかも分からない
R > Cならば、そのような符号は存在しない

ということが示されている("A Mathmatical Theory of Communications" 1948)。