第四章：无失真信源编码

实验一无失真信源编码一、实验目的与要求1. 理解并掌握无失真信源编码定理的内容及支撑理论；2. 掌握唯一可译码的含义及判断方法；3. 掌握赫夫曼码的数学基础、编码原理与实现技术；4. 掌握二进制、三进制赫夫曼码的编码方法与结果分析；5. 基于Visual C++环境使用面向对象方法设计赫夫曼编码软件。

二、实验仪器与设备1. 微型电子计算机80台2. Windows 2000以上版本操作系统80套3. Visual C++ 6.0开发系统80套三、实验内容与步骤（一）二进制赫夫曼编码使用以下两种不同的方法编写二进制赫夫曼码：·信源合并后的新符号排在其它相同概率的符号的前面；·合并后的新符号排在其它相同概率的符号的后面。

具体要求：1.使用Visual C++6.0开发环境，应用面向对象的程序设计模式，编写CHuffman_2类，并根据具体要求，添加必须的数据成员和成员函数；2.分别求出两种编码方法下的平均码长、信息率和编码效率，并分析实际中应选择哪种编码方法；3.添加成员函数IsUniDecodableCdoe()，以判断赫夫曼码是否唯一可译码；4.添加成员函数IsCodingwithoutDistoryion()，以判断赫夫曼码是否满足无失真编码定理；5.用户可以随机输入多个心愿符号信息，并在主函数中至少测试两组数据，并显示有关结果信息。

（二）三进制赫夫曼编码与上述步骤类似，设计CHuffman_3类，编写三进制赫夫曼码。

要求使用相同的测试数据，并比较平均码长、信息率及编码效率等，给出自己的思考结论。

（三）m进制赫夫曼编码设计CHuffman_m类，编写m进制赫夫曼码。

m在运行时由用户输入。

其它要求同上。

综合实验代码及分析：#include <iostream.h>#include <math.h>#include <string.h>#include <stdio.h>#include <stdlib.h>#include <vector>using namespace std;#define MAX 10 //输入进制，最多10进制struct Huffman_InformationSource //信源类型{char InformationSign[10]; //信源符号double Probability; //概率char Code[20]; //编码结果int CodeLength; //码长};struct HuffNode //赫夫曼树的节点类型{char InformationSign[10];double Probability;HuffNode *Subtree[MAX]; //子树HuffNode *Next;char Code[20];int CodeLength;};class CHuffman_m //赫夫曼编码{public:CHuffman_m(int M) //初始化{m=M;ISNumber=0;AvageCodeLength=0.0;InformationRate=0.0;CodeEfficiency=0.0;}~CHuffman_m(){// DestroyBTree(HuffTree);}void Huffman_Input(); //输入信息void Huffman_Sort(); //排序void Huffman_Tree(); //构造赫夫曼树void Huffman_Coding(); //生成赫夫曼编码void Huffman_CodeAnalyzing(); //结果分析void Huffman_Display(); //显示结果信息void DestroyBTree(HuffNode *TreePointer); //释放资源private:vector<Huffman_InformationSource>ISarray; //声明ISarray数组，初始时为空int ISNumber; //符号个数double AvageCodeLength; //平均码长double InformationRate; //信息率double CodeEfficiency; //编码效率int m; // m 进制HuffNode * HuffTree; //赫夫曼树private:void Huffman_Code(HuffNode *TreePointer);}; //输入信源信息void CHuffman_m::Huffman_Input(){ int n,i,j;double sum=0;cout<<"请输入信源符号个数: ";cin>>n;cout<<"请信源符号和概率: "<<endl;for(i=0;i<n;i++){Huffman_InformationSource temp;cin>>rmationSign;cin>>temp.Probability;strcpy(temp.Code,"");temp.CodeLength=0;ISarray.push_back(temp);ISNumber=ISarray.size();}for(j=0;j<ISarray.size();j++)sum+=ISarray[j].Probability;if(sum==1)return;else{cout<<"\a\a\a概率和不为1！请重新输入"<<endl;ISarray.clear();CHuffman_m::Huffman_Input();}}//按概率"从大到小"排序：void CHuffman_m::Huffman_Sort(){Huffman_InformationSource temp;int i,j;for(i=0;i<ISNumber-1;i++)for(j=i+1;j<ISNumber;j++)if(ISarray[i].Probability<ISarray[j].Probability){temp=ISarray[i];ISarray[i]=ISarray[j];ISarray[j]=temp;}}//基于ISarray数组构造赫夫曼树void CHuffman_m::Huffman_Tree(){int i,j;HuffNode *ptr1,*ptr2;//（1）：基于数组，创建单向链表ptr1=new HuffNode;strcpy(ptr1->InformationSign,ISarray[0].InformationSign);ptr1->Probability=ISarray[0].Probability;strcpy(ptr1->Code,ISarray[0].Code);for(j=0;j<m;j++) //初始化子树ptr1->Subtree[j] =NULL;ptr1->Next=NULL;HuffTree=ptr1; //赋给数据成员HuffTreefor(i=1;i<ISNumber;i++){ptr2=new HuffNode;strcpy(ptr2->InformationSign,ISarray[i].InformationSign);ptr2->Probability=ISarray[i].Probability;strcpy(ptr2->Code,ISarray[i].Code);for(j=0;j<m;j++) //初始化子树ptr2->Subtree[j] =NULL;ptr2->Next=ptr1;ptr1=ptr2;}//结果：链表的表头为数组的最小元素。

《信息论基础》题目：常用无失真信源编码程序设计目录1. 引言 (2)2. 香农编码 (2)2.1 编码步骤 (3)2.2 程序设计 (3)2.3 运行结果 (3)3. 费诺编码 (4)3.1 编码步骤 (5)3.2 程序设计 (5)3.3 运行结果 (5)4. 哈夫曼编码 (6)4.1 编码步骤 (7)4.2 程序设计 (7)4.3 运行结果 (8)5. 结论 (9)6. 参考文献 (10)7. 附录 (11)7.1 香农编码Matlab程序 (11)7.2 费诺编码Matlab程序 (12)7.3 哈夫曼编码Matlab程序 (14)1. 引言信息论（Information Theory）是运用概率论与数理统计的方法研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。

信息系统就是广义的通信系统，泛指某种信息从一处传送到另一处所需的全部设备所构成的系统。

信息论是关于信息的理论，应有自己明确的研究对象和适用范围[1]。

信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。

信息传输和信息压缩是信息论研究中的两大领域。

这两个方面又由信息传输定理、信源－信道隔离定理相互联系。

信源编码是一种以提高通信有效性为目的而对信源符号进行的变换，或者说为了减少或消除信源冗余度而进行的信源符号变换。

具体说，就是针对信源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列[2]。

在通信中，传送信源信息只需要具有信源极限熵大小的信息率，但在实际的通信系统中用来传送信息的信息率远大于信源极限熵。

为了能够得到或接近信源熵的最小信息率，必须解决编码的问题，而编码分为信源编码和信道编码，其中的信源编码又分为无失真信源编码和限失真信源编码。

由于无失真信源编码只适用于离散信源，所以本次作业讨论无失真离散信源的三种简单编码，即香农（Shannon）编码、费诺(Fano) 编码和哈夫曼(Huffman) 编码[3]。

《信息论》讲义204教研室2005年11月主要内容：第一章绪论第二章离散信源及其信息测度第三章离散信道及其信道容量第四章无失真信源编码第五章有噪信道编码第一章 绪论信息论——人们在长期通信工程的实践中，由通信技术与概率论、随机过程和数理统计相结合而逐步发展起来的一门学科。

奠基人——香农1948年发表了著名的论文——《通信的数学理论》，为信息论奠定了理论基础。

1.1 信息的概念人类离不开信息，信息的接收、传递、处理和利用时时刻刻都在发生。

如：“结绳记事”、“烽火告警”，信息的重要性是不言而喻的。

什么是信息？——信息论中最基本、最重要的概念。

信息与“消息”、“情报”、“知识”、“情况”等的区别：“情报”——人们对于某个特定对象所见、所闻、所理解而产生的知识。

是一类特定的信息。

“知识”——人们根据某种目的，从自然界收集得来的数据中，整理、概括、提取得到的有价值的、人们所需的信息。

是一种具有普遍和概括性质的高层次的信息。

“消息”——以文字、符号、数据、语言、音符、图片、图像等能够被人们感觉器官所感知的形式，表达客观物质运动和主观思维活动的状态。

消息包含信息，是信息的载体。

二者既有区别又有联系。

“信号”——消息的运载工具。

香农从研究通信系统传输的实质出发，对信息作了科学的定义，并进行了定性和定量的描述。

收信者：收到消息前，发送者发送的消息——1、描述的是何种事物运动状态的具体消息；2、描述的是这种消息还是那种消息；3、若存在干扰，所得消息是否正确与可靠。

存在“不知”、“不确定”或“疑问”收到消息后，知道消息的具体内容，原先的“不知”、“不确定”或“疑问”消除或部分消除了。

消息传递过程——从不知到知的过程；从知之甚少到知之甚多的过程；从不确定到部分确定或全部确定的过程。

通信过程——消除不确定性的过程。

不确定性的消除，就获得了信息。

若原先不确定性全部消除了，就获得了全部的消息；若消除了部分不确定性，就获得了部分信息；若原先不确定性没有任何消除，就没有获得任何消息。

第4章习题4-1 对信源⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡01.010.015.017.018.019.02.0s s s s s s s P S 7654321进行二元编码，编码方案为（1）计算平均码长L ； （2）编码后信息传输率R ；（3）编码信息率R '； （4）编码效率η。

解：（1）()14.3Ls p L iq1i i=⋅=∑=（码元/信源符号）（2）()61.2S H =（比特/信源符号）()831.014.361.2L S ===H R （bit/码元） （3）logr L R ='=3.14（ bit/信源符号） （4）831.0R Rmax==η 或者()831.0R S H ='=η 4-2 设离散无记忆信源的概率空间为⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡4143s s S 21P ，若对信源采取等长二元编码，要求编码效率96.0=η，允许译码错误概率510-≤δ，试计算需要的信源序列长度N 为多少？解：信源熵为()811034log 434log 41S .Η=+=（bit/符号）自信息量的方差()()()[]22i q1i i 2S H logp p S -=∑=σ4715.0811.041log 4143log 43222=-⎪⎭⎫⎝⎛+⎪⎭⎫ ⎝⎛= 因为编码效率96.0=η，由()()ε+=S S H H η可得()3379.0811.096.004.0S H 1=⨯=-=ηηε 可得()752221013.4103379.04715.0S N ⨯=⨯=≥-δεσ 所以，信源序列长度达到71013.4⨯以上，才能实现给定的要求，因此等长编码没有实际的意义，一般统计编码都是采用不等长编码。

4-6设离散无记忆信源的概率空间为⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡1.09.0s s S 21P ，对信源进行N 次扩展，采用霍夫曼编码。

当N=1，2，∞时的平均码长和编码效率为多少？解：（1）N=1时，将1s 编成0，2s 编成1，则1L 1=又因为信源熵()469.0))logp(s p(s S H q1i i i =-=∑=bit/符号所以()469.0L S H 11==η （2）N=2时，编码过程如下2S概率 霍夫曼编码11s s 0.81121s s 0.09 01 12s s 0.09 000 22s s 0.01001所以()=+⨯+⨯+⨯=0.090.0130.0920.811L 2则645.02L 2= 所以()==0.645X H 2η （3）N=∞时，由香农第一定理可知，必然存在唯一可译码，使()S H N L limr NN =∞→而霍夫曼编码为最佳码，即平均码长最短的码，故()()469.0S H S H N L limr NN ===∞→即1lim N N =∞→η4-7已知信源共7个符号消息，其概率空间为()⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡01.010.015.017.018.019.02.0s s s s s s s x P S 7654321试进行香农编码。

1Y有一信源，它有6个可能的输出，其概率分布如题表所示，表中给出了对应的码A.B.C.D.E 和Fo题表消息P(aJ A BcD E FJ O1 1/2 0000 00 0 0021/41 00101 10 10 10 10061/16 010 Oil110 110 1100 10104 1/16 Oil 0111 1110 1110 1101 110 051/16 100 01111 11110 1011 1100 111 ■061/1610101111111111011011111Oil(1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码(即时码)；(3) 对所有唯一可译码求出其平均码长Z 。

解：(1)唯一可译码：A, B, CA 是等长码，码长3,每个码字各不相同，因此是唯一可译码。

B 是非即时码，前缀码，是唯一可译码。

C 是即时码，是唯一可译码。

D 是变长码，码长｛1, 2, 3, 4, 4, 4),不是唯一可译码，因为不满足Kraft 不等式。

E 是变长码，码长｛1, 2, 4, 4, 4, 4｝,满足Kraft 不等式，但是有相同的码字，VV 3=^=11OO,不是唯F 是变长码，码长｛1, 3, 3, 3, 3, 3｝,不满足Kraft 不等式，不是唯一可译码。

一可译码。

x4=l<l+ (丄］x5 = 1.125>l \2)_x3 + —x4 + —x^ + —x & = 1325⑵非延长码：A, C设离散信源的概率空间为S| 孔 S3 $4$5 几0.25 0.25 0.20 0.15 0.10 0.05对其釆用香农编码，并求出平均码长和编码效率。

解：XiP(Xi) Po(Xi) kt码字X 丄0 3 000 X23 001 X3 *3 Oil X43 100 X53 101 X64 1110 X771111110L=Y J P i ・厶=0.25x2 + 0・25x2 + 0・2x3 + 0 ・15x 3 + 0.1 x4 + 0・05x5 = 2.7 iH(S) = p i log /?. = -(0.25 x log 0.25 +... + 0.05 x log 0.05)= 2.423 hit 型】士’9 7%L 2.7设无记忆二元信源，其概率7^=0.005, /72 =0.995 o 信源输出N = 100的二元序列。

信息论与编码理论-第4章无失真信源编码-习题解答-20071202信息论与编码理论第4章无失真信源编码习题及其参考答案4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F（1）求这些码中哪些是唯一可译码；（2）求哪些码是及时码；（3）对所有唯一可译码求出其平均码长。

?X??s14-2 设信源????p(s)P(X)???1s6?p(s2)?p(s6)???s2?p(s)?1。

对此次能源进行m元唯一ii?16可译编码，其对应的码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值的最好下限。

（提示：用kraft不等式）?s?X??14-3设信源为??1??p(X)???2?（1）信源的符号熵；（2）这种码的编码效率；s214s3s411816s5132s6s7s8?，编成这样的码：（000，001，111???64128128?010，011，100，101，110，111）。

求（3）相应的仙农码和费诺码。

4-4求概率分布为(,11122信)源的二元霍夫曼编码。

讨论此码对于概率分布为355151511111(,,,,)的信源也是最佳二元码。

555554-5有两个信源X和Y如下：1信息论与编码理论s2s3s4s5s6s7??X??s1??p(X)??0.200.190.180.170.150.100.01?????s2s3s4s5s6s7s8s9??Y??s1??p(Y)??0.490.140.140.070.070.040.020.02 0.01?????（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率；（2）从X，Y两种不同信源来比较三种编码方法的优缺点。

4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样霍夫曼码的信源的所有概率分布。

4-7设信源为?码。

无失真编码定理
无失真编码定理是指在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度L与信源的熵H(s)任意地接近，即L=H(s)+ε，其
中ε为任意小的正数，但以H(s)为其下限，即L≥H(s)。

无失真编码是一种基于信号统计特性的编码技术，其码字中的0和1
是独立的，并且基本上等概率出现。

无失真编码是一种无损编码，即
能够无差错地从码字恢复信源符号。

无失真定长编码定理是指在定长编码中，如果对信源进行等长编码，
必须满足nL≤mK，其中nL是信源的符号数，mK是码字的符号数。

只
有当K长的码符号序列数mK大于或等于信源的符号数nL时，才可能
存在等长非奇异码。

无失真定长编码定理在某些情况下可能会限制编码效率，例如当信源
的符号概率分布非常不均匀时。

因此，在实际应用中，通常会采用变
长编码技术，如霍夫曼编码和香农-法诺编码等，以实现更高的编码效率。

无失真编码与保真度准则下的信源编码比较无失真编码和保真度编码是两种不同的信源编码方法。

无失真编码是一种编码方法，其中编码的输出与其输入完全相同，即没有信息损失。

保真度编码是一种编码方法，其中编码输出与输入之间具有某种度量，通常用于指定被编码信源的相关度量。

在无失真编码中，被编码的信源通常通过重复信源符号来实现。

例如，在串行传输系统中，数据被重复多次，以确保接收方能够正确地接收数据。

虽然这种方法可以确保完全输送原始信源，但它有几个限制。

首先，它需要更多的带宽，因为数据需要被重复发送多次。

其次，它并不适用于所有类型的数据，特别是当数据非常长或不规则时，这种方法会变得非常昂贵和低效。

与此不同的是，保真度编码的目标是在尽可能减少带宽和存储空间的情况下，最大限度地保留原始信源的信息。

通过使用保真度准则，可以将信源表示为某种度量形式。

这些度量通常包括信号功率、功率频谱分布、自相关函数和互相关函数等。

保真度编码通常使用一些高级编码技术，如哈夫曼编码、熵编码和维纳滤波器等。

这些编码方法都源于信息论和通信工程领域的数学理论。

通过这些编码技术，保真度编码可以提高信源的压缩效率，同时最大程度地保留信源的信息。

当比较无失真编码和保真度编码时，无失真编码通常比较简单，但需要更多的带宽和存储空间。

而保真度编码则需要更复杂的算法和技术，但可以在尽可能减少带宽和存储空间的情况下保留更多的原始信息。

综上所述，在处理信源编码问题时，需要综合考虑多个方面，包括数据类型、带宽和存储空间要求等。

无失真编码适用于对带宽和存储空间要求不是很高的应用，例如音频、图片和视频的传输。

保真度编码适用于对存储空间和带宽要求较高的应用，例如用于数字通信系统的压缩算法。

4。

1 某集源按P （0)=3/4，P(1）=1/4的概率产生统计独立的二元序列.(1) 试求N 0，使当N>N 0时有： P ｛｜I(a i )/N －H(S ）｜ ≥0.05}≤0.01其中H （S)是信源的熵。

(2)试求当N= N 0时典型序列集G εN 中含有的信源序列个数.解：(1) H(S)= —∑Pi ㏒Pi= -3/4㏒(3/4)—1/4㏒(1/4） =0.811 比特/符号根据契比雪夫不等式，对于任意ε＞0，当N ＞N0时，P ｛∣I(αi)/N – H(S ）∣≥ε｝≤D[I(Si ）］/N ε2现有ε=0.05,欲证原式，只要 D ［I(Si ）]/N ε2≤0。

01根据信源，D ［I （Si)]=∑P （Si ）［㏒P(Si)］2– H 2（S)=3/4（㏒3/4)2+1/4（㏒1/4)2—(0。

811)2=0。

471∴N0= D[I(Si)]/0。

01ε2=0.471/0。

01×（0.05)2=18840(2) 序列G εN 是所有N 长的ε典型序列集合，（1-δ）2N ［H （S ）—ε]≤‖G εN ‖≤2N[H （S ）-ε]0.99×214342。

5≤‖G εN ‖≤216226。

54。

2 设无记忆二元信源，其概率为P1=0.005, P0=0。

995.信源输出N ＝100的二元序列.在长为N ＝100的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。

（1）求码字所需的最小长度。

（2）计算式（4.27a ）中的ε。

(3）考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率PE 是多少？若从契比雪夫不等式（4。

22）考虑，PE 应是多少？试加以比较。

解：（1）无记忆二元信源()⎢⎣⎡⎥⎦⎤=⎢⎣⎡⎥⎦⎤005.0995.01,0i s P S N=100的扩展信源()()()()()⎢⎢⎢⎣⎡⎥⎥⎦⎤⨯⨯=====⎢⎢⎣⎡⎥⎦⎤--N N N N NN N N i N N N P S 005.0,005.0995.0005.0995.0,995.0111,1011010001121221，，，，，－ ααααα 现只对含有3个或小于3个“1”的各信源序列构成一一对应的一组二元等长码。