信源编码及信道编码1

第3章(1)

信源及信源编码邮箱:frankgy@126.com

电话2/67-学习目标知道为什么要进行信源编码？掌握信源及信源的数学模型掌握信息熵的概念了解典型的无失真信源编码了解典型的限失真信源编码学习完本节课程，您应该能够：-3/67-课程内容

3.1信源及分类3.2信源的数学模型3.3信息的度量—信息熵3.4无失真信源编码3.5限失真信源编码-4/67-3.1信源及分类信源和信道：在现代通信中，信源和信道是组成通信系统的最基本单元。信源是产生信息的源信道则是传送载荷信息的信号所通过的通道信源与信宿之间的通信是通过信道来实现的。-5/67-3.1信源及分类(续)为什么要进行信源编码？信源信源编码信道编码调制传输媒介信源译码信宿信道译码解调噪声干扰若不进行编码，信源会存在大量的统计多余的成分它完全可以利用信源的统计特性在接收端恢复出来-6/67-3.1信源及分类(续)信源编码信号要通过数字信道传输，首先要进行数字化处理，包括采样、量化、编码、压缩等。信源编码保证了信号能否进入有一定条件限制的数字信道里。信源编码的任务是在分析信源统计特性的基础上，设法通过信源的压缩编码去掉这些统计多余成分。保证信号进入有一定条件限制的数字信道。-7/67-3.1信源及分类(续)信源的分类按刻画信源的随机过程的性质划分无记忆信源有记忆信源平稳信源非平稳信源连续信源离散信源。根据输出符号间的依赖关系统计特性是否随时间的起点改变根据信源符号的取值-8/67-3.1信源及分类(续)按取值时刻与取值集合的连续与离散划分时间(空间)取值信源种类举例数学描述离散离散离散信源（数字信源）文字、数据、离散化图象

离散随机变量序列

离散连续连续信号跳远比赛的结果、语音信号抽样以后

连续随机变量序列

连续连续波形信源（模拟信源）

语音、音乐、热噪声、图形、图象

随机过程

连续离散不常见-9/67-课程内容

3.1信源及分类3.2信源的数学模型3.3信息的度量—信息熵3.4无失真信源编码3.5限失真信源编码-10/67-3.2信源的数学模型离散信源数学模型：集合A中，包含该信源的所有可能输出的消息，集合P中包含对应消息的概率密度，各个消息的输出概率总和应该为1。AP=a1a2……aqp1p2……pq-11/67-3.2信源的数学模型(续)连续信源数学模型：每次只输出一种消息，但消息的可能数目是无穷多个。-12/67-课程内容

3.1信源及分类3.2信源的数学模型3.3信息的度量—信息熵3.4无失真信源编码3.5限失真信源编码-13/67-3.3.1信息的度量中的概念度量通信的技术性能

度量通信的技术性能主要是从通信的数量与质量两方面来讨论的一般数量指标用有效性度量，主要与信源统计特性有关而质量指标用可靠性度量。主要决定于信道的统计特性有效性(数量指标)信道一定时,系统能够传输信息内容的多少。可靠性(质量指标)系统接收端恢复信息的准确程度。-14/67-3.3.1信息的度量中的概念(续)自信息：一个事件（消息）本身所包含的信息，它是由事件的不确定性决定的。比如抛掷一枚硬币的结果是正面这个消息所包含的信息。

互信息：一个事件所给出关于另一个事件的信息比如今天下雨所给出关于明天下雨的信息-15/67-3.3.1信息的度量中的概念(续)平均自信息：事件集（用随机变量表示）所包含的平均信息，它表示信源的平均不确定性。比如抛掷一枚硬币的试验所包含的信息。

平均互信息一个事件集所给出关于另一个事件集的平均信息比如今天的天气所给出关于明天的天气的信息。-16/67-3.3.1信息的度量中的概念(续)什么是信源的不确定性信源发出的消息中必须包含信宿事先不知道的内容，这样发出的信息才有意义，这就是信源的不确定性。消息的不确定性越大，信息量就越多信源提供的不确定度就是信源提供的信息量。信道信源信宿-17/67-3.3.1信息的度量中的概念(续)什么是信源的不确定性(续)自信息量：设信源发出的消息Xi的概率为P(i),I(xi)表示Xi提供的信息量

I(xi)=log(1/P(i))对数若取2为底，则信息量的单位为比特（bit）对数若取e为底，则信息量的单位为奈特（nat）对数若取10为底，则信息量的单位为笛特（Det）换算公式如下：

1bit=0.693Nat=0.301Det1、当事件发生前，表示该事件发生的不确定性；2、当事件发生后，表是该事件所提供的信息量-18/67-3.3.1信息的度量中的概念(续)举例:当某事件必然发生时，就不存在不确定性，即不确定性为0。即P(xi)=1时，I(1)=-log1=0当某事件几乎不发生时（或发生概率很小），其不确定性应趋于无穷大，即limI[p(xi)]=-log0=∞发生概率小的事件其不确定性比大概率事件大，即I(x1)=-logp(x1)I(x2)=-logp(x2),(p(x1)>p(x2)),则I(x1)<I(x2)-19/67-例：设天气预报有两种消息，晴天和雨天，出现的概率分别为1/4和3/4，我们分别用来表示晴天，以来表示雨天，则我们的信源模型如下：3.3.1信息的度量中的概念(续)-20/67-3.3.2离散信源的平均信息量—信息熵离散信源由有限个消息符号或状态构成的信源就是有限信源也称离散信源。信息熵设离散信源X可输出n种彼此独立的符号,各符号出现概率如下：

X:x1,x2,……,xn

P(x):P(x1),P(x2),……,P(xn)

则该信源的平均信息量为：-21/67-3.3.2离散信源的平均信息量—信息熵(续)信息熵定义：信源各个离散消息的自信息量的数学期望(即概率加权的统计平均值)为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时称为无条件熵或熵函数，简称熵，记为。信息熵具有以下两种物理含义：1、表示信源输出前信源的平均不确定性2、表示信源输出后，每个符号所携带的平均信息量-22/67-3.3.2离散信源的平均信息量—信息熵(续)举例例：对于二元离散信源，出现0、1的概率分别为：P(0)=p,P(1)=1-p,则该信源熵为：数学证明只有当p=1/2时H2(x)取值最大:H2(x)=1当p=1或p=0时H2(x)取值最小。即当一个二元信源只能发出全0或全1时，其消息序列不包含任何信息。反之当等概率发出0、1时信息量最大。对于N个符号：p=1/N时，信源的熵最大HN(x)=log2N-23/67-

则：说明第二个信源的平均不确定性更大一些3.3.2离散信源的平均信息量—信息熵(续)例：天气预报，有两个信源-24/67-3.3.2离散信源的平均信息量—信息熵(续)信息熵的基本性质熵函数可以表示为：-25/67-性质1：非负性即H(X)≥0由于0≤pi≤1，所以logpi≤0，-pilogpi≥0，则总有H(X)≥0。3.3.2离散信源的平均信息量—信息熵(续)-26/67-性质2：对称性

当变量交换顺序时，熵函数的值不变。

信源的熵只与概率空间的总体结构有关，而与各概率分量对应的状态顺序无关；3.3.2离散信源的平均信息量—信息熵(续)-27/67-性质3：确定性；

当信源X的信源空间[X，P]中,任一个概率分量等于1，根据完备空间特性，其它概率分量必为0，这时信源为一个确知信源，其熵为0。

如果一个信源的输出符号几乎必然为某一状态，那么这个信源没有不确定性，信源输出符号后不提供任何信息量。3.3.2离散信源的平均信息量—信息熵(续)-28/67-性质4：可加性

即统计独立信源X和Y的联合信源的熵等于它们各自的熵之和。3.3.2离散信源的平均信息量—信息熵(续)H(XY)=H(X)+H(Y)-29/67-性质5：极值性

上式表明，对于具有q个符号的离散信源，只有在q个信源符号等可能出现的情况下，信源熵才能达到最大值，这也表明等概分布的信源的平均不确定性最大，这是一个很重要得结论，称为最大离散熵定理例：对于一个二元信源H(X)=H(1/2,1/2)=log2=1bit3.3.2离散信源的平均信息量—信息熵(续)-30/67-联合熵及条件熵类似于对信息熵H(X)的定义，同理也可以进一步对信宿熵H(Y)、条件熵H(Y/X)、H(X/Y)联合熵H(X，Y)作如下类似定义：3.3.2离散信源的平均信息量—信息熵(续)-31/67-它们之间，有如下主要性质：

又称为Shannon不等式。3.3.2离散信源的平均信息量—信息熵(续)-32/67-3.3.3冗余度什么是冗余度定义:它表示给定信源在实际发出消息时所包含的多余信息,也称余度或剩余度。为了定量地描述信源的有效性，定义下面两个概念其中：H∞

表示考虑全部信源统计特性后信源的最小信息熵，它是信道传送的理论上最佳值。H0是不考虑信源统计特性，即认为信源消息均为等概率时信源的最大熵。-33/67-3.3.3冗余度(续)信源的冗余度来自两个方面信源符号间的相关性信源符号分布的不均匀性。压缩剩余度的方法减小符号间的相关性使信源符号等概率分布-34/67-3.3.3冗余度(续)冗余的利弊从提高信息传输效率的观点看从提高抗干扰能力角度来看信源编码与信道编码的目的信源编码是减少或消除信源的剩余度以提高信息的传输效率信道编码则通过增加冗余度来提高信息传输的抗干扰能力。-35/67-3.3.3冗余度(续)冗余度计算举例:下表为各字母出现概率，计算其冗余度字母概率字母概率字母概率空格0.2S0.052Y,W0.012E0.105H0.047G0.011T0.072D0.035B0.0105O0.654L0.029V0.008A0.063C0.023K0.003N0.059F,U.0225X0.002I0.055M0.021J,Q0.001R0.054P.0175Z0.001-36/67-3.3.3冗余度(续)由上述表格，首先求得独立等概率情况下的值：再求独立不等概率情况下的还可进一步求得有一阶、二阶记忆下的和：-37/67-3.3.3冗余度(续)最后用推断方法求这样，利用公式可分别求得η=H∞/H0=1.4/4.76=0.29，γ=1-0.29=0.71。-38/67-课程内容

3.1信源及分类3.2信源的数学模型3.3信息的度量—信息熵3.4无失真信源编码3.5限失真信源编码-39/67-3.4.1码的分类分组码是一组固定长度的码组，可表示为（n,k）。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。线性分组码:当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。kn-kn100100118偶校验-40/67-设各字母的使用频度为{E,M,C,A,D}={1,2,3,3,4}。用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，树枝分配代码“0”或“1”分组码形式：EMCAD=>000001010011100共15位3.4.1码的分类(续)非分组码是一组非固定长度的码组，也称树码。例如：哈夫曼编码-41/67-3.4.1码的分类(续)奇异码和非奇异码若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。非奇异码可以将符号唯一的恢复，但是当信源输出符号序列的时候，会遇到麻烦。

例如：C(x1)=0,C(x2)=1,C(x3)=01，01解码出现了歧义。解决的方法是在输出码字之间加入间隔符，这是低效的做法。-42/67-3.4.1码的分类(续)唯一可译码任意有限长的码元序列，只能被唯一地分割成一个个的码字。例如：若C(x1)=00，C(x2)=11，则C(x1x2)=0011即时码和非即时码如果接收端收到一个完整的码字后，能立即译码，不需等下一个码接收后就能判断是否可以译码，这样的码叫做即时码。例如：C(1)=0,C(2)=10,C(3)=110,C(4)=111，则序列01011111010可以立即断句为0,10,111,110,10，从而立即可译-43/67-3.4.2编码的理论知识信源编码器模型分组码单符号信源编码器模型

分组码单符号信源译码器模型-44/67-唯一可译码的条件：可导出唯一可译码存在的充分和必要条件，即各码字的长度Ki应符合Kraft不等式：式中，m是进制数，n是信源符号数。3.4.2编码的理论知识(续)-45/67-3.4.2编码的理论知识(续)例:设二进制码树中X∈｛x1，x2，x3,x4｝，K1=1，K2=2，K3=2，K4=3，应用上述判断定理，可得因此，不存在满足这种Ki的唯一可译码,例：若C(x1)=00，C(x2)=11K1=2,k2=2-46/67-3.4.3几种典型编码方法最佳码定义:

若一个唯一可译码的平均码长小于所有其它唯一可译码，则称该码为最优码。下面重点介绍几种最佳编码:-47/67-3.4.3几种典型编码方法(续)香农编码方法将信源消息符号按其出现的概率大小依次排列p(x1)≥p(x2)≥…≥p(xn)

确定满足下列不等式的整数码长Ki：为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。-48/67-3.4.3几种典型编码方法(续)香农编码方法举例：消息序号si

消息概率p(si)

累加概率Pi

-logp(si)

代码组长度li

二进制代码组

s1

0.2000

0.0000

2.3219

3

000

s2

0.1900

0.2000

2.3959

3

001

s3

0.1800

0.3900

2.4739

3

011

s4

0.1700

0.5700

2.5564

3

100

s5

0.1500

0.7400

2.7370

3

101

s6

0.1000

0.8900

3.3219

4

1110

s7

0.0100

0.9900

6.6439

7

1111110-49/67-3.4.3几种典型编码方法(续)费诺编码过程如下：将信源消息符号按其出现的概率大小依次排列：p(x1)≥p(x2)≥…≥p(xn)。将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。如此重复，直至每个组只剩下一个信源符号为止。信源符号所对应的码字即为费诺码。-50/67-3.4.3几种典型编码方法(续)哈夫曼编码过程如下：将n个信源消息符号按其出现的概率大小依次排列，p(x1)≥p(x2)≥…≥p(xn)取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。对重排后的两个概率最小符号重复步骤(2)的过程。不断继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。-51/67-3.4.3几种典型编码方法(续)举例:哈夫曼编码0.60.3CEDBA0.10.40.30.10.1F0.020.0810.20000111101最后结果:A-0B-10C-1100D-1101E-1110F-1111-52/67-3.4.3几种典型编码方法(续)哈夫曼编码的基本特点构造了一个码树，码树从端点开始构造，直到树根结束，最后得到一个码树，编出的码是即时码。采用概率匹配方法来决定各码字的码长编出的码字并不惟一。优点：可取得较好的冗余压缩效果。可使输出码元概率均匀化。-53/67-3.4.3几种典型编码方法(续)游程编码游程长度：在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(1).对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号r的游程，其长度L(r)就是“r”的游程长度。-54/67-3.4.3几种典型编码方法(续)游程编码游程编码(简写为RLE或RLC)是一种十分简单的压缩方法,它将数据流中连续出现的字符(称为游程)用单一的记号来表示。例如,字符串abaCCCbbaaaa

可以压缩为aba3c2b4a游程编码的压缩效果不太好,但由于简单,编码/解码的速度非常快,因此仍然得到广泛的应用。许多图形和视频文件,如.TIF及.AVI等,都使用了这种压缩。-55/67-课程内容

3.1信源及分类3.2信源的数学模型3.3信息的度量—信息熵3.4无失真信源编码3.5限失真信源编码-56/67-3.5限失真信源编码什么是限失真信源编码限失真信源编码要解决的问题：在允许一定失真程度的条件下，用尽可能少的符号来表达信源的信息，即信源熵所能压缩的极限或者说编码后信源输出的信息率压缩的极限值。它是量化、数模转换、频带压缩和数据压缩的理论基础。无失真的冗余度压缩编码主要是针对离散信源的有失真的熵压缩编码主要是针对连续信源主要方法：矢量量化编码-57/67-3.5限失真信源编码(续)本节介绍以下几种限失真编码3.5.1矢量量化编码3.5.2变换编码3.5.3预测编码-58/67-3.5.1矢量量化编码标量量化：是对每个信源符号单独处理忽略了信源符号的相关性。矢量量化通过将多个符号构成的序列作为一个整体进行量化的方法,可以避免标量量化的固有缺点，这种方法称为矢量量化。矢量量化编码是在图像、语音信号编码技术中研究得较多的新型量化编码方法。-59/67-3.5.1矢量量化编码(续)矢量量化原理：

先将待编码的信源符号序列划分为一个个等长的分组，每个分组含有若干个符号，形成一个矢量。每个矢量与预先生成的矢量码书中的每个码字进行比较，求出相应的失真，然后用失真最小的码字的编号作为量化器的输出就实现了矢量量化。在译码端有一个同样的码书，所以译码工作只是通过接收的码字序号在码书中搜索相应的码字，算法简单，容易实现。-60/67-3.5.1矢量量化编码(续)矢量量化原理图搜索码书查表信道传输矢量下标码书输入矢量输出矢量-61/67-3.5.1矢量量化编码(续)矢量码书的构造(一般了解)目前最流行的算法是由Y.Linde、A.Buzo、R.M.Gray共同提出的LBG算法：采集用于构造码书的训练数据，为了得到性能较好的矢量码书，一般要求训练样本的数量N和码字的个数L满足：N≥20L；构造初始码书，常用的构造方法有随机码书法、白噪声码书法等；按照初始码书对所有的训练样本进行矢量量化，得到分属不同码字的L个样本集合和相应的量化误差；对每个样本集合进行聚类，根据聚类的结果修正初始码字，得到新的码书；判断量化误差是否小于门限值、迭代次数是否超出规定值，若是，则训练结束，否则转第3步继续。-62/67-3.5.