哈弗曼费诺汉明码matlab.docx

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.13M 资料格式：docx 举报版权申诉

第1页 / 共14页

第2页 / 共14页

第3页 / 共14页

第4页 / 共14页

第5页 / 共14页

第6页 / 共14页

第7页 / 共14页

第8页 / 共14页

文本预览

信息论实验报告姓名班级学号胡小辉电子信息工程 0902 0909091112

1. 实验目的 1、掌握哈夫曼编码、费诺编码、汉明码原理； 2、熟练掌握哈夫曼树的生成方法； 3、学会利用 matlab、C 语言等实现 Huffman 编码、费诺编码以及 hamming 编码。 2. 实验原理 Huffman 编码：哈夫曼树的定义：假设有 n 个权值，试构造一颗有 n 个叶子节点的二叉树，每个叶子带权值为 wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；实现 Huffman 编码原理的步骤如下： 1. 首先将信源符号集中的符号按概率大小从大到小排列。 2. 用 0 和 1 表示概率最小的两个符号。可用 0 表示概率小的号，也可用 1 表示概率小的符号，但整个编码需保持一致。 3. 将这两个概率最小的符号合并成一个符号，合并符号概率符为最小概率之和，将合并后的符号与其余符号组成一个 N-1 的新信源符号集，称之为缩减符号集。 4. 对缩减符号集用步骤 1,2 操作 5. 以此类推，直到只剩两个符号，将 0 和 1 分别赋予它们。 6. 根据以上步骤，得到 0,1 赋值，画出 Huffman 码树，并从最后一个合并符号回朔得到 Huffmaan 编码。费诺编码：费诺编码的实现步骤： 1、将信源消息符号按其出现的概率大小依次排列：。

2、将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。 3、将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。 4、如此重复，直至每个组只剩下一个信源符号为止。 5、信源符号所对应的码字即为费诺码。 hamming 编码：若一致监督矩阵 H 的列是由不全为 0 且互不相同的所有二进制 m(m≥2 的正整数) 重组成，则由此 H 矩阵得到的线性分组码称为[2m-1,2m-1-m，3]汉明码。我们通过（7，4）汉明码的例子来说明如何具体构造这种码。设分组码（n， k）中，k = 4，为能纠正一位误码，要求r≥3。现取r＝3，则n＝k＋r＝7。我们用a0ala2a3a4a5a6表示这7个码元，用S1、S2、S3表示由三个监督方程式计算得到的校正子，并假设三位S1、S2、S3校正子码组与误码位置的对应关系如表1所示。 S1S2S3 错码位置 S1S2S3 错码位置 001 010 100 011 a0 al a2 a3 101 110 111 000 a4 a5 a6 无错码表1 校正子和错码位置关系由表可知，当误码位置在a2、a4、a5、a6时，校正子S1＝1；否则S1＝0。因此有S1 ＝a6⊕a5⊕a4⊕a2，同理有S2＝a6⊕a5⊕a3⊕a1和S3＝a6⊕a4⊕a3⊕a0。在编码时a6、 a5、a4、a3为信息码元，a2、a1、a0为监督码元。则监督码元可由以下监督方程唯一确定 a6⊕a5⊕a4⊕a2 = 0 a6⊕a5⊕a3⊕a1 = 0 a6⊕a4⊕a3⊕a0 = 0 (1.1.1)

也即 a2＝a6⊕a5⊕a4 a1＝a6⊕a5⊕a3 （ 1.1.2） a0 = a6⊕a4⊕a3 由上面方程可得到表 2 所示的 16 个许用码组。在接收端收到每个码组后，计算出 S1、S2、S3，如果不全为 0，则表示存在错误，可以由表 1 确定错误位置并予以纠正。举个例子，假设收到码组为 0000011，可算出 S1S2S3=011,由表 1 可知在 a3 上有一误码。通过观察可以看出，上述（7，4）码的最小码距为 dmin＝3，纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码. 信息位 a6a5a4a3 监督位 a2a1a0 信息位 a6a5a4a3 监督位 a2a1a0 0000 0001 0010 0011 0100 0101 0110 0111 000 011 101 110 110 101 011 000 1000 1001 1010 1011 1100 1101 1110 1111 111 100 010 001 001 010 100 111 表2 （7,4）汉明码的许用码组 3.1 (7,4)汉明码的编码思路 (7,4)汉明码的编码就是将输入的四位信息码编成七位的汉明码，即加入三位监督位。根据式(2.2.0）A = [a6 a5 a4 a3] ·G 可知，信息码与生成矩阵 G 的乘积就是编好以后的(7,4)汉明码，而生成矩阵 G 又是已知的，由式(1.1.9)得 1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1

所以，可以得出如下方程组 a6 = a6 a5 = a5 a4 = a4 a3 = a3 a2 = a6 + a5 + a4 a1 = a6 + a5 + a3 a0 = a6 + a4 + a3 根据此式子编出编码程序。 3. 实验过程及结果 1、哈弗曼编码例如：当 p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4 则根据其原理得到的 matlab 程序如下： clc; clear; A=[0.3,0.15,0.05,0.1,0.4];%信源消息的概率序列 A=fliplr(sort(A));%按降序排列 T=A; [m,n]=size(A); B=zeros(n,n-1);%空的编码表（矩阵） for i=1:n B(i,1)=T(i);%生成编码表的第一列 end r=B(i,1)+B(i-1,1);%最后两个元素相加 T(n-1)=r; T(n)=0; T=fliplr(sort(T)); t=n-1; for j=2:n-1%生成编码表的其他各列 for i=1:t

B(i,j)=T(i); end K=find(T==r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在 %该列的位置 r=(B(t-1,j)+B(t,j));%最后两个元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T)); t=t-1; end B;%输出编码表 END1=sym('[0,1]');%给最后一列的元素编码 END=END1; t=3; d=1; for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码 for i=1:t-2 if i>1 & B(i,j)==B(i-1,j) d=d+1; else end d=1; B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp==B(i,j)); END(i)=END1(x(d)); end y=B(n,j+1); END(t-1)=[char(END1(y)),'0']; END(t)=[char(END1(y)),'1']; t=t+1;

END1=END; end A%排序后的原概率序列 END%编码结果 for i=1:n [a,b]=size(char(END(i))); L(i)=b; end avlen=sum(L.*A)%平均码长 H1=log2(A); H=-A*(H1')%熵 P=H/avlen%编码效率输出结果：

费诺编码：同样，例如：p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4 时根据其原理所得到的 matlab 程序如下： clc; clear; A=[0.3,0.15,0.05,0.1,0.4]; A=fliplr(sort(A));%降序排列 [m,n]=size(A); for i=1:n B(i,1)=A(i);%生成 B 的第 1 列 if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a) end %生成 B 第 2 列的元素 a=sum(B(:,1))/2; for k=1:n-1 end for i=1:n%生成 B 第 2 列的元素 break; end if i<=k else end B(i,2)=0; B(i,2)=1; end %生成第一次编码的结果 END=B(:,2)'; END=sym(END); %生成第 3 列及以后几列的各元素 j=3; while (j~=0) p=1; while(p<=n) x=B(p,j-1); for q=p:n if x==-1 break; else if B(q,j-1)==x y=1; continue;

分享到：

赞收藏

资料库

哈弗曼费诺汉明码matlab.docx

相关推荐

开发技术

热门标签

最新资料