信息論與編碼上機報告

1、. 信息論與編碼上機報告學 校： 中國地質(zhì)大學（武漢） 指 導 老 師： 嚴 軍 姓 名： 龍 勛 班 級 序 號： 071112-11 學 號： 20111000681 目 錄1. Lempel Zil 字典編碼································&

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

3、83;··········113. Hamming碼的編碼與解碼····································&#

4、183;··144. 循環(huán)碼的生成與最下距離的計算·································185. 卷積碼的編碼與解碼·········

5、;··································226. 上機心得··············&#

6、183;······································311. Lempel ziv 字典編碼 1.1題目要求：Write a program that executes the Lempe

7、l 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) T

8、he 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算法設(shè)計：（1） 構(gòu)建初始字典。（2）增添開始與結(jié)束標志位。（3）從第一個字符開始讀入，以兩個字符串為一組形成新的字符。（4）判斷新的字符是否存在于字典中，如果存在，則不處理，如果不存在，則將新的字符存進字典中。（5）將新的字符在字典中的位置作為編碼發(fā)送。（6）進行解碼（過程與編碼過程相反）。注：編碼時始終對字符和字符串進行操作，但

9、發(fā)送的始終是對應的字典編號。解碼時始終對 字典編號進行操作，但輸出的是編號對應字符。在編程的過程中對字典的手尾應增添起始標志位，方便處理。 1.3算法流程：開始構(gòu)建初始字典增加初始結(jié)束標志讀入一個字符（temp1）讀入下一個字符（temp2）temp1+temp2是否在字典中NYtemp1=temp1+temp2將temp1+temp2存入字典發(fā)送temp1編號 temp1=temp2 1.4程序代碼：1. 構(gòu)建初始字典：function new_dic = Creat_newdic( )%構(gòu)建初始字典%使用說明：% new_dic = Creat_newdic( );new_dic=zero

10、s(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_news

11、tr( 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);po

13、sition = 0;for i=1:512 if dic(i,1:N)=str position=i; break; endendend5. 字符串相加函數(shù)：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 =

14、LZ_coding( dic_in,str )% 字典編碼之發(fā)送端% 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、9;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_o

16、ut,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('解碼碼失敗，信號結(jié)尾錯誤'); 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; el

19、se 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_o

20、ut = char(str_out); end8. 運行腳本函數(shù)：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 運行結(jié)果：1. 編碼前后字符串結(jié)果比較：2. 編碼與解碼字典比較： 1.6結(jié)果分析： 通過程序運行的結(jié)果可以看到，程序較好地實現(xiàn)了Lempel zil字典編碼與解碼的功能。字典編碼與解碼的過程比較繁雜，需要對字典編碼有較好地認識。在實驗開始的時候，我準備按照教材上介紹的方法進行編碼

22、與解碼，即對不定長的字符串直接與字典進行比較，以為那樣做的話解碼是一個很輕松地過程，但是實際上一個想法的實現(xiàn)并不是像想象的那樣輕松，在用MATLAB實現(xiàn)的過程中遇到了很多問題，后來又重新用了老師上課時講的方法，即開始時對兩個字符合并再開始比較，這樣一來在實現(xiàn)上過程比較長，但是編程的思路比較清晰。2. 計算信道容量 2.1題目要求：Write a compute program that takes in the channel transition probability matrix and computes the capacity of the channel.2.2算法設(shè)計:(1)設(shè)定

23、各信源發(fā)送的初始值。(2)設(shè)定信道轉(zhuǎn)移概率矩陣。(3)計算各信宿的接收概率。(4)將接收概率與設(shè)定的精度進行比較。(5)根據(jù)一定的規(guī)則重新設(shè)定發(fā)送概率。(6)重復（3）（4）（5）直到滿足設(shè)定的精度再結(jié)束計算信道容量。2.3程序流程：開始初始概率設(shè)定計算通過信道得到各碼的概率計算各碼的自信息量I計算所有碼信息量加權(quán)和（S）s-Imax>e N Y根據(jù)自信息量重新分派信源發(fā)送信號的概率C = Imax并輸出結(jié)果2.4程序代碼：1. 信道容量計算：function C,px = Get_C(Pyx,e) M,N=size(Pyx); px(1:N,1)=1/N;py=Pyx*px; whil

24、e (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運行結(jié)果：2.6結(jié)果分析： 通過程序運行的結(jié)果可以看到程序的正確性。但是程序本身也存在一些不足，比如在輸入某些計算中用到的數(shù)據(jù)存在唯一性，或者在輸入過程中如果輸入有誤，不能滿足計算要求時也不能進行調(diào)整與報錯，這是在以后的編程設(shè)計中需要改進的地方。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 an

26、d 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 probabili

27、ty 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算法設(shè)計：（1）根據(jù)m構(gòu)造伴隨矩陣P。（2）根據(jù)給定的伴隨矩陣P構(gòu)造漢明碼的生成矩陣G與奇偶校驗矩陣H。（3）根據(jù)生成矩陣進行編碼。（4）隨機生成錯誤。（5）解碼與糾錯。3.3算法流程: 3.4程序代碼：1. 構(gòu)造伴隨矩陣：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. 構(gòu)造生成矩陣與奇偶校驗矩陣：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);

29、G = I1,P; H = P',I2; end3. 進行編碼：function codeword_out,flag = Encoding( codeword_in,G )% 編碼函數(shù) codeword_out = codeword_in*G; codeword_out = mod(codeword_out,2); flag = 1;end4. 隨機生成錯誤：function codeword_out = Occur_error( codeword_in,p )% 出錯函數(shù)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 )% 解碼函數(shù)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

32、0 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('發(fā)生錯誤,糾正成功查看！'); else msgbox('發(fā)生錯誤,糾正失??！'); end msgbox('查看數(shù)組t可得知出錯位置（錯誤0 正確1）！'); else msgbox('未發(fā)生錯誤！')

33、;end 3.5運行結(jié)果：（1）未發(fā)生錯誤時：（2）發(fā)生錯誤時：3.6結(jié)果分析： 通過運行結(jié)果可以看到，程序在隨機發(fā)生錯誤的過程中有可能出錯也有可能不出錯。出錯的結(jié)果可以根據(jù)WORKSPACE中的數(shù)組t進行查看。由于生成的是（7,4）漢明碼，由理論可知，（7,4）漢明碼只能糾正1bit的錯誤，當發(fā)生的錯誤在2bit以上時，就不能正確地糾正錯誤了。在編碼與解碼的過程中也讓我進一步了解了系統(tǒng)碼的生成與解碼過程。對以后的學習有很大的幫助。4. 循環(huán)碼的生成與最小距離的計算 4.1題目要求： Write a computer program to find the minimum distance o

34、f a cyclic code over GF(q),given the generator polynomial(or the generator matrix)for the code. 4.2算法設(shè)計： （1）根據(jù)循環(huán)碼的生成多項式得到循環(huán)碼的生成矩陣G。 （2）根據(jù)生成矩陣生成所有的碼字。 （3）利用for循環(huán)的嵌套求得所有兩個碼字之間的漢明距離。 （4）比較所有漢明距離求得最小的距離即為所求。 4.3算法流程： 4.4程序代碼：1.生成指定長度指定域的所有碼字：function data = Creat_data(GF,n)% 按照指定的長度在指定域內(nèi)產(chǎn)生所有可能的碼字temp =

35、zeros(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. 根據(jù)已知生成碼字編碼：function codeword = CycCoding(data,g,GF,k)% 根據(jù)已知生成碼字編碼Mg,Ng = size(g);Md,Nd = size(data); fo

36、r 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) distan

37、ce(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運行結(jié)果：4.6結(jié)果分析： 由程序的運行結(jié)果可以看到在給

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 b

39、it stream. 5.2算法設(shè)計：（1）對給定的碼字進行編碼。（2）建立狀態(tài)表用于儲存寄存器的每一個狀態(tài)。（3）根據(jù)碼長確定要使用的寄存器個數(shù)。（4）計算每一條路徑的漢明距離。（5）選擇最小漢明距離的路徑作為解碼結(jié)果。 5.3算法流程： 5.4程序代碼 ：1.將十進制數(shù)轉(zhuǎn)換為 n 位二進制數(shù)：function b = Det2Bin(d,n)% bc = dec2bin(d,n);Mb,Nb = size(bc);for i = 1:Nb b(i) = bc(i)-48;endend2.將八進制數(shù)轉(zhuǎn)為二進制：function Bins = Oct2Bin(Oct)% 將八進制數(shù)轉(zhuǎn)為二進制%

40、 將八進制數(shù)轉(zhuǎn)為十進制并拆分i=1;while Oct Oct_temp(i) = mod(Oct,10); Oct = floor(Oct/10); i = i+1;end% 將十進制數(shù)轉(zhuǎn)為二進制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.編碼函數(shù):function coded_out = Encoding(g,coded_in)Mg,Ng = size(g);G = cell(1,Ng);Max_g = 0;% 將八進制碼字轉(zhuǎn)為二進制并求碼長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,Ma

42、x_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.建立狀態(tài)表：function dic_output = Creat_dic(g)

43、Mg,Ng = size(g);G = cell(1,Ng);Max_g=0;% 將八進制碼字轉(zhuǎn)為二進制并求碼長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)%*假設(shè)輸入為 0 *% dic_output2*i-1,1 = Det2Bin(i-1,

44、Reg); % 寄存器初始狀態(tài) dic_output2*i-1,2 = 0; % 輸入始狀態(tài) 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; % 當前輸出 % 更新后的寄存器狀態(tài) dic_output2*i-1,4 = dic_output2*i-1,2,dic_output2*i-1,1(1:Reg-1); %*假設(shè)輸入為 1 *% dic_output2*i,1 = Det2Bi

45、n(i-1,Reg); % 寄存器初始狀態(tài) dic_output2*i,2 = 1; % 輸入始狀態(tài) 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; % 當前輸出 % 更新后的寄存器狀態(tài) dic_output2*i,4 = dic_output2*i,2,dic_output2*i,1(1:Reg-1);endend5.根據(jù)指定狀態(tài)查找下一個狀態(tài)：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.查找某個狀態(tài)在表中的位置：function pos = Search_di

47、c(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.發(fā)生錯誤模塊：function codeword_out,t = Occur_error( codeword_in,p )% 出錯函數(shù)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); % 創(chuàng)建狀態(tài)表Md,Nd = size(dic);

49、% 所有可能出現(xiàn)的狀態(tài)x1,l_sta = size(dic1,1); % 狀態(tài)長度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_