霍夫曼编码的matlab实现(信源编码实验)

重庆交通大学信息科学与工程学院综合设计实验报告专业课：2012年通信工程一班学校编号：631206040118名字：王松实验课程：信息论与编码实验室(中心):软件与通信实验中心黄，讲师2015年4月教师评论：签名：月，年实验结果：霍夫曼编码的Matlab实现首先，实验的目的和要求。采用霍夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在本实验中，霍夫曼编码是通过Matlab语言编程实现的。第二，实验原理。霍夫曼编码算法是一种平均二进制码长最短且满足前缀条件的编码源输出符号，较短的编码码字被分配给概率较高的源输出。该算法如下：在源符号集中，两个最小概率的源输出首先组合成一个新的输出，该概率是两个相应输出符号的概率之和。重复该过程，直到只剩下一个组合输出，最后一个组合输出符号的概率为1。这样，就获得了树形图。从树的根开始，编码符号1和0被分配在同一节点的任意两个分支上。这种分配过程一直重复到离开。从根到叶的分支路径上的代码最终形成一组不同的前缀，它们是霍夫曼编码输出。离散无记忆源：例如U u1 u2 u3 u4 u5P(U)=0.4 0.2 0.2 0.1 0.1码字Wi符号si概率；可能性P(si)编码过程第一次第二次第三次W1=0W2=10W3=111W4=1101W5=1100S1S2S3第四心音表面抗原-50.40.20.20.10.10.40.20.210.200.40.410.200.61 0.401 A(1)0通过上表中源的归约和合并过程，完成源的霍夫曼编码。三。实验步骤它分为两步。第一个是代码树形成过程：将源概率组合起来形成代码树。然后是码树回溯过程：在码树上分配码字，最后得到霍夫曼编码。1.码树形成过程：源概率从小到大排序，并建立相应的位置索引。然后根据上述规则合并信息源，然后对信息源进行排序并建立新的位置索引，直到合并完成。在这个过程中，排序的源概率存储在矩阵G中，位置索引存储在矩阵索引中。这样，可以从排序后的概率矩阵G和索引矩阵Index中恢复原始概率矩阵P，从而确保回溯过程能够进行。2.码树回溯过程：码字分布在码树上，最后得到霍夫曼码。回溯从索引矩阵m的最后一行开始。(1)在索引的最后一行元素2的位置填充0和1。(2)根据该行索引1位置指示，在前一行的第一和第二元素位置中填充索引1位置的代码(1)，并在其后分别添加0和1。(3)将索引不是“1”的位置的编码值(“0”)填入前一行的相应位置(第3列)。(4)从索引的倒数第二行开始，重复步骤(1)至(3)，直到计算出索引的第一行。四、程序代码：%获取源概率矩阵，并进行合法性判断清除；p=输入(请输入源概率向量p=)；n=长度(P)；对于组件=1:1:N如果(零件)0错误(源概率不能小于0)；目标目标如果(总和(P)-1)0.0001)错误(源概率之和必须为1)；目标%来建立每个概率符号的位置索引矩阵索引，这有利于编码后从树根追溯，从而得到相应的编码Q=P指数=零(N-1，N)；%初始化索引对于i=1:N-1Q，L=排序(Q)；指数(I，)=L(1:N-i 1)，零(1，I-1)；G(i，)=Q；Q=Q(1) Q(2)，Q(3:)，1；%将Q中概率最低的两个元素合并，元素不足的地方填写1目标%根据上面建立的索引矩阵，进行回溯得到源代码对于i=1:N-1Char(i，)=空格(N * N)；%初始化由存储代码的空格字符组成的字符矩阵N*N目标%从代码树的根追溯到叶，即根据与索引中的索引位置的对应关系，从g矩阵的最后一行编码到其第一行字符(N-1，N)=0；%G中第N-1行的第一个元素，即最后一行，被赋值为0，并存储在字符中第N-1行的N列位置Char(N-1，2 * N)=1；%G中第N-1行的第二个元素(即最后一行)被赋值为1，并存储在字符中第N-1行的2*N列位置低于%是从g的倒数第二行向前编码的对于i=2:N-1字符(N-i，1:N-1)=字符(N-i 1，N*(查找(索引(N-i 1，)=1)-(N-2):N *(查找(索引(N-i 1，)=1)；%在当前行的第一个编码位置填充索引后一行中索引为1的编码码字char(N-1，N)=0；%然后在当前行的第一个编码位置的末尾填写0字符(N-i，N 1:2 * N-1)=字符(N-i，1:N-1)；%将G下一行的索引为1的码字填充到当前行的第二个编码位置char(N-1，2 * N)=1；%然后在当前行的第二个编码位置的末尾填写1对于j=1:i-1%内部循环函数：在当前行的第三个位置的开头，按照从左到右的顺序在索引之后的行中用索引而不是1填充代码，最后计算到第一行索引的末尾Char(N-i，(j 1)*N 1:(j 2)*N)=Char(N-i 1，N*(查找(索引(N-i 1，)=j 1)-1)1:N *查找(索引(N-i 1，)=j 1)；目标目标%Char中第一行的编码结果是所需的霍夫曼编码输出。编码通过索引中的第一行索引映射到相应概率的源符号。对于i=1:N结果(I，1:N)=Char(1，N*(查找(索引(1，)=I)-1)1:查找(索引(1，)=I)* N)；目标%打印编码结果字符串=源概率及其对应的霍夫曼码如下：显示(字符串)；显示(P)；显示(结果)；五、对比分析，通过给出不同的信息源，对结果进行分析、比较和验证，并得出相应的子分析报告。以0.1，0.2，0.3，0.2，0.1，0.1为例：运行程序，结果如下以0.3 0.3 0.2 0.1 0.1为例：运行程序，结果如下分析：从上图可以看出，该程序已经完成了霍夫曼编码功能，但是霍夫曼编码并不是唯一的。因为：当源符号组合的最小概率相同时，组合可以随意进行。当代码树分配代码字时，1和0的位置可以是任意的。6.提交实验报告。1.在实验过程中，利用矩阵记录每次排序前概率的位置是实验的关键。通过在编码过程中使用矩阵可以容易地执行霍夫曼编码。2.通过这个实验，我们对霍夫曼编码的具体实现原理有了更深的了解。在实验过程中，我们也遇到了一些问题，通过查找资料和相关书籍解决了这些问题。通过这个实验，我们了解了哈夫曼编码的特点，可以利用哈夫曼编码的基本原理和编码算法来设计和实现程序。已经取得了很多成果，为以后的进一步研究打下了基础。一般来说，在完成实验的过程中，我们学到了很多知识，包括更熟练地掌握一些matlab语句，完成一个算法必须有一个全面的掌握，等等。3.通过课程设计，我对二叉树和哈夫曼编码树有了更深的了解。在课程设计中，我掌握了二进