配套课件-现代编码技术.ppt

1、第1章通信与编码概述 习题习题1.通信系统的基本模型通信系统的基本模型通信系统的基本模型如图1.1所示，组成部分如下：信源：消息的发出者。信宿：消息的接收者。信源编码器：消息的重组单元。信道编码器：消息抗毁能力的构建单元。信道：消息的传输媒介，如电话机之间的电缆、无线电台之间的电磁空间等。干扰源：毁坏传输信号的各种因素的等价体，可分为自然干扰源和人为干扰源两类。如大气的雷电干扰、电离层的扰动等属于自然干扰；信号的转发干扰等属于人为干扰。信道译码器：消息的毁坏检验及恢复单元。信源译码器：消息的还原单元。发送端：从信源到信道前的各部分的总称。接收端：从信道后到信宿的各部分的总称。图1.1通信系统的

2、基本模型2.信道模型信道模型信道是发送端和接收端之间的连接通道，它可以等效为一个输入端和一个输出端的系统，如图1.2所示。图1.2信道简化模型根据信道是否存在干扰，可将其分为无噪信道和有噪信道；根据传输信道是否连续，可将其分为离散信道和模拟信道；根据信道当前输出与先前的输入是否有关，可将其分为有记忆信道和无记忆信道；根据信道参数是否随时间而变化，可将其分为恒参信道和随参信道；此外，信道还可以分为二元信道和多元信道，对称信道和非对称信道，有损信道和无损信道等。1)离散信道首先，我们来考虑信道的表示。假设发送端发射的信号都取自字符集：X=a1，a2，an由于信道中存在噪声干扰、传输衰落、传输失真等

3、因素，因此从发送端发出符号ai，在接收端收到的未必是符号ai，甚至于还可能是X中不存在的符号。于是可以假设接收端接收的信号都属于符号集：Y=b1，b2，bm对给定的信道进行大量的实验后，经统计可以发现：从发送端符号集中发送的符号ai以概率pij转化为接收端符号集中的bj。为方便起见，概率pij常常表示为条件概率的形式，即pij=p(bj|ai)(i=1，2，n；j=1，2，m)这样，用符号转移概率pij就可以充分描述信道特性。为方便起见，引入信道转移矩阵P，即111212122212mmnnnmpppppppppP常用的离散信道模型有以下几种：(1)二元对称信道。在这种信道中，X=Y=0，1，

4、并且p(1|0)=p(0|1)=p，即字符0和1发生错传的概率相同，信道转移矩阵P为二元对称信道常常用状态转移图来简化表示，如图1.3所示。11ppppP 图1.3二元对称信道(2)二元删除信道。在这种信道中，X=0，1，Y=0，1，Y中的字符表示0或1在传输中发生畸变而在接收端产生的一种发送端字符集中不存在的字符。在一个通信系统中，字符0和1分别代表正脉冲和负脉冲，发送端发送出正脉冲或负脉冲后，接收端收到的是受到干扰的畸变正脉冲或负脉冲，当畸变变化比较严重时，无法识别出是正脉冲还是负脉冲，这种接收信号就用来表示。对接收端是没有意义的，应被删除。畸变脉冲如图1.4所示。图1.4接收端收到的畸变

5、脉冲(a)畸变的正脉冲；(b)畸变的负脉冲；(c)畸变的脉冲二元删除信道的信道转移矩阵P为其中，p(|0)=p，p(|1)=q。二元删除信道常用图1.5来表示。1001ppqqP 图1.5二元删除信道(3)多元(N元)对称信道。多元(N元)对称信道常用状态转移图来简化表示，如图1.6所示。图1.6多元(N元)对称信道(4)无记忆扩展信道。字符序列x经信道后转移成y的概率为 1()(|)Njkikkpp bay|x(1.1.1)二维扩展信道的信道转移矩阵P为(1.1.2)1 11 11 21 12 11 1221 11 1121 2122 11222121 1211 2212 12122211

6、1221 2222 1222222|p bb a ap bba ap b b a ap b ba ap bb a ap bba ap b b a ap b ba ap bb a ap bba ap b b a ap b ba ap bb a ap bba ap b b a ap b ba aP2)输入离散、输出连续的AWGN信道AWGN信道的全称是加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道。输入离散、输出连续的AWGN信道具有输入信号是离散的、输出信号是连续的、信道受到的干扰服从高斯分布等特点，是通信中最常用的信道模型之一。图1.7是二元输入离散

7、、输出连续的AWGN信道简化模型。图1.7二元输入离散、输出连续的AWGN信道简化模型3.编码定理编码定理1)香农第一定理(无失真压缩编码定理)定义定义1.1.1设离散信源空间X=a1，a2，an，离散变量ai(i=1，2，n)及对应变量的概率分布p(X)为式中，。1212()()()()nnaaaXp ap ap ap X1()1niip a称lbp(ai)为离散变量ai的自信息量；称为信源空间X的熵，单位为bit。1()()lb()niiiH Xp ap a(1.1.3a)定义定义1.1.2设有离散空间X=a1，a2，an和Y=b1，b2，bm，称为条件熵；称为平均互信息量。其中，p(ai

8、，bj)为离散变量ai与bj的联合概率密度，p(ai|bj)为条件概率密度。(1.1.3b)11|,lb|nmijijijH X Yp a bp a b 11|;,lbnmijijijip abI X Yp a bp a(1.1.3c)定义定义1.1.3对信源输出的一列符号序列按一定规则进行变换称为编码，变换后形成的新序列称为码字，码字中的每一个元素称为码元，码元所属符号集称为码符号集，码字中码元的数量称为码长，全部码字构成的集合称为码。如果q=2，则称为二元码；如果q2,则称为q元码，这里q表示码符号集中元素的个数。如果在一种码的编译码过程中没有信息损失，并且该码在理想信道(无噪无信道损失)

9、上传输后能不失真地恢复原消息，则称该编码为无失真编码；如果在编译码过程中有控制地损失一些信息，则称该编码为限失真编码。限失真编码在通信中是十分重要的，如一张仅几百兆的光盘能容纳数十小时的视频内容就源于该技术的重要贡献。定义定义1.1.4设有码C=c1，c2，ci，p(ci)=pi，码字ci的长度为li，称为码C的平均码长，单位为bit。定义定义1.1.5设信源符号集为X，并有q元码C，称为编码效率。ii icCL Cpl lbH XL Cq(1.1.5)(1.1.4)引理引理1.1.1(概率匹配原则概率匹配原则)设无记忆信源X=0，1，2，q1且元素相互独立和等出现概率，其上有一种码C=ci|

10、i=1，2，M，ci有长度li，发生概率为pi，若C是无损编码且L(C)最小，那么(1.1.6)lb1loglbiiqiplpq 证明证明由于0，1，2，q1是独立等概的，因此每一个这样的元素有自信息量。这样，码C中平均每个码字含有的信息量为L(C)lbq。由于是无损编码，因此L(C)lbq不应当小于H(X)，又由于L(C)最小，因此1lblbqq 1lblblb0MiiiiL CqH Xp lqp定理定理1.1.1设离散平稳无记忆信源的熵为H(X)，X=a1，a2，an，那么一定存在一种码C使熵和平均码长间满足下列关系：证明证明基于信源X，构造一个长度为N的符号串si=(r1,r2,rN)，

11、riX，这样的符号串si形成一个N维扩展信源XN，对N维扩展信源进行编码，获得码C=ci|i=1,2,，每个ci长为li，发生概率为pi。按概率匹配原则进行编码，码长应满足：1lblbH XL CH XqNqN(1.1.7)式(1.1.8)两边乘以pi并求和后，有(1.1.8)11log1 logqiqiilpp 11loglogiiiiiqi iiiqcCcCcCcCiipplpppp(1.1.9)注意到由此可得(1.1.10)2log11loglblbiiiNiicCiiqcCcCippH Xpppqq，1lblbNNH XH XL Cqq 由于是无记忆信源，故H(XN)=NH(X)(1.

12、1.11)将式(1.1.11)代入式(1.1.10)，即得式(1.1.7)。2)香农第二定理定义定义1.1.6对离散无记忆信道，信源和信宿分别为X和Y，px表示信源X的概率分布，称为信道容量。max;xcpCI X Y(1.1.12)定义定义1.1.7消息在信道上的传输过程中，单位时间内传送的实际信息量称为信息传输速率，记为R。定理定理1.1.2设离散无记忆信道的信道容量为Cc，总存在一种RCc的码C使接收端恢复消息的误码率peCc的码C使pe任意小。顺便指出，在连续AWGN信道上，香农信道容量公式为0 ，(1.1.13)lb 1cSCWN3)香农第三定理在许多实际情况下进行无失真编码是不必要

13、的，信源可以在信宿恢复消息所需的条件下对消息进行压缩处理，以减小存储或传输的总量。这种压缩方式通常就是去掉消息间的冗余度。要满足信宿恢复消息所需要的条件，就必须在编码时对失真设置一个最大值，称为保真度，记为D。保真度越高，即D越小，意味着压缩去掉的传输的信源信息量就越少，需要传输更多的信源信息量。很显然，对给定的保真度D，信息传输速率R不能低于某一个下限值。保真度不同，下限值也不一定相同，即下限值是D的函数，称为率失真函数，记为R(D)。定理定理1.1.3对任意给定的保真度D0，只要码长N足够大，一定可以找到一种码C使编码后每个符号的信息传输率不小于R(D)，且码的平均失真度不超过D。4.数字

14、调制的基本原理数字调制的基本原理所谓调制，是指根据调制信号的变化规律去改变载波某些参数的过程。调制具有搬移信号频谱的作用，能够把信号的频谱搬移到理想的位置，从而获得适合于信道传输的信号，大大提高信号传输的有效性和可靠性。调制可以分为模拟调制和数字调制两种，模拟调制的调制信号取值是连续的，数字调制的调制信号取值是离散的。1)二进制数字调制二进制数字调制是指调制信号为二进制数字信号的调制方式，在这类调制中，载波的某个参数(如幅度、频率或相位)仅有两种简单的变化状态。二进制数字调制分为幅度键控、频移键控和相移键控三种。(1)二进制幅度键控(Binary Amplitude Shift Keying，

15、BASK)。设xk是来自于信源的二进制数字信息1和0，其发生概率分别为p和1p，即1()0()kpxp 出现概率为 出现概率为1-则BASK信号可以表示为式中：fc为载波频率；g(t)是一个矩形脉冲；Ts为持续时间。式(1.1.14)表明在二进制幅度键控调制中，载波幅度随二进制被调信号序列的变化而改变，如图1.8所示。2ASKccos 2kskstx g tnTf t(1.1.14)图1.8BASK调制信号示意图(2)二进制频移键控(Binary Frequency Shift Keying，BFSK)。设xk是来自于信源的二进制数字信息1和0，其发生概率分别为p和1p，则BFSK信号可以表示

16、为式(1.1.15)表明BFSK调制信号随被调信号序列在两个载波频率间切换。当xk=1时，使用载波频率f1；当xk=0时，使用载波频率f2，如图1.9所示。2FSK12cos 2(1)cos 2kskkskstx g tnTf txg tnTf t(1.1.15)图1.9BFSK调制信号示意图(3)二进制相移键控(Binary Phase Shift Keying，BPSK)。设xk是来自于信源的二进制数字信息1和0，其发生概率分别为p和1p，则BPSK信号可以表示为式(1.1.16)表明BPSK调制信号随被调信号序列在两个相位相差为180的信号间切换。当xk=1时，载波信号为cos(2fct

17、)；当xk=0时，载波信号为cos(2fct)，如图1.10 所示。BPSK(1)cos 2kxsckstg tnTf t(1.1.16)图1.10BPSK调制信号示意图2)M进制数字调制设xk是来自于信源的二进制数字信息1和0，将m个二进制符号的所有可能组合与M(M=2m)个载波相位相对应，则MPSK信号可以表示为例如，取m=2，那么载波相位数为M=22=4，称为QPSK(即4PSK)信号。2个二进制符号的可能组合为00，01，10，11，2个二进制符号与载波相位间的对应关系见表1.1。cs21cos 2(1,2,0)iis tg tf tMiMtT(1.1.17)表表1.1QPSK信号的载

18、波相位对应关系信号的载波相位对应关系 为了更清楚地表明这种对应关系，常使用信号星座(Constellation)图形来描述。图 1.11 给出了BPSK、QPSK和8PSK信号的星座图。图1.11MPSK信号星座图(a)BPSK信号星座图；(b)QPSK信号星座图；(c)8PSK信号星座图习题习题11.信源编码和信道编码的根本目的是什么？2.已知离散无记忆信源求信源的熵。3.在二元对称信道中，已知信源，信宿Y的概率分布p(Y)=0.60.4，求信道转移矩阵。0.50.10.150.25Xabcdp X，010.70.3Xp X4.在实际信道中，噪声和损失是不可避免的。矩阵P1是有噪无损信道的信

19、道转移矩阵，P2是无噪有损信道的信道转移矩阵，即试画出两信道的状态转移图，并比较两者的差异，以及据此推断出无噪无损信道和有噪有损信道的状态转移图。121001000.30.20.50001000000.70.30010000001010001，PP5.已知信源，信道转移矩阵，信宿求信宿Y的概率分布p(Y)。6.求出无记忆二元对称信道的二维扩展信道的信道转移矩阵。010.50.5Xp X0.80.150.050.050.150.8P 123123Ybbbp Yp bp bp b，第2章信源编码 2.1无失真信源编码无失真信源编码2.2限失真信源编码限失真信源编码习题习题2.1无失真信源编码无失真

20、信源编码无失真信源编码的理论基础就是第1章介绍的香农第一定理，实现的途径之一是概率匹配原则，最终目的是找到一种平均码长最短的码。先来看一个例子。例例2.1.1设有离散无记忆信源，进行以下两种方式的二进制编码：(1)a100，a201，a310，a411；(2)a10，a210，a3110，a4111，试求两种编码方式的平均码长和编码效率。12340.50.30.150.05Xaaaap X解解信源熵为H(X)=(0.5 lb0.5+0.3 lb0.3+0.15 lb0.15+0.05 lb0.05)=1.6477 bit(1)L(C1)=20.5+20.3+20.15+20.05=2 bit(

21、2)L(C2)=0.51+0.32+0.153+0.053=1.7 bit1182.4%H XL C2296.9%H XL C2.1.1Huffman编码编码1.编码原理编码原理利用概率匹配原则，编码时，码长应当选择满足式(1.1.8)的整数，但并非每次应用都能获得理想的编码。看下面两个例题。例例2.1.2无记忆信源，利用概率匹配原则进行编码，并求出平均码长和编码效率。解解根据式(1.1.8)，字符a1、a2、a3、a4、a5对应的码长分别为1、2、3、4、4，用二进制符号来表示字符，即12345111112483232aaaaaXp X那么，平均码长为1234501011011101111a

22、aaaa 11111123441.875 bit2483232L C 又因为所以，获得的编码效率为=100%例2.1.2的二元码的码树见图2.1。11111lb2lb4lb8lb32lb321.875 bit2483232H X 图 2.1例2.1.2编码的码树例例2.1.3无记忆信源，试利用概率匹配原则进行编码，并求出平均码长和编码效率。解解根据式(1.1.8)，字符a1、a2、a3、a4、a5、a6对应码长分别为2、2、3、5、6、6，用二进制符号来表示字符，即1234560.40.30.20.050.0250.025Xaaaaaap X12345600101101111011111011

23、1111aaaaaa计算后，得到H(X)=1.83 bit，L(C)=2.55 bit，71.8%例2.1.3编码的码树见图2.2。图 2.2例2.1.3编码的码树由例2.1.3的计算可知，该编码效率很低。从码树上我们可以看到，离树根较近的地方有许多空枝，如果不考虑式(1.1.8)而把其他码字移到这些空枝上会出现什么情况呢？图2.3就是移动码字后的码树。图 2.3改进图2.2后的码树图2.3所示的码树对应的符号编码如下：图2.3所示码树对应编码的平均码长和编码效率分别为L(C)=2.15 bit，85.1%12345600100111011101111aaaaaa由此可见，改进后的码树(图2.

24、3)的编码效率明显提高。例2.1.3启示我们编码时码树不能留有空枝，单纯地应用概率匹配原则不一定能得到最佳编码。例2.1.3获得较高编码效率实质上是对码树实行了全局性能匹配，图2.2所示的码树只是在局部枝上实行概率匹配原则，而忽略了全局优化，因而效率较低。那么图2.3是否是例2.1.3的最佳编码呢？我们再来观察针对例2.1.3的另一码树图2.4。图 2.4例2.1.3编码的另一码树图2.4所示码树对应的符号编码如下：图2.4所示码树对应编码的平均码长和编码效率分别为L(C)=2.05 bit，89.3%12345601011011101111011111aaaaaa定理定理2.1.1(q元元H

25、uffman编码编码)设离散无记忆信源按下述步骤进行编码，获得的码一定具有最小平均码长。第一步，根据出现概率的大小，按从大到小的顺序重排字符符号。第二步，在重组的信源中，从最小概率的符号开始，按概率从小到大的方式取q个符号作为q片树叶合并到一个节点上，将0，1，2，q1这q个数不重复地分配到这q个树叶上。1212nnXaaap Xp ap ap aXp X第三步，被合并的q个字符用一个临时字符代替，这个临时字符的概率为被合并的q个字符的概率之和，其余字符及概率不变，从而形成一个新的信源空间。第四步，如果新的信源空间的概率分布p(X)=1，这时的节点就是码树的树根，则转到第五步，否则，转到第一步

26、。第五步，从树根开始，沿枝到达树叶，途中遇到的数字按行走顺序组合就得到该树叶字符所对应的码字，找完全部树叶，编码完成。Xp XXp X()Xp X证明证明设Huffman编码完成后，aici(i=1，2，n)，并且码ci的长度为li，则Huffman编码的平均码长。再设p(ak)p(aj)，根据Huffman编码，则有ljlk。如果重新构造一个编码C，其对应关系如下：即交换字符ak与aj所对应的码字，而其余字符对应码字不变，形成码C，那么码C的平均码长为 1niiiL Cp a l1,2,1,2,kjijkiaaain ik ijin ik ijccc式(2.1.1)说明Huffman编码的平

27、均码长最短。1,1niikjjkii k ijniikjjkkkjjikjjkL Cp a lp alp alp a lp alp alp alp alL Cllp ap aL C(2.1.1)从Huffman编码过程来看，如果完成编码共引入了r个临时字符，除第一次合并用了信源的q个字符外，其余各次合并都只使用了信源的q1个符号，所以信源符号的数量应当为n=r(q1)+q(2.1.2)例例2.1.4设离散无记忆信源，构建平均码长最短的二元码。1234560.250.20.250.10.050.15Xaaaaaap X1234560.250.20.250.10.050.15Xaaaaaap X解

28、解第一次合并：按概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d1。132645132610.250.250.20.150.10.050.250.250.20.150.15Xaaaaaap XXXaaaadp Xp X第二次合并：按照概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d2。1326113220.250.250.20.150.150.250.250.20.3Xaaaadp XXXaaadp Xp X第三次合并：按照概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d3。21322130.30.250.250.20.30.250.45Xdaaap

29、XXXdadp Xp X第四次合并：按照概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d4。第五次合并：按照概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d5。因为p(X)=1，故编码结束。321340.450.30.250.450.55XXXddaddp Xp Xp X5430.550.451XXdddp Xp X从图2.5所示的码树的树根开始，可以读出对应于每一字符的Huffman编码如下：经计算，本例的熵、平均码长和编码效率分别为H(X)=2.42 bit，L(C)=2.45 bit，98.8%12345601111000000001001aaaaaa 图 2

30、.5例2.1.4的Huffman编码过程例例2.1.5已知离散无记忆信源试求Huffman三元和四元编码。解解本例的三元Huffman编码过程见图2.6，三元Huffman编码如下：1234567890.240.20.140.110.100.140.040.020.01Xaaaaaaaaap X12345678920001101102120121122aaaaaaaaa 图 2.6三元Huffman编码过程由于不满足式(2.1.2)，因此添加一个字符a10，并取p(a10)=0。本例的四元Huffman编码过程见图2.7，四元Huffman编码如下：1234567891230102000300

31、31032aaaaaaaaa 图 2.7四元Huffman编码过程2.举例举例CCITT T.4对三类传真机的扫描线长度和每行像素作了如下规定：(1)A4纸文本的一行(215 mm1%)扫描后构成一条扫描线，线上有1728个黑白像素；(2)B4纸文本的一行(255 mm1%)扫描后构成一条扫描线，线上有2048个黑白像素；(3)A3纸文本的一行(303 mm1%)扫描后构成一条扫描线，线上有2432个黑白像素。三类传真机对扫描线的编码的结构如图2.8所示。图 2.8三类传真机对扫描线的编码的结构(a)一维编码方案；(b)二维编码方案经过大量统计发现游程长度有以下特点：(1)游程长度的概率分布表

32、现为对扫描的文本的行与行间不同，对扫描的文本的页与页间不同；(2)出现于每一扫描线中的游程长度的种类非常多，例如，在一条有1728个黑白像素的扫描线上出现的可能游程长度为1，2，3，1728。MH码表见表2.1和表2.2。表表2.1一维改进一维改进Huffman编码表编码表构造码构造码 表表2.2一维改进一维改进Huffman编码表编码表结尾码结尾码 传真机传输一页文件文本是按图2.9所示的数据传输格式进行传输的。图 2.9一页文件传真的数据传输格式2.1.2算术编码算术编码1.基本概念基本概念Huffman编码是在信源符号与可变长度码字之间建立一个1-1对应关系而实现编码的，算术编码则是对信

33、源的输出符号流进行编码，因此，算术编码不需要像Huffman编码那样为每一个信源符号指定一个码字。本节先介绍算术编码的思想和基本概念，具体编码方法的介绍将在后续各小节中陆续展开。设有无记忆信源空间，其中，p1p2pn，定义信源字符的累积概率为1212nnXaaap Xppp很明显，有下列关系：l0=0，l1=p1，l2=p1+p2，并且pi=lili1 (2.1.4)111iikklp(1,2,1)in(2.1.3)由于概率的大小总是在0和1之间，因而可以把li与li1视为区间0，1)中的两个点，那么，pi刚好等于子区间li1，li)的长度。很明显，这些子区间是互不重叠的，不同的信源符号有唯一

34、一个子区间与之对应，因而，我们可以任选子区间的一个点来代表这个子区间所对应的信源符号。例如，可以选子区间的左端点，这种代表是可变的，但代表的信源符号是唯一的，如图2.10所示。图 2.10信源字符累积概率划分的子区间与信源符号的对应关系不同的字符序列与唯一一个子区间对应，如图2.11所示。图 2.11序列的累积概率划分的子区间与序列的对应关系()rks很明显，每一序列的概率恰好为所对应子区间li1，li)的长度，有关系式：()rks()()11()()rriiiiiillp sp sll或(2.1.5)新序列或者的累积概率为(1)()(0rrius()1)ris11()()()()111()(

35、)1(0)(0)(1)()(0)(1)()()iirrrriiiikkirriikl sp sp sp sppp sl s()()()()()(1)()(0)()()rrrrriiiiil sl sp sl sp sp(2.1.6)(2.1.7)2.编码方法编码方法算术编码的编码过程实质上就是寻找字符所对应的子区间，新到字符对应的子区间是通过迭代更新前一个字符的子区间来获得的。设信源输出的第k1个字符对应的子区间为DLk1，DHk1)，子区间的宽度为k1=DHk1DLk1，那么，第k个字符对应的子区间DLk，DHk)为(2.1.8)11111kkkkkikkkiDLDLlDHDLl 式(2.1

36、.8)也可以变形为用子区间下端点和区间宽度来表示，即(2.1.9)111111()()kkkkkkkikkkiikkiDLDLlDHDLllDLp a算术编码的具体编码过程如下。首先，初始化。然后，输入字符进行迭代运算。第一步，信源X输出第一个字符。设 。取，更新区间，即新区间。如果信源输出字符结束，则任取作为字符 的算术编码。否则，继续第二步，并令1ia1111,)iiiall000DHDL11001iDLDLl1100 iDHDLl111,)iDL DH1ia11111iiDLlDHl11111,),)iiDL DHll(2.1.10)第二步，信源X输出第二个字符。设。取，更新区间，。如果

37、信源输出字符结束，则任取 作为字符 的算术编码。否则，继续第三步，并令第三步，信源X输出第三个字符。假设已进行了第k1步，即已知和，继续第k步。第k步，信源X输出第k个字符。(2.1.11)2ia2221,)iiiall111DHDL222111211,iiDLDLlDHDLl222,)iDL DH1ia2ia111211122111111()()iiiiiiiiDLllllDHllll3ia1kDL1kDHkia设。取，更新区间，。如果信源输出字符结束，则任取作为字符的算术编码。否则，继续第k+1步，并令归纳起来，算术编码的编码流程图如图2.12所示。(2.1.12)1,)kkkiiiall

38、111kkkDHDL11111,kkkkkikkkiDLDLlDHDLl,)kikkDL DH12kiiia aa12311231111121111111211kkkkkiiikikikiiikikiDLlllllDHlllll 图 2.12算术编码的编码流程图例例2.1.6设有离散无记忆信源空间，求出字符流a2a0a1a0a0a4a3的算术编码。解解首先，将区间0，1)分成5个子区间，即其次，初始化，即DL0=0，DH0=1，j=0最后，输入字符进行迭代运算，见表2.3。012340.50.20.150.10.05Xaaaaap X012340,0.5)0.5,0.7)0.7,0.85)0.

39、85,0.95)0.95,1)aaaaa，表表2.3例例2.1.6字符流的算法编码过程字符流的算法编码过程3.译码方法译码方法因为每一字符被唯一地指定了一个子区间，所以只需要根据码字来反推是哪个子区间就能得到相应的字符，从而实现译码。算术译码的过程如下。第一步，译出字符流的第一个字符。第二步，译出字符流的第二个字符。第三步，译出字符流的第三个字符。如此继续下去，直到最后一个字符译出。归纳起来，算术编码的译码流程图如图2.13所示。图 2.13算术编码的译码流程图例例2.1.7信源空间同于例2.1.6，译出算术编码b=0.7412261962890625。解解译码过程见表2.4，得到算术编码b对

40、应的字符流为a2a0a1a0a0a4a3。表表2.4例例2.1.7的算术编码的算术编码b的译码过程的译码过程4.二元二元QM编译码器编译码器二元QM编译码器是一种自适应方式的算术编译码器，其优点是无需预先确定信源空间的概率模型，特别适合于难以进行概率统计的信源空间，编译码中所需要的概率通过概率估计器估计来获得。此外，算术编码每次递推要进行乘法运算，并且要求运算在下一个字符到来前完成，有时要达到这一要求是困难的。QM编译码器能转乘法运算为移位操作或减法运算，极大地提高了处理速度，因此，QM编译码器得到了广泛应用。例如，JPEG图像压缩标准中就使用QM编译码器。QM编译码器的编译码原理框图见图2.

41、14。图 2.14QM编译码器的编译码原理框图(a)编码器；(b)译码器式(2.1.9)的子区间迭代关系可以简化为如下两种形式：(1)如果第k个字符的概率较大，即字符a1，则有(2)如果第k个字符的概率较小，即字符a2，则有111kkkkkDLDLDHDLp11112kkkkkkDLDLpDHDLp(2.1.14)(2.1.13)式(2.1.13)和(2.1.14)可以用如下的计算机赋值语句来实现：(1)对于MPS，有 DLDL，(12Q)(2.1.15)(2)对于LPS，有 DLDL+(12Q)，2Q(2.1.16)实际的QM编译码器就是按式(2.1.15)和(2.1.16)来实现编译码的。

42、2.2限失真信源编码限失真信源编码2.2.1基本概念基本概念什么是失真？简单地说，失真就是信宿接收到的符号与信源发出的符号不同。定义定义2.2.1设信源X=a1，a2，an，信宿Y=b1，b2，bm，从信源发送出符号xX，信宿接收到符号yY，称为失真函数。(2.2.1)00,xyd x ydxy失真函数d(x，y)可以通过设置不同的d0来表示失真的严重程度，常见的d0取值方法主要有以下几种形式。误码失真：d0=1绝对失真：d0=|xy|(2.2.2)平方失真：d0=(xy)2(2.2.3)相对失真：(2.2.4)0 xydx定义定义2.2.2设从信源X发送长度为N的符号序列(x1，x2，xN)

43、，信宿接收到的是长度为M的符号序列(y1，y2，yM)，定义阶是NM的矩阵A：称A为失真矩阵。(2.2.5)111212122212,MMNNNMd x yd x yd x yd xyd xyd xyd xyd xyd xyA例例2.2.1在N元对称信道中，采用误码失真函数，即d(i，i)=0，d(i，j)=1，i，j=0，1，N1且ij，失真矩阵为在二元删除信道中，定义d(0，0)=d(1，1)=0，d(0，1)=d(1，0)=1，失真矩阵为011110111110A10,1,2dd设信源X=0，1，2，3，信宿Y=0，1，2，3，采用平方失真函数，失真矩阵为10121102 A014910

44、1441019410A定义定义2.2.3设信源p(ai，bj)表示ai与bj的联合概率，称为平均字符失真度。式中，E表示数字期望，p(ai，bj)=p(ai)p(bj|ai)。1212nnXaaap Xp ap ap a 1212mmYbbbp Yp bp bp b ,|,ijijijijiiji ji jDE d a bp a bd a bp ap ba d a b(2.2.6)如果是连续信号，式(2.2.6)中的求和符号转化为积分符号，概率转化为随机变量的概率密度函数，就得到连续随机变量的平均失真函数：(2.2.7),d dDE d x yp x y d x yxy 定义定义2.2.4设信

45、源发出长为N的字符序列，其中，信宿接收字符序列为，其中，那么字符序列x与y间的失真函数为12(,)NiiixxxxkixX12(,)NjjjyyyykjyY1,kkNijkdd xyx,y定义定义2.2.5设有信源X的N维扩展信源XN，信宿Y的N维扩展信宿YN，那么平均序列失真度为对于无记忆信道，与间有关系：NNNx Xy YDpd x,yx,yDNDNDND(2.2.9)(2.2.8)例2.2.2设有离散无记忆信源，无记忆信道转移矩阵，求在误码失真函数下平均字符失真度和平均序列失真度。解解设信宿为，则有 p(b1|a1)=0.75，p(b2|a1)=0.25，p(b1|a2)=0.4，p(b

46、2|a2)=0.6由式(2.2.6)得平均字符失真度为120.50.5Xaap X0.750.250.40.6P 1212Ybbp YppD0.50.75 00.25 1 0.4 1 0.6 00.325D D2DX二维扩展信源X2为由于无记忆信道 ，因此由式(1.1.2)得二维扩展信道P2为21 112212220.250.250.250.25Xa aa aa aa ap X12121122(|)(|)(|)iijjijijp b ba ap bap ba20.56250.18750.18750.06250.30.450.10.150.30.10.450.150.160.240.240.36

47、P又因为各字符序列间的误码失真函数为根据式(2.2.8)，平均序列失真度 为1 11 11 11 21 12 11 122121 1121 2122 11222211 1211 2212 12122221 1221 2222 12222,0112,1021,1201,2110d a a bbd a a bbd a a b bd a a b bd a a bbd a a bbd a a b bd a a b bd a a bbd a a bbd a a b bd a a b bd a a bbd a a bbd a a b bd a a b b2D20.25 0.5625 00.1875 1 0

48、.1875 1 0.0625 20.3 10.45 00.1 20.15 1 0.3 1 0.1 20.45 00.15 10.16 20.24 1 0.24 1 0.36 00.65D 显然，符合式(2.2.9)的结论。在通信系统中，允许的失真有一定的限度，这个限度可以用平均字符失真度和保真度D来衡量，即满足所谓的如下保真度准则：22DDDDD(2.2.10)2.2.2离散与连续信源的限失真离散与连续信源的限失真编码方法编码方法1.离散信源的限失真编码离散信源的限失真编码设X=0，1，考虑无记忆等概信源X3=000,001,010，011，100，101，110，111，信源需要向信宿传送消

49、息101000100010111110001110假设通过无噪无损信道进行传送，应当如何进行压缩编码呢？一种压缩方法是将信源分成两个子集，分别是000，001，010，100和011，101，110，111，前一个子集的字符序列全部编码为000，后一个子集的字符序列全部编码为111。将000与111分别压缩为0和1在信道上传输，那么消息、编码、压缩、传输与接收、译码的关系见表2.5。表表2.5消息、编码、压缩、传输与接收、译码间的关系消息、编码、压缩、传输与接收、译码间的关系2.模模/数数(A/D)转换的量化失转换的量化失真编码真编码现代通信中大量采用数字通信技术，这是因为数字信号比模拟信号具

50、有更强的抗干扰能力和压缩能力。A/D转换过程如图2.15所示。图 2.15A/D转换过程设连续变量x的取值范围在区间(b0，bn)中，将区间(b0，bn)分成n=2N个小区间b0，b1)，b1，b2)，b2,b3)，bi，bi+1)，n称为量化级数。对于位于bi，bi+1)中的任何采样值，都用yi(bi，bi+1)来表示(i=0，1，2，n1)，见图2.16。那么，y0，y1，yn1就是x(b0，bn)的n级量化值。图 2.16量化示意图下面来讨论如何选取量化值yi。由于yi是指定的，不再是随机变量，因而式(2.2.7)变为采用平方失真函数，则式(2.2.11)变为 ,dDE d x yp x