信息论与编码上机报告.doc

信息论与编码上机报告学 校： 中国地质大学（武汉） 指 导 老 师： 严 军 姓 名： 龙 勋 班 级 序 号： 071112-11 学 号： 20111000681 目 录1. Lempel Zil 字典编码32. 计算信道容量113. Hamming码的编码与解码144. 循环码的生成与最下距离的计算185. 卷积码的编码与解码226. 上机心得311. Lempel ziv 字典编码 1.1题目要求：Write a program that executes the Lempel Ziv algorithm.The input to the program can be the English alphabets.It should convert the alphabets to their ASCII code and then perform the compression routine.It should output the compression achieved.Using this program,find out the compression achieved for the following strings of letters.(i) The Lempel Ziv algorithm can compress the English text by about fifty five percent.(ii)The cat cannot sit on the canopy of the car.1.2算法设计：（1） 构建初始字典。（2）增添开始与结束标志位。（3）从第一个字符开始读入，以两个字符串为一组形成新的字符。（4）判断新的字符是否存在于字典中，如果存在，则不处理，如果不存在，则将新的字符存进字典中。（5）将新的字符在字典中的位置作为编码发送。（6）进行解码（过程与编码过程相反）。注：编码时始终对字符和字符串进行操作，但发送的始终是对应的字典编号。解码时始终对 字典编号进行操作，但输出的是编号对应字符。在编程的过程中对字典的手尾应增添起始标志位，方便处理。 1.3算法流程：开始构建初始字典增加初始结束标志读入一个字符（temp1）读入下一个字符（temp2）temp1+temp2是否在字典中NYtemp1=temp1+temp2将temp1+temp2存入字典发送temp1编号 temp1=temp2 1.4程序代码：1. 构建初始字典：function new_dic = Creat_newdic( )%构建初始字典%使用说明：% new_dic = Creat_newdic( );new_dic=zeros(512,30);new_dic=uint8(new_dic);for i=1:256 new_dic(i,1)=i;end new_dic=char(new_dic);new_dic(257,1:8) = Newchar:;% new_dic(258,1:5)=!stop;new_dic(258,1:7) = Link.; end2. 向字典添加新字符串：function dic_out,flag = Add_newstr( dic_in,newstr )%向字典添加新字符串% 使用方法% dic_out,flag = Add_newstr( dic_in,newstr )dic_out = dic_in;L = size(newstr);flag = 1;position = Search_str(dic_in,Link.);if position=512 flag=0; return;end dic_out(position,:) = 0;dic_out(position,1:L(2) = newstr;dic_out(position+1,1:7) = Link.;end3. 取出字典中指定位置的字符串：function str = Get_str( dic,position )%取出某字典中的指定位置的字符串%使用说明：% str = Get_str( dic,position );% L = size(dic(position,:);for i = 1:30 if(dic(position,i)=0) N = i; else break; endend str(1:N) = dic(position,1:N);end4. 在字典中查找某字符串的位置：function position = Search_str( dic,str )%在字典中查找某字符串%使用方法：% position = Search_str( dic,str ); M,N=size(str);position = 0;for i=1:512 if dic(i,1:N)=str position=i; break; endendend5. 字符串相加函数：function str3 = Plus_str( str1,str2 )% 字符串相加% Detailed explanation goes hereL1 = size(str1);L2 = size(str2); str3(1:L1(2) = str1(1:L1(2); for i = 1:L2(2) str3(i+L1(2) = str2(i);end end6. 编码过程：function code_out,dic_out = LZ_coding( dic_in,str )% 字典编码之发送端% Detailed explanation goes heredic_out=dic_in;M,N=size(str);counter=1; if N=0 code_out(counter) = Search_str(dic_out,Newchar:); counter=counter+1; code_out(counter) = Search_str(dic_out,Link.); return;else code_out(counter)=Search_str(dic_out,Newchar:); counter=counter+1;end temp1=str(1); for i=2:N temp2 = str(i); temp = Plus_str(temp1,temp2); pos = Search_str(dic_out,temp); if pos=0 temp1 = temp; else dic_out,flag = Add_newstr(dic_out,temp); if flag =0 msgbox(编码失败，添加新码失败); break; end code_out(counter) = Search_str(dic_out,temp1); counter = counter+1; temp1 = temp2; endend code_out(counter) = Search_str(dic_out,temp1);counter = counter+1;code_out(counter) = Search_str(dic_in,Link.); end7. 解码过程：function str_out,dic_out = LZ_decoding(dic_in,code_in)%dic_out = dic_in;M,N=size(code_in); if code_in(1) = Search_str(dic_in,Newchar:) msgbox(解码码失败，信号起始错误); return;end if code_in(N) = Search_str(dic_in,Link.) msgbox(解码码失败，信号结尾错误); return;end buf1 = code_in(2); str_out = Get_str( dic_out,buf1 ); for i = 3:(N-1) buf2 = code_in(i); last = Search_str(dic_in,Link.); if buf2 e N Y根据自信息量重新分派信源发送信号的概率C = Imax并输出结果2.4程序代码：1. 信道容量计算：function C,px = Get_C(Pyx,e) M,N=size(Pyx); px(1:N,1)=1/N;py=Pyx*px; while (1) for j=1:N sum_k=0; for k=1:M if(Pyx(k,j) sum_k=sum_k+(Pyx(k,j)*log(Pyx(k,j)/py(k); end end f(j)=exp(sum_k); end x=f*px; Il=log2(x); Iu=log2(max(f); if(Iu-Ile) C=Il; break; else for j=1:N px(j,1)=f(j)*px(j,1)/x; end py=Pyx*px; endend End2. 运行脚本文件：clear;pyx=0.75 0.25 0.25 0.75;e=0.1;C,px=Get_C(pyx,e);2.5运行结果：2.6结果分析： 通过程序运行的结果可以看到程序的正确性。但是程序本身也存在一些不足，比如在输入某些计算中用到的数据存在唯一性，或者在输入过程中如果输入有误，不能满足计算要求时也不能进行调整与报错，这是在以后的编程设计中需要改进的地方。3. Hamming码的编码与解码 3.1题目要求：Write a computer program for a universal binary Hamming encoder with rate(2m-1)/(2m-m-1)The program should take as input the value of m and a bit-stream to be encoded.It should then generate an encoded bit-stream.Develop a program for the decoder also.Now,perform the following takes:(i)Write an error generator module that takes in a bit stream and output another bit-stream after inverting every bit with probability p,i.e,the probability of a bit error is p.(ii)For m=3,pass the Hamming encoded bit-stream through the above-mentioned module and then decode the received words using the decoder block.3.2算法设计：（1）根据m构造伴随矩阵P。（2）根据给定的伴随矩阵P构造汉明码的生成矩阵G与奇偶校验矩阵H。（3）根据生成矩阵进行编码。（4）随机生成错误。（5）解码与纠错。3.3算法流程: 3.4程序代码：1. 构造伴随矩阵：function P = Creat_P( k,m )%建立伴随矩阵counter = 1;P = zeros(k,m); for i = 1:(2m-1) if mod(log2(i),1)=0 t = dec2bin(i,m); for q = 1:m P(counter,q) = t(1,q)-48; end counter = counter+1; endend end2. 构造生成矩阵与奇偶校验矩阵：function G,H = Creat_GH( m )% 建立汉明码生成矩阵和奇偶校验矩阵n = 2m-1;k = 2m-1-m; P = Creat_P( k,m );I1 = eye(k);I2 = eye(n-k); G = I1,P; H = P,I2; end3. 进行编码：function codeword_out,flag = Encoding( codeword_in,G )% 编码函数 codeword_out = codeword_in*G; codeword_out = mod(codeword_out,2); flag = 1;end4. 随机生成错误：function codeword_out = Occur_error( codeword_in,p )% 出错函数M,N=size(codeword_in);codeword_out =zeros(M,N); for j = 1:M for i=1:N if rand(1) Max_g Max_g = Nb; endend% 建立虚拟寄存器Register = zeros(1,Max_g-1);coded_in = coded_in,zeros(1,Max_g-1);Mm,Nm = size(coded_in);coded_out = ;for i = 1:Nm Reg_temp = ; for j = 1:Ng Reg_temp(j) = mod(sum(coded_in(i),Register.*G1,j),2); end coded_out = coded_out,Reg_temp; Register = coded_in(i),Register(1:Max_g-2);endend4.建立状态表：function dic_output = Creat_dic(g)Mg,Ng = size(g);G = cell(1,Ng);Max_g=0;% 将八进制码字转为二进制并求码长for i = 1:Ng bin_temp = Oct2Bin(g(i); G1,i = bin_temp; Mb,Nb = size(bin_temp); if Nb Max_g Max_g = Nb; endend% 建立虚拟寄存器Reg = Max_g-1;status = 2(Reg)*2;dic_output = cell(status,4);for i = 1:2(Reg)%*假设输入为 0 *% dic_output2*i-1,1 = Det2Bin(i-1,Reg); % 寄存器初始状态 dic_output2*i-1,2 = 0; % 输入始状态 Reg_temp = ; for j = 1:Ng Reg_temp(j) = . mod(sum(dic_output2*i-1,2,dic_output2*i-1,1.*G1,j),2); end dic_output2*i-1,3 = Reg_temp; % 当前输出 % 更新后的寄存器状态 dic_output2*i-1,4 = dic_output2*i-1,2,dic_output2*i-1,1(1:Reg-1); %*假设输入为 1 *% dic_output2*i,1 = Det2Bin(i-1,Reg); % 寄存器初始状态 dic_output2*i,2 = 1; % 输入始状态 Reg_temp = ; for j = 1:Ng Reg_temp(j) = . mod(sum(dic_output2*i,2,dic_output2*i,1.*G1,j),2); end dic_output2*i,3 = Reg_temp; % 当前输出 % 更新后的寄存器状态 dic_output2*i,4 = dic_output2*i,2,dic_output2*i,1(1:Reg-1);endend5.根据指定状态查找下一个状态：function next_sta,output = Search_sta(table,status,input)M,N = size(table);next_sta = ;output = ;for i = 1:M cu_sta = cell2mat(table(i,1); cu_input = cell2mat(table(i,2); if cu_sta = status if cu_input = input next_sta = cell2mat(table(i,4); output = cell2mat(table(i,3); end endendend6.查找某个状态在表中的位置：function pos = Search_dic(dic_input,status)M,N = size(dic_input);pos = inf;for i = 1:M s_temp = cell2mat(dic_input(i,2); if s_temp = status pos = i; endendif pos = inf msgbox(解码失败，输入码字有误！);endend7.发生错误模块：function codeword_out,t = Occur_error( codeword_in,p )% 出错函数M,N=size(codeword_in);codeword_out =zeros(M,N);t = zeros(M,N);for j = 1:M for i=1:N if rand(1) = p codeword_out(j,i)= mod(codeword_in(j,i)+1,2); t(j,i) = 1; else codeword_out(j,i) = codeword_in(j,i); end endendend8.维克比解码：function code_out,dic_out = Decoding(g,code_in)Mc,Nc = size(code_in); % 输入的码流长度dic = Creat_dic(g); % 创建状态表Md,Nd = size(dic); % 所有可能出现的状态x1,l_sta = size(dic1,1); % 状态长度x2,l_ctemp = size(dic1,3); % 单个码字长度dic_out = cell(Md/2,10);for i = 1:Md/2 dic_outi,1 = 0; dic_outi,2 = dic2*i,1; dic_outi,3 = 0; dic_outi,4 = ;endpos = Search_dic(dic_out,zeros(1,l_sta);dic_outpos,1 = 1;len_code = floor(Nc/l_ctemp); %信息长度for i = 1:len_code dic_out(:,5:10) = ; dic_out(:,6) = Nc+1; dic_out(:,9) = Nc+1; Reg_temp = code_in(i-1)*l_ctemp+1):(i*l_ctemp); % 取出下一个码字 flag = cell2mat(dic_out(:,1);% 穷举所有的路径 for j = 1:Md/2 if flag(j,1) = 1 next_sta0,output0 = Search_sta(dic,dic_outj,2,0); next_sta1,output1 = Search_sta(dic,dic_outj,2,1); pos0 = Search_dic(dic_out,next_sta0); pos1 = Search_dic(dic_out,next_sta1); dic_outpos0,1 = 1;% 假设下一个码字为 0 if isempty(dic_outpos0,5) offset = 5; else offset = 8; end dic_outpos0,offset = dic_outj,2; dic_outpos0,offset+1 = . dic_outj,3+sum(mod(output0+Reg_temp,2); dic_outpos0,offset+2 = dic_outj,4,0;% 假设下一个码字为 1 if isempty(dic_outpos1,5) offset = 5; else offset = 8; end dic_outpos1,1 = 1; dic_outpos1,offset = dic_outj,2; dic_outpos1,offset+1 = dic_outj,3+sum(mod(output1+Reg_temp,2); dic_outpos1,offset+2 = dic_ou