编码理论

• 数据可看作随机变量 ${\displaystyle X:\Omega \rightarrow {\mathcal {X}}}$，其中${\displaystyle x\in {\mathcal {X}}}$出现概率为 ${\displaystyle \mathbb {P} [X=x]}$。
• 数据用字母表 ${\displaystyle \Sigma }$ 中的字符串（单词）进行编码的。
• 码是一个函数 ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$（或当空字符串不在字母表内时为 ${\displaystyle \Sigma ^{+}}$）。${\displaystyle C(x)}$ 是与 ${\displaystyle x}$ 关联的码字。
• 码长写作 ${\displaystyle l(C(x))}$。
• 码长的期望值为 ${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}$
• 码字拼接 ${\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})}$.
• 空字符串的码字为空字符串本身：${\displaystyle C(\epsilon )=\epsilon }$

1. 当 ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ 为单射时，是非奇异码。
2. 当 ${\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}}$ 为单射时，是唯一可解码代码。
3. 如果 ${\displaystyle C(x_{1})}$ 和 ${\displaystyle C(x_{2})}$ 相互不是另一个的前缀，则 ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ 是前缀码。

信源的熵是信息的度量。基本上，信源编码在尽量减少信源的冗余，用携带更多信息的更少的比特来表示信源。

明确试图根据特定的假定概率模型来最小化消息的平均长度被称为熵编码。

有各种采用信源编码方案试图达到信源熵的极限的技术。C(x) ≥ H(x)，其中 H(x) 为信源熵（比特率），C(x) 为压缩后的比特率。特别指出，没有源编码方案可以比信源的熵更好。

傳真传输使用简单的游程编码。信源编码去除所有发射机必要发送以外所有多余数据，降低了传输所需的带宽。