雑音のある通信路モデル

アルファベット ${\displaystyle \Sigma }$ が与えられたとき、${\displaystyle \Sigma ^{*}}$ を ${\displaystyle \Sigma }$ による全ての有限文字列の集合とし、有効な単語からなる辞書 ${\displaystyle D}$ を ${\displaystyle \Sigma ^{*}}$ の部分集合（すなわち ${\displaystyle D\subseteq \Sigma ^{*}}$ ）とする。

雑音のある通信路は行列

${\displaystyle \Gamma _{ws}=\Pr(s|w)}$,

である。ここで、${\displaystyle w\in D}$ は意図した単語、${\displaystyle s\in \Sigma ^{*}}$ は実際に受信された乱された単語である。

英語のアルファベット ${\displaystyle \Sigma =\{a,b,c,...,y,z,A,B,...,Z,...\}}$ を考える。いくつかの部分集合 ${\displaystyle D\subseteq \Sigma ^{*}}$ は、有効な英語の単語の辞書を構成する。

入力中に、以下のような間違いが発生する可能性がある。

1. 文字の脱落（例: letterがleterになる）
2. 文字の追加（例: mistakeがmisstakeになる）
3. 文字の入れ替え（例: receivedがrecievedになる）
4. 文字の置換（例: finiteがfimiteになる）

雑音のある通信路行列 ${\displaystyle \Gamma }$ を構築するには、与えられた意図した単語（全ての ${\displaystyle w\in D}$ と ${\displaystyle s\in \Sigma ^{*}}$ についての ${\displaystyle \Pr(s|w)}$）について、それぞれの間違いの確率を考慮する必要がある。これらの確率は、${\displaystyle s}$ と ${\displaystyle w}$ の間のレーベンシュタイン距離を考慮して、あるいは、エッセイの草稿と手作業で綴りを編集したものとを比較することによって、集めることができる。

雑音のある通信路モデルの目標は、受信した乱された単語から、意図した単語を見つけることである。決定関数 ${\displaystyle \sigma$ :\Sigma ^{*}\to D} は、乱された単語を与えると、目的の単語を返す関数である。

決定関数を構成する方法には、最尤推定法、最大事後法、最小距離法（英語版）がある。

乱された単語をそのまま意図した単語として受け入れる方が、辞書内の目的の単語を見つけようとするよりも良い場合もある。 たとえば、schönfinkeling（curryingの別名）という単語は辞書にないかもしれないが、実際には意図された単語かもしれない。

• 符号理論