第五章 编码定理.ppt

第五章 编码定理,5.1 引言 5.2 无失真离散信源编码定理 5.3 限失真信源编码定理5.4 离散信道编码定理5.5 连续信道编码定理,5.1 引言,信源熵、信道容量、信息率失真函数，解决了在无失真和限失真的条件下，传送信源信息所必须具有的最小信息率以及能通过信道的最大信息率问题问题：以上最大和最小信息率的极限是否能达到或接近？编码定理要解决的问题：尽量达到或接近上述最大和最小信息率的极限故编码定理也被称为极限定理无失真编码定理→第一极限定理 信源 限失真编码定理→第三极限定理编码定理 离散信道编码定理 信道 →第二极限定理 连续信道编码定理以上定理有其逆定理，即当信息率小于信源熵（或R(D)）时，或信息率大于信道容量时，被传送的信息必然有失真,,,,,5.2 无失真离散信源编码定理,信源编码：将信源输出的随机序列变换成码序列，且能进行反变换或译码，同时使传送码序列所需的信息率最小。

一、等长信源编码定理信源符号Si（i=1,2, ‥‥ q）码字Wi（i=1,2, ‥‥q）若Wi中的码元有r种可能的取值，码长为l则对S进行等长编码，须满足 q ≤ rl,若S送出一个信源符号所需的信息率为R，则N长符号所需的信息率为NR而每个码元的最大信息量为log r，则 l 长码序列的信息量为 l log r编码前后信息量应保持不变，即： NR＝ l log r送出一个信源符号所需信息率：R＝（l /N ）log r为使传送信息率最小，需找到一种编码方式，使R最小编码定理所研究的就是最小的R为何值才能得到无失真的译码，若小于此信息率是否还能无失真地译码？,等长信源编码定理：无记忆平稳离散信源的熵为H(S)，若对信源长为N的符号序列进行等长编码，码字从 r 个码符号集中选取 l 个码元组成，对于任意∈＞0，只要满足： 或则当N足够大时，可实现几乎无失真编码．即译码错误概率能为任意小反之，若：则不能实现无失真编码，而当N足够大时，译码错误概率近似等于1，译码几乎必定出错定理证明：设N长符号组成的序列为aN，则相应的切比雪夫不等式为：即：由于信源取值有q种，则N长信源序列就有qN种，将qN种序列分成两个互补的集 和,,,,,,根据随机序列aN的切比雪夫不等式，显然： ① ②假设 中的序列有 个，且：即：因此序列概率必然满足条件：,,,,,,序列处于 集中的概率必为集内各序列aN的概率之和：将 式代入②式，得： ③,,,,,由于N长的全部可能的序列有qN个，若只对属于 集的 个序列进行编码，则： rl＞ 考虑③式，可得：最终可得：其它 集内的序列会在译码时将发生差错，考虑①式可得差错概率：上式中， 和 为定值，只要N足够大，Pe 可以小于任一正数 ，即：为达到差错要求，信源序列长 N须满足：,,,,,,,,,,,,,以上为正定理部分的证明。

利用表达式： ④ 当 N→∞时，由④式得： →0 绝大部分在 中的序列已 无对应的码字，译码一定出错在N→∞时，由①式得 →1 全部序列几乎都落入 集，且无对应的码字，故译码错误概率趋于1完成逆定理的证明小 结:当每个信源符号必须输出的信息率为R＝（l /N ）log r 时，只要R>H(S)，这种编码一定可以做到几乎无失真；反之，当R

例：已知某信源可以求得H(S)=2.5524比特/符号及方差若要求编码效率为90%，即 设译码差错为：信源符号序列长度必须满足：可见，差错率与编码效率要求并不高时，必须把108个符号一起编码才可满足要求，这不便于工程实现二、变长码编码原则：出现概率大的符号用短码，概率小的符号用长码，可提高编码效率问题：码字如何分离变长码必须是唯一可译码，才能实现无失真编译码1、码字可分离性异前置码（前缀条件码）：任一码字的前面任一起始部分都不构成其它码字这是码字可分离的充分条件译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号，则称为即时码2、码树某节点被安排为码字后，不再继续伸枝，称终端节点，其它为中间节点，中间节点不安排码字3、克拉夫特不等式：对于码符号为X＝{x1，x2，‥‥，xr}的任意即时码，其码字为w1，w2， ‥‥， wq，所对应的码长为l1，l2， ‥‥， lq，则必定满足克拉夫特不等式；反之，若码长满足克拉夫特不等式，则一定存在码长为li的即时码终端节点,中间节点,,,三、离散信源变长编码定理 1、平均码长的概念设信源：编码后的码字：对应的码长：则平均码长： （码符号/每信源符号）平均码长是每个信源符号平均需用的码元数。

平均每个码元携带的信息量（编码后所需信道的信息传输率）： R＝若传输一个码符号平均需要t秒钟，则编码后信道每秒钟传输的信息量为：显然，平均码长越短，则Rt越大，信息传输效率就越高，编码中使平均码长为最短的码是人们感兴趣的最佳码： 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳码或紧致码无失真信源编码的基本问题就是要找最佳码，变长码的编码定理确定了最佳码的平均码长可能达到的理论极限2、按符号变长编码定理 若一离散无记忆信源的符号熵为H(S)，每个信源符号用r元码元进行变长编码，则一定存在一种无失真编码方法，构成唯一可译码，其平均码长满足： 以上定理给出了平均码长的上、下界，平均码长不能小于下界 否则唯一可译码不存在3、无失真变长信源编码定理（香农第一定理） 对于平均符号熵为H(S)的离散平稳无记忆信源， 必存在一种无失真编码方法，使平均信息率满足 不等式：H(S) ≤R＜H(S)＋∈，∈为任意正数 或平均码长满足：对香农第一定理的理解：若R＞H(S)，就存在唯一可译变长编码；若R＜H(S)，唯一可译变长编码不存在，不能实现无失真的信源编码。

香农第一定理的物理意义：,无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信源）尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量C，实现信源与信道理想的统计匹配定义变长码的编码效率为：,5.3 几种信源编码方法,一、信源编码种类归纳1、熵保持编码（匹配编码，平均信息量法）特点：在编码过程中，不允许丢失任何信息根据符号的概率分布，分别对应长短不同的代码如香农编码法、费诺编码法、霍夫曼编码法等2、预测编码特点：编码和传输的不是采样值本身，而是采样值的预测值与实际值之间的差值如差值脉冲编码调制法（DPCM）,,3、变换编码特点：将原来的信号空间变换为另外一个空间如Fourier（傅里叶）变换、Haar（哈尔）变换、 Walsh-Hadamard（阿达玛）变换（简称DWHT）、Slant变换、Cosine变换、Sine变换、 Hotelling变换等4、识别编码特点：关联识别（与样本比较识别），逻辑识别（利用逻辑表达式判断识别）二、霍夫曼编码方法,1、二元霍夫曼编码步骤：①把一个信源符号的几种字母按概率大小的次序排列好；②取二个概率最小的字母分配以“0”和“1”，并把这二个概率相加作为一个新字母的概率重新与未分配的二进符号的字母排队；③重新排队后，再取二个概率最小的字母分别配以“0”和“1”，再把这二个概率相加作为一个新的字母的概率；,④重复③，直到概率之和为1；⑤倒回写出相应码字。

举例）2、r元霍夫曼编码规则：由二元霍夫曼编码推广而来，每次把r个概率最小的符号合并成一个新的信源符号，并分别用码元0，1，‥，（r －1）表示为使平均码长最短，必须使最后一步的缩减信源有r个信源符号即信源符号个数q必须满足：,注意：若q不满足上式，可虚设t个出现概率为0的信源符号，使q＋t满足表达式，得到r元霍夫曼码一定也是最佳码（紧致码）例：信源符号概率分布如下，实现四元霍夫曼编码：S1 S2 S3 S4 S5 S6 S7 S80.22 0.2 0.18 0.15 0.1 0.08 0.05 0.02,,二、费诺（Fano）编码步骤①先把消息按概率大小顺序排列；②将概率序列分成两组，使两组的概率尽可能接近或相等，两组消息分别以“0”和“1”表示；③再对每组符号又分成两组，也使两组的概率尽可能接近或相等，两组消息分别以“0”和“1”表示；④重复③，直至每个消息被分隔出来为止；⑤将二进数字顺序写出得到相应消息的码字例：信源消息如下，实现费诺编码：S1 S2 S3 S4 S5 S60.25 0.25 0.2 0.15 0.1 0.05,5.4 限失真信源编码定理（香农第三定理）,定理具体描述（P311定理7.1）限失真编码定理说明：当传输速率R＞R(D)时，只要码长足够长，就一定存在一种编码方法，使平均失真任意接近于D，否则这种编码不存在。

注意：不同的编码，将有不同的平均失真，希望找到平均失真最小的编码，即最佳编码小结：,比较香农第一和第三定理可知，当信源给定后，无失真信源压缩的极限值是信源熵H(S)，而有失真信源压缩的极限值是信息率失真函数R(D) ，在给定失真值D后，一般R(D) ＜H(S)存在的问题：1）符合实际信源的R(D)函数的计算相当困难；2）采用何种实用的最佳编码方法才能达到R(D)？,5.5 有噪信道编码,一、信道编码概念信道编码是为了保证信息传输的可靠性，使信源与信道特性相匹配，且传输中的差错为任意小，提高传输质量而设计的一种编码信道编码是在信息码中增加一定数量的多余码元，在编码效率一定的条件下，提高检纠错能力，使码字具有一定的抗干扰能力，故又称为抗干扰编码。