1、 xx大學(dxu)信息論課程設計 姓名(xngmng)： 學號：學院(xuyun)： 指導老師： 完成日期：2015.01.04一、判定唯一可譯碼1任務說明：輸入：任意的一個碼(即已知碼字個數(shù)及每個具體的碼字)輸出：判決結果（是/不是）輸入文件:in1.txt，含至少2組碼，每組的結尾為”$”符 輸出文件:out1.txt，對每組碼的判斷結果說明：為了簡化設計，可以假定碼字為0，1串2問題分析、實現(xiàn)原理 判定唯一可譯碼 根據(jù)唯一可譯碼的判別方法，利用數(shù)據(jù)結構所學的知識，定義字符串數(shù)據(jù)類型并利用指針進行編程來實現(xiàn)算法。 算法：1、考察C 中所有的碼字，若Wi是 Wj的前綴，則將對應的后綴作為一

2、個尾隨后綴碼放入集合Fi+1中； 2、考察(koch)C和Fi倆個集合(jh)，若Wi C是 WjF的前綴(qinzhu)或Wi F是 WjC的前綴，則將相應的后綴作為尾隨后綴碼放入集合Fi+1中； 3、F=Fi即為碼C的尾隨后綴集合； 4、若F中出現(xiàn)了C中的元素，算法終止，返回假（C不是唯一可譯碼）；否則若F中沒有出現(xiàn)新的元素則返回真。3.源代碼：#include #includestdlib.h#include using namespace std;struct strings char *string; struct strings *next; ; struct strings Fs

3、tr, *Fh, *FP; /輸出當前集合void outputstr(strings *str) do coutstringnext; while(str); coutb?b:a; inline int MAX(int a, int b) return ab?a:b; #define length_a (strlen(CP) #define length_b (strlen(tempPtr) /判斷一個碼是否在一個碼集合中，在則返回，不在返回int comparing(strings *st_string,char *code) while(st_string-next) st_string

4、=st_string-next; if(!strcmp(st_string-string,code) return 0; return 1; /判斷兩個碼字是否一個是另一個的前綴，如果是則生成后綴碼void houzhui(char *CP,char *tempPtr) if (!strcmp(CP,tempPtr) cout集合(jh)C和集合F中有相同碼字:endl CPendl 不是(b shi)唯一可譯碼碼組!next=NULL; cp_temp-string=new charabs(length_a-length_b)+1; char *longstr; longstr=(lengt

5、h_alength_b ? CP : tempPtr);/將長度(chngd)長的碼賦給longstr /取出后綴 for (int k=MIN(length_a,length_b); kstringk - MIN(length_a,length_b)=longstrk; cp_temp-stringabs(length_a-length_b)=NULL; /判斷新生成的后綴碼是否已在集合F里，不在則加入F集合 if(comparing(Fh,cp_temp-string) FP-next=cp_temp; FP=FP-next; void main() /功能提示和程序初始化準備 coutt

6、tt判定唯一可譯碼nstring=new charstrlen(c); strcpy(Ch-string, c); Ch-next=NULL; char f=后綴集合F :; Fh-string=new charstrlen(f); strcpy(Fh-string, f); Fh-next=NULL; int Cnum; /待檢測碼的個數(shù) coutCnum; cout輸入待檢測碼，每輸入一個都按回車鍵結束：endl;for(int i=0; iCnum; i+) cout第i+1個碼字是tempstr; CP-next=new (struct strings); CP=CP-next; CP

7、-string=new charstrlen(tempstr) ; strcpy(CP-string, tempstr); CP-next = NULL; outputstr(Ch); CP=Ch; while(CP-next-next) CP=CP-next; tempPtr=CP; do tempPtr=tempPtr-next; houzhui(CP-string,tempPtr-string); while(tempPtr-next); outputstr(Fh); struct strings *Fbegin,*Fend; Fend=Fh; while(1) if(Fend = FP

8、) cout是唯一(wi y)可譯碼碼組!next) CP=CP-next; tempPtr=Fbegin; for(;) tempPtr=tempPtr-next; houzhui(CP-string,tempPtr-string); if(tempPtr = Fend) break; outputstr(Fh);/輸出F集合(jh)中全部元素 4.程序(chngx)結果截圖： 二、LZW編碼(bin m)與譯碼1任務說明：輸入(shr)：由集合a,b,c,d內字符構成的輸入(shr)串，輸入序列長度L=100處理：先編碼，再對編碼結果譯碼輸出：編碼結果，譯碼結果輸入文件:in4.txt，含

9、至少兩組輸入，每組包含滿足要求的串 輸出文件:out4.txt，對每組輸入的編碼和譯碼結果2. 問題分析、實現(xiàn)原理（1）.編碼程序： 步驟一：開始時的詞典包含所有可能的根，而當前前綴P是空的。 步驟二：當前字符C：=字符流中的下一個字符。 步驟三：判斷P+C是否在詞典中： （1） 如果“是”， P:=P+C。 （2） 如果“否”，則： 把代表當前前綴P的碼字輸出到碼字流。 把綴-符串P+C添加到詞典中。 令P：=C。 （3） 判斷字符流中是否還有字符需要編碼： 如果“是”，返回到步驟二。 如果“否”：輸出相應于當前前綴P的碼字。 結束編碼。 （2）.譯碼程序： 步驟一：在開始譯碼時，詞典包含所

10、有可能的前綴根。 步驟二：當前碼字cW：=碼字流中的第一個碼字。 步驟三：輸出當前綴-符串string.cW到字符流。 步驟四：先前碼字pW：=當前碼字cW。 步驟五：當前碼字cW:=碼字流中的下一個碼字。 步驟六：判斷當前綴-符串string.cW是否在詞典中： （1）如果“是”，則： 當前綴-符串string.cW輸出到字符流。 當前前綴P：=先前綴-符串string.pW。 當前字符C：=當前前綴-符串string.cW的第一個字符。 把綴-符串P+C添加到詞典。 （2）如果“否”，則： 當前前綴P：=先前綴-符串string.pW。 當前字符C：=當前綴-符串string.pW的第一個

11、字符。 輸出綴-符串P+C到字符流，然后把它添加到詞典中。 步驟七：判斷碼字流中是否還有碼字要譯： （1） 如果“是”，就返回到步驟四。 （2） 如果“否”，結束。3.源代碼：#include #include #include using namespace std; string dic30; int n; int find(string s) /字典中尋找(xnzho),返回序號 int temp=-1; for(int i=0;i30;i+) if(dici=s) temp=i+1; return temp; void init() /字典(zdin)初始 dic0=a; /開始時詞典

12、(cdin)包含所有可能的根 dic1=b; dic2=c; dic3=d; for(int i=4;i30;i+) /其余為空 dici=; void code(string str) init(); /初始化 char temp2; temp0=str0; /取第一個字符 temp1=0; string P=temp; /P為前綴 int i=1; int j=4; /目前字典存儲的最后一個位置 cout編碼后的碼字為：; while(1) char t2; t0=stri; /取下一字符 t1=0; string C=t; /C為字符流中下一個字符 if(C=) /無碼字要譯，結束 co

13、ut -1) /有碼字要譯，如果P+C在詞典中，則用C擴展P，進行下一步： P=P+C; i+; else /如果P+C不在詞典(cdin)中，則將P+C添加到詞典中，令P:=C cout find(P); string PC=P+C; dicj+=PC; P=C; i+; coutendl; cout生成(shn chn)的詞典為：endl; for(i=0;ij;i+) /輸出(shch)詞典中的內容,j為詞典的長度 coutsetw(12)i+1setw(12)diciendl; coutendl; void decode(int c) init(); /譯碼詞典與編碼詞典相同，將a,b

14、,c設為初始的前綴 int pw,cw; /pw：先前碼字，cw：當前碼字 cw=c0; /輸入碼字流的第一個碼字，賦給當前碼字 int j=3,i; cout譯碼為：; coutdiccw-1; /輸出當前字符串到字符流 for(int m=0;mn-1;m+) pw=cw; /當前碼字賦給先前碼字 cw=cm+1; if(cw=j+1) /若當前碼字在詞典中 coutdiccw-1; /輸出當前碼字鎖代表的字符串 char t2; t0=diccw-10; t1=0; string k=t; j+; dicj=dicpw-1+k; /將先前碼字與當前碼字所代表的字符串的首字符連接而成的 /

15、字符串添加到詞典中 else /若當前碼字不在詞典中 char t2; t0=dicpw-10; t1=0; string k=t; j+; dicj=dicpw-1+k; /將先前碼字與當前碼字所代表的字符串的首字符連接而 /成的字符串添加到詞典中 coutdiccw-1; /輸出(shch)該字符串 coutendl; cout生成(shn chn)的詞典為：endl; for(i=0;ij;i+) /輸出(shch)詞典中的內容,j為詞典的長度 coutsetw(12)i+1setw(12)diciendl; coutendl; int main() /主程序 string str; c

16、har choice; while(1) coutnntt1.編碼tt2.譯碼nn; coutchoice; if(choice=1) /若選擇1則編碼 coutstr; code(str); else if(choice=2) /若選擇2則譯碼 int c30; coutn; coutn準備譯碼的消息碼字依次是：; for(int i=0;ici; decode(c); else return 0; /其他選擇則退出程序 4.程序結果截圖：三：循環(huán)碼的編碼(bin m)與譯碼1.任務說明：要求(yoqi)：(7,4)非系統(tǒng)(xtng)循環(huán)碼,其中(qzhng),g(x)= x3+x+1，分別

17、實現(xiàn)編碼（多項式乘法）和譯碼，要求譯碼可在伴隨式法和標準陣列法中隨意選擇選擇編碼時，輸入文件:in51.txt，包括至少兩組待編碼的信息元序列 輸出文件:out51.txt，對每組信息元的編碼選擇譯碼時，輸入文件:in52.txt，包括至少2組長為7的0/1串輸出文件:out52.txt，譯碼結果2. 問題分析、實現(xiàn)原理、流程圖（1）.編碼過程在編碼時，首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項式g(x)，也就是從的因子中選一個（n-k）次多項式作為g(x)；然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式A(x)都可以被g(x)整除，來定義生成多項式g(x)。根據(jù)上述原理可以得到一個較簡單的系統(tǒng)

18、：設要產生（n,k）循環(huán)碼，m(x)表示信息多項式，循環(huán)碼編碼方法則其次數(shù)必小于k，而m(x)的次數(shù)必小于n，用m(x)除以g(x)，可得余數(shù)r(x)，r(x)的次數(shù)必小于（n-k），將r(x)加到信息位后作監(jiān)督位，就得到了系統(tǒng)循環(huán)碼。（2）譯碼過程對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目的的譯碼十分簡單，可以由式（8-37），通過判斷接收到的碼組多項式B(x)是否能被生成多項式g(x)整除作為依據(jù)。當傳輸中未發(fā)生錯誤時，也就是接收的碼組與發(fā)送的碼組相同，即A(x)=B(x)，則接收的碼組B(x)必能被g(x)整除；若傳輸中發(fā)生了錯誤，則A(x)B(x)，B(x)不能被g(x)整

19、除。因此，可以根據(jù)余項是否為零來判斷碼組中有無錯碼。需要指出的是，有錯碼的接收碼組也有可能被g(x)整除，這時的錯碼就不能檢出了。這種錯誤被稱為不可檢錯誤，不可檢錯誤中的錯碼數(shù)必將超過這種編碼的檢錯能力。在接收端為糾錯而采用的譯碼方法自然比檢錯要復雜許多，因此，對糾錯碼的研究大都集中在譯碼算法上。我們知道，校正子與錯誤圖樣之間存在某種對應關系。如同其它線性分組碼，循環(huán)編碼和譯碼可以分三步進行：（1）由接收到的碼多項式B(x)計算校正子（伴隨式）多項式S(x)；（2）由校正子S(x)確定錯誤圖樣E(x)；（3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。上述第（1）步運算和檢錯譯碼類似，也就是求

20、解B(x)整除g(x)的余式，第（3）步也很簡單。因此，糾錯碼譯碼器的復雜性主要取決于譯碼過程的第（2）步。基于錯誤圖樣識別(shbi)的譯碼器稱為梅吉特譯碼器，它的原理圖如圖8-7所示。錯誤(cuw)圖樣識別器是一個具有（n-k）個輸入端的邏輯電路，原則上可以采用查表的方法，根據(jù)校正子找到錯誤圖樣(tyng)，利用循環(huán)碼的上述特性可以簡化識3.源代碼：#include #include #include void main() int aa10000; int i; int N; int b47=1,0,0,0,1,0,1,0,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0,

21、1,0,1,1;/定義生成矩陣 int y=0,s=0; int j,k,m; int a4,q7,rr10000/4*7; int p,D=0; int cc2500,dd2500; int e87=1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0, 0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0; /定義錯誤圖樣 int w10000/4*7; int H73=1,0,1,1,1,1,1,1,0,0,1,1,1,0,0,0,1,0,0,0,1; int A=0,M=

22、0,L=8; int f3; int ww10000/4*7; printf(ttt循環(huán)碼的編碼與譯碼:nn); printf(請輸入你想產生的二進制位數(shù)：); scanf(%d,&N); /輸入想產生的信源的個數(shù)while(N4) printf(輸入無效，請重新輸入 ); printf(請輸入你想產生的二進制位數(shù)：); scanf(%d,&N); printf(隨機產生的二進制序列為：); srand( (unsigned)time( NULL ) ); /產生一個隨機序列，并把它放入a中 for(i=0;iN;i+) aai=rand()%2; printf(%d,aai); printf

23、(n); printf(產生的二進制序列編碼后變?yōu)椋?; /編碼生成碼字for(m=0;mN/4;m+) for(i=y;i(y+4);i+) ai-y=aai; /取出位出來 for (j=0;j7;j+) qj=0; for(k=0;k4;k+) qj+=ak*bkj; /與生成(shn chn)矩陣相乘 for(i=s;i(s+7);i+) rri=0; rri=qi-s%2; printf(%d,rri); /將生成(shn chn)的放入rr中 y=y+4;/向后移動(ydng)位 s=s+7;/向后移動位 printf(n); printf(經過信道后變?yōu)椋?; srand( (u

24、nsigned)time( NULL ) ); for(j=0;jN/4;j+) ccj=rand()%100; /產生一個99的隨機數(shù) if(ccj9) /當隨機數(shù)小于時，一個碼字產生個錯誤 for(i=D;i=9)&(ccj=30) /當隨機數(shù)在30時，一個碼字產生一個錯誤 ddj=rand()%7; p=ddj; /隨機產生一個6的數(shù)，以確定是碼字一個錯誤的位置 for (i=D;i(D+7);i+) wi=0; wi=(rri+epi-D)%2; printf(%d,wi); else /當隨機數(shù)在99時，不發(fā)生錯誤 for(i=D;i(D+7);i+) wi=0; wi=rri; printf(%d,wi); D=D+7; /向后移動位 printf(%6d,ccj); /進行跟蹤，以確定碼字錯幾位