読者です 読者をやめる 読者になる 読者になる

符号の性能評価

情報理論

9回目。一限はお腹が減る。。。

  • 色々な線形符号が存在
    • 性能がよいものもあれば悪いものもあるので、性能を客観的に測れる指標が欲しい
  • 最小ハミング距離や符号の重み分布を使った性能評価のやり方をやる
  • ベクトル間の距離を定義してやる必要がある
  • 常識的な通信路なら間違うならちょっとだけ間違うはず
    • (色々考えられる)符号語の選び方を、近いところにあるものを符号語にしてしまうと間違いにする影響されてしまいそう
    • 符号語同士の距離が離れていれば、ちょっとくらいの間違いには負けなさそう。ちょっと間違えても検出できる
  • 符号語同士の距離が離れていたほうがよさそうだ(直感的に)
  • ハミング距離
    • 系列中で異なる記号の個数
    • 距離の公理を満たす
  • 最小ハミング距離について考える
    • 和とかじゃなくって、最小を考えるのはわりと妥当かな
      • あんまり間違えないけど、時々間違えるみたいな状況だから最悪のケースをよくすることを考えたほうがよさそう
    • 線形符号ならば簡単に最小ハミング距離を計算することができる
      • まともにやると2乗のオーダーかかるし
  • 最小ハミング重み
    • 系列に含まれる1の個数
    • Cの符号語のハミング重みの最小値(0系列を除く)
  • 線形符号の場合、最小ハミング距離と最小ハミング重みは等しい
  • 「ハミング符号の最小ハミング距離は3である」という定理がある
    • 最悪ケースでも、これくらいは保証できるってことか
      • 3bits間違いが発生しないと符号語と符号語がかぶることはない
      • 3bitsも間違いが発生することはかなり低いはず
    • 「理論的に」最悪ケースを保証できる
  • 1ビット誤りを訂正できることがこれから分かってくる
  • 限界距離復号法
    • もうちょっと先まで行けるんだけど、あえてやらない
    • 検出はできるけど、訂正はしない
  • なんでそんなことをやるのか?
    • p19
  • 同じ符号長で同じ最小ハミング距離なら同じ性能なのか?
    • 厳密にはそうとは限らない
  • 最悪ケースしか考えていなかったから、期待値(的なもの)を考えるってことかな
    • 符号の重み分布というものについて考える
  • 線形符号なら符号の重み分布とハミング距離が一致する