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

情報を正確に伝える

情報理論 誤り訂正符号

今日から通信路符号化の話。信頼性の低い情報伝達媒体を介した情報通信を考えよう、という内容(効率化より、正確に伝えるというところにウエイトを置いてる)。

  • 誤りが起きないようにするのがベストだが、全く起きないようにするのは現実的に困難
    • 発想を変えて、誤りを検出できるようにしよう。検出できるようにしたら再送信を要求するようにしよう
  • 伝えたい情報に加えて、誤り訂正のための冗長な情報を付与してあげよう
    • 「い」と「り」だけじゃなくて、いろはの「い」とかりんごの「り」という感じ
  • 「正しい表現」間の距離が大きくなるように、冗長情報を付加
  • 送信された可能性の高い符号語を推測 => 復号
  • 誤り訂正符号を使う上でのデメリット
    • 復号結果が常に正しいとは限らない
    • 長い系列を送るので、系列中の誤り発生確率は増える => 本当に長くすることで得になるのか考えないといけない
      • 授業の例では得している例が挙げられていた
      • 必ずしもそうではない
      • 確率がどう変化するかグラフ書いておきたい
  • 通信路のモデル
    • 信頼のできない通信路を解した情報通信とモデル化
    • 入出力が一致するとは限らない
    • 消失通信路や記憶のある通信路、非定常な通信路(楕円軌道を取る人工衛生)などいくつか通信路のモデルがある
  • 長さmの2進系列をV^mと表記
  • 情報の集合をI = V^K、符号C \subset V^n(ただしn > k)とする
  • 加減算は2進体上で行ない、2進数として計算するわけではない
  • 符号選択の基準としては、符号化と復号が簡単に行なえるとうれしい
    • 線形符号という特殊なクラスについて考える
  • 偶パリティ符号
    • 一つ冗長な情報を付け加える
    • 全部の和(排他的論理和)を最後にくっつけてやる
  • こうすることで符号語に含まれる1の個数は必ず偶数個
    • 受信系列中に1が奇数個なら異常系列と分かる => 奇数個のビット誤りを検出できる線形符号
  • 情報記号が奇数個、冗長記号も間違えたらだめ? => 質問してみた
    • 偶数個だとダメで諦めるしかないが、実際に誤る確率は非常に低くて1ビットしか間違ない確率と2bit間違う確率は格段に違うのである意味妥当と言える諦め
    • もっと強力な符号化もあるらしい(2bit訂正するようなやつ)
  • 水平垂直パリティ検査符号
    • 縦横にパリティ用の符号を付け加えておく
    • 1bitの誤りが起こったときに、どこでそれが起こっているかを特定することができる
    • 2bit以上の誤りが発生したときには(検出はできる)訂正ができないのが水平垂直パリティ検査符号の限界
      • 性能評価は次回以降
  • 線形符号の定義
    • うほ、なんか式がいっぱい出てきたw
  • 偶パリティ符号も水平垂直パリティ検査符号も線形符号の具体的なものの一つ => これから一般化したものを考えたい
  • 定理 => 任意の符号語u, v \in Cに対し、u + vも符号語
    • 証明のところで出てくるfはパリティに使う冗長記号に対応している
      • 補題は証明する必要がある
  • 線形符号の任意の要素は規定符号語の線形組み合せの形で書き表わすことができる
    • p25の例が分かりやすい
  • 生成行列
    • この辺からよく分からなくなる...
    • この行列を使うと符号化の操作が簡単にできる...らしい