《后3章复习.》由会员分享，可在线阅读，更多相关《后3章复习.（30页珍藏版）》请在金锄头文库上搜索。
1、1、信源编码 信源编码分类：信源编码分类： 无失真编码：只对信源的冗余度进行压缩，不会改变：只对信源的冗余度进行压缩，不会改变 信源的熵，又称信源的熵，又称冗余度压缩编码，它能保证码元序列经，它能保证码元序列经 译码后能无失真地恢复成信源符号序列。译码后能无失真地恢复成信源符号序列。 有失真编码：会改变信源的熵，不可逆压缩，又称：会改变信源的熵，不可逆压缩，又称熵 压缩编码。 无失真信源编码的作用：无失真信源编码的作用： 符号变换：使信源的输出符号与信道的输入符号相匹：使信源的输出符号与信道的输入符号相匹 配；配； 冗余度压缩：使编码之后的新信源概率分布均匀化，：使编码之后的新信源概率分布均匀
2、化， 信息含量效率等于或接近于信息含量效率等于或接近于100%100%。 2 2、单符号信源无失真编码器模型、单符号信源无失真编码器模型 编码器编码器 f f 信信 源源 f f 是一一对是一一对 应的映射应的映射 bit/bit/码字或码字或bit/bit/符号符号 bit/bit/码元码元 新信源X ： 编码后的信息率R ：平均一个码元：平均一个码元 携带的信息量。携带的信息量。 bit/bit/码元码元 平均码长越小，每个码元携带的信息 量就越多，传输一个码元就传输了较 多的信息。 码元码元/ /符号符号 编码效率：编码后的实际信息率与编：编码后的实际信息率与编 码后的最大信息率之比。码
3、后的最大信息率之比。 新信源的冗余度也是也是码的冗余度码的冗余度： 码 奇异码 非奇异码 非唯一可译码 唯一可译码 定长非奇异码 变长非续长码 （部分）变长续长码 非分组码 分组码 唯一可译码（唯一可译码（UDCUDC）：）：该码的码字组成的任意有限长码字序列该码的码字组成的任意有限长码字序列 都能恢复成唯一的信源序列。否则称为都能恢复成唯一的信源序列。否则称为非唯一可译码非唯一可译码。 定长码定长码：所有的码字都具有相同的长度，否则为：所有的码字都具有相同的长度，否则为变长码变长码。 奇异码奇异码：含相同码字的码。否则称为：含相同码字的码。否则称为非奇异码非奇异码。 非续长码非续长码：码中任
4、一码字都不是另一码字的续长（延长）。否：码中任一码字都不是另一码字的续长（延长）。否 则为则为续长码续长码。 非即时码非即时码：如果接收端收到一个完整的码字后，不能立即译码：如果接收端收到一个完整的码字后，不能立即译码 ，还需等下一个码字开始接收后才能判断是否可以译码。否则，还需等下一个码字开始接收后才能判断是否可以译码。否则 为为即时码即时码。 定长无失真编码定理定长无失真编码定理：用：用r r元符号表对离散无记忆信源元符号表对离散无记忆信源U U 的的N N长符号序列进行定长编码，长符号序列进行定长编码，N N长符号序列对应的码长为长符号序列对应的码长为l l N N ，若对于任意小的正数
5、，若对于任意小的正数 ，有不等式，有不等式 就几乎能做到无失真编码，且随着序列长度就几乎能做到无失真编码，且随着序列长度N N的增大，译码的增大，译码 差错率趋于差错率趋于0 0。反过来，若。反过来，若 就不可能做到无失真编码，且随着就不可能做到无失真编码，且随着N N的增大，译码差错率趋的增大，译码差错率趋 于于1 1。 3、定长编码定理 无失真变长编码定理无失真变长编码定理：用：用 元符号表对离散无记忆信源元符号表对离散无记忆信源 的的 长符号串进行变长编码，记长符号串进行变长编码，记 长符号串对应的平均码长为长符号串对应的平均码长为 ，那么，要做到无失真编码，平均码长，那么，要做到无失真
6、编码，平均码长 必须满足必须满足 另一方面，一定存在唯一可译码，其平均码长另一方面，一定存在唯一可译码，其平均码长 满足满足 3、香农第一定理 编码效率： 4 4、变长编码方法、变长编码方法 变长编码采用变长编码采用非续长码；非续长码； 力求平均码长最小，此时编码效率最高，信源的冗余得力求平均码长最小，此时编码效率最高，信源的冗余得 到最大程度的压缩；到最大程度的压缩； 对给定的信源，使平均码长达到最小的编码方法称为对给定的信源，使平均码长达到最小的编码方法称为最最 佳编码佳编码，编出的码称为，编出的码称为最佳码最佳码； 三种变长编码方法：三种变长编码方法：霍夫曼编码霍夫曼编码、费诺编码费诺编
7、码以及以及香农编香农编 码码； 霍夫曼编码霍夫曼编码是真正意义下的是真正意义下的最佳编码最佳编码。 霍夫曼编码霍夫曼编码 二进制霍夫曼编码过程如下：二进制霍夫曼编码过程如下： （1 1）将信源符号按概率大小排序；）将信源符号按概率大小排序； （2 2）对概率最小的两个符号求其概率之和，同时给两符号）对概率最小的两个符号求其概率之和，同时给两符号 分别赋予码元分别赋予码元“0”0”和和“1”1”； （3 3）将）将“概率之和概率之和”当作一个新符号的概率，与剩下符号当作一个新符号的概率，与剩下符号 的概率一起，形成一个缩减信源，再重复上述步骤，直的概率一起，形成一个缩减信源，再重复上述步骤，直
8、到到“概率之和概率之和”为为1 1为止；为止； （4 4）按上述步骤实际上构造了一个码树，从树根到端点经）按上述步骤实际上构造了一个码树，从树根到端点经 过的树技即为码字。过的树技即为码字。 霍夫曼编码的基本特点：霍夫曼编码的基本特点： 编出的码是非续长码；编出的码是非续长码； 平均码长最小；平均码长最小； 码字不唯一。码字不唯一。 r r进制霍夫曼编码进制霍夫曼编码 每次求缩减信源时，求每次求缩减信源时，求r r个最小概率之和，即将个概率个最小概率之和，即将个概率 最小的最小的r r符号缩减为一个新符号，直到概率之和为符号缩减为一个新符号，直到概率之和为1 1终止终止 。 新问题新问题：缩减
9、到最后时剩下不到：缩减到最后时剩下不到r r个符号了。个符号了。 为保证平均码长最小，希望缩减到最后刚好还剩下为保证平均码长最小，希望缩减到最后刚好还剩下r r个个 符号。为达到此目的，可给信源符号。为达到此目的，可给信源添加几个无用的符号添加几个无用的符号（ 概率为概率为0 0的符号），使得信源符号数的符号），使得信源符号数q q满足满足: : q+iq+i=(r-1)=(r-1) +r+r 信源缩减的次数信源缩减的次数增加无用符号增加无用符号 的个数的个数 费诺（费诺（FanoFano）编码）编码 费诺（费诺（FanoFano）编码也是构造一个码树，因此，编出的码）编码也是构造一个码树，因
10、此，编出的码 是非续长码，但不一定是最佳码。是非续长码，但不一定是最佳码。 费诺编码步骤费诺编码步骤( (以二进制编码为例以二进制编码为例) )： （1 1）将信源符号按概率从大到小的排序；）将信源符号按概率从大到小的排序； （2 2）将信源符号分成）将信源符号分成2 2组，使组，使2 2组信源符号的概率之和组信源符号的概率之和 近似相等，并给近似相等，并给2 2组信源符号分别赋码元组信源符号分别赋码元“0”0”和和“1”1” ； （3 3）接下来再把各小组的信源符号细分为）接下来再把各小组的信源符号细分为2 2组并赋码元组并赋码元 ，方法与第一次分组相同；，方法与第一次分组相同； （4 4）
11、如此一直进行下去，直到每一小组只含一个信源）如此一直进行下去，直到每一小组只含一个信源 符号为止；符号为止； （5 5）由此即可构造一个码树，所有终端节点上的码字）由此即可构造一个码树，所有终端节点上的码字 组成费诺码。组成费诺码。 香农编码香农编码 香农（香农（ShannonShannon）编码步骤）编码步骤( (以二进制编码为例以二进制编码为例) )： （1 1）将信源符号按概率从大到小的排序；）将信源符号按概率从大到小的排序； （2 2）按下式求）按下式求i i个信源符号对应的码长个信源符号对应的码长l l i i ，并取整；，并取整； （3 3）按下式求）按下式求i i个信源符号的累加
12、概率个信源符号的累加概率P P i i ； （4 4）将累加概率）将累加概率P P i i 转换成二进制数；转换成二进制数； （5 5）取）取P P i i 二进制数小数点后二进制数小数点后l l i i 个二进制数字作为第个二进制数字作为第i i个信源个信源 符号的码字。符号的码字。 信道编码 信息传输系统的基本功能：在系统输出端准确地再现系 统输入端发送的消息。 衡量信息传输速度的指标是信息（传输）率R 衡量信息传输可靠性的指标是平均差错率Pe。 为了降低平均差错率，可先对消息进行编码再送入信道 传送，这种为了降低平均差错率而进行的编码称为信道 编码。 1、译码规则与平均差错率 DMCDM
13、C 信道译码信道译码 F F 信道信道译码函数译码函数F F，又称，又称译码规则，译码规则， 是从信道输出符号集合是从信道输出符号集合B B到信道输到信道输 入符号集合入符号集合A A的映射的映射 ： b j j 的的译码正确概率译码正确概率是后验概率：是后验概率： bj的的译码错误概率译码错误概率： 平均差错率平均差错率P P e e : : 2、最佳译码规则与极大似然译码规则 极大似然译码规则极大似然译码规则 最佳译码规则最佳译码规则 结论结论：信道输入等概时，：信道输入等概时，极大似然译码规则极大似然译码规则与与最佳译码规则最佳译码规则等价。等价。 DMCDMC 信道译码信道译码 F F
14、 3 3、汉明距离、汉明距离 定义：定义：两个两个等长等长符号序列符号序列 和和 之间的汉明距离，记为之间的汉明距离，记为 ， 是是 与与 之间对应位置上不同符号的个数。之间对应位置上不同符号的个数。 汉明距离的汉明距离的性质性质（距离公理距离公理）：）： （1 1）非负性：）非负性： ，当且仅当，当且仅当 时等号成立；时等号成立； （2 2）对称性：）对称性： （3 3）三角不等式：）三角不等式： 二元序列汉明重量 ：二元序列 中含“1”的个数。 最小码间距离最小码间距离 ： 最小（汉明）最小（汉明） 距离译码规则距离译码规则 ： 平均差错率平均差错率： 4 4、香农第二定理、香农第二定理
15、定理定理（有噪信道编码定理）：（有噪信道编码定理）： 若信道是离散、无记忆、若信道是离散、无记忆、 平稳的，且信道容量为平稳的，且信道容量为C C，只要待传送的信息率，只要待传送的信息率RC ，则肯定找不到一种信，则肯定找不到一种信 道编码方法，使得码长足够大时，平均差错率任意接近于零。道编码方法，使得码长足够大时，平均差错率任意接近于零。 5 5、线性分组码、线性分组码 码字，码字，N N 维行阵：维行阵： 信息组，信息组， K K 维行阵维行阵： 码字生成式：码字生成式： 校验方程：校验方程： G G ：K K N N 生成矩阵。生成矩阵。 HH：r r N N 一致性校验矩阵一致性校验矩阵。 汉明距离和码的纠、检错能力：汉明距离和码的纠、检错能力： (1)(1)一个码能够检测出一个码能够检测出t t d d 个错误的充要条件：个错误的充要条件： d dmin min t t d d +1 +1 (2)(2)一个码能够纠正一个码能够纠正t t c c
