4.8 定长编码

定长编码

定长编码（fixed-length coding）是指所有码字长度均相等的编码方式。对于信源符号集 $\mathcal{X}$，如果每个符号使用 $\lceil \log |\mathcal{X}|\rceil$ 个比特来表示，则编码后总长度为 $n\log |\mathcal{X}|$ 比特。这种编码方式虽然简单直观，但完全没有利用符号概率分布的非均匀性，通常存在较大的冗余。

利用典型集（typical set）的概念，可以将定长编码的压缩率大幅降低。根据渐进等分性（Asymptotic Equipartition Property, AEP），当序列长度 $n$ 足够大时，信源序列属于 $ϵ$-典型集的概率趋近于 1，而典型集中序列的个数约等于 $2^{nH(X)}$：

$$\mathrm{Pr}\left(X^{(n)}\in A_{ϵ}^{(n)}\right)\to 1,|A_{ϵ}^{(n)}|\approx 2^{nH(X)}$$

其中 $A_{ϵ}^{(n)}$ 表示 $ϵ$-典型集。因此，编码时只需对典型集中的序列分配码字，每个序列约用 $nH(X)$ 比特表示；对非典型序列则可以统一使用一个特殊标记或者原样输出。由于非典型序列出现的概率极低，这种编码方案在 $n$ 充分大时能够将总长度从 $n\log |\mathcal{X}|$ 压缩到约 $nH(X)+1$ 比特，且译码错误概率可以任意小。

定长编码的局限性在于：要保证译码错误概率足够小，序列长度 $n$ 必须很大，这导致编码器和译码器的实现复杂度显著增加。此外，定长编码即使结合典型集方法，码长也是预先固定的，无法根据每个符号的实际概率自适应调整。因此在实际工程中，变长编码（如 Huffman 编码和算术编码）往往比定长编码有更好的压缩性能，尤其是处理短数据或非平稳信源时优势更加明显。

链接到

• 上一个知识点：4.7 哈夫曼编码
• 下一个知识点：4.9 块编码