无失真信源编码理论，作为信息论的研究理论基础，一直以来都受到人们的广泛关注。无失真信源编码是一种可逆编码的基础，即是指当信源符号转换成代码后，可从代码无失真到恢复原信源符号。
本文主要介绍了无失真编码的几种常用方法：香农码、费诺码、算术码和哈夫曼码。分别详细阐述了各个编码方法的编码原理、编码过程以及算术码和哈夫曼码的改进优化。并且结合数字网络的快速发展，介绍了无失真信源编码方法及哈夫曼编码的软件仿真，对其对图象压缩的性能进行了分析。文章的最后两章介绍了无失真编码在MP3和数字电视广播中的应用，对未来的发展趋势也进行了阐述。
无失真编码技术也在信息化、网络化、高科技化的特殊时代环境背景下，迎来了发展的机遇与挑战。无失真编码的应用领域越来越广，因而编码方法有待进一步的深入研究。
关键字：无失真；编码方法；图象压缩
Without distortion source coding theory, information theory research as a theoretical basis, have been subject to people's attention. Without distortion source coding is the basis of a reversible coding, refers when the source code into symbols, from the code without distortion to restore the original source symbols.
This paper without distortion of several commonly used method of coding: Shannon code, for Connaught code, and arithmetic code Huffman code. Were elaborated on the various coding method of coding theory, coding process and arithmetic code and Huffman code to improve optimization. And with the rapid development of digital networks, introduced without distortion source coding methods and Huffman coding software simulation, the image compression to the performance analysis. The article's final two chapters on the non-coding distortion in the MP3 and digital television broadcasting of the future trend of development have also carried out on.
Lossless coding technology is information technology, network-based, high-tech environment of the special context of the era, ushered in the development of the opportunities and challenges. Lossless coding applications more widely, thus coding method to be further in-depth study.
Keyword： source Without distortion Coding technology
Image compression
目录
第一章绪论 (1)
1.1无真编码方法的形成背景和发展……………………………………
1.2无失真编码方法的应用领域...................................................第二章无失真信源编码 (2)
2.1 编码定理 (3)
2.2 常用编码方法 (7)
2.2.1 香农编码方法……………………………………………………8.
2.2.2 费诺编码方法 (9)
2.2.3 哈夫曼编码方法 (10)
2.2.4 算术编码方法 (11)
第三章哈夫曼编码和算术编码的改进优化 (12)
3.1 哈夫曼编码算法的分析改进 (14)
3.2 算术编码算法的改进 (13)
第四章哈夫曼编码的软件实现 (15)
4.1仿真软件MATLAB简介
4.2 哈夫曼编解码流程图
4.3 仿真结果分析
第五章无失真编码技术的实际应用 (15)
5.1 在MP3中的音频压缩 (17)
5.2 在数字电视广播中的应用 (16)
第六章无失真编码技术的未来发展趋势..............................总结 (20)
致谢 (21)
参考文献 (22)
附录 (23)
第一章绪论
“信息”这个词相信大家都不陌生，几乎每时每刻都会接触到。不仅在通信，电子行业其他各个领域也都十分重视信息，所谓进入了“信息时代”。信息不是静止的，它会产生也会消亡，人们要获取它，并完成它的传输，交换，处理，检测，识别，存储，显示功能。而在信息传输的过程中，我们就要涉及到信源编码技术的研究。象图象压缩传输，视频和音频的压缩处理等都要用到无失真编码。
通过本章的学习，可以了解以下问题：无失真编码的形成背景和发展趋势；编码技术的具体应用领域。
1.1无失真编码技术的形成背景和发展
信息论理论基础的建立,一般来说开始于香农(C.E.Shanon)研究通信系统时所发表的论文。随着研究是深入与发展，信息论具有了较为宽广的内容。
信息在早些时期的定义是有Nyquest,H 和 Hartley,L.V.R在20世纪20年代提出来的。1924年Nyquest,H解释了信号带宽度量方法；1936年阿姆斯特朗提出了增大带宽可以使抗干扰能力加强。1948年香农公开发表《通信的数学理论》，这是一篇关于现代信息论的开创性权威论文，为信息论的创立作出了独特的贡献。香农因此也成为了信息论的奠基人。
50年代信息论在学术界引起了巨大的反响。1951年美国IRE成立了信息论组，并于1955年正式出版了信息论汇刊。60年代信道编码技术发展到了高峰，找到了大量可纠正多个错误的码，而且提出了可实现的译码方法。其次是卷积码和概率译码有了重大突破，提出了序列译码和ViterbiYI 译码方法。
到了70年代，有关信息论的研究，从点到点间的单用户通信推广到多用户系统的研究。1972年盖弗发表了有关广播信道的研究，以后陆续有关于多人接入信道和广播信道模型的研究，但由于这些问题比较难，到目前为止，多用户信息论研究得不多，还有许多尚待解决的课题。
信息论主要用在通信领域，在含噪信道中传输信息的最优方法到今天还不十分清楚。在这样的特殊时代和背景下，无失真编码方法的研究课题应运而生。
1.2无失真编码技术的应用领域
随着网络技术的不断新起和发展，信息在网络中的传输已经成为人们获取信息的主要来源。而如何正确无误地从一方传递信息给另一方，无失真编码技术体现出了其功能与作用。数字图象压缩就要用到编码技术，还有视频和音频都要用到编码。
另外，电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的；一些商品上的粗细条纹组成的标签中我们可以得知生产厂家的生产日期和价格，都是用到条行码设计出来的，非常方便非常有用。每出版一本书，都给定一个国际标准书号（ISBN），大大方便了图书的销售和编目收藏工作。可以说，人们在日常生活和生产实践中，正在越来越多地使用到无失真编码技术。
第二章 无失真信源编码
由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编 码的主要任务就是减少冗余，提高编码效率。信源编码的基础是信息论中的两个 编码定理：无失真编码定理和限失真编码定理。前者是可逆编码的基础。可逆是 指当信源转换成代码后，可以从代码无失真地恢复原信源符号。无失真编码或可 逆编码只适用于离散信源。信源编码定理出现后，编码方法就趋于合理化。本章 讨论离散信源无失真编码，从无失真编码定理出发，重点讨论以香农码，费诺码， 哈夫曼码和算术码为代表的最佳码。
2.1编码定理 2.1.1编码的定义
将信源消息分成若干组，即符号序列Xi,Xi=(X1,X2…Xl …XL),序列的每个符 号取自符号集A ，X l ∈{a1,a2,…,ai,…an}。而每个符号序列Xi 依照固定的码 表映射成一个码字Yi ，这样的码称为分组码，有时也叫块码。只有分组码才有 对应的码表，而非分组码中则不存在码表。如图2-1所示的信源编码器，如果 信源输出的符号序列长度为1
X={x1,x2, … 源概率空间为
??
?
?
???
?????=??????)()2()
1(21
xn p x p x p xn x x P X 一元信道是常用的一种信道，他的信道基本符号集为{0，1}。若将信源X 通过一个二元信道传输，就必须把信源符号xi 变成符号组成的码字序列，即编码。可用不同的码字符号序列，如表2-1所示。
表2-1 不同的码符号序列
一般情况下，码可分为两类：一类是固定长度的码，码中所有码字长度都相同，如表2-1中的码就是定长码。另一类 是可变码，码中的码字长短不一，如表中码2就变长码。
奇异码和非奇异码：若信源和码字是一一对应的，则该码为非奇异码。反之则为奇异码。如表2-2中的码字是奇异码，码2是非奇异码。
表2-2中的码3是唯一可译码，但码2不是唯一可译码。
一般情况下，可将码作如下分类： 非分组码 奇异码 码
分组码 非唯一可译码
非奇异码 非即时码
唯一可译码 即时码
例2-1-1设二进制码树中X ∈{x1,x2,x3,x4},K1=1,K2=2,K3=2,K4=3,应用上述判断定理，可得
∑=4
12i -Ki =2
－1
+2
－2
+2
－2
+2
－3
=8
9
﹥1 因此，不存在满足这种Ki 的唯一可译码。可以用树码进行检查，由图2-1-3所示，要形成上述码字，必然在中间节点放置码字，如a1a1处，这样就产生了延长码。如码字为{0，10，11，110}。如果将各个长度改成K1=1，K2=2，K3=3，K4=3，则此时
∑=4
12i -Ki =2
－1
+2
－2
+2
－3
+2
－3
=1
这样的码就存在唯一可译码，如{0，10，110，111}。但是必须注意，克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码 的判断。如码字{0，10，010，111}，虽然满足克劳夫特不等式，但它不是唯一可译码。
X=（X 1X 2…L l X X ）, （2-1-1） Xl ∈{a 1,a 2,…,ai,an}
变换成由KL 个符号组成的码序列（有时也叫做码字，以下均用码字来叙述。）
Y=（Y1Y2…Yk …YKL ）, （2-1-2） Yk ∈{b1,b2,…,bj,…bm}。
变换的要求是能够无失真或无差错地从Y 恢复X ，也就是能够正确地进行反变换或译码，同时希望传送Y 时所需要的信息率最小。在无失真的信源编码定理中相应的有定长编码定理和变长编码定理，下面我们分别加以讨论。
2.1.2 定长和变长编码定理
1. 定长编码定理
在定长编码中，K 是定值,且K=KL.我们的目的是寻找最小K 值。要实现无失真的信源编码,不但要求信源符号Xi(i=1,2,…,q)与码字Y i ，（i=1,2,…,q)）是一一对应的，而且还要求由码字组成的码符号序列的逆变换也是唯一的。也就是说，由一个码表编出的任意一串有限长码字符号只能被唯一地反译成所对应的信源符号序列。
定长编码定理：由L 个符号组成的，每个符号的熵为H L （X ）的无记忆平稳信源符号序列X 1X 2…L l X X ,可用K L 个符号Y 1Y 2，…,Y K , …, L
K Y (每个符号
有m 中可能值)进行定长编码。对任意ε﹥0，δ﹥0，只要
L
KL
㏒m ≥H L (X)+ε （2-1-3） 则当L 足够大时，必可使译码差错小于δ；反之，当
L
KL
㏒m ≤L(X)-2ε （2-1-4） 时，译码差错一定是有限值，而当L 足够大时，译码几乎必定成错。
通过上述编码定理，使我们对信源平均符号熵HL （X ）有叫好的理解。当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是
K = L
KL
㏒m （2-1-5）
时，只要K ﹥HL （X ），这种编码器一定可以做到几乎无失真，也就是收端译码差错概率接近于零，条件是所取符号数L 足够大。 将上述定理的条件（2-1-3）式改写成
K L ㏒m ﹥LH L （X ）=H （X ）
上式大于号左边为K L 长码字所能携带的最大信息量，右边为L 长信源符号的信息量。K =H L （X ）时，则为临界状态，可能无失真，也可能有失真。
例如，某信源有8种等概率符号，L=1，信源序列熵达到最大值： H 1（X ）=㏒28
=3比特
即该信源符号肯定可以用3比特的信息率进行无失真的编码。 2. 变长编码定理
在变长编码中，码长K 是变化的，我们可根据信源各个符号的统计特性，如概率大的符号用短码，如例2-2-1可用1或2比特，而对概率小的X 7，X 8用较长的码，这样的大量信源符号编成码后平均每个信院符号所需的输出符号数就可以降低，从而提高编码效率。下面分别给出单个符号（L=1）和符号序列的变长编码定理。
单个符号变长编码定理： 若一离散无记忆信源的符号熵为H （X ） ，每个信源符号用M 进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度K 满足下列不等式
K m X H ≤l o g )(＜m
X H log )
(+1 （2-1-6） 离散平稳无记忆序列变长编码定理：对于平均符号熵为H L （X ）的离散平稳无记忆源，必存在一种无失真编码方法，使平均信息率K 满足不等式 H L （X ）≤K ＜H L （X ）+ε （2-1-7） 其中ε为任意小数。
可从（2-1-6）式推出（2-1-7）式。设用进制码元作变长编码，序列长度为L 个信源符号，则由2-3-1式可以得到平均码字L K 满足下列不等式
m X LH L log )(≤L K ＜m
X LH L log )(+1 已知平均输出信息率为 K =
m L
K L
log 则 H L （X ）≤K ＜ H L （X ）+ L
m
log 当L 足够大时，可使
L
m
log ＜ε，这就得到了（2-1-8）。 用变长编码来达到相当高的编码效率，一般要求的符号长度L 可以比定长
编码小得多。从（2-1-8）式可得编码效率的下界：
L
m X H X H K X H L L L l o g )()
()(+>
=η （2-1-8）
例如用二进制，m=2, m 2log =1,仍用前面的例（2-1-6），H （X ）=2.55比特/符号，如要求 η>90﹪ ，则
428
.01
,9.0155.255
.2≈=
=+
L L
就可以了。编码效率总是小于1的，我们可以用它来衡量各种编码方法的
优劣。另外为了衡量各种编码方法最佳的差距，定义码的剩余度为
K
X H L )
(11-=-=ηγ （2-1-9）
例 2-1-2 设离散的无记忆信源、概率空间为
???
?????=??? ??414321x x
P X 其信源为
81.034
log 434log 41)(22=+=X H 比特/符号
若用二元定长编码（0，1）来构造一个即时码：1,021→→x x 。这时平均码长
K =1二元码符号/信源符号 编码效率为
811.0)
(==
K
X H η 输出的信息率为
R=.0811比特/二元码符号
再对长度为2 的信源序列进行变长编码，其即时码如表2-3所示
这个码字平均长度
16
27
31613163216311692=?+?+?+?=K 二元码符号/信源符号
每个单一符号的平均码长 32
2722==K K 二元码符号/信源符号 其编码效率
961.027
811
.0322=?=
η比特/二元码符号
R 2=0.961比特/二元码符号
可见编码复杂了些，但信息传输率有提高。
用同样的方法可进一步将信源的长度增加，L=3或L=4，对这些信源序列进行X 进行编码，并求出其编码效率为
991.0985
.043==ηη
这时信息传输率分别为
R 3=0.985比特/二元码符号
如果对这一信源采用定长二元编码，要求编码效率达到96﹪时，允许译码错误概率10
≤δ-5
。则根据前面所学，自信息的方差
∑==2
1
2)(log )(i i i p p X σ2
－[H （X ）]
很明显，定长编码需要的信源序列长，使得码表很大，且总存在译码差错；而变长码编码效率达到96 ﹪时，只需L=2。因此用变长码编码时，L 不需要很大就可达到相当高的编码效率，而且可实现无失真编码。
2.2常用编码方法
凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码字集合都可称为最佳码。为次必须将概率大的信息符号编以短码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳码方法主要有：香农（Shannon ）,费诺 (Fano)，哈夫曼(Huffman)编码和算术编码等。下面我们分别介绍这几种编码方法。
2.2.1香农编码方法
香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度K 满足下式
i i i i x I K x I ?+<≤,1)()(
就可以得到这种码。这种编码称为香农编码。
香农编码法多余度稍大，实用性不大，但有重要的理论意义。编码方法如下：
(1) 将信源消息符号按其出现的概率大小依次排列 p(x 1) ≥p(x 2) ≥…≥p(x n) (2) 确定满足下列不等式的整数码长Ki:
－㏒2p(xi) ≤Ki ＜－㏒2p(xi)+1
(3) 为了编成唯一可译码，计算第i 个消息的累加概率
∑-==1
1)(i k k i x p P
(4) 将累加概率i P 变换成二进制数。
(5) 取i P 二进数的小数点后Ki 位即为该消息符号的二进制码字。
从上面可看出，香农编码按照概率从大到小排序，进行类加取对数实现。
2.2.2费诺编码方法
费诺编码属于概率匹配编码，但他不是最佳的编码方法。编码过程如下： (1) 将信源消息符号按其出现的概率大小依次排列：
p(x 1) ≥p(x 2) ≥…≥p(x n)。
(2) 将依次排列的信源符号按概率值分两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。
(3) 将每一大组的信源符号进一步再分成两组，使划分的两组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。 (4) 如此重复，直至每个组只剩下一个信源符号为止。 (5) 信源符号所对应的码字即为费诺码。
下面再以上面的例子来求费诺码。编码过程参见表2-5。该费诺码的平均码长
∑===7
174.2)(i i i K x p K 码元/符号
信息传输速率
74.261
.2)(==
K
X H R =0.953比特/码元 显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率
高。
2.2.3 哈夫曼编码方法
(1) 将信源消息符号按其出现的概率大小依次排列：
P(x1) ≥p(x2) ≥…≥p(xn)
(2)取两个小概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进制符号的字母重新排队。 (3)对重新排后的两个概率最小符号重复步骤(2)的过程。 (4)不断继续上述过程,直到最后两个符号配以0和1为止。
(5)从最后一级开始,向前返回得到各个信源符号所对应的8元符序列,即相应的码字。我们还是用上面的例子中的信源, 哈夫曼编码过程如表2-6所示。
表 2-6 哈夫曼编码过程
该哈夫曼编码的平均码长为
∑==
7
1
)(i i
i
K x p K =2.72 码元/符号
信息传输速率
72.261
.2)(==
K
X H R =0.9596 比特/码元 由此可见, 哈夫曼码的平均码长最小，消息传输速率最大,编码效率最高。
哈夫曼编码方法得到的码并非是唯一的。 造成非唯一的原因如下：
（1） 每次对信源缩减时,赋予信源最后两个概率小的符号，用0和1是可以任
意的,所以可以得到不同的哈夫曼码,但不会影响码字的长度。
（2） 对信源进行缩减时, 两个概率小的符号合并后的概率与其他信源符号的
概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。 下面举例来说明。
例 2-2-1 设有离散无记忆信源
???
?
??=???? ??1.01.02.02.04.054321x x x x x P X
可有两种哈夫曼编码方法，如表 （2-7）和表（2-8）所示，码树见图（2-2）
(a) 和 (b) 所示。
（a ）
(b)
图2-2 哈夫曼树
由表（2-2-4）和表（2-2-5）给出哈夫曼码的平均码长相等： ∑===5
12.2)(i i i K x p K 码元/符号
编码效率也相等：
965.0)
(==
K
X H η 但是两种码的质量不完全相同,可用码方差来表示：
ζ
2l
=E[(ki-K )2
]=
∑=5
1
)(i xi p (k i －K )2
表（2-2-4）中哈夫曼码的方差为1l σ2
=1.36；表（2-2-5）中哈夫曼码的方差为2l σ2
=0.16。
因此可见，第二种哈夫曼编码方法得到的码方差比第一种哈夫曼编码方法得到的码方差小许多。故第二种哈夫曼码的质量比较好。
下面看下哈夫曼编码的具体编码过程：
若执行自定义编译，请输入Y继续。否则程序将结束。请输入哈夫曼编码测试数据，注意小写，空格由大写字母T代替，并且字符数小于27。如下输入aTbTcTb
设T 秒内有N 个信源符号输出，信源输出符号速率S=N/T ，若符号的平均码长为K ，则信道传输速率
R=S K （2-2-1） 时可以满足条件。
N 个码字的长度分别为Ki,i=1,2…,N,即在此期间输入存储器∑i
i K 比特，输
出至信道RT 比特，则在存储器内还剩下X 比特，
RT K X N
i i -=∑=1 （2-2-2）
已知K i 是随机变量，其均值和方差分别为
∑===m
j j j i K p K E K 1][ （2-2-3）
变长编码可以无失真地译码，这是理想的情况。如果这种变长码由信道传送时，有某一个符号错了。因为一个码字前面有某个字母错了，就可能误认为是另一个码字而点断，结果后面一系列的码字也会译错，这常称为差错的扩散。当然也可以采用某些措施，使错了一段以后，能恢复正常的码字分离和译码，这一般要求在传输过程中差错很少，或加纠错用的监督码位，但是这样一来又增加信息率。
前面介绍的几种最佳编码都能实现，因为它们具体规定了编码的方法，能使无失真编码的效率非常接近于1。其他如定长编码以及以后将要讨论的限失真信源编码和信道编码，都还没有具体的实用编法，只是证明了存在性和大致方法。所以在压缩信源信息率的实用设备中，哈夫曼编码还是比较常用的。
2.2.4 算术编码方法
以上所讨论的无损编码，都是建立在符号和码字相对应的基础上的，这种编码通常称为块码或分组码。此时符号应是多元的，而且不考虑符号相关性。
为了克服这种局限性，就需要跳出分组码的范畴，研究非分组码的编码方法，算术码为其中之一。算术编码的基本思路是：从全序列出发，将各个信源的概率映射到[0，1]区间上，使每个序列对应这区间的一点，也就是一个二进制的小数。这些点把[0，1]区间分成许多小段，每个小段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率的编码目的。 如果信源符号集为A={a 0,a 1,…,a m-1},信源序列X=(x 0,x 1,…,x l ,…,x L-1),x l ∈A,共有m L 种可能序列。由于考虑是全序列，也许是整页纸上的信息作为一个序列，因而序列长度L 很大。实用中很难得到对眼序列的概率，只能从已知的信源
符号概率P={p(a 0),p(a 1),…,p(a m-1)}={p 0,p 1,…,p r ,…,p m-1}中递推得到。定义各符号的累积概率为
∑-==1
0r P r i i p （2-2-4）
显然，由上式可得P 0=0，P 1= p 0，P 2=p 0+ p 1等，而且
pr =P r+1—Pr （2-2-5）
由于P r+1和Pr 都是小于1的正数，可用[0，1]区间内的两个点来表示，则Pr 就是这两点间的小区间的长度，如图2-3所示。
图2-3信源符号概率和累积概率
不同的符号有不同的小区间，它们互不重叠，所以可将这种小区间内的任何一点作为该符号的代码。以后将计算这代码所需的长度，使之能与其概率匹配。
实用中，采用积累概率P （S ）表示码字C （S ），符号概率p(S)表示状态区间A （S ），则有
C （Sr ）= C （S ）+ A （S ）Pr A （Sr ）= A （S ）pr （2-2-9）
对于二进制符号组成的序列，r =0，1。
实际编码过程是这样的：先置两个存储器C 和A ，起始时可令 A （φ）=1，C=（φ）=0
其中φ代表空集。每输入一个信源符号，存储器C 和A 就按照（2-2-9） 式进行更新一次 ，直至程序结束，就可将存储器C 的内容作为码字输出。由于A （S ）是递增的，而这增量随着序列的增长而减小，因为这增量是序列的概率与信源符号的积累概率的乘积；所以C 的前面就位一般已固定，在以后计算中不会被更新，因而可以输出。只需保留后面几位用做更新。
译码也可逐位进行，与编码过程相似。
例 2-4-1 有简单的四个符号a,b,c,d 构成序列S=abda,各个符号及其对应概率如表2-4-1，算术编码过程如下：
设起始状态为空序列 ?，则A （?）=1，C （?） =0。
表 2-9各符号及其对元概率
译码可通过对上述编码后的数值大小来比较进行，即判断码字C（S）落在哪个区间就可以得出一个相应的符号序列。根据递推公式的相反过程译出符号。具体译码顺序是后编的先译，故称为LIFO算术码，步骤如下：
C（abda）=0.010111<0.1∈[0,0.1) 第一个符号为a；放大至[0，1)(×Pa-1)：C（abda）×21=0.10111∈[0.1,0.110)第二个符号为b；去掉累积概率Pb： 0.10111-0.1=0.00111
放大至[0，1)(×Pb-1)：0.00111×22=0.111∈[0.111，1）第三个符号为d；去掉累积概率Pd： 0.111-0.111=0
放大至[0，1)(×Pd-1)：0 ×24=0∈[0,0.1) 第四个符号为a。
算术编码从性能上看具有许多优点，特别是由于所需的参数很少，不象哈夫曼那样需要一个很大的码表，常设计成自适应算术编码来针对一些信源概率未知或非平稳情况。但是在实际实现时还有一些问题，如计算复杂性，计算的精度以及存储量等，随着这些问题的解决，算术编码正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。这就是我们下有章要介绍到的算术编码的改进。
青岛农业大学 本科生课程论文 论文题目联合信源信道编码的原理及其在通信中的应用学生专业班级信息与计算科学09级1班 学生姓名（学号）董晨晨（20093991） 指导教师吴慧 完成时间 2012年6月27日 2012 年 6 月 27 日
课程论文任务书 学生姓名董晨晨指导教师吴慧 论文题目联合信源信道编码的原理及其在通信中的应用 论文内容（需明确列出研究的问题）：由于通信的根本目的是将消息有效而可靠地从信源传到信宿，信源编码的目的在于提高系统的有效性，信道编码理论核心是提高系统的可靠性，因此在编码时应在一定的传信率条件下，通过有规律的增加冗余度保证信息以尽可能小的差错概率从信源传到信宿，并且充分利用系统资源。基于这种情况下，提出了信源信道联合编码，可以跟随信道的变化充分利用通信系统的资源，达到最好的端对端的通信效果。本文主要研究了以下几个方面的问题：（1）信源信道联合编码的原理；（2）信源信道联合编码的研究方向；（3）信源信道联合编码的关键技术；（4）联合编码在通信系统方面的应用。 资料、数据、技术水平等方面的要求：通过书籍报刊杂志、网络等各种渠道广泛搜集资料，充分利用现有文献，借鉴他人的学术成果，做到了资料翔实，数据准确，引用规范，论证充分。论文符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。文字流畅、语言准确、要点清楚，有独立的观点和见解。内容理论联系实际，计算数据准确，涉及到他人的观点、统计数据或计算公式标明出处，结论写的概括简短。 发出任务书日期2012.6.20完成论文日期2012.6.27 教研室意见（签字） 院长意见（签字）
课程论文成绩评定表
信源编码的基本原理及其应用 课程名称通信原理Ⅱ 专业通信工程 班级******* 学号****** 学生姓名***** 论文成绩 指导教师***** ******
信源编码的基本原理及其应用 信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文《通信的数学理论》所定义的，它为信息论奠定了理论基础。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。 信息通过信道传输到信宿的过程即为通信，通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信，需要解决两个问题：一是不失真或允许一定的失真条件下，如何提高信息传输速度（如何用尽可能少的符号来传送信源信息）；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大（如何尽可能地提高信息传输的可靠性）。这样就对信源的编码有了要求，如何通过对信源的编码来实现呢？ 通常对于一个数字通信系统而言，信源编码位于从信源到信宿的整个传输链路中的第一个环节，其基本目地就是压缩信源产生的冗余信息，降低传递这些不必要的信息的开销，从而提高整个传输链路的有效性。在这个过程中，对冗余信息的界定和处理是信源编码的核心问题，那么首先需要对这些冗余信息的来源进行分析，接下来才能够根据这些冗余信息的不同特点设计和采取相应的压缩处理技术进行高效的信源编码。简言之，信息的冗余来自两个主要的方面：首先是信源的相关性和记忆性。这类降低信源相关性和记忆性编码的典型例子有预测编码、变换编码等；其次是信宿对信源失真具有一定的容忍程度。这类编码的直接应用有很大一部分是在对模拟信源的量化上，或连续信源的限失真编码。可以把信源编码看成是在有效性和传递性的信息完整性（质量）之间的一种折中有段。 信源编码的基本原理： 信息论的创始人香农将信源输出的平均信息量定义为单消息（符号）离散信源的信息熵： 香农称信源输出的一个符号所含的平均信息量为 为信源的信息熵。 通信原理中对信源研究的内容包括3个方面： (1)信源的建模 信源输出信号的数学描述已有成熟的理论——随机过程，一般的随机过程理∑=-=L i i i x p x p x H 12) (log )()()(x H
数字通信中的信源编码和信道编码 摘要：如今社会已经步入信息时代，在各种信息技术中，信息的传输及通信起着支撑作用。而对于信息的传输，数字通信已经成为重要的手段。本论文根据当今现代通信技术的发展，对信源编码和信道编码进行了概述性的介绍. 关键词：数字通信；通信系统；信源编码；信道编码 Abstract：Now it is an information society. In the all of information technologies, transmission and communication of information take an important effect. For the transmission of information, Digital communication has been an important means. In this thesis we will present an overview of source coding and channel coding depending on the development of today’s communica tion technologies. Key Words：digital communication; communication system; source coding; channel coding 1.前言 通常所谓的“编码”包括信源编码和信道编码。编码是数字通信的必要手段。使用数字信号进行传输有许多优点, 如不易受噪声干扰, 容易进行各种复杂处理, 便于存贮, 易集成化等。编码的目的就是为了优化通信系统。一般通信系统的性能指标主要是有效性和可靠性。所谓优化，就是使这些指标达到最佳。除了经济性外，这些指标正是信息论研究的对象。按照不同的编码目的，编码可主要分为信源编码和信道编码。在本文中对此做一个简单的介绍。 2.数字通信系统 通信的任务是由一整套技术设备和传输媒介所构成的总体——通信系统来完成的。电子通信根据信道上传输信号的种类可分为模拟通信和数字通信。最简单的数字通信系统模型由信源、信道和信宿三个基本部分组成。实际的数字通信系统模型要比简单的数字通信系统模型复杂得多。数字通信系统设备多种多样，综合各种数字通信系统，其构成如图2-l所示。 图2-1 数字通信系统模型 信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。 信道，通俗地说是指以传输媒质为基础的信号通路。具体地说，信道是指由有线或无线电线路提供的信号通路。信道的作用是传输信号，它提供一段频带让信号通过，同时又给信号加以限制和损害。 信道编码是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率或带宽。与信源编码正好相反。在计算机科学领域，信道编
Joint Source-Channel Decoding of Huffman Codes with LDPC Codes Zhonghui Mei and Lenan Wu Abstract In this paper, we present a joint source-channel decoding algorithm (JSCD) for LDPC codes by exploiting the redundancy of the Huffman coded sources.When the number of Huffman codes increases, just a moderate complexity is added for our algorithm by increasing the size of the lookup table, which is used to estimate the information bit probability based on the source redundancy. Key words － LDPC, Variable length codes (VLC), Huffman code, sum-product algorithm (SPA), joint source-channel decoding (JSCD) I. INTRODUCTION Recently in [1]-[4] several joint source-channel decoding algorithms for variable length codes (VLC) have been proposed. All of these algorithms consider the overall sequence of variable length codeword to exploit the source redundancy. The drawback is that the symbols have to be synchronized in order to limit error propagating. Furthermore, when the number of VLC increases, the decoding complexity of these algorithms explodes. In this paper we present a JSCD algorithm for LDPC codes in combination with Huffman coded sources. The error correcting property of our JSCD algorithm mainly depends on channel codes rather than source redundancy. In order to exploit the source redundancy, we estimate the information bit probability with just some corresponding bits before it, which simplifies the decoding algorithm significantly. The rest of the paper is organized as follows. Section II presents the Huffman coded source model. The JSCD algorithm for LDPC codes is described in section III. Section IV provides the simulation results. Section V concludes this paper. II. HUFFNAN CODED SOURCE MODEL Let denotes a sequence of information bits coded by VLC (e.g. a Huffman code). In [1], [3] and [4], they consider the overall sequence and express the source redundancy with . In order to compute , [3] and [4] design a trellis to illustrate statistics of the source sequence. When the number of the trellis states increases, the computational complexity of will rise explosively. ],......,,,[321n s s s s S =),......,,,()(21n s s s s p S p =)(S p )(S p In this paper, we make use of the source redundancy with , as is illustrated in Fig.1 and table 1. k is chose to be larger than the maximum length of Huffman codes. When the number of VLC increases, we only need to expand the lookup table. In addition, for we just estimate one bit probability with a small part bit of the information sequence every time, the error propagation phenomenon has been avoided successfully. ]),......,,[|(11?+??i k i k i i s s s s p
第八章 限失真信源编码 8.1设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d (αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明: ∑==r i j i j i b a d a p D 1 min )},(min ){( 并写出取得min D 的试验信道的传输概率选取的原则,其中 ))}/(,),/(),/({min ),(min 21i S i i j j i j a b p a b p a b p b a d = (证明详见:p468-p470) 8.2设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d(αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明: }),()({min 1 max ∑==r i j i i j b a d a p D 并写出取得max D 的试验信道传递概率的选取原则. (证明详见:p477-p478) 8.5设二元信源X 的信源空间为: -1 )( 1 0X :][X ????ωωX P P 令ω≤1/2,设信道输出符号集Y:{0,1},并选定汉明失真度.试求: (1) D min ,R(D min ); (2) D max ,R(D max ); (3) 信源X 在汉明失真度下的信息率失真函数R(D),并画出R(D)的曲线; (4) 计算R(1/8). 解： {}{}{}{}0 )()(0);()1()}0();1({min )1,1()1()1,0()0(;)0,1()1()0,0()0(min ),()(min )2() ()()/()(min );(min )0()(0 )/(),2,1(1)/(0)/(100110][1 0 00 0)1(0)0(),(min )()1(max 21min max min min 2 1 min ==∴====++=? ?? ???=' ===-===∴====?? ?? ??===?+?==∑∑==ωω ωR D R Y X I p p p d p d p d p d p b a d a p D D H X H Y X H X H Y X I R D R Y X H i a b p a b p P D D p p b a d a p D j j i j i i j i j i j i j i j i 此时故此时或的信道矩阵 则满足保真度＝最小允许失真度：
信源编码与信道编码解析 摘要：衡量一个通信系统性能优劣的基本因素是有效性和可靠性，有效性是指信道传输信息的速度快慢，可靠性是指信道传输信息的准确程度。在数字通信系统中，信源编码是为了提高有效性，信道编码是为了提高可靠性，而在一个通信系统中，有效性和可靠性是互相矛盾的，也是可以互换的。我们可以用降低有效性的办法提高可靠性，也可以用用降低可靠性的办法提高有效性。本文对信源编码和信道编码的概念，作用，编码方式和类型进行了解析,以便于更好的理解数字通信系统的各个环节。 关键字：信源编码信道编码 Abstract: the measure of a communication system the basic factor is quality performance efficiency and reliability, effectiveness refers to channel to transfer information machine speed, reliability is to point to the accuracy of the information transmission channel. In digital communication system, the source coding is in order to improve the effectiveness, channel coding is in order to improve the reliability, and in a communication system, effectiveness and reliability is contradictory, is also can be interchanged. We can use to reduce the availability of improving the reliability, also can use to improve the effectiveness of reduces reliability. In this paper, the source coding and channel coding concept, function, coding mode and the types of analysis, in order to better understand all aspects of digital communication systems. Key words: the source coding channel coding 中图分类号：TN911.21 文献标识码：A 文章编号： 1引言 数字通信系统： 信源是把消息转化成电信号的设备，例如话筒、键盘、磁带等。 信源编码的基本部分是压缩编码。它用于减小数字信号的冗余度，提高数字信号的有效性，如果是模拟信源，则它还包括数模转换功能，在某些系统中，信源编码还包括加密功能。
目录 1 课程设计目的 (1) 2 课程设计正文 (1) 2.1 调制原理 (1) 2.2 解调原理 (3) 2.3 程序分析 (3) 3 课程设计总结 (9) 4 参考文献 (9)
1 课程设计目的 通过我们对这次CDIO 二级项目的学习和理解，综合运用课本中所学到的理论知识完成一个以香农编码为信源编码、（7,4）循环码为信道编码的2FSK 信号调制解调的课程设计。以及锻炼我们查阅资料、方案比较、团结合作的能力。学会了运用MA TLAB 编程来实现2FSK 调制解调过程，并且输出其调制及解调过程中的波形，并且讨论了其调制和解调效果，增强了我们的动手能力，为以后学习和工作打下了基础。 2 课程设计正文 本次课程设计我们所做的课题是一个以香农编码为信源编码、（7,4）循环码为信道编码的2FSK 信号调制解调的CDIO 项目，这就要求我们需要完成信源编码、信道编码、信号的调制解调以及误码率分析等问题。 图1 数字通信系统模型 数字信号的传输方式分为基带传输和带通传输，在实际应用中，大多数信道具有带通特性而不能直接传输基带信号。为了使数字信号在带通信道中传输，必须使用数字基带信号对载波进行调制，以使信号与信道的特性相匹配。这种用数字基带信号控制载波，把数字基带信号变换为数字带通信号的过程称为数字调制。 2.1 调制原理 用基带信号)(t f 对高频载波的瞬时频率进行控制的调制方式叫做调频，在数字调制系统中则称为频移键控(FSK)。频移键控在数字通信中是使用较早的一种调制方式，这种方式实现起来比较容易，抗干扰和抗衰落的性能也较强。其缺点是占用频带较宽，频带利用串不够高，因此，额移键控主要应用于低、中速数据的传输，以及衰落信道与频带较宽
《信息论与信源编码》实验报告 1、实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2、实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图象若干幅） 3、实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像 3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4、实验结果及分析 (1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下： a.图像1.bmp：
第3章无失真信源编码 教学内容包括：信源编码概述、定长编码、变长编码常用的信源编码 3．1信源编码概述 讲课内容： 1、信源编码及分类 2、信源编码定义 3、信源编码基础 1、给出编码译码示意图 2、编码：信源编码、信道编码。 信源 = 信息 + 冗余 信源编码：针对信源的编码，能更加有效地传输、存储信息。编码后尽可能减少所需信息的损失，提高编码后携带信息的效率。 3、信源编码的主要任务 a、减少冗余 b、提高编码效率 4、信源编码的基本途径 a、解除相关性
b 、概率均匀化 4、信源编码的两个基本定理 a 、无失真编码定理（可逆编码的基础、只适用于离散信源） b 、限失真编码定理（连续信源） 5、信源编码的分类 a 、冗余度压缩编码，可逆压缩，经编译码后可以无失真地恢复。 统计特性：Huffman 编码，算术编码Arithmetic Coding b 、熵压缩编码，不可逆压缩 压缩超过一定限度，必然带来失真 允许的失真越大，压缩的比例越大 译码时能按一定的失真容许度恢复，保留尽可能多的信息 本章讨论离散信源无失真编码，包括定长、变长无失真编码定理和编码方法，以及几种实用的无失真信源编码，如香农编码、费诺编码、哈夫曼编码等。 6、信源编码的定义 首先给出信源编码的定义， 信源编码就是从信源符号到码符号的一种映射f ，它把信源输出的符号u i 变换成码元序列w i 。 f ：u i ——>w i ，i =1，2，…，q 译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应的、可逆的。 给出马元、码字、马块、二元编码的概念
结合P34例3.1.1给出编码的分类如下： 给出平均码长的定义和公式。 结合P34例3.1.1进行二进制信源的简单编码，并计算平均码长。 3．2克拉夫特（Kraft）不等式 讲课内容： 1、变长码的码字分离技术 2、即时码的引入和码树表示方法 3、即时码与克拉夫特不等式 1、变长码的码字分离技术 a、同步信号 b、可分离码字 2、即时码和码树表示法 即时码是一种实时的惟一可译码，这类码无需另加同步信息，就能在接收端被分离出来。在信源编码和数据压缩中，这类编码无论在理论还是在实际中都有很大意义，对较简单的信源，可以很方便地用码树法直接且直观地构造出可以分离码（异前缀码）。
WCDMA技术的信源编码和信道编码 WCDMA网络是全球商用时间最长，技术成熟、可演进性最好的，全球第一个3G商用网络就是采用WCDMA制式。我国采用了全球广泛应用的WCDMA 3G技术，目前已全面支持HSDPA/HSUPA，网络下载理论最高速率达到14.4Mbps。2G无线宽带的最高下载速度约为150Kbps，我国的WCDMA网络速度几乎是2G网络速度的100倍。支持业务最广泛，基于WCDMA成熟的网络和业务支撑平台，其所能实现的3G业务非常丰富。无线上网卡、手机上网、手机音乐、手机电视、手机搜索、可视电话、即时通讯、手机邮箱、手机报等业务应用可为用户的工作、生活带来更多的便利和美妙享受。终端种类最多，截至2008年底，支持WCDMA商用终端的款式数量超过2000款，全球主要手机厂商都推出了为数众多的WCDMA手机。国内覆盖广泛，截至2009年9月28日，联通3G网络已成功在中国大陆285个地市完成覆盖并正式商用，新覆盖的城镇数量还在不断增长中，联通3G网络和业务已经覆盖了中国绝大部分的人口和地域。开通国家最广，可漫游的国家和地区最多，截至2008年底，全球已有115个国家开通了264个WCDMA网络，占全球3G商用网络的71.3%。截至2009年9月28日，中国联通已与全球215个国家的395个运营商开通了。 WCDMA的优势明显，技术成熟，在WCDMA物理层来看，信源编码和信道编码是WCDMA技术的基础，信源编码是采用语音编码技术，AMR语音编码技术是由基于变速率多模式语音编码技术发展而来，主要原理在于：语音编码器模型由一系列能提供多种编码输出速率与合成质量的声码器构成AMR支持八种速率。鉴于不同信源比特对合成语音质量的影响不同AMR 语音编码器输出的话音比特在传输之前需要按照它们的主观重要性来排序分类，分别采用不同保护程度的信道编码对其进行编码保护。 信源编码AMR模式自适应选择编码器模式以更加智能的方式解决信源和信道编码的速率匹配问题，使得无线资源的配置和利用更加灵活和高效。实际的语音编码速率取决于信道条件，它是信道质量的函数。而这部分工作是解码器根据信道质量的测量参数协助基站来完成，选择编码模式，决定编码速率。原则上在信道质量差时采用低速率编码器，就能分配给信道编码更多的比特冗余位来实现纠错，实现更可靠的差错控制。在信道质量好、误比特率较低时采用高速率编码器，能够提高语音质量。在自适应过程中，基站是主要部分，决定上下行链路采用的速率模式。 信源编码AMR编码器原理，WCDMA系统的AMR声码器共有八种编码模式，它们的输出比特速率不同。为了降低成本和复杂度，八种模式都采用代数码本激励线性预测技术，它们编码的语音特征参量和参量提取方法相同，不同的是参量的量化码本和量化比特数。AMR语音编码器根据实现功能大致可分为LPC分析、基音搜索、代数码本搜索三大部分。其中LPC分析完成的主要功能是获得10阶LPC滤波器的-.个系数，并将它们转化为线谱对参数，并对LSF进行量化；基音搜索包括了开环基音分析和闭环基音分析两部分，以获得基音延迟和基音增益这两个参数；代数码本搜索则是为了获得代数码本索引和代数码本增益，还包括了码本增益的量化。
7.1 设输入符号集为}1 ,0{=X ，输出符号集为}1 ,0{=Y 。定义失真函数为 1 )0,1()1,0(0)1,1()0,0(====d d d d 试求失真矩阵D 。 解： 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 7.2 设输入符号集与输出符号集为}3 ,2 ,1 ,0{==Y X ，且输入信源的分布为 )3 ,2 ,1 ,0( 4 1 )(===i i X p 设失真矩阵为 []????? ???? ???=01 11 101111011110d 求D max 和D min 及R(D)。 解： 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数： ?? ? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )( 其中a = 1, n = 4, 所以率失真函数为： ()()D D D D D R --++=1ln 13 ln 4ln )( 7.3 利用R(D)的性质，画出一般R(D)的曲线并说明其物理含义？试问为什么R(D)是非负且非增的？ 解： 函数曲线：
信源编码和信源解码 字、符号、图形、图像、音频、视频、动画等各种数据本身的编码通常称为信源编码，信源编码标准是信息领域的基础性标准。无论是数字电视、激光视盘机，还是多媒体通信和各种视听消费电子产品，都需要音视频信源编码这个基础性标准。 大家用电脑打字一定很熟悉，当你用WORD编辑软件把文章（DOC文件）写完，存好盘后，再用PCTOOLS工具软件把你的DOC文件打开，你一定能看到你想象不到的东西，内容全是一些16进制的数字，这些数字叫代码，它与文章中的字符一一对应。现在我们换一种方法，用小画板软件来写同样内容的文章。你又会发现，用小画板软件写出来的BMP文件，占的内存（文件容量）是DOC文件的好几十倍，你知道这是为什么？原来WORD编辑软件使用的是字库和代码技术，而小画板软件使用的是点阵技术，即文字是由一些与坐标位置决定的点来组成，没有使用字库，因此，两者在工作效率上相差几十倍。[信源]->[信源编码]->[信道编码]->[信道传输+噪声]->[信道解码]->[信源解码]->[信宿] 目前模拟信号电视机图像信号处理技术就很类似小画板软件使用的点阵技术，而全数字电视机的图像信号处理技术就很类似WORD编辑软件使用的字库和代码技术。实际上这种代码传输技术在图文电视中很早就已用过，在图文电视机中一般都安装有一个带有图文字库的译码器，对方发送图文信号的时候只需发送图文代码信息，这样可以大大地提高数据传输效率。 对于电视机，显示内容是活动图像信息，它哪来的“字库”或“图库”呢？这个就是电视图像特有的“相关性”技术问题。原来在电视图像信号中，90%以上的图像信息是互相相关的，我们在模拟电视机中使用的Y/C（亮度信号/彩色信号）分离技术，就是利用两行图像信号的相关性，来进行Y/C分离。如果它们之间内容不相关，Y/C信号则无法进行分离。全数字信号电视也一样，如果图像内容不相关，则图像信号压缩也就要免谈。如果图像内容有相关性，那么上一幅图像的内容就相当于下一幅图像的“图形库”，或一幅图像中的某部分就是另一部分的“图形库”，因此，下一幅图像或图像中某一个与另一个相关的部分，在发送信号时，只需发送一个“代码”，而传送一个“代码”要比送一个“图形库”效率高很多，显示时也只需把内容从“图形库”中取出即可，这就是MPEG图像压缩的原理。 利用电视信号的相关性，可以进行图像信号压缩，这个原理大家已经明白，但要找出图像相关性的内容来，那就不是一件很容易的事情，这个技术真的是太复杂了。为了容易理解电视图像的相关性，我们不妨设想做一些试验，把图像平均分成几大块，然后每一块，每一块的进行比较，如果有相同的，我们就定义它们有相关性；如果没有相同的，我们继续细分下去，把每大块又分成几小块，一直比较下去，最后会发现，块分得越细，相同块的数目就越多，但分得太细需要的代码也增多，所以并不是分得越细越好。我们在看VCD的时候经常发现，如果VCD读光盘数据出错，就会在图像中看到“马赛克”，这些“马赛克”就是图像分区时的最小单位，或把数码相片进行放大，也可以看到类似“马赛克”的小区，这就是数码图像的最小“图形库”，每个小“图形库”都要对应一个“代码”。 在单幅图像中找出相关性的几率并不是很大的，所以对单幅图像的压缩率并不很大，这个通过观察数码相片的容量就很容易明白，如果把寻找相关性的范围扩大到两幅图像，你就会发现，具有相关性的内容太多了，这是因为运动物体对于人的眼睛感觉器官来说，是很慢
第五章无失真信源编码定理与编码 5．1．1 信源编码和码的类型 1．信源编码 2．码的类型 若码符号集中符号数r=2称为二元码，r=3称为三元码，……，r元码。 若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。 若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。 若每个码符号x i∈X的传输时间都相同则称为同价码，否则称为非同价码。 若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。 若分组码中，没有任何完整的码字是其他码字的前缀，则称为即时码(又称非延长码或前缀条件码)，否则称为延长码。 本章主要研究的是同价唯一可译码。 5．1．2 即时码及其树图构造法 即时码(非延长码或前缀条件码)是唯一可译码的一类子码。 即时码可用树图法来构造。构造的要点是： (1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头
为节点。 (2)从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。 (3)每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。 即时码可用树图法来进行编码和译码。 从树图可知，即时码可以即时进行译码。 当码字长度给定，即时码不是唯一的。 可以认为等长唯一可译码是即时码的一类子码。 5．1．3 唯一可译码存在的充要条件 (1)对含有q个信源符号的信源用含r个符号的码符号集进行编码，各码字的码长为l1，l2，…，l q的唯一可译码存在的充要条件是，满足Kraft不等式 5．1．4 唯一可译码的判断法 唯一可译码的判断步骤： 首先，观察是否是非奇异码。若是奇异码则一定不是唯一可译码。 其次，计算是否满足Kraft不等式。若不满足一定不是唯一可译码。 再次，将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。 或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾
第6章 限失真信源编码 一、例题： 【例6.1】 二元对称信源，信源{0,1}U =，接收变量{0,1}V =，在汉明失真定义下，失真函数为： (0,0)(1,1)0d d ==，(0,1)(1,0)1d d == 其失真矩阵为 011 0??=? ??? D 容易看出：对于离散对称信源，其汉明失真矩阵D 为一个方阵，且对角线上的元素为零，即： 011110111 1011 1 1 0?? ??????=???????? D 【例6.2】 信源U ＝{0,1,2}，接收变量V ＝{0,1,2},失真函数为2 (,)()i j i j d u v u v =-，求失真矩阵。由失真定义得： d (0,0)＝d (1,1)＝d (2,2)＝0 d (0,1)＝d (1,0)＝d (1,2)＝d (2,1)＝1 d (0,2)＝d (2,0)＝4 所以失真矩阵D 为 141 014 1 4?? ??=?????? D 【例 6.3】 离散无记忆信源输出二维随机序列12()U U =U ，其中(1,2)i U i =取自符号集 {0,1}，通过信道传输到信宿，接收N 维随机序列12()V V =V ，其中(1,2)i V i =取自符号集
{0,1}，定义失真函数 (0,0)(1,1)0(0,1)(1,0)1 d d d d ==== 求符号序列的失真矩阵。 解： 由N 维信源序列的失真函数的定义得 1 1(,)(,)(,) ,k k N N N i j i j k d d d u v N αβ=== ∈∈∑u v u U v V 所以 [][]1(00,00)(0,0)(0,0)0211(00,01)(0,0)(0,1)2 2 N N d d d d d d =+== += 类似计算其他元素值，得到信源序列的失真矩阵为 11012211012211102211102 2 N ??????????=? ?????????? ? D 【例6.4】 设信源符号有8种，而且等概率，即1()8 i P u = 。失真函数定义为 0(,)1i j i j d u v i j =?=?≠? 假如允许失真度12 D =，即只要求收到的符号平均有一半是正确的。我们可以设想这 样的方案： 方案一：对于1234,,,u u u u 这四个信源符号照原样发送，而对于5678,,,u u u u 都以4u 发送。如图6.1(a )所示。 方案二：对于1234,,,u u u u 这四个符号照原样发送，而对于5678,,,u u u u 分别以 1234,,,u u u u 发送。如图6.1(b )所示。
信源编码技术 为什么要进行信源编码 通信系统就是将产生的信息传输到目的地。信源有各种不同的形式，
如广播的信源是语音或音乐，电视的信源是活动图像，这些信源的输 出都是模拟信号，称为模拟信源。计算机和存储器件（磁盘或光盘） 输出的是离散信号，称为数字信源。在数字系统中传输的都是数字信 息，不论是模拟信源还是离散信源其输出都必须转化为可以传输的数 字信息，这种转化通常是由信源编码器来完成的。 信源编码在移动通信中也称语音编码。 ? 信源编码的作用是用信道能传输的符号来表示信源发出的信息，在不 失真或一定失真的条件下用尽可能少的符号传送信源消息，提高信息 传输率。信源编码（如语音）对数字传输非常重要，而且对无线通信
来说显得尤其重要。
PDF created with pdfFactory Pro trial version https://www.doczj.com/doc/dc10907631.html,
?
随着数字电话和数据通信容量日益增长的迫切要求，而又 不希望明显降低传送话音信号的质量，除了提高通信带宽之外， 对话音信号进行压缩是提高通信容量的重要措施。
?在移动通信中，稀少而又昂贵的无线信道更一定要和必 须要对传输的各种信号源进行压缩，以提高通信容量。
PDF created with pdfFactory Pro trial version https://www.doczj.com/doc/dc10907631.html,
模拟信源（语音）编码的种类
波形编码、参量编码、混合编码 一般来说，波形编码器的话音质量高，但数据率也很高；参量编码器的数据 率很低，产生的合成话音的音质有待提高；混合编码器同时使用参量编译码技 术和波形编译码技术，数据率和音质介于它们之间。 （1）波形编码 波形编码比较简单，编码前采样定理对模拟语音信号进行量化，然后进行 幅度量化，再进行二进制编码。解码器作数／模变换后再由低通滤波器恢复出现 原始的模拟语音波形，这就是最简单的脉冲编码调制（PCM），也称为线性 PCM。可以通过非线性量化，前后样值的差分、自适应预测等方法实现数据压 缩。波形编码的目标是让解码器恢复出的模拟信号在波形上尽量与编码前原始波 形相一致，也即失真要最小。波形编码的方法简单，数码率较高，在64kbit/s至 32kbit/s之间音质优良，当数码率低于32kbit/s的时候音质明显降低，16 kbit/s时 音质非常差。
PDF created with pdfFactory Pro trial version https://www.doczj.com/doc/dc10907631.html,
信源编码 一种以提高通信有效性为目的而对信源符号进行的变换；为了减少或消除信源剩余度而进行的信源符号变换。为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。 既然信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。 一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立；②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者称为概率均匀化。 信源编码的一般问题可以表述如下： 若某信源的输出为长度等于M的符号序列集合式中符号A为信源符号表，它包含着K个不同的符号，A=｛ɑk|k=1,…,K｝，这个信源至多可以输出KM个不同的符号序列。记‖U‖=KM。所谓对这个信源的输出进行编码，就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U。若V的各个序列的长度等于N，即式中新的符号表B共含L个符号，B=｛bl|l=1,…,L｝。它总共可以编出LN个不同的码字。类似地,记‖V‖＝LN。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系‖V‖＝LN≥‖U‖＝KM 或者N/M≥logK/logL 。 假若编码符号表B的符号数L与信源符号表A的符号数K相等，则编码后的码字序列的长度N必须大于或等于信源输出符号序列的长度M；反之，若有N＝M，则必须有L≥K。只有满足这些条件，才能保证无差错地还原出原来的信源输出符号序列(称为码字的唯一可译性)。可是，在这些条件下，码字序列的每个码元所载荷的平均信息量不但不能高于，反而会低于信源输出序列的每个符号所载荷的平均信息量。这与编码的基本目标是直接相矛盾的。下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。
2.10常用信源编码 信源编码也称为有效性编码，通过编码的方式，压缩信源的冗余度，从而提高了了通信的有效性。 2.10.1山农—费诺编码 山农—费诺编码是一种常见的信源编码，其编码的步骤如下： (1)将信源的符号按其概率从大到小排列。 (2)将这一列符号分成尽可能概率接近或相同的两组。 (3)上面一组符号编为0，下面一组符号编为1，或反之。 (4)已分的组再按（2）、（3）步骤重复做，直至不能再分组。 (5)自左至右写出各码字。 [例2.10.1]有一单符号离散无记忆信源X如下，要求进行山农—费诺编码
因为信源有8个符号，其理论最大熵为lb8=3比特/符号，而实际熵为2.55比特/符号，如采用三位二进制等长编码，则效率η=2.55/3 = 85%，或者说采用定长编码效率较低。如采用山农—费诺编码，则效率会提高不少。 2.10.2哈夫曼编码 哈夫曼编码是效率比较高的又一种无失真信源编码，二进制哈夫曼编码步骤如下： (1) 把信源符号按概率从大到小排成一列； (2) 把概率最小的两个分成一组，上面一个编为0，下面一个编为1，并将这两个符号的概率加起来，其结果再和尚未处理过的符号重新按大小排序； (3) 重复步骤2，直到所有信源符号都处理完。 (4) 从右向左依据编码路径返回，就得到各码字。 [例2.10.2]同前例,编码过程见下图2.10.2：（PPT 001第四章）
第五节香农编码 ? 设离散无记忆信源 ? 二进制香农码的编码步骤如下：?将信源符号按概率从大到小的顺序排列，为方便起见，令p (x 1)≥p (x 2)≥…≥p (x n )?令p (x 0)=0，用p a (x j )，j =i +1表示第i 个码字的累加概率，则： ?确定满足下列不等式的整数k i ，并令k i 为第i 个码字的长度?－log 2p (x n )≤k i <－log 2p (x n )+1 ? 将p a (x j ) 用二进制表示，并取小数点后k i 位作为符号x i 的编码。 1 ()(),1,2,,j a j i i p x p x j n -== =∑ 121 12,,,,,,()1 (), (), , (), , ()()n i n i i i n x x x x X p x p x p x p x p x P X =????==? ???????∑ 2.10.3冗余位编码 冗余的信息完全可以不全部传送（压缩掉），从而提高了传输效率。 1．L —D 编码 现在来讨论一种由林绪（Lynch ）和达维生（Davission ）分别独立提出的冗余位编码法，称为L —D 编码。 例如有一二元序列，其中的一串000100000001000共二进制15位，其余的也可分割成15位一串，称为一帧。现在研究压缩冗余的方法。显然对该帧可确切描述为： （1） 帧长为15。