信息论与编码(傅祖云_讲义)第四.pptVIP

信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。 当N无穷大时，则可以实现几乎无失真编码 等长最佳编码效率下 ， 译码错误的概率 式中， 为信源序列的自方差。 当 和 均为定值时，只要L足够大， 可一小于任一正数 ，即 此时要求信源序列长度必满足 只要δ足够小，就可以几乎无差错地译码，当然代价是L变得更大。 无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。 例题：设离散无记忆信源概率空间为 信源熵为 自信息方差为 对信源符号采用定长二元编码，要求编码效率?=90%，无记忆信源有 ，因此 可以得到 如果要求译码错误概率 ，则 由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。 惟一可译变长码的判断法 结论：不能用Kraft不等式，只能根据定义判断码C是否是惟一可译码。 依据：非惟一可译变长码 有限长的码符号序列能译成两种不同的码字序列。 惟一可译变长码判别：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字时，码C为惟一可译变长码。 惟一可译变长码的判断法 构成集合F的方法： 首先，观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。依此下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随后缀产生为止。 接着，按照上述步骤将次短的码字直至所有码字可能产生的尾随后缀全部列出。 费诺编码也是一种常见的信源编码方法。 编码步骤如下： 将概率按从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。 例 设有一单符号离散信源 对该信源编二进制费诺码。编码过程如下表。 该信源的熵为 平均码长为 编码效率为 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。 题中码字还可用码树来表示，如图所示。 第七节 香农-费诺-埃里斯编码 霍夫曼(Huffman)编码是一种效率比较高的变长 无失真信源编码方法。 编码步骤 二进制哈夫曼编码 m进制哈夫曼编码 将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 例 设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。 信源熵为： 平均码长为 编码效率为