瞬時復号可能な符号

瞬時復号可能とは？

復号処理においては，入力として与えられるビット列は符号語の連接であるが， その切れ目を求める必要がある． ビット列を左から右へ処理する際に，各符号語の最後のビットを読んだ時点で それ以降のビット列に依存せずに決まる場合，瞬時復号可能 であるという．

例：瞬時復号可能な符号

例：瞬時復号可能でない符号

次の符号の場合，符号語の分割が後続するビット列に依存して決まるため， 復号に遅延が生じる．このような符号は，瞬時復号可能ではない．

語頭符号

いずれの符号語も別の符号語の先頭部分と一致しないとき， その符号を 語頭符号 とよぶ．

例

語頭符号と符号木

情報源符号を木構造として表したものを 符号木 とよぶ． 符号木は，各情報源記号に対応する節点を１つずつ含む． 情報源記号 に対応する節点を とするとき， 根から へ向かうパスは の符号語に対応する．

語頭符号の場合，その符号木において， 情報源記号に対応する節点は葉，すなわち，子孫をもたない節点である．

例：語頭符号とその符号木

例１ 例２ 例３ 例４

例：非語頭符号と符号木

例４ 例５ 例６

語頭符号の利点

任意の語頭符号は一意復号可能である．

任意の語頭符号は瞬時復号可能である．

語頭符号の復号

語頭符号の場合，符号木をたどることにより， 以下のように遅延なく復号を行うことができる（ 瞬時復号可能 ）．

例

例１ 例２ 例３