信息论与编码上机报告

1、 信息论与编码上机报告学 校： 中国地质大学（武汉） 指 导 老 师： 严 军 姓 名： 龙 勋 班 级 序 号： 071112-11 学 号： 20111000681 目 录1. Lempel Zil 字典编码································&#

2、183;·········32. 计算信道容量······································

3、3;··········113. Hamming码的编码与解码····································

4、83;··144. 循环码的生成与最下距离的计算·································185. 卷积码的编码与解码·········

5、··································226. 上机心得··············

6、83;······································311. Lempel ziv 字典编码 1.1题目要求：Write a program that executes the Lempel

7、 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) Th

8、e 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）进行解码（过程与编码过程相反）。注：编码时始终对字符和字符串进行操作，但发

9、送的始终是对应的字典编号。解码时始终对 字典编号进行操作，但输出的是编号对应字符。在编程的过程中对字典的手尾应增添起始标志位，方便处理。 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

10、(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_newst

11、r( 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 )%取

12、出某字典中的指定位置的字符串%使用说明：% 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);pos

13、ition = 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 = L

14、Z_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,'

15、;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_ou

16、t,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_

17、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.');

18、if buf2 < last temp2 = Get_str( dic_out,buf2 ); str_out = Plus_str(str_out,temp2); temp1 = Get_str( dic_out,buf1 ); temp = Plus_str(temp1,temp2); pos = Search_str( dic_out,temp); if pos=0 dic_out,flag=Add_newstr(dic_out,temp); if flag =0 msgbox('解码码失败，添加新码失败'); break; end buf1 = buf2; els

19、e buf1 = pos; end else temp1 = Get_str(dic_out,buf1); temp = Plus_str(temp1,temp1(1); str_out=Plus_str(str_out,temp); pos = Search_str( dic_out,temp); if pos=0 dic_out,flag=Add_newstr(dic_out,temp); if flag =0 msgbox('解码码失败，添加新码失败'); break; end buf1 = buf2; else buf1 = pos; end; endendstr_ou

20、t = char(str_out); end8. 运行脚本函数：clear; dic=Creat_newdic();str1='aaaaaaa'str2='The Lempel Ziv algorithm can compress the English text by about fifty five precent.'str3 ='There is no proficient,just being injured!' code1,dic_1=LZ_coding(dic,str1);code2,dic_2=LZ_coding(dic,str2)

21、;code3,dic_3=LZ_coding(dic,str3); str_out1,dic_de1=LZ_decoding(dic,code1);str_out2,dic_de2=LZ_decoding(dic,code2);str_out3,dic_de3=LZ_decoding(dic,code3);1.5 运行结果：1. 编码前后字符串结果比较：2. 编码与解码字典比较： 1.6结果分析： 通过程序运行的结果可以看到，程序较好地实现了Lempel zil字典编码与解码的功能。字典编码与解码的过程比较繁杂，需要对字典编码有较好地认识。在实验开始的时候，我准备按照教材上介绍的方法进行编码与

22、解码，即对不定长的字符串直接与字典进行比较，以为那样做的话解码是一个很轻松地过程，但是实际上一个想法的实现并不是像想象的那样轻松，在用MATLAB实现的过程中遇到了很多问题，后来又重新用了老师上课时讲的方法，即开始时对两个字符合并再开始比较，这样一来在实现上过程比较长，但是编程的思路比较清晰。2. 计算信道容量 2.1题目要求：Write a compute program that takes in the channel transition probability matrix and computes the capacity of the channel.2.2算法设计:(1)设定各

23、信源发送的初始值。(2)设定信道转移概率矩阵。(3)计算各信宿的接收概率。(4)将接收概率与设定的精度进行比较。(5)根据一定的规则重新设定发送概率。(6)重复（3）（4）（5）直到满足设定的精度再结束计算信道容量。2.3程序流程：开始初始概率设定计算通过信道得到各码的概率计算各码的自信息量I计算所有码信息量加权和（S）s-Imax>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

24、 (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-Il<e) 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_

25、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

26、 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 probabilit

27、y 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(

28、 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

29、 = 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:

30、M for i=1:N if rand(1) <= p codeword_out(j,i)= mod(codeword_in(j,i)+1,2); else codeword_out(j,i) = codeword_in(j,i); end endendend5. 解码与纠错：function codeword_out,t,error = Deconding( codeword_in,H )% 解码函数M,N = size(H);C,R = size(codeword_in);t = zeros(C,R);error = 0;Ht = H'r = mod(codeword_in*

31、Ht,2); if sum(sum(r)=0 error = 1; for j = 1:C for i=1:N if r(j,:) = Ht(i,:) codeword_in(j,i) = mod(codeword_in(j,i)+1,2); t(j,i) = 1; end end endendfor i = 1:C codeword_out(i,1:N-M) = codeword_in(i,1:N-M);endend6. 运行脚本文件：clear; m=3; p=0.05;G,H = Creat_GH(m); data_in = 1 0 1 1; 1 0 1 1;%data_in = 1 0

32、 1 1;codeword_out,flag = Encoding(data_in,G);erroword = Occur_error(codeword_out,p);data_out,t,error = Deconding(erroword,H); if error if data_in = data_out msgbox('发生错误,纠正成功查看！'); else msgbox('发生错误,纠正失败！'); end msgbox('查看数组t可得知出错位置（错误0 正确1）！'); else msgbox('未发生错误！');

33、end 3.5运行结果：（1）未发生错误时：（2）发生错误时：3.6结果分析： 通过运行结果可以看到，程序在随机发生错误的过程中有可能出错也有可能不出错。出错的结果可以根据WORKSPACE中的数组t进行查看。由于生成的是（7,4）汉明码，由理论可知，（7,4）汉明码只能纠正1bit的错误，当发生的错误在2bit以上时，就不能正确地纠正错误了。在编码与解码的过程中也让我进一步了解了系统码的生成与解码过程。对以后的学习有很大的帮助。4. 循环码的生成与最小距离的计算 4.1题目要求： Write a computer program to find the minimum distance of

34、 a cyclic code over GF(q),given the generator polynomial(or the generator matrix)for the code. 4.2算法设计： （1）根据循环码的生成多项式得到循环码的生成矩阵G。 （2）根据生成矩阵生成所有的码字。 （3）利用for循环的嵌套求得所有两个码字之间的汉明距离。 （4）比较所有汉明距离求得最小的距离即为所求。 4.3算法流程： 4.4程序代码：1.生成指定长度指定域的所有码字：function data = Creat_data(GF,n)% 按照指定的长度在指定域内产生所有可能的码字temp = z

35、eros(GFn,n);data = zeros(GFn,n);for i = 1:(GFn) a = dec2base(i,GF); L = length(a); for j = 1:L temp(i,j) = a(1,L-j+1)-48; endendfor i = 1:(GFn) for j = 1:n data(i,n-j+1) = temp(i,j); endend end2. 根据已知生成码字编码：function codeword = CycCoding(data,g,GF,k)% 根据已知生成码字编码Mg,Ng = size(g);Md,Nd = size(data); for

36、 i = 1:(GFk) if Nd = Mg codeword(i,:) = inf; else codeword(i,:) = mod(data(i,:)*g,GF); end endend3. 计算最小汉明距离：function min_distance = Calculate_D(codeword)% 计算最小汉明距离M,N = size(codeword);counter = 1;for i = 1:M-1 for j = i+1:M distance(counter) = 0; for k = 1:N if codeword(i,k) = codeword(j,k) distanc

37、e(counter) = distance(counter)+1; end end counter = counter+1; endend min_distance = min(distance); end4. 运行脚本文件：clear G = 1 1 1 0 0; 0 1 1 1 0; 0 0 1 1 1; GF = 2; k = 3; data = Creat_data(GF,k); codeword_G = CycCoding(data,G,GF,k); min_d_G = Calculate_D(codeword_G); 4.5运行结果：4.6结果分析： 由程序的运行结果可以看到在给定

38、的域为二元域，码长为3时，对应的G矩阵为3*5的尺寸。对所有的二元域上的码字进行编码后，计算得到的最小汉明距离为2，由给定的WORKSPACE也可以很直观地看到这是符合理论的。5.卷积码的编码与解码 5.1题目要求：Write a Viterbi Decoder in software that takes in the following:(i)code parameters in the Octal Format,and(ii)the received bit-stream The decoder then produces the survivors and the decoded bi

39、t stream. 5.2算法设计：（1）对给定的码字进行编码。（2）建立状态表用于储存寄存器的每一个状态。（3）根据码长确定要使用的寄存器个数。（4）计算每一条路径的汉明距离。（5）选择最小汉明距离的路径作为解码结果。 5.3算法流程： 5.4程序代码 ：1.将十进制数转换为 n 位二进制数：function b = Det2Bin(d,n)% bc = dec2bin(d,n);Mb,Nb = size(bc);for i = 1:Nb b(i) = bc(i)-48;endend2.将八进制数转为二进制：function Bins = Oct2Bin(Oct)% 将八进制数转为二进制%

40、将八进制数转为十进制并拆分i=1;while Oct Oct_temp(i) = mod(Oct,10); Oct = floor(Oct/10); i = i+1;end% 将十进制数转为二进制Mo,No = size(Oct_temp);Oct_temp(1:No) = Oct_temp(No:-1:1);Bins = ;for i = 1:No det_temp = Det2Bin(Oct_temp(i),3);% det_temp = det3bin(Oct_temp(i); Bins = Bins,det_temp;endMb,Nb = size(Bins);% 将非零开头的部分滤除

41、while Bins(1) Bins = Bins(2:Nb); Nb = Nb-1;endend3.编码函数:function coded_out = Encoding(g,coded_in)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% 建立虚拟寄存器Register = zeros(1,Max

42、_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)M

43、g,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,R

44、eg); % 寄存器初始状态 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

45、(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

46、= 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

47、(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 =

48、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); %

49、 所有可能出现的状态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