第3章:離散情報源の符号化

情報源符号化/通信路符号化

3.1 符号の分類

符号化をすると符号語ができる。

記号の種類数による分類

符号に使う記号の種類数
よく使うのは２元符号 {0,1}

符号化の単位による分類

• 通報の記号毎
• 通報のブロック毎（n文字毎：n次拡大情報源）…（等長の）ブロック符号
• 通報の非等長の系列の組（非ブロック符号）

復号化からみた分類

• 特異符号：符号語とシンボルが1対1でない（Ⅵ）
• 非特異符号：符号語とシンボルが1対1である
  • 一意復号可能な符号
    • 瞬時符号：逐次復号可能な符号（Ⅰ,Ⅱ,Ⅲ）
    • 非瞬時符号：逐次復号不可能な符号（Ⅳ）
  • 一意復号不可能な符号（Ⅴ）

非特異な等長符号は必ず瞬時符号になる。

望ましい情報源符号化

1. 一意復号可能。できれば瞬時符号
2. 1情報源シンボルあたりの平均符号長ができるだけ短い
3. 符号化・復号化の操作が簡単

3.2 符号の基本性質

符号の木と瞬時符号

符号をtree構造であらわす。