符号
情報理論や計算機科学において符号とは、情報源アルファベットから符号アルファベットへと一意に符号化するアルゴリズムを指す。一連のシンボル(文章)については情報源アルファベットから符号アルファベットへの変換を逐一行い、それらを連結することで符号化がなされる。
大雑把な例を示す。写像
C = { a ↦ 0 , b ↦ 01 , c ↦ 011 } {\displaystyle C=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}}
は符号を表しており、情報源アルファベットは集合 { a , b , c } {\displaystyle \{a,b,c\}} であり、符号アルファベットは集合 { 0 , 1 } {\displaystyle \{0,1\}} である。この符号を使って 0011001011 という符号文字列が得られたとする。これを符号語に分割すると 0 – 011 – 0 – 01 – 011 となり、復号すれば acabc というシンボル列が得られる。
形式言語理論の用語を使うと、符号の概念は次のように定義される。SとTという2つの有限集合があり、Sを情報源アルファベット、Tを符号アルファベットとする。符号 C : S → T ∗ {\displaystyle C:\,S\to T^{*}} は、Sの個々のシンボルがTの元を使ったワード(シンボルの並び)に対応する写像であり、 S ∗ {\displaystyle S^{*}} から T ∗ {\displaystyle T^{*}} への準同型写像に拡大すれば、情報源アルファベットの並びを符号アルファベットの並びへと自然に写像できる。