線形符号と生成行列

• 復習
  • 偶パリティ符号は線形符号だったら、奇パリティ符号は線形符号ではない
  • 具体的な生成行列の生成方法の復習
    • p3の例。分かりやすい
    • modに乗せて、排他的論理和で考える

先週の続き(誤り訂正符号)。

• 線形符号は
  • 符号語集合がベクトル空間をなすような符号
  • 検査記号が，情報記号の線形式で定義される符号
• 生成行列
  • 基底符号語を行とする行列
  • 符号化操作を効率的に行うための道具

線形符号の復号操作(誤りの検出と訂正)

• 系列が「正しい」符号語の必要十分条件はパリティ符号のところの数字が等しくなること(方程式のところ)
  • パリテイ検査方程式
    • ここで、2進演算x - y = x + y(排他的論理和)が効いていることに注意
  • 系列の転置をかけて0ベクトルになるかを確認するだけでよい

• 生成行列と検査行列の比較
  • 係数の行列と単位行列の位置が入れ変わったような感じ

シンドローム

• 生成行列で検査行列で一通りのことができるようになった
• さっきは右辺に出てきたベクトルが0ベクトルかで符号語かを確認していたが、その系列のことをシンドロームと呼ぶ、らしい
  • このシンドロームを使って、誤りの訂正をすることができないか?ということを考えたい

• PRMLの線形回帰モデルっぽく符号語に誤りベクトル(雑音)が「加法的」に作用するモデルを考える
  • シンドロームは送信符号語に依存せず、誤りのみに依存する!!
    • uのところは消えてくれる
  • シンドロームを見れば、どんな誤りが発生したかを知ることができる

• シンドロームを見れば受信語の何ビット目に誤りがある、というようなパターンが出てくることが分かる
  • p14のスライド
• 誤りとシンドロームの対応表を「事前に」持っておくことができることが分かる
  • これを使えば正しく手元で復号できる
• 対応表をどうやってうまく作る?

• 符号語の中のどこか一つだけが間違う場合について考える
  • iビット目に誤りが発生したとする
  • シンドロームにはが出てくることが分かる
  • シンドロームと検査行列の列でどこと一緒かを見てやる(p17)
• こういう感じで1つだけしか違わない場合はわざわざstaticに対応表を持っておかなくてもよい

• いい符号を作るにはどうすればいいか、について考える
  • (1ビットだけ誤りが発生したのについて考えているのはまだ続いている模様)
• 誤りの場所がどこかを特定することができない符号が存在する
  • あれ、偶パリティ符号とかって線形符号の範疇じゃないんだっけ...?
• 列ベクトルが全て異なるように検査行列を設計してやればいいじゃないか

• 効率についても考えてやりたい
  • 検査行列が縦に長いと符号語中の検査記号数が多くなってしまって、符号の効率はよくない
  • 検査行列に対して、本質的に伝えたい情報の占める割合が小さくなってしまう
  • 検査行列を横に長くすればいいんじゃないか
    • そこでハミング符号ですよ、奥さん!!

ハミング符号

• できるだけ検査行列を横に長くする、がポリシー
• 全部0になっているベクトルは列ベクトルには考えない

• ハミング符号と垂直パリティ検査符号との比較
  • 情報記号数と両方とも1ビット誤り訂正可能
  • 効率ではハミング符号が上
  • 符号長が短かいこともあって、信頼性でもハミング符号がよい
    • 結構意外な感じの結果だけど、まあそうか

• 同等以上の能力でより効率的なものは存在するのか?
  • 実は存在しない(!!)
  • 系列の集合について考えてやると矛盾が出てきて、存在しないことが証明できる
• ハミング符号は系列を部分集合にちょうど分割してくれるという性質がある => ハミング符号は完全符号と言われる

情報理論 (ちくま学芸文庫)