1、4.5 4.5 信源编码的基本方法信源编码的基本方法一一.信源编码的基本方法信源编码的基本方法 1.1.信源编码的目的：提高传输效率信源编码的目的：提高传输效率 （1）去除信息中的冗余度，使传输的符号尽可能都是独立的，没有多余的成分(如语音、图像信号压缩)；（2）使传输的符号所含的信息最大化。例如，通过编码使符号以等概分布的形式出现，使每个符号可能携带的信息量达到最大；（3）采用不等长编码，让出现概率大的符号用较短的码元序列表示，对概率小的符号用较长的码元序列；(4)在允许一定失真的条件下，如何实现高效率的编码。(DMS:Discrete(DMS:Discrete MemorylessMemo
2、ryless Source Source）离散无记忆信源的输出序列：离散无记忆信源的输出序列：各个符号间彼此独立符号间彼此独立 其中 反之，若输出的各符号间有一定的相关性有一定的相关性，则其为一种 有记忆的信源有记忆的信源。有记忆的信源，经过处理后，有可能变为一种无记忆的信 源。如有记忆的信源，经过理想的、完全去除冗余的 压缩编码后产生的输出。.21012nXXXXXXSXiLiSSi,.2,1,:若将信源输出的符号按每J个为一组进行编码，则任意的第m个分组可以表示为 编码输出编码输出 其中 为输出的码元集。接收端的译码输出译码输出 LiSSXXXXXimkmJmmmJ,.2,1,:,.,21
3、 mJmNXCYJ DiCCYYYYYimkmNmmmNJJ,.,2,1,:.21DiCCi,.2,1,:1JmmJnXCY 待编码码组待编码码组 编码输出码组输出码组(码字码字)LiSSXXXXXikJJ,.2,1,:,.,2112.:,1,2,.,JJNnkiYY YYYC C iD定义定义4.5.14.5.1 若对信源的每个不同的符号或不同的符号序列，编 码后产生的码字不同的，则称该码为唯一可译码唯一可译码。若待编码的符号序列的不同组合个数为 码字集中不同的码字个数 唯一可译码的条件唯一可译码的条件JJLXJJnnYDJnJDL编码表示一个信源符号所需的平均信息量的定义为 编码速率编码速
4、率 。码字长度为常数的编码称为等长编码等长编码，发之称为不等长编码不等长编码。的编码速率编码速率 不等长编码不等长编码的编码速率编码速率 其中 为不等长编码的平均码长。平均码长。RJn2logJnRDJ2logJnRDJ 定义定义4.5.3 4.5.3 信源的熵信源的熵 与编码速率与编码速率 的比值定义为编码效率的比值定义为编码效率 要保证编码没有信息丢失，要求 SHR RSHC 1CRH S3.霍夫曼霍夫曼(Huffman)(Huffman)编码编码 霍夫曼编码是一种异字头不等长编码异字头不等长编码，其基本思想是：对出现概率大的符号或符号组用位数较少的码字表示；对出现概率小的符号或符号组用位
5、数较多的码字表示。由此可提高编码效率。霍夫曼编码霍夫曼编码：定理定理4.5.174.5.17 霍夫曼编码一种最佳的不等长编码最佳的不等长编码。霍夫曼编码的应用条件应用条件：信源的分布(统计)特性已知。记 信源符号集为：编码输出符号集为：LiSPSSii,.,2,1,:DiZZi,.,2,1,:霍夫曼编码的步骤霍夫曼编码的步骤：(1)将L个信源符号按概率大小，以递减次序，从上到下排成一列；(2)对处于最下面的概率最小的D个信源符号，一一对应地分别赋予码字元素Z1、Z2、ZD，把这D个概率最小的信源符号相应的概率相加，所得的值用一个虚拟的符号代表，与余下的L-D个符号组成含有(L-D)+1=L-(
6、D-1)个符号的第一次缩减信源S(1)；(3)对缩减信源S(1)仍按其概率大小以递减次序从上到下排列，按照步骤(2)的方法处理，得到一个含有(L-D)+1-D+1=L-2(D-1)个符号的第二次缩减信源S(2)；(4)按照上述的方法，依次继续下去，每次缩减所减少的符号数是D-1个；只要缩减后的信源Si符号的个数大于D，缩减就继续进行；(5)当进行第k次缩减后信源S(k)符号个数刚好等于D，即有 则对最后这D个符号分别赋予码字元素Z1、Z2、ZD；DDkL1 霍夫曼编码的步骤：(6)从最后赋予的码符号开始，沿着每一信源符号在各次缩减过程中得到的码字元素进行路线前向返回，达至每一信源符号，按前后次
7、序，把返回路途中所遇到的码元素排成序列，这个序列，就是相应信源符号对应的码字；(7)若进行k次缩减后，当进行第k次缩减后信源S(k)符号个数不等于D，即有则中止缩减，增加 个概率为0的虚假信源符号 重新编码，使在k次编码后一定有 。DDkL11DkLDm 0.00.:212121LmLixPxPxPxxxxxxxPXDDkL1示例示例：已知信源符号集编码输出的码字符号集为 解：已知：尝试 需要增加虚假符号数为 新构建的信源满足：S123456:0.240.200.180.160.140.08iiSSSSSSSP S2,1,0:Z6L3D2k3213261DkL1132631DkLDmDDkL3
8、132711234561:0.240.200.180.160.140.080iiSSSSSSSSP S改造后的符号概率场为:编码过程如下消息符号消息符号S S1 1符号概率P(S符号概率P(Si i)SS1 1S S6 6S S5 5S S4 4S S3 3S S2 20.240.240.200.200.180.180.160.160 00.080.080.140.140 01 12 20.240.240.200.200.180.180.160.160.220.220 01 12 20.540.540.240.240.220.220 01 12 2码字码字C C1 1：1：1C C7 7：22
9、：22C C6 6：21：21C C5 5：20：20C C4 4：02：02C C3 3：01：01C C2 2：00：00S S(1)(1)S S(2)(2)1 0.242 0.202 0.182 0.162 0.142 0.081.76n 码字符号 信源符号 平均码字长度：示例(续)：如果不加入虚假符号，直接进行编码，则有 平均码字长度2 0.242 0.202 0.182 0.162 0.142 0.082n 码字符号 信源符号 码字长度的均匀性和方差码字长度的均匀性和方差 在同样的平均码字长度的情况下，码字长度越均匀，对传输越有利。定义定义4.5.164.5.16 码字长度的方差方差
10、 其中 编码过程的排序过程不同会影响码长的方差。2221LCiiiiEnnP Snn1LiiinP S n 码字长度的均匀性和方差 示例：信源的符号空间为 编码输出码字集 编码方式1 将局部概率和置于相同概率的最低位置12345:0.40.20.20.10.1iiSSSSSSP S1,0:Z消息符号消息符号S S1 1符号概率P(S符号概率P(Si i)S S5 5S S4 4S S3 3S S2 20.40.40.20.20.20.20.10.10.10.10 01 1码字码字C C1 1：1：1C C5 5：0011：0011C C4 4：0010：0010C C3 3：000：000C
11、C2 2：01：010.20.20.20.20 01 10.20.20.40.40 01 10.60.60.40.40 01 1S S(1)(1)S S(2)(2)S S(3)(3)0.40.40.20.20.40.4示例：编码方式1 平均码长平均码长：方差方差：1 0.42 0.23 0.24 0.14 0.12.2An 码字符号 信源符号252122222n0.412.20.222.20.232.20.142.20.142.21.36AiiiP Sn编码方式2 将局部概率和置于相同概率的最高位置 平均码长平均码长：方差方差：消息符号消息符号S S1 1符号概率P(S符号概率P(Si i)S
12、 S5 5S S4 4S S3 3S S2 20.40.40.20.20.20.20.10.10.10.10 01 1码字码字C C1 1：00：00C C5 5：011：011C C4 4：010：010C C3 3：11：11C C2 2：10：100.20.20 01 10.20.20.40.40 01 10.60.60.40.40 01 10.20.20.20.20.40.4S S(1)(1)S S(2)(2)S S(3)(3)0.40.42 0.42 0.22 0.23 0.1 3 0.12.2Bn 码字符号 信源符号252122222n0.422.20.222.20.232.20.
13、132.20.132.20.16BiiiP Sn 可见 虽然平均码长一样，但编码方法2使得输出的码长更为均匀。在编码过程中，当对缩减信源概率重新排列时，应使合并得到的局部概率和，尽量使其处于最高位置；使得合并元素重复编码的次数减少，有利于降低码字长度的方差。22BA4.6 4.6 率失真理论率失真理论一.实际系统中的权衡问题实际系统中的权衡问题 实际系统中通常需要考虑性能性能与经济性经济性之间的权衡问题；可采用以某些不可察觉或可察觉但不影响应用的信号失真代价，来换取所需的传输速率、存储空间、运算复杂度和系统实现成本的降低；电话系统采样8kHz采样，8比特量化；数字音响系统采样44kHz采样，1
14、6或24比特量化；1.失真的概念失真的概念 失真失真是指用某种尺度衡量的理想信源样值 与“变换”后的样值 间的差异。这里所谓的“变换”，可以是某种有损的编码，或者是经传输后受到劣化的信号。失真函数失真函数：对由符号 变为符号 产生失真造成的影响，可根据不同的情况定义一个非负函数 来描述，该函数就称为失真函数。失真函数的取值通常反映失真产生的代价。kx kx,0iid x xkx kx失真函数的示例：失真函数的示例：22221 ,2 ,01,3 ,0,14 ,lim kkkkpkkkkkkHkkkkTTTd xxxxd xxxxpxxdxxxxd x tx tx tx tdtTx tx t有失真
15、时无失真时，为连续信号 率失真理论研究的是限定失真条件下信源的编码和信息传输问题的方法。分析在允许一定失真的条件下，要重构信源的符号，至少应获得多少信源的信息量；(1)(1)率失真理论在通信系统中应用时的参数率失真理论在通信系统中应用时的参数 输入信号集：输出信号集：对离散无记忆信道，有 失真函数：失真函数：其中 为输入符号；为输出符号MixXi,.,2,1,:NjyYj,.,2,1,:112111222212/././././NNMMNMp yxp yxp yxp yxp yxp yxp Y Xp yxp yxp yx,01,2,.,;1,2,.ijd x yiM jNjyix(2).(2)
16、.平均失真度平均失真度 失真函数矩阵失真函数矩阵 与转移概率矩阵对应，可定义相应的失真度矩阵：定义定义 4.6.1 4.6.1 平均失真度定义为平均失真度定义为 平均失真度是从统计意义上来说每个符号失真的平均值。111212122212,.,.,.,.,NNMMMNd x yd x yd x yd xyd xyd xyDd xyd xyd xy 1111,/MNijijijMNijijiijDd x yp x yd x yp xp yx 在通信系统中，失真通常在信道中产生，平均失真度与信道的关系可由转移概率的函数来描述。给定信源的统计特性 和失真函数的定义 平均失真度由信道转移概率决定,1,2
17、,.ip xiMjiyxd,/jiDD p yx平均失真度与信道转移概率的关系 示例示例 已知信源统计特性 信道转移概率矩阵 当失真测度采用汉明失真函数时，平均失真度为01:1 21 2XxxP00100111/3 41 4/1 32 3jip yxp yxp yxp yxp yx 2200,/13111112701102424232324ijijiijDd x yp xp yx (3).(3).率失真函数率失真函数 回顾平均互信息定义 定理定理4.6.2 4.6.2 给定信源的统计特性 平均互信息量是信道转移概率 的型凸函数。型凸函数。定理成立的主要依据：对数函数 的型凸函数特性；概率的基本
18、关系式：MiNjjijiyxIyxpYXI11;11/;/logMNjijiiijjp yxI X Yp yxp xp y ijxypMi,.,2,1Nj,.,2,1 ip xMi,.,2,1log x/ijjiiijjp x yp yxp xq xyp y 定义定义4.6.34.6.3 给定信源统计特性 给定失真度准则 率失真函数率失真函数定义为 其中 转移概率矩阵集 定理4.6.2保证了率失真函数的存在。Mixpi,.2,1,CDD/min;jiDCp yxBR DI X YDB:(/);DjiCBp yxDD(4).(4).率失真函数的物理意义率失真函数的物理意义：如果将符号通过信道传输
19、看作某种变换过程，为了以小于 等于DC 的失真度恢复信源的输出，平均每个信源符号平均每个信源符号需 要得到的最小信息量最小信息量。若将率失真函数看作D的函数，显然有如下的关系 DRDDRD 当没有失真时():当失真达到最大时()：0D max;R DI X YH XmaxDD;00I X YR D 率失真函数的定义域率失真函数的定义域 参见上页图，但并非所有 的取值都有意义。一般地 使 的最小平均失真度 minmax,DDD min11/minmin,/jijiMNijijiijp yxp yxDDd x yp xp yx Dmax:D;0I X YR DminDmaxmin,0I X YR
20、DDD0D min:D 率失真函数率失真函数 的主要性质：的主要性质：(1)(1)(定理定理4.6.3)4.6.3)率失真函数率失真函数 是是D的的 型凸函数。型凸函数。作为作为D D的函数存在最小值。的函数存在最小值。(2)(2)(定理定理4.6.4)4.6.4)率失真函数率失真函数 是是D的单调递减函数。的单调递减函数。允许的失真越大，所需的互信息量越小。允许的失真越大，所需的互信息量越小。(3)(3)(定理定理4.6.5)4.6.5)是是D的连续函数。的连续函数。DR DR DR DR DR 示例示例：已知等概分布的信源 信源的熵为：采用汉明失真函数 汉明失真测度的失真矩阵为：nixXi
21、2,.,2,1,:nxpi21211log2log2log22niiiH Xp xp xnnnn jijiyxdji10,01.110.1.11.0D 示例示例：若转移概率矩阵为 即有12.2112.21.210.00001.000./00.10000.01000.001.00.001nnnnnnnjip yxninixxynii 则平均失真度为:随机变量 Y 的分布为 因为转移概率矩阵的元素非 0 即 1，因此有 22112121,/,/111122nnijijiijnininii nni nDd x yp xp yxd x xp xp xxn 1122111111:,.,2222nnnnn
22、p Yp yxp yxp yxp yxnnnn 0loglog211211 ijijninjiijninjjixypxypxpxypyxpXYH 111;/log1111loglog22221log 2log12njjjnjI X YH YH Y XH Yp yp ynnnnnnnnnn 平均互信息量为:即若允许平均互失真度为 可只发送信源的 前面n个符号，后面的 n个符号全部用 替代。此时表示单位符号所需的比特数由 1 2D nixXi2,.,2,1,:nx nXHR2log0 log 21 2log1Rnnnn4.4.汉明失真与传输差错概率汉明失真与传输差错概率 设信源符号的分布特性为 汉明失真矩阵为 12112:.1:.NNiiNXxxxp xp Xp xp xp x 1212.01.110.1.11.0NNyyyxDxx1211121121222212./././././NNjiNNNNNNyyyxp yxp yxp yxp yxxp yxp yxp yxxp yxp yxp yx 设信道转移矩阵为 由汉明失真矩阵，得平均失真度为 而传输出错的概率 因此有 即失真是由传输出错所致失真是由传输出错所致。11,/NNijijiijiijijDd x yp xp yxp xp yx /eijijiijijPp x yp xp yxeDP
