一意復号可能な符号
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/08/04 04:40 UTC 版)
拡張が非特異である場合、符号が一意復号可能(uniquely decodable)であるという。符号が一意復号可能であるかどうかは、サーディナス＝パターソンのアルゴリズム（英語版）によって決定することができる。 写像 M 3 = { a ↦ 0 , b ↦ 01 , c ↦ 011 } {\displaystyle M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}} は一意復号可能である。これは、0が符号語の先頭にしか現れないので、符号文字列中に0が現れたら、それが符号語の区切りであることが明白だからである。 ここで前節の符号 M 2 {\displaystyle M_{2}} を再度検討する。この符号（実例はにある）は一意復号可能ではない。符号文字列 011101110011 は、符号語 01110-1110-011 の列として解釈できるほか、符号語 011-1-110 の列としても解釈できるからである。よって、この符号文字列は cdb と babe の2通りに復号しうる。しかし、このような符号は、全て可能な情報源シンボルの集合が完全に既知で有限である場合、またはこの拡張の情報源要素が受け入れられるかどうかを決定する制限（たとえば正式な構文）がある場合に便利である。そのような制限は、同じシンボルに写像される可能性のある情報源シンボルのどれがこれらの制限の下で有効であるかをチェックすることによって、元のメッセージを復号することが可能になる。
※この「一意復号可能な符号」の解説は、「可変長符号」の解説の一部です。
「一意復号可能な符号」を含む「可変長符号」の記事については、「可変長符号」の概要を参照ください。
- 一意復号可能な符号のページへのリンク
