信息工程实习报告 信息论部分.doc

信息工程实习报告信息论部分 课 程 名 称 信息论、编码与密码学 姓 名 罗灵 指 导 老 师 严军 班 级 071121-20 学 号 20121000865 中国地质大学（武汉）机电学院 2014/11/26实习一题目要求：1.19写一个执行Lempel-Ziv算法的程序。该程序的输入可以是英文字母。它将该字母转化为它们的ASCII码然后进行压缩。它应该输出压缩结果。用这个程序对下列的字符串所得到的压缩：(1)The Lempel-Ziv algorithm can compress the English text by about fifty five pecent.(2) The cat cannot sit on the canopy of the car.实验原理：首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如print 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出 266所代表的字符串print，在解压缩时，串表可以根据压缩数据重新生成。实验程序：clear;clc;string1=The Lempel Ziv algorithm can compress the English text by about fifty five percent.; str1bin=dec2bin(string1,7);%这里将字符全部转为7位二进制表示mylength,wei=size(str1bin); stringbin= ;for i=1:mylength stringbin=strcat(stringbin, str1bin(i,:);end string=stringbin;%1011001110000000001;% zd=cell(1,100);%申明一个字符串数组zd1,1=string(1);yibijiao=1;fujiabijiao=1;zdlength=1;stringlength=length(string);%二进制表示时的长度while(yibijiao+fujiabijiao=stringlength)%yibijiao实际是上次循环已经比较的 j=1;%j代表字典里面的变量 % equalflag=0； bijiao=string(yibijiao+1); %里面的循环为每一次的循环比较 while(jstringlength) break; end % bijiao=strcat(bijiao,string(yibijiao+fujiabijiao); bijiao=strcat(bijiao,string(yibijiao+fujiabijiao); j=1; else j=j+1;%j代表字典里面的变量 end end % if(equalflag=1) yibijiao=yibijiao+fujiabijiao;%更新已比较的数目 fujiabijiao=1;%附加比较要重新置一 zdlength=zdlength+1;%字典长度+1 zd1,zdlength=bijiao;end zdwei=ceil(log2(zdlength); for i=1:zdlength zd2,i=dec2bin(i,zdwei);end qianling=0;for i=1:zdwei-1 qianling=strcat(qianling,0);endzd3,1=strcat(qianling,zd1,1);for i=2:zdlength ilength=length(zd1,i);%待比较字典的长度 if ilength=1 if zd1,1=1 zd3,i=strcat(qianling,0); else zd3,i=strcat(qianling,1); end else for j=1:i if (isequal(zd1,j,zd1,i(1:ilength-1)%判断待比较的字典的前n-1位和之前那个字典相同 zd3,i=strcat(zd2,j,zd1,i(ilength); break; end end endend output=zd3,1;for i=2:zdlength output=strcat(output,zd3,i);endoutputzd实验结果：实验心得： 通过lz的实验了解lz算法的具体工作原理，了解的lz编码的具体编码方式和与其他编码的不同，利用字典的方式对每一个字符和短语进行编码，在对于较长字符，较多重复字符串的文本中有较高的编码效率。实习二题目要求：2.11写一个程序，它在输入信道转移概率矩阵后计算出信道容量。实验原理：1. 初始化信源分布：（一般初始化为均匀分布），置迭代计算器k=0，设信道容量相对误差门限为，0，可设C（0）=-；2. i=1，.，r，j=1，.，s；3. i=1，.，r；4. ；5. 如果，转第7步；6. 置迭代序号，转第2步；7. 输出*=和的结果；8. 停止。 否是输入结束实验程序：function main()clc; p=1/2 1/4 0 1/4 0 1 0 0 0 0 1 0 1/4 0 1/4 1/2%P：转移概率矩阵channel_cap(p,0.001)function channel_cap(P, e)%e:信道容限n=0;C=0;%C：信道容量C_0=0;C_1=0;r,s=size(P); %r为行，s为列for i=1:r if(sum(P(i,:)=1)%检测概率转移矩阵是否行和为1. error(概率转移矩阵输入有误！) return; end for j=1:s if(P(i,j)1)%检测概率转移矩阵是否负值或大于1 error(概率转移矩阵输入有误！) return; endendendX=ones(1,r)/r%X：输入概率分布fprintf(初始化中间变量矩阵A和B：,n)A=zeros(1,r)B=zeros(r,s)%B：中间变量矩阵fprintf(迭代过程中C_0和C_1以及输入概率分布的变化：,n)while(1) n=n+1;%n：迭代次数 for i=1:r for j=1:s B(i,j)=log(P(i,j)/(X*P(:,j)+eps); end A(1,i)=exp(P(i,:)*B(i,:); %ai end C_0=log2(X*A) C_1=log2(max(A) if (abs(C_0-C_1)e) %满足迭代终止条件停止迭代 fprintf(迭代终止时完后中间变量矩阵A和B：,n) B(r,s)=log(P(r,s)/(X*P(:,s)+eps) A(1,s)=exp(P(r,:)*B(r,:) C=C_0; fprintf(迭代次数: n=%dn,n) fprintf(信道容量: C=%f比特/符号n,C) break; %满足后输出结果并退出 else X=(X.*A)/(X*A) fprintf(-n,n) continue; end End实验结果： 实验心得： 通过本次实验,我更深地得理解了什么是信道，什么是信道容量，什么事离散信道容量，什么是迭代算法，什么是离散信道容量的迭代算法,在理论的掌握基础上,更进一步的实现了程序的运行算法,同时又加深了matlab编程语言上的一些不足和毛病。实习三题目要求：给码率（2m-1）/（2m-1-m）的通用二元汉明码写一个程序，该程序在得到输入m和一个将被编码的比特流时将输出一个编码后的比特流。也给译码器编个程序完成下面的任务：（1）写一个错误生成器模块，在给定的一个比特流作输入时，他的输出流的每个比特流都以概率p发生了改变，即比特错误概率为p。（2）对m=3，将汉明码编码后的比特流输入到上述模块，然后对收到的字用译码器进行译码。实验原理：（1） 错误生成模块：任一给以p，系统任意生成一数，若比p小则让其出错，否则不出错。（2） 编码：由已知的G知道n和k，从而知道m，有c=m*G得到编码码字。（3） 解码： 若v*H=0，则没有出错，直接输出v中前k位； 若v*H!=0,列出所有的e和e*H得到伴随阵s，若能在s中找到一s=v*H,则c0=v-e，输出c0中前k位；若找不到s，则直接输出v中前k位。实验程序：clearclc;a=1 0 0 0 ;display(二进制信源消息标准序列:);a H=1 1 1 0 1 0 0;1 1 0 1 0 1 0;1 0 1 1 0 0 1; %奇偶校验矩阵%在奇偶校验阵H的基础上变出生成矩阵G%P=1 1 1 0;1 1 0 1;1 0 1 1; %P矩阵%I=1 0 0 0;0 1 0 0;0 0 1 0;0 0 0 1;G=I,P; %两个矩阵水平拼接，I;P为竖直拼接%display(生成矩阵:);G c=mod(a*G,2); %mod函数为求余函数，C为信道编码后的码子矩阵% cX1=randerr(1,7,1); %该矩阵即1*14中只有一个1，其余元素均为1%Q=mod(X1+c,2); %该矩阵为产生1比特错误的信道编码矩阵% disp(经过信道后变为：);Q Z=mod(Q*H,2); %为了能够找出一比特的错误%disp(检验出的错误矩阵：);Z %本应该为0，但信道若有噪声它就不为0% %纠正一比特的错误% Q2=zeros(1,7);for i=0 T(i+1)=4*Z(i+1,1)+2*Z(i+1,2)+1*Z(i+1,3); if T(i+1) Q2(i+1,8-T(i+1)=1; end; end T=mod(Q+Q2,2);disp(纠正后的输出码：);T n=size(T);for i=1:n(1) for j=1:4 C(i,j)=T(i,j); endenddisp(输出译码序列:);C实验结果： 实习四 题目要求：4.12 Write a computer program to find the minimum distance of a cyclic code over GF(q),given the generator polynomial(or the generator matrix) for the code. 4.12 写一个程序来计算GF(q)上循环码的最小距离，输入为码的生成多项式（或生成矩阵）。实验原理： 首先利用函数cyclpoly函数来产生(15,4)循环码的所有可能的生成多项式，然后在有可能的生成多项式中任选一个作为(15,4)循环码的生成多项式g，任选一个信息码元m1求其对应的循环码字，具体过程如下：1. 将信息码元m1*x11，即将信息码元左移11位，并将其由多项式形式转化为矩阵形式m2。2. 用g除m2得到余数R,由于在求解余数时是按照一般的算术运算计算的，而实际要求的为模2运算，所以要经过适当的转化，转化为模2运算，得到符合要求的R。3. 将m2与R相加，即得到对应于信息码为m1的码字T。4. 将得到的码字T进行循环移位运算，即得到所有码字。5. 利用与问题一同样的方法即可得到最小汉明距离。实验程序：clear all;close all;syms xn=15;k=4;G=cyclpoly(n,k,all) %求出（15，4）所有的生成多项式g=G(2,:)%1 2 3 %任意选择一个作为（15，4）循环码的生成多项式r=n-k %监督位数 m1=x3+x2+1 %信息码元m11=expand(xr*m1) %用xr乘以m1，相当于对m1进行左移r位的操作m2=sym2poly(m11) %讲多项式m11用矩阵表示Q,R=DECONV(m2,g) %求m2除以g所得的余数R=abs(R)for i=1:length(R)if R(i)=2 R(i)=0endend %由于在求解余数时是按照一般的算术运算计算的，而实际要求的为模2运算，转化为模2运算GF(2)T=R+m2 %T为生成的一个循环码字T2(1,:)=Tfor i=1:14 T2(i+1,:)=circshift(T2(i,:),0,1);%T2为将得到的第一个循环码字进行循环，得到其他的码字endT2(15,:)=circshift(T2(14,:),0,1) %现实最后一个T2C=zeros(1,15);T2 %C矩阵位生成的全部码字t=1;for i=1:15 for j=i+1:16M(t,:)=(C(i,:)=C(j,:);t=t+1; endend %分别比较两行不同的元素S=(sum(M,2) %将M矩阵的每一行求和，得出的人以两个码字之间的距离 d=min(S) %最小汉明距离实验结果： 实验心得： 通过这次实验，对matlab的使用有了一个更加熟练的掌握和了解，更加体会到matlab功能的强大。在这个实验中通过求循环码的生成码字和最小汉明距离等，对这些码字的构成原理有了更加深刻的理解和掌握，受益很深。题目要求： 写一个程序对（35,27）fire码进行编码和译码。他应该自动纠正长度不大于3的突发性错误。如果一个接收到的码字发生了长度为4的突发错误，你试图对他进行译码会怎样呢？实验原理：设计待输入的消息序列；输入生成多项式generater;根据生成多项式确定生成矩阵G和奇偶校验矩阵H；根据生成多项式和生成矩阵进行编码，得到code；对得到的码产生随机错误得到v;根据所有的错误模式，产生相应的伴随矩阵；判断v是否有错，若无措，直接进行相应解码；若无错，在伴随矩阵中查找相应错误模式，若能找到，用c=V-e得到原始编码后，在进行解码；若找不到，直接进行处理。对解码出来的序列和原始序列进行比较观察是都相同。实验程序：clc;clear;n=35;k=27;q=2;% n=35;% k=27;disp(输入的原始序列如下：);yuanshixinxi=round(rand(1,k)%生成原始随机序列a=zeros(1,n+1);a(1)=1;a(n+1)=-1; %a实际长度为n+1g=1 0 1 1 0 1 0 1 1;%这里的g是正序排列的 % g=1 0 1 1%测试序列 G=zeros(k,n); %生成G矩阵for i=1:k G(i,i:n-k+i)=fliplr(g);%倒序排列end%fire_code=cyc_code(g,yuanshixinxi,q,n); h=generate_h(a,g,q); H=zeros(n-k,n); %生成H矩阵for i=1:n-k H(i,i:k+i)=h;end% G% H% mod(G*H.,q)% % % % % % % %所有可能检测到的错误，及伴随矩阵的 生成% % % % % % % % % % % % % s_length=n+n-1+n-2+n-2;%所以突发错误的可能情况s1=eye(n);s2=zeros(n-1,n);for i=1:n-1 s2(i,i:i+1)=1 1;ends3_101=zeros(n-2,n);for i=1:n-2 s3_101(i,i:i+2)=1 0 1;ends3_111=zeros(n-2,n);for i=1:n-2 s3_102(i,i:i+2)=1 1 1;ende=s1;s2;s3_101;s3_111;e_h=mod(e*H.,q);disp(未加噪声的编码:);code=mod(yuanshixinxi*G,q) % % % % % % % % %加噪声% % % % % % % % % % % % % % % % % % % % % % p_error=0.1;v=code;for i=1:n if randp_error v(i)=round(rand); endenddisp(出错后的编码：);v decode=v*H.; % % % % % % % % %下面为解码判断比较部分 % % % % % % % % % % % % % %correct_flag=0;if mod(v*H.,q)=0 disp(解码后的序列如下：n); shang,yushu=deconv(v,fliplr(g);%矩阵生成的码会将g倒置 decode=mod(shang,q)else s=mod(v*H.,q); error_count=0; for i=1:n %统计出错码的位数,与解码无多大关系 if (isequal(code(i),v(i) error_count=error_count+1; end end fprintf(发生了%d个错误n,error_count); % % % % % % % %在 伴随矩阵中是否有相同的错误% % % % % % for i=1:s_length if e_h(i,:)=s %在表中找到了相应的伴随吗 correct_flag=1; temp=mod(v-e(i,:),q); disp(纠错后的码如下：) shang,yushu=deconv(temp,fliplr(g);%矩阵生成的码会将g倒置 decode=mod(shang,q) break end end% % % % % % % %在 伴随矩阵中没有相同的错误时的处理方法 % % % % % if correct_flag=0 disp(It has too many errors!); disp(解码器对源码进行了近似解码：); shang,yushu=deconv(v,fliplr(g);%矩阵生成的码会将g倒置 decode=mod(shang,q) end end fprintf(原信息和解码是否相等：1代表相同，0代表不一样：n%d n. ,isequal(yuanshixinxi,decode)实验结果：实验心得： 通过本次实验，了解fire码的特点，利用G和H的组成形式，形成fire码；用穷举法编程实现多错误生成器，及进一步学习编码解码，区分与循环码的不同。实习五题目要求： 写一个维特比译码软件，它接受下列输入：（1）以八进制形式给出码的参数，以及（2）接收到的比特流实验原理：卷积码的viterbi译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程，并可以纠正接收码字中的错误比特。Viterbi 译码算法步骤如下描述： 根据接收码符号R ,计算出相应的分支量度值BM( R/ Cj) , j = 1 、2 ；进入某一状态的2 条分支量度BM ( R/ Cj)与其前状态路径量度PM累加求和；比较到达当前状态的2 条新的路径量度PM的大小，选择最大者作为新的状态路径量度存储起来，并保存与此路径对应的码字；对所有的256 个状态都实施上述加、比、选(ACS) 运算；在每一译码时刻，满足延时就从256 条留存路径中，选择路径量度最大的一条路径作为译码数据输出；进入下一译码时刻，重复以上步骤，直至译码结束。对于(n，k，m)卷积码，其编码存储度(移位寄存器单元的数量)为m，幸存路径有2m条。每条幸存路径(或信息序列)存储器单元数是n*D，其中，n是卷积码码组宽度，D是需要存储的码组的个数。D的取值一般考虑取m的整倍数，称D为幸存路径长度。编码存储度和幸存路径长度的取值问题关系到芯片规格、传输时延等问题。若D很大，则译码器的存储量太大而难以实用。一般情况下，当译码进行到第5级(每级包括m个时刻)以后，每个状态幸存路径的前几个分支已基本重合在一起，这就是说每个路径存储器不必存储D个很大的码序列。译码时，当译码器接收并处理完第D个码组后，译码器中的幸存路径存储器已全部存满，当译码器开始处理第D+1个码组时，他就对幸存路径存储器中的最顶端的码组做出判决并输出。(1)适当增加幸存路径的长度可以提高译码器的纠错能力。(2)幸存路径的长度在增加到一定值时，译码器纠错能力趋于稳定。当N值增加到6以上，误比特率降低幅度大为减小，曲线有合二为一的趋势。因此，可以认为幸存路径长度D取编码存储度的6倍以上就可以取得比较好的译码性能。（3）选择合适的延时。路经量度(似然度)的累加选取和码字延时判决输出提高了译码的准确性，D 越大越有利于判决的正确性，但是这又和通信的实时性背道而驰，一般D 为卷积码约束长度N的510 倍即可，本文算法D 取50。（4）留存路径的更新的描述。每个状态的留存路径选择实际上是从当前时刻往前推的，例如，在时刻t，又假设到达状态s2 的路径有两个，分别为s4 和s5，对应的输出码字分别是00 和11，我们分别计算出两条路经的分支量度BM，并累加它们对应的前状态路径量度PM_l，发现累加后s5- s2的PM值比s4- s2 的大，所以保留s5 所对应的留存路径，并更新状态s2 所对应的留存路径存储器。对每一状态都做如此比较，保存大的分支量度BM，然后再累加前一状态路径量度PM_l，最后完成所有状态的选择，比较当前所有状态的路经量度PM,选择最大路径，如果延时超过D 就判决输出码字。显然此处判决的码字要延时D 时刻才能移位输出。实验程序：clc;clear;fprintf(原始信息：);xinxi=1 0 1 0 0 1 1 0 1% in=0;input_g=63;str_length=length(input_g);for i=1:str_length g_dec=base2dec(input_g,8); g=num_jinzhi(g_dec,2,3*str_length);endg; %测试g global G;for i=1:str_length G_yuanshi(i,1:3)=g(3*i-2:3*i);endG=G_yuanshi.; % % % % % % % % % %生成查询表格 % % % % % % % % % % % % % % % % % % % % state=init_state;% % % % % % % % % %编码 % % % % % % % % % % % % % % % % % % % % % % % xinxi_bu0=xinxi 0 0;xinxi_length=length(xinxi_bu0);%这里的长度实际为补0后的长度state_temp=0 0;%初始的状态寄存器里面为00for xinxi_index=1:xinxi_length for state_index=1:4 if isequal(state_temp,statestate_index,1) if xinxi_bu0(xinxi_index)=0 code(2*xinxi_index-1:2*xinxi_index)=statestate_index,3; state_temp=statestate_index,4; else if xinxi_bu0(xinxi_index)=1 code(2*xinxi_index-1:2*xinxi_index)=statestate_index,6; state_temp=statestate_index,7; end end break; end endend fprintf(信息编码如下：n);code % % % % % % % %加入错误编码 (这里仅将第三位出错)% % % % % % % % % % % % % % % % % % % % code(3)=code(3);disp(出错后的编码：);code% % % % % % % % % % % % % % % % % % % % % % 第8列表示输入0时由当前状态转到下一状态所增加的距离% 第9列表示输入1时由当前状态转到下一状态所增加的距离% 地10列表示上一时刻到达四种状态后每种累计下来的最小距离% 第11列表示上一时刻解码后累计下来的解码序列，% 第12列表示当前时刻解码后累计下来的解码序列，% 第13列表示当前时刻到达四种状态后每种累计下来的最小距离% % % % % % % % % % % % 解码% % % % % % % % % % % % % % % % % % % % % code_length=length(code);%这里的长度实际为补0后的长度state_temp=0 0;%初始的状态寄存器里面为00%直接将前面两个数据输入后，使四种状态都出现，并统计到达各状态时的最小距离state1,10=min_dist(state1,3,code(1) code(2)+min_dist(state1,3,code(3) code(4);state2,10=min_dist(state1,3,code(1) code(2)+min_dist(state1,6,code(3) code(4);state3,10=min_dist(state1,6,code(1) code(2)+min_dist(state2,3,code(3) code(4);state4,10=min_dist(state1,6,co