[信息和通信]源代码.ppt

紧凑型实时代码: 平均代码长度恰好等于源熵信源编码分为，并且其编码效率为100％的实时代码. 1963年，艾布拉姆森（Abramson）发现，符号的概率为码字是ni，可以编译紧凑的实时代码. 示例假设连续符号出现在源中的概率分别为1 / 2、1 / 4、1 / 8和1/8. 尝试编译紧凑的即时代码，并将其平均代码长度与源熵进行比较. 解决方案: 众所周知，四个码字的长度分别选择为1、2、3和3. 编码后获得的码字分别为0、10、110和111. *源代码第2部分（第3章）效率与可靠性效率平均代码长度应尽可能小可靠性从传输中的错误中恢复的能力编码解码信息源源编码通道编码信息通道通道解码源解码目的地1基本概念2基本定理: 变长编码定理3即时代码（非连续代码）4 Shannon-Fano方法5 Huffman方法* 6数据压缩的分类和国际标准的介绍§1基本概念编码: 消息符号集的某种转换使用编码符号集.

示例汉字电报汉字号？标准电报？五单元电报，即{kanji}？ {0，1，2，...，9}？ {0，1}（5位数字0，1代表数字）0？ 01101，1？ 01011，2？ 11001，...，4？ 11010，...，8？ 01110，9？ 10011（0022）国家（0948）01101 01101 1101 110101101 10011 11010 01110 2源代码: 也称为数据（语音，图像信源编码分为，文本）压缩，目的是减少数字信息中的冗余并提高通信或存储的效率. 连续源代码: （A）A / D转换（未讨论）； （B）消除冗余. 离散源的统计特征: 离散消息-在一组有限的符号中选择几个符号的随机序列；形成消息时，每个符号出现的概率是不同的；组成消息的符号之间存在一定的相关性. 源的最佳编码: 在信息量保持不变（或允许一定程度的失真）的条件下，每个码字的平均长度最短，即每个符号中包含的平均信息量为最大的. §2无干扰离散信道的源编码定理（仙农第一定理，先农无失真源编码定理）传输效率: 实际传输速率（R）与信道容量之比，即信道利用率容量. ？ = R / C对于无干扰（无噪声）通道，？ =实际源熵/最大源熵= H0（X）/最大H（X）问: 可以有多大？ 2 [仙农的第一定理]: 如果离散无记忆源的熵为H（X），并且通过容量为C（位/符号）的无干扰信道传输，则始终可以找到一种编码方法对输出进行编码，以使其在通道中的传输速率任意接近通道容量C（正定理）.

（证明的缩写）逆定理: 没有编码方法，因此传输速率R大于或等于C. 3源编码器的作用: 转换源以最大化H（X） ，这样的过程？ 1？ 1是优化源代码的过程. 源编码也称为将源与通道匹配的最佳编码. 类比: 源分为带内存的源和不带内存的源: 有带内存的源-源发送的符号前后连接. 一个符号的外观将影响另一符号的外观. 没有存储源-符号是独立的，并且符号出现的概率与前面的符号有关. ？最大化H（X）涉及两个步骤: （1）符号独立性，符号之间的相关性除外； （2）每个符号的概率相等. 本章仅考虑无内存离散源的编码，而不考虑步骤（1）. §3编码效率和变长编码定理的最小平均编码长度和编码效率平均编码长度: 可以证明，码字的平均长度（1）如果D = 2，则为最小平均编码长度，则（2）编码效率: （3）编码残差度: 例如，离散源输出为4个符号，长度为1，每个符号的概率为1 / 2、1 / 4、1 / 8. 1/8，求平均码长度和编码效果. 解: ？源代码编码的必要性: 实际的源代码通常包含很多冗余，例如，英文字母（包括空格字符）总共有27个符号，如果等价出现，则每个符号的信息量为4.76位，在没有内存的情况下，实际的源熵仅为4.076bit /符号. 如果考虑两个字母之间的相关性，则实际的熵仅为3.32bit /符号. 如果考虑100个字母之间的相关性，则实际字母的源熵仅为1位/符号，其余编码度为79％！如何编码以使平均代码长度最短？通常，离散源的每个符号的概率不相等. 可以看出，具有高概率的符号被短编码，而具有低概率的符号被长编码，从而平均编码长度是最短的. 莫尔斯电报使用此方法. 编码方法示例离散源由4个符号S1，S2，S3和S4组成，它们的出现概率分别为0.6、0.2、0.2、0.1和0.1. 尝试使用其他方法进行编码和比较. 代码（1）: Ruofa S4S1 =（110），接收时可以转换为11，0 = S4S1或110 = S3，不能唯一翻译；代码（2）: 等长代码，可唯一翻译，效率较低；代码（3）: 每个代码字都以0结尾，称为逗号代码，它是唯一可翻译的，可以与收据一起翻译；代码（4）: 从0开始，必须等待下一个0到达，然后才能启动代码； 5）: 可立即翻译.

编码的一般原则: 必须是唯一可翻译的； （2）高概率的短码，低概率的长码； （3）可以区分空格的代码字； （4）必须立即可用翻译. 可变长度编码定理: 如果离散源的熵为H（X），并且每个源符号都用D元符号编码，则存在某种编码方法，并且对于二进制编码，满足码字的平均长度（D = 2），则有（2）对于L阶扩展源，存在以下关系[注]: （1）定理只是一个极限定理，当L为无穷大时必须达到理论条件; （2）一些信息源（例如语音，图像等）在实际应用中经常允许一定程度的失真（未研究）. §4实时代码（非连续长代码，非扩展代码）1唯一可解码（单个代码）和实时代码编码的等长代码，变长代码等长代码: 效率低，简单方便可变长度代码: 效率高，但难以区分代码字. 要求: ？只能翻译；？立即-可以在接收时翻译，无需等待. （1）唯一可解码（单个代码）: 只能翻译一个结果示例C1 = {1、01、00}接收顺序（唯一翻译）1、00、01、10、1（唯一可翻译代码，单个含义代码） C2 = {0，10，01}接收序列01001？ （两者都可以翻译成）01、0、01？ （也可以翻译成）0、10、01（不是唯一可翻译的，不是单一的）（2）实时代码（非连续代码）: 可以在收到代码字后进行翻译，而无需等待和观察什么符号以后收到.

示例（1）C1 = {S1，S2，S3，S4} = {0，01，011，111}接收顺序: 0111101101？如果接收和翻译: 0、111、1？不再翻译了吗？如果翻译是在接收后（从后到前）完成的: 01、111、011、01只能翻译，但需要等待（2）C2 = {S1，S2，S3，S4，S5} = {00， 01、10、110、111}接收顺序: 110101110100？ 110、10、111、01、00（可唯一解码）（3）实时代码与唯一可解码（唯一代码）之间的关系: 实时代码必须是唯一可解码（唯一代码），但唯一可解码的（monocode）不一定是即时代码. 实时代码存在的充要条件（1）实时代码存在的充要条件（就结构而言）: 即时代码中的任何代码字都不能作为另一个代码字的开头（前缀）或任何代码字不能是另一个代码字的延续（扩展），因此此代码也称为非延续代码. （2）即时代码存在的充分必要条件（从代码长度开始）: 存在代码长度为ni（i = 1,2，...，n）的N个即时代码存在的充分必要条件是（D是编码符号集中的符号，即数字，即系统中使用的编码）. 已知示例: 源X = {x1，x2，...，x7}，使用2合编码，代码长度为ni = {2,2,3，3,3,4,5}，请尝试确定是否有这样的即时代码.

解决方案: 示例令wi表示代码长度为i，且w1 = 0，w2 = 3，w3 = 0，w4 = 5的代码字的数量. 找到可以编码为瞬时值的D的最小值. 码. 解决方案: 实时代码编码和解码编码器的说明（1）实时代码编码（代码树方法）例如，设置A = {0，1}，并编码X = {x1，x2，x3，x4 }转换成代码长度. 它是1,2,3,3的即时代码. 解决方案: D = 2原理: 任何代码字都不能用作另一个代码字的开头. 使用代码树图进行编码的步骤: 从顶点（树的根）开始，绘制两个（D = 2）分支，一个分支表示“ 0”，另一个分支表示“ 1”. 选择端点之一作为代码字，例如w1 = 0;？. 从未选择的端点再绘制两个分支，然后选择一个端点作为代码字w2;？. 继续直到W中的所有代码字都有一个端点用于表示；从树的根部开始到每个端点，依次读取每个分支代表的符号（0，1），并获得相应的代码字. w1 = 0 W2 = 10 W3 = 110 W4 = 111（2）实时代码解码示例在上面的示例中，如果接收到一串代码字100110010，请尝试使用代码树进行解码. 解决方案: 解码方法: 遵循代码树，遇到端点时获取一个代码字，然后返回到树的根，然后从头开始，直到所有代码序列都已翻译. 解码结果: W2 W1 W3 W1 W2，即10、0、110、0、10 *

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-195439-1.html