信息论编码。
一．信息论的认识。
1.消息是信息的载荷者。信息是抽象的，消息是具体的。要研究信息，还得从研究消息入手。
2.由于信源发送什么消息预先是不可知的，只能用概率空间来描述信源。
3.单符号信源：输出是单个符号（**）的消息。
离散信源。连续信源。
4.平稳随机序列信源：信源输出的消息由一系列符号序列所组成，可用n维随机矢量 x＝(x1,x2,…,xn)描述，且随机矢量x 的各维概率分布都与时间起点无关---平稳！
离散平稳信源。
连续平稳信源。
无记忆（独立）离散平稳信源。
有记忆信源。
m阶马尔可夫信源。
5.随机波形信源。
信息是信息论中最基本、最重要的概念，既抽象又复杂。
信息在日常生活中被认为是“消息”、“知识”、“情报”等
“信息”不同于消息（在现代信息论形成之前，信息一直被看作是通信中消息的同义词，没有严格的数学含义），消息是表现形式，信息是实质；
“信息”不同于情报，情报的含义比“信息”窄的多，一般只限于特殊的领域，是一类特殊的信息；
信息不同于信号，信号是承载消息的物理量；
信息不同于知识，知识是人们根据某种目的，从自然界收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次的信息。
6.互信息量 i(xi ; yj)：收到消息yj 后获得关于xi的信息量。
即：互信息量表示先验的不确定性减去尚存的不确定性，这就是收信者获得的信息量。
对于无干扰信道，i(xi ; yj) =i(xi)；
二．我们学到了。
1.离散信源熵和互信息。
定义具有概率为p（xi）的符号xi的自信息量为。
i(xi)=-logp（xi）
信源输出的整体特征用平均自信息量，表示本身的特征用信源熵。
2.信道与信道容量。
信道分类：根据用户数量可分为单用户信道和多用户信道。
根据信道输入端和输出端的关系可分为无反馈信道和反馈信道。
根据信道参数与时间的关系可分为固定参数信道和时变参数信道。
根据信道中所受噪声种类的不同，可分为随即差错信道和突发差错信道。
根据输入输出的特点可分为离散信道、连续信道、半离散半连续信道、波形信道等。
3.信源编码。
编码———码树。
1） r进制码树对应r进制编码。
2） 码序列为树根到每个终端结点的树枝的序号。
3） n级终端节点对应一个码字最多有n个码字符号。
4） q个终端节点对应q个不同码字。
一。编码器模型。
由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。下图为一个编码器模型：
4.码树形状：倒立树。
概念：树枝：码树上的线段。
结点：树枝的两端点。
树根。n级结点。
r进制码树。
终端节点。5.编码。
1）变长码。
若一组码中码字的码长各不相同（即码字长度不等），则称为变长码 .
如表中“编码1”为等长码，“编码2”为变长码。
2）分组码。
若每个信源符号按照固定的码表映射成一个码字，则称为分组码。否则就是非分组码。
如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。下面讨论分组码的一些直观属性。
3）非奇异码和奇异码。
若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列)，则称为非奇异码。反之，则为奇异码。如表中的“编码2”是奇异码，其他码是非奇异码。
4）惟一可译码。
若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（或称单义可译码）。否则就称为非惟一可译码或非单义可译码。
若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。
5）综上所述，可将码作所示的分类：
6.码树如下图。
树根码字起点树枝数码的进制数；
节点码字或码字的一部分； 终端节点码字；
阶数码长非整树变长码；
整树等长码。
变长码往往在码长的平均值不很大时，就可编出效率很高而且无失真的码，其平均码长受香农第一定理所限定，即：
若对信源离散无记忆信源s的n次扩展信源进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源s中每个信源符号所需的平均码长满足：
7.编码分类：
香浓编码。1） 香农第一定理指出，可选择每个码字的长度满足关系式：
或：2） x 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。
3）香农码的编码步骤如下：
【1】将个信源符号按概率递减的方式进行排列：
【2】按香农不等式计算出每个信源符号的码长 ；
【3】为了编成惟一可译码，计算第i个信源符号的累加概率。
【4】将累加概率用二进制数表示。
【5】取对应二进制数的小数点后位构成该信源符号的二进制码字。
费诺编码。1）费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现分布形式的条件下，才能达到最佳码的性能。
2）费诺码的编码步骤如下：
【1】信源符号以概率递减的次序排列起来；
【2】将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”；
【3】将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号；
【4】依次下去，直至每个小组只剩一个信源符号为止；
5】信源符号所对应的码字即为费诺码。
3）例：将下列消息按二元费诺码方法进行编码。
解：其编码过程如下页：
码的性能分析：
此信源的熵比特／符号)，而码的平均长度
二元码符号／符号)
显然，该码是紧致码，编码效率：
该码之所以能达到最佳，是因为信源符号的概率分布正好满足式，否则，在一般情况下是无法达到编码效率等于“1”的。
4）费诺码具有如下的性质：
①费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。
②费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。
③费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用：当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。
可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。
r 元费诺码。
前面讨论的费诺码是二元费诺码，对r元费诺码，与二元费诺码编码方法相同，只是每次分组时应将符号分成概率分布接近的r个组。
2023年，霍夫曼（huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码。
设信源其对应的概率分布为。
则对二元霍夫曼码而言，其编码步骤如下：
1）将q个信源符号按概率递减的方式排列起来；
2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为s信源的s1缩减信源；
3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源s2；
4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示；
5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。
:对离散无记忆信源。
哈弗曼编码。
（1） 进行霍夫曼编码。
解：编码过程如表所示：
1】将信源符号按概率大小由大至小排序。
2】从概率最小的两个信源符号和开始编码，并按一定的规则赋予码符号，如下面的信源符号（小概率）为“1”，上面的信源符号（大概率）为“0”。若两支路概率相等，仍为下面的信源符号为“1” 上面的信源符号为“0”。
3】将已编码两个信源符号概率合并，重新排队，编码。
4】重复步骤3）直至合并概率等于“1.0”为止。
5】从概率等于“1.0”端沿合并路线逆行至对应消息编码。
2）按霍夫曼码的编码方法，可知这种码有如下特征：
①它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；
②它是一种惟一可解的码：任何码符号序列只能以一种方式译码；
③它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接解码出来。
信息论作业
b.2 唯一可译码判决准则。1.实验目的。1 进一步熟悉唯一可译码判决准则 2 掌握c语言字符串处理程序的设计和调试技术。2.实验要求。1 已知 信源符号个数，码字集合c。2 输入 任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。3 输出 判决 是唯一可译码 不是唯一可译码 4 源程序格式...
2023年《信息论与编码》复习要点
rt信息论与编码的学习要点。自信息。自信息表示随机事件xi发生前的不确定性或发生后所包含的信息量，其定义为 互信息。互信息表示已知事件yj后所消除的关于事件xi的不确定性，等于事件xi本身的不确定性i xi 已知事件yj后对xi仍然存在的不确定性i xi yj 其定义为 平均自信息。平均自信息表示整...
信息论大作业
电子工程学院。班。号。编码。1 huffman 编码原理 将信源符号按概率从大到小的顺序排列，令p x1 p x2 p xn 给两个概率最小的信源符号p xn 1 和p xn 各分配一个码位 0 和 1 将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含 ...