配套课件-现代编码技术

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，即常用的离散信道模型有以下几种：(1) 二元对称信道。在这种信道中，X=Y=0，1，并且p(1|0)=p(0|1)=p，即字符0和1发生错传的概率相同，信道转移矩

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

5、P为其中，p(|0)=p，p(|1)=q。二元删除信道常用图1.5来表示。图1.5二元删除信道(3) 多元(N元)对称信道。 多元(N元)对称信道常用状态转移图来简化表示，如图1.6所示。图1.6多元(N元)对称信道(4) 无记忆扩展信道。字符序列x经信道后转移成y的概率为 (1.1.1) 二维扩展信道的信道转移矩阵P为(1.1.2) 2) 输入离散、输出连续的AWGN信道AWGN信道的全称是加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道。输入离散、输出连续的AWGN信道具有输入信号是离散的、输出信号是连续的、信道受到的干扰服从高斯分布等特点，是通信

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

7、3b) (1.1.3c) 定义1.1.3对信源输出的一列符号序列按一定规则进行变换称为编码，变换后形成的新序列称为码字，码字中的每一个元素称为码元，码元所属符号集称为码符号集，码字中码元的数量称为码长，全部码字构成的集合称为码。如果q=2，则称为二元码；如果q2, 则称为q元码，这里q表示码符号集中元素的个数。如果在一种码的编译码过程中没有信息损失，并且该码在理想信道(无噪无信道损失)上传输后能不失真地恢复原消息，则称该编码为无失真编码；如果在编译码过程中有控制地损失一些信息，则称该编码为限失真编码。限失真编码在通信中是十分重要的，如一张仅几百兆的光盘能容纳数十小时的视频内容就源于该技术的重要

8、贡献。定义1.1.4设有码C=c1，c2，ci，p(ci)=pi ，码字ci的长度为li，称为码C的平均码长，单位为bit。定义1.1.5设信源符号集为X，并有q元码C，称为编码效率。(1.1.5) (1.1.4) 引理1.1.1(概率匹配原则) 设无记忆信源X=0，1，2，q1且元素相互独立和等出现概率，其上有一种码C=ci|i=1，2，M，ci有长度li，发生概率为pi，若C是无损编码且L(C)最小，那么(1.1.6) 证明由于0，1，2，q1是独立等概的，因此每一个这样的元素有自信息量。 这样，码C中平均每个码字含有的信息量为L(C)lbq。由于是无损编码，因此L(C)lbq不应当小于H

9、(X)，又由于L(C)最小，因此定理1.1.1设离散平稳无记忆信源的熵为H(X)，X= a1，a2，an，那么一定存在一种码C使熵和平均码长间满足下列关系：证明基于信源X，构造一个长度为N的符号串si= (r1,r2,rN)，riX，这样的符号串si形成一个N维扩展信源XN，对N维扩展信源进行编码，获得码C=ci|i=1,2,，每个ci长为li，发生概率为pi。按概率匹配原则进行编码，码长应满足：(1.1.7) 式(1.1.8)两边乘以pi并求和后，有(1.1.8) (1.1.9) 注意到由此可得(1.1.10) 由于是无记忆信源，故H(XN)=NH(X) (1.1.11)将式(1.1.11)

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

11、种压缩方式通常就是去掉消息间的冗余度。要满足信宿恢复消息所需要的条件，就必须在编码时对失真设置一个最大值，称为保真度，记为D。保真度越高，即D越小，意味着压缩去掉的传输的信源信息量就越少，需要传输更多的信源信息量。很显然，对给定的保真度D，信息传输速率R不能低于某一个下限值。保真度不同，下限值也不一定相同，即下限值是D的函数，称为率失真函数，记为R(D)。定理1.1.3对任意给定的保真度D0，只要码长N足够大，一定可以找到一种码C使编码后每个符号的信息传输率不小于R(D)，且码的平均失真度不超过D。4. 数字调制的基本原理所谓调制，是指根据调制信号的变化规律去改变载波某些参数的过程。调制具有搬

12、移信号频谱的作用，能够把信号的频谱搬移到理想的位置，从而获得适合于信道传输的信号，大大提高信号传输的有效性和可靠性。调制可以分为模拟调制和数字调制两种，模拟调制的调制信号取值是连续的，数字调制的调制信号取值是离散的。1) 二进制数字调制二进制数字调制是指调制信号为二进制数字信号的调制方式，在这类调制中，载波的某个参数(如幅度、频率或相位)仅有两种简单的变化状态。二进制数字调制分为幅度键控、频移键控和相移键控三种。(1) 二进制幅度键控(Binary Amplitude Shift Keying，BASK)。设xk是来自于信源的二进制数字信息1和0，其发生概率分别为p和1p，即则BASK信号可以

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

14、信号示意图(3) 二进制相移键控(Binary Phase Shift Keying，BPSK)。设xk是来自于信源的二进制数字信息1和0，其发生概率分别为p和1p，则BPSK信号可以表示为式(1.1.16)表明BPSK调制信号随被调信号序列在两个相位相差为180的信号间切换。当xk=1时，载波信号为cos(2fct)；当xk=0时，载波信号为cos(2fct)，如图1.10 所示。(1.1.16) 图1.10BPSK调制信号示意图2) M进制数字调制设xk是来自于信源的二进制数字信息1和0，将m个二进制符号的所有可能组合与M(M=2m)个载波相位相对应，则MPSK信号可以表示为例如，取m=2

15、，那么载波相位数为M=22=4，称为QPSK (即4PSK)信号。2个二进制符号的可能组合为00，01，10，11，2个二进制符号与载波相位间的对应关系见表1.1。(1.1.17) 表1.1QPSK信号的载波相位对应关系 为了更清楚地表明这种对应关系，常使用信号星座(Constellation)图形来描述。图 1.11 给出了BPSK、QPSK和8PSK信号的星座图。图1.11MPSK信号星座图(a) BPSK信号星座图；(b) QPSK信号星座图；(c) 8PSK信号星座图习题11. 信源编码和信道编码的根本目的是什么？2. 已知离散无记忆信源求信源的熵。3. 在二元对称信道中，已知信源，信

16、宿Y的概率分布p(Y)=0.60.4，求信道转移矩阵。4. 在实际信道中，噪声和损失是不可避免的。矩阵P1是有噪无损信道的信道转移矩阵，P2是无噪有损信道的信道转移矩阵，即试画出两信道的状态转移图，并比较两者的差异，以及据此推断出无噪无损信道和有噪有损信道的状态转移图。5. 已知信源，信道转移矩阵，信宿求信宿Y的概率分布p(Y)。6. 求出无记忆二元对称信道的二维扩展信道的信道转移矩阵。第2章信源编码 2.1无失真信源编码2.2限失真信源编码习题2.1无失真信源编码无失真信源编码的理论基础就是第1章介绍的香农第一定理，实现的途径之一是概率匹配原则，最终目的是找到一种平均码长最短的码。先来看一个

17、例子。例2.1.1设有离散无记忆信源，进行以下两种方式的二进制编码：(1) a100，a201，a310，a411；(2) a10，a210，a3110，a4111，试求两种编码方式的平均码长和编码效率。解信源熵为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(2) L(C2)=0.51+0.32+0.153+0.053=1.7 bit2.1.1Huffman编码1. 编码原理利用概率匹配原则，编码时，码长应当选择满足式(1.1.8)的整数，但并

18、非每次应用都能获得理想的编码。看下面两个例题。例2.1.2无记忆信源，利用概率匹配原则进行编码，并求出平均码长和编码效率。解根据式(1.1.8)，字符a1、a2、a3、a4、a5对应的码长分别为1、2、3、4、4，用二进制符号来表示字符，即那么，平均码长为又因为所以，获得的编码效率为=100%例2.1.2的二元码的码树见图2.1。图 2.1例2.1.2编码的码树例2.1.3无记忆信源，试利用概率匹配原则进行编码，并求出平均码长和编码效率。解根据式(1.1.8)，字符a1、a2、a3、a4、a5、a6对应码长分别为2、2、3、5、6、6，用二进制符号来表示字符，即计算后，得到H(X)=1.83

19、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%由此可见，改进后的码树(图2.3)的编码效率明显提高。例2.1.3启示我们编码时码树不能留有空枝，单纯地应用概率匹配原则不一定能得到最佳编

20、码。例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%定理2.1.1(q元Huffman编码)设离散无记忆信源按下述步骤进行编码，获得的码一定具有最小平均码长。第一步，根据出现概率的大小，按从大到小的顺序重排字符符号。第二步，在重组的信源中，从最小概率的

21、符号开始，按概率从小到大的方式取q个符号作为q片树叶合并到一个节点上，将0，1，2，q1这q个数不重复地分配到这q个树叶上。第三步，被合并的q个字符用一个临时字符代替，这个临时字符的概率为被合并的q个字符的概率之和，其余字符及概率不变，从而形成一个新的信源空间。第四步，如果新的信源空间的概率分布p(X)=1，这时的节点就是码树的树根，则转到第五步，否则， ，转到第一步。第五步，从树根开始，沿枝到达树叶，途中遇到的数字按行走顺序组合就得到该树叶字符所对应的码字，找完全部树叶，编码完成。证明设Huffman编码完成后，aici(i=1，2，n)，并且码ci的长度为li，则Huffman编码的平均码

22、长。再设p(ak)p(aj)，根据Huffman编码，则有ljlk。如果重新构造一个编码C，其对应关系如下：即交换字符ak与aj所对应的码字，而其余字符对应码字不变，形成码C，那么码C的平均码长为式(2.1.1)说明Huffman编码的平均码长最短。(2.1.1) 从Huffman编码过程来看，如果完成编码共引入了r个临时字符，除第一次合并用了信源的q个字符外，其余各次合并都只使用了信源的q1个符号，所以信源符号的数量应当为n=r(q1)+q (2.1.2)例2.1.4设离散无记忆信源，构建平均码长最短的二元码。解第一次合并：按概率从大到小的顺序重排字符，并合并最后两个字符为新的临时字符d1。

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

24、.5已知离散无记忆信源试求Huffman三元和四元编码。解本例的三元Huffman编码过程见图2.6，三元Huffman编码如下：图 2.6三元Huffman编码过程由于不满足式(2.1.2)，因此添加一个字符a10，并取p(a10)=0。本例的四元Huffman编码过程见图2.7，四元Huffman编码如下：图 2.7四元Huffman编码过程2. 举例CCITT T.4对三类传真机的扫描线长度和每行像素作了如下规定：(1) A4纸文本的一行(215 mm1%)扫描后构成一条扫描线，线上有1728个黑白像素；(2) B4纸文本的一行(255 mm1%)扫描后构成一条扫描线，线上有2048个黑

25、白像素；(3) A3纸文本的一行(303 mm1%)扫描后构成一条扫描线，线上有2432个黑白像素。三类传真机对扫描线的编码的结构如图2.8所示。图 2.8三类传真机对扫描线的编码的结构(a) 一维编码方案；(b) 二维编码方案经过大量统计发现游程长度有以下特点：(1) 游程长度的概率分布表现为对扫描的文本的行与行间不同，对扫描的文本的页与页间不同；(2) 出现于每一扫描线中的游程长度的种类非常多，例如，在一条有1728个黑白像素的扫描线上出现的可能游程长度为1，2，3，1728。MH码表见表2.1和表2.2。 表2.1一维改进Huffman编码表构造码 表2.2一维改进Huffman编码表结

26、尾码 传真机传输一页文件文本是按图2.9所示的数据传输格式进行传输的。图 2.9一页文件传真的数据传输格式2.1.2算术编码1. 基本概念Huffman编码是在信源符号与可变长度码字之间建立一个1-1对应关系而实现编码的，算术编码则是对信源的输出符号流进行编码，因此，算术编码不需要像Huffman编码那样为每一个信源符号指定一个码字。本节先介绍算术编码的思想和基本概念，具体编码方法的介绍将在后续各小节中陆续展开。设有无记忆信源空间，其中，p1p2pn，定义信源字符的累积概率为很明显，有下列关系：l0=0，l1=p1，l2=p1+p2，并且pi=lili1 (2.1.4)(2.1.3)由于概率的

27、大小总是在0和1之间，因而可以把li与li1视为区间0，1)中的两个点，那么，pi刚好等于子区间li1，li)的长度。很明显，这些子区间是互不重叠的，不同的信源符号有唯一一个子区间与之对应，因而，我们可以任选子区间的一个点来代表这个子区间所对应的信源符号。例如，可以选子区间的左端点，这种代表是可变的，但代表的信源符号是唯一的，如图2.10所示。图 2.10信源字符累积概率划分的子区间与信源符号的对应关系不同的字符序列与唯一一个子区间对应，如图2.11所示。图 2.11序列的累积概率划分的子区间与序列的对应关系很明显，每一序列的概率恰好为所对应子区间li1，li)的长度，有关系式：(2.1.5)

28、 新序列或者的累积概率为(2.1.6) (2.1.7) 2. 编码方法算术编码的编码过程实质上就是寻找字符所对应的子区间，新到字符对应的子区间是通过迭代更新前一个字符的子区间来获得的。设信源输出的第k1个字符对应的子区间为DLk1，DHk1)，子区间的宽度为k1=DHk1DLk1，那么，第k个字符对应的子区间DLk，DHk)为(2.1.8) 式(2.1.8)也可以变形为用子区间下端点和区间宽度来表示，即(2.1.9) 算术编码的具体编码过程如下。首先，初始化。然后，输入字符进行迭代运算。第一步，信源X输出第一个字符。设 。取，更新区间，即新区间。如果信源输出字符结束，则任取作为字符 的算术编码

29、。否则，继续第二步，并令(2.1.10) 第二步，信源X输出第二个字符 。设。取，更新区间，。如果信源输出字符结束，则任取 作为字符的算术编码。否则，继续第三步，并令第三步，信源X输出第三个字符 。 假设已进行了第k1步，即已知和，继续第k步。第k步，信源X输出第k个字符 。(2.1.11) 设。取，更新区间， 。如果信源输出字符结束，则任取作为字符的算术编码。否则，继续第k+1步，并令归纳起来，算术编码的编码流程图如图2.12所示。(2.1.12) 图 2.12算术编码的编码流程图例2.1.6设有离散无记忆信源空间，求出字符流a2a0a1a0a0a4a3的算术编码。解首先，将区间0，1)分成

30、5个子区间，即其次，初始化，即DL0=0，DH0=1，j=0最后，输入字符进行迭代运算，见表2.3。表2.3例2.1.6字符流的算法编码过程3. 译码方法因为每一字符被唯一地指定了一个子区间，所以只需要根据码字来反推是哪个子区间就能得到相应的字符，从而实现译码。算术译码的过程如下。第一步，译出字符流的第一个字符。第二步，译出字符流的第二个字符。第三步，译出字符流的第三个字符。如此继续下去，直到最后一个字符译出。归纳起来，算术编码的译码流程图如图2.13所示。图 2.13算术编码的译码流程图例2.1.7信源空间同于例2.1.6，译出算术编码b=0.7412261962890625。解译码过程见表

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

32、2.14QM编译码器的编译码原理框图(a) 编码器；(b) 译码器式(2.1.9)的子区间迭代关系可以简化为如下两种形式：(1) 如果第k个字符的概率较大，即字符a1，则有(2) 如果第k个字符的概率较小，即字符a2，则有(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)来实现编译码的。2.2限失真信源编码2.2.1基本概念什么是失真？简单地说，失真就

33、是信宿接收到的符号与信源发出的符号不同。 定义2.2.1设信源X=a1，a2，an，信宿Y=b1，b2，bm，从信源发送出符号xX，信宿接收到符号yY，称为失真函数。(2.2.1) 失真函数d(x，y)可以通过设置不同的d0来表示失真的严重程度，常见的d0取值方法主要有以下几种形式。误码失真：d0=1绝对失真：d0=|xy| (2.2.2)平方失真：d0=(xy)2 (2.2.3)相对失真： (2.2.4) 定义2.2.2设从信源X发送长度为N的符号序列(x1，x2，xN)，信宿接收到的是长度为M的符号序列(y1，y2，yM)，定义阶是NM的矩阵A：称A为失真矩阵。(2.2.5) 例2.2.1

34、在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，失真矩阵为设信源X=0，1，2，3，信宿Y=0，1，2，3，采用平方失真函数，失真矩阵为定义2.2.3设信源p(ai，bj)表示ai与bj的联合概率，称为平均字符失真度。式中，E表示数字期望，p(ai，bj)=p(ai) p(bj|ai)。(2.2.6) 如果是连续信号，式(2.2.6)中的求和符号转化为积分符号，概率转化为随机变量的概率密度函数，就得到连续随机变量的平均失真函数：(2.2.7) 定

35、义2.2.4设信源发出长为N的字符序列，其中，信宿接收字符序列为，其中，那么字符序列x与y间的失真函数为定义2.2.5设有信源X的N维扩展信源XN，信宿Y的N维扩展信宿YN，那么平均序列失真度为对于无记忆信道，与间有关系：(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(b2|a2)=0.6由式(2.2.6)得平均字符失真度为X二维扩展信源X2为由于无记忆信道 ，因此由式(1.1.2)得二维扩展信道P2为

36、又因为各字符序列间的误码失真函数为根据式(2.2.8)，平均序列失真度 为显然，符合式(2.2.9)的结论。在通信系统中，允许的失真有一定的限度，这个限度可以用平均字符失真度和保真度D来衡量，即满足所谓的如下保真度准则：(2.2.10) 2.2.2离散与连续信源的限失真编码方法1. 离散信源的限失真编码设X=0，1，考虑无记忆等概信源X3=000, 001, 010，011，100，101，110，111，信源需要向信宿传送消息101000100010111110001110假设通过无噪无损信道进行传送，应当如何进行压缩编码呢？一种压缩方法是将信源分成两个子集，分别是000，001，010，1

37、00和011，101，110，111，前一个子集的字符序列全部编码为000，后一个子集的字符序列全部编码为111。将000与111分别压缩为0和1在信道上传输，那么消息、编码、压缩、传输与接收、译码的关系见表2.5。 表2.5消息、编码、压缩、传输与接收、译码间的关系2. 模/数(A/D)转换的量化失真编码现代通信中大量采用数字通信技术，这是因为数字信号比模拟信号具有更强的抗干扰能力和压缩能力。A/D转换过程如图2.15所示。图 2.15A/D转换过程设连续变量x的取值范围在区间(b0，bn)中，将区间(b0，bn)分成n=2N个小区间b0，b1)，b1，b2)，b2, b3)，bi，bi+1

38、)，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)变为(2.2.11) (2.2.12) 对式(2.2.12)求关于bi+1的导数，并令其为零，得到于是，得到(2.2.13) 式(2.2.13)说明平均失真度达到最小，应选择bi+1为区间yi，yi+1的中点。又因为所以(2.2.14) 考虑变量x的概率密度函数

39、是均匀的，即那么，式(2.2.14)可化为(2.2.16) (2.2.15) 式(2.2.16)说明yi应为区间bi，bi+1的中点，结合式(2.2.13)，得到各小区间是均匀的，不难计算将式(2.2.17)代入式(2.2.12)，求得(2.2.18) (2.2.17) 2.2.3最小均方误差准则下的最佳线性预测编码方法通常，在模拟信号采样值间存在一定的相关性，因此，相邻采样值之差的方差会比采样值的方差小许多，这说明如果用量化采样值的量化级数去量化差值，那么量化误差会减小，这意味着在保持相同量化精度的条件下，对相邻采样值之差的量化级数可以减小，这一结论对数据压缩极为有利。差分脉冲编码调制(DP

40、CM)系统就是利用上述思想进行工作的，见图2.17。图 2.17DPCM系统框图从图2.17可以看出，DPCM系统的关键就是预测器的构造，预测器可以通过前向预测法来实现。已知采样值x(1)，x(2)，x(n1)，需要估计x(n)。自然会想到，估计x(n)的最简单的方法就是把它视为已知采样值的线性组合，即x(n)被估计为预测器可以通过图2.18所示的横向FIR滤波器结构来实现。(2.2.19) 图 2.18前向预测器的实现结构式(2.2.19)通过过去的数据来估计当前数据，因此称为前向预测。式(2.2.19)中的N称为预测器的阶，ai称为预测器系数，预测误差为人们当然希望前向预测器是最佳的，也就

41、是预测的均方误差应当最小。要使最小，必须合理选择预测器系数ai。由(2.2.20) (2.2.21) 得到方程组使用自相关函数的定义，并考虑信源是平稳随机过程，于是有Ex(ni)x(nj)=R(|ij|) (2.2.23)式中，R()表示x(n)在相移为时的自相关函数。(2.2.22) 通常，采样数据是有限的，因而R()只能通过有限个数据来估计。如果有M个采样数据，则R()能被估计为又根据式(2.2.21)，预测的均方误差为(2.2.24) (2.2.25) 联合式(2.2.22)和式(2.2.23)，得到(2.2.26) 图2.19给出了Levinson递推算法的流程。图 2.19Levin

42、son递推算法的流程2.2.4最佳变换编码方法数据压缩编码的实质是去掉冗余消息，正交变换是完成这一任务的有力工具之一。正交变换主要有Karhunen-Love变换(简称K-L变换)、离散正弦变换(Discrete Sine Transform，DST)、 离散余弦变换(Discrete Cosine Transform，DCT)、离散Hartley变换、离散W变换等。1. K-L变换设x与y是两个阶为N1的列向量(信号矢量)，A是一个NN的矩阵，如果y=Ax，则称x被变换为y。如果变换矩阵A是正交矩阵，则称这个变换为正交变换。设Ai表示矩阵A的第i行的转置，则A=A1，A2，ANT又因为A是正

43、交矩阵，即ATA=AAT=I，所以A1=AT于是，由变换y=Ax得到(2.2.27) 设x的均值为0，现在我们希望用较少的y的分量来表示x，从而实现对数据x的压缩。例如，用y的前m个分量来表示数据x，这样的表示只能是x的近似，记为，即误差矢量为(2.2.28) (2.2.29) 当然，在恢复信号x时，也只能用y的这前m个分量。因此，希望能合理选择变换矩阵A使均方误差达到最小。这里使用了A是正交矩阵，即 的条件。由式(2.2.27)有，将其代入式(2.2.30)，有(2.2.30) (2.2.31) 为了使式(2.2.31)最小，考虑Lagrange条件极值，约束条件是矩阵A正交，有于是，获得C

44、xAi=iAi (2.2.33)式(2.2.33)提示我们，实现数据的压缩的变换矩阵应当由信号的协方差矩阵的特征向量来构成。将式(2.2.33)代入式(2.2.31)，得到均方误差er为(2.2.34) (2.2.32) 2. DCT变换1) 一维DCT变换一维DCT变换由Ahmed和Rao首先给出，一维DCT变换能将信号x=(x(0)，x(1)，x(N1)T 变换到信号y=(y(0)，y(1)，y(N1)T，且满足下列关系式：(2.2.35) 令那么，一维DCT变换的正变换可以简写为(2.2.37) (2.2.36) 写成矩阵形式，有y=CNx (2.2.38)式中：(2.2.39) 由于矩

45、阵CN是正交的，因此一维DCT的反变换不难求出，即将式(2.2.40)写成一般表达式，即(2.2.40) (2.2.41) 令称式(2.2.42)为一维DCT变换的变换核。利用变换核，一维DCT变换的正、反变换可以简单表示为(2.2.43) (2.2.42) 2) 二维DCT变换在许多场合，需要变换的信号不是一维信号，而是二维信号，如一幅静态数字图像就是用二维信号来表示的。二维DCT变换是非常重要的一类二维变换。设x(n，m)|n=0，1，N1；m=0，1，M1表示一个二维离散信号集合，二维DCT变换将信号集合x(n，m)变换为y(u，v)|u=0，1，N1；v=0, 1，M1，且满足下列关系

46、：(2.2.44) 二维DCT变换的反变换为定义二维DCT变换的变换核为(2.2.45) (2.2.46) 那么，二维DCT变换的正、反变换在变换核下可以简化表示为(2.2.47) 注意到变换核是可分离的，即h(u，v，n，m)=g(u，n，N)g(v，m，M)，这里的g(，)就是式(2.2.42)，所以，二维DCT变换的正变换也可以写成如下的矩阵形式：式中：y(u，v)NM表示NM阶矩阵，第u行第v列元素为y(u，v)；CN和CM的意义同于式(2.2.39)。(2.2.48) 展开式(2.2.47)的反变换，得到式(2.2.49)表示一个NM个点的图像可以理解为由NM个基图像的加权和构成，其

47、权重就是二维DCT变换值y(u，v)，因而y(u，v)代表了对应的基图像h(u，v，n，m)在加权和中所占的比重，在物理概念上相当于二维DCT变换把空间像素的几何分布变换成空间的频率分布。(2.2.49) 图像块的大小NM除了对二维DCT变换的计算量有很大影响外，对图像的压缩效果也有明显影响。通常，在对图像进行DCT变换时往往把图像分割成许多小方块，然后按顺序对每一块进行处理，图像块较小，图像中包含的像素就少，进行DCT变换的计算量就小，但压缩效果差，还会产生“方块效应”；图像块过大，虽然去相关性能好，但计算量很大并且一旦图像块的像素足够多后对数据压缩的效果就会达到饱和状态，再加大块的尺寸对改

48、进压缩效果不会有明显提高。因此，在对静止图像进行压缩的JPEG技术标准中，建议的图像块的大小为88，其压缩流程见图2.20。图 2.20静止数字图像的JPEG压缩流程3. 小波变换1) 概念准备设有函数f(t)(t+)，如果函数f(t)满足：那么，称f(t)为绝对可积函数。设函数f(t)(t+)绝对可积，称(2.2.50) (2.2.51) 为f(t)的傅里叶变换。称为F()的傅里叶反变换。这里j2=1。设有函数f(t)(t1，b00，定义，称下面积分为离散小波变换。(2.2.85) (2.2.86) 最典型的a0和b0的取值是a0=2，b0=1，即我们已经熟悉的二尺度小波伸缩平移族式(2.2

49、.71)。例如, 以为尺度函数，那么，小波函数就是Harr函数，其小波伸缩平移族为(2.2.87) 图2.27给出了几个较小的i和k对应的Harr小波伸缩平移族及尺度函数的波形。图 2.27尺度函数波形与Harr小波伸缩平移族的几个波形由式(2.2.80)不难看出，二尺度下的离散小波变换就是离散细节系数，Mallat塔式算法为计算提供了一套递推公式。在式(2.2.81)中令i=0并用n来代替k，则有由式(2.2.88)，对(t)进行伸缩平移操作，即用2itk代替t后，有(2.2.88) (2.2.89) 再令m=2k+n，则式(2.2.89)可以简化表示为将式(2.2.90)两边同乘以2i/2

50、并应用式(2.2.65)，得到又由式(2.2.79)，有(2.2.91) (2.2.90) (2.2.92) 同理，不难推导出式(2.2.92)和式(2.2.93)是离散小波变换Mallat塔式算法的两个关键递推方程，这两个方程建立了Vi1空间的分辨率为i1的离散平滑逼近系数到Vi和Ui两个子空间的分辨率为i的离散平滑逼近系数 和离散细节系数 间的递推关系，使计算量大幅度地减小。Mallat塔式算法的分解递推流程见图2.28。(2.2.93) 图 2.28Mallat格式算法的分解递推流程在递推出离散平滑逼近系数和离散细节系数后，由式(2.2.64)、式(2.2.76)和式(2.2.77)，f

51、(t)可以分解成(2) 离散小波反变换。离散小波变换主要用于信号的分解，离散小波反变换主要用于信号的重建，重建是分解的逆过程。为了快速完成信号的重建，我们也需要找到离散平滑逼近系数和离散细节系数间的递推关系。由式(2.2.76)、式(2.2.77)和式(2.2.78)，有(2.2.94) (2.2.95) 利用式(2.2.65)和式(2.2.71)，并把二尺度函数的性质式(2.2.81)和式(2.2.83)代入式(2.2.95)，有由式(2.2.65)，式(2.2.96)可以简化为(2.2.97) (2.2.96) 注意到，所以式(2.2.97)两边同乘以i1，m(t)后求内积，可以得到进一步

52、地，有式(2.2.99)就是重建信号的Mallat快速算法递推公式，递推流程可以用图2.29来表示。(2.2.99) (2.2.98) 图 2.29Mallat算法的重建递推流程(3) Mallat算法的初值及h(n)与g(n)间的关系。于是，分辨率i=0时的离散平滑逼近系数a0可以用对原函数的采样来近似代替，即式中，t为采样间隔时间。已知h(n)与g(n)间的关系是实现Mallat算法快速分解的另一个前提，可以证明两者有如下关系：g(n)=(1)nh(1n) (2.2.101)(2.2.100)5) 二维离散小波变换类似于一维离散小波变换，在分辨率i下的二维尺度空间Vi可以表示为与的张量积，

53、即用Wi表示在的正交补空间，即且则有(2.2.102)(2.2.103)设f()是Wi上的小波函数，fi，m(x)=2i/2(2ixm)，f i，n(y)=2i/2(2iyn)，f i，m(x)|mZ和f i，n(y)|nZ是Wi上的标准正交基，定义(2.2.104)f(x，y)可以在二维小波函数和二维尺度函数下展开为式中：、 和分别为空间、 和上的小波展开系数； 为空间Vi上的尺度展开系数，即(2.2.105)(2.2.106)类似于一维情况，二维离散小波变换也有快速Mallat分解算法，算法公式如下：(2.2.107)二维离散小波变换的快速Mallat重建算法递推公式为(2.2.108)习

54、题21. 已知离散无记忆信源为求二元Huffman编码，并计算效率，画出码树。2. 已知离散无记忆信源为求三元和四元Huffman编码。3. 已知离散无记忆信源为算术编码为b=0.57470703125(0.10010011001)，译出长度N=5的字符流。4. 无记忆信源，信道转移矩阵为 ，试求在平方失真函数下的平均字符失真度。 5. 求采用绝对失真函数时，A/D转换的量化失真编码的平均失真度，其中，p(x)采用式(2.2.15)。6. 设信号x=(x1，x2)T的协方差矩阵，求出K-L变换y=Ax的正交矩阵A。7. 验证N=4时的一维DCT变换矩阵是正交矩阵。8. 设有一个二维图像信号(a

55、0)，试求出二维DCT变换。9. 结合表2.1和表2.2，对用MH编码压缩的传真信号 00110101000011010110001011100000011010110000000000001译出黑白游程长度的顺序分布，并计算压缩比。第3章分组码 3.1纠、检错编码的基本概念3.2线性分组码3.3循环码3.4BCH码习题 3.1纠、检错编码的基本概念为了降低错误概率pe及使接收端具备检错、纠错能力，我们这样来对待传消息进行编码。选码C1=00000，11111，作映射：即消息中的每一符号比特按其重复的5比特码字来表示，并由发送端传送。接收端按选大原则进行译码，在接收的5比特矢量中，哪个符号多就

56、译为哪个。例如接收为10110，则译为11111。消息的编码、译码关系见表3.1。表3.1消息的编码、译码关系定义3.1.1，x=(x1，x2，xn)，y=(y1，y2，yn)，称dist(x，y)=|i|xiyi，i=1，2，n| (3.1.1)为码字x与y的汉明距离。码字间的汉明距离满足下列三角不等式：dist(x，y)dist(x，z)+dist(z，y) (3.1.2)在一个码中，任意两个不同码字间汉明距离的最小者称为这个码的最小汉明距离。定义3.1.2设有码C，称 (3.1.3)为码C的最小汉明距离。在一个码中，码字中非零码元的数目也是一个重要的参数，这个参数通常称为码字的汉明重量。

57、定义3.1.3设有码C，称wt(x)=|i|xi0，i=1，2，n| (3.1.4)为码字x的汉明重量。定义3.1.4设有码C，0 =(0，0)，称wt(C)=minwt(x)|xC，x0 (3.1.5)为码C的最小汉明重量。例3.1.1设有码C2=(a1，a2，a3，a4，a5，a6，a7，a8)，式中a1=(0000000)a2=(0011101)a3=(0100111)a4=(0111010)a5=(1001110)a6=(1010011)a7=(1101001)a8=(1110100)求dist(a2，a4)，dist(a3，a7)，wt(a8)，dist(C2)，wt(C2)。解di

58、st(a2，a4)=4，dist(a3，a7)=4，wt(a8)=4，dist(C2)=4，wt(C2)=4定义3.1.5设有码C，如果，有x+yC，则称码C是线性码。所有的这样2k个码字构成的集合称为分组码。须注意一点，nk个校验元可以放在码字中的任何位置，如果码字前k位固定为信息码，则这种分组码称为系统分组码，如图 3.1 所示。图 3.1系统(n，k)分组码码字结构定义3.1.6将k位信息码通过一定的规则添加nk个校验元而形成长为n的码字，如果所有这样的码字组成一个线性码，则称为(n，k)线性分组码。定义3.1.7称(n，k)线性分组码的 为码率。例3.1.2构造奇偶校验码。对X=0，1

59、的k维扩展信源Xk添加一位校验位形成一个长为k+1的码字，即且满足关系：x1+x2+xk+xk+1=0(偶校验) (3.1.6)即信息码(x1x2xk)中如有偶数个1，则xk+1=0，如有奇数个1，则xk+1=1。或x1+x2+xk+xk+1=1(奇校验) (3.1.7)即信息码(x1x2xk)中如有偶数个1，则xk+1=1，否则xk+1=0。解仅讨论偶校验，所得结论适合于奇校验。设发送码字(x1x2xkxk+1)，接收矢量为(y1y2ykyk+1)，如果无错，则接收矢量应满足式(3.1.6)；如果产生奇数个错误，则y1+y2+ yk+yk+1=1， 因为一个码元x发生错误意味着这个码元变为x

60、+1，为讨论方便，不防设y1，y2，y2r+1发生错误，于是y1+y2+yk+yk+1=(1+x1)+(1+x2)+(1+x2r+1)+x2r+2+xk+xk+1=(2r+1)+(x1+x2+xk+xk+1)=2r+1=1 (mod2)说明不满足式(3.1.6)，从而发现错误，但无法判别哪些码元、多少码元出错，所以无纠错能力。如果是偶数个错误，则有 y1+y2+yk+yk+1=2r+(x1+x2+xk+xk+1)=2r=0 (mod2)说明满足式(3.1.6)，因而无法检出错误。综合起来，奇偶校验码能检奇数个错误，不能检偶数个错误，无纠错能力，码率为。定理3.1.1在一个线性分组码中，码的最小