信息论课程设计报告

1、xx大学信息论课程设计学院：2015.01.04姓名：学号：指导老师：完成日期:、判定唯一可译码1 .任务说明：输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果(是/不是)输入文件：in1.txt,含至少2组码，每组的结尾为"$”符输出文件:out1.txt,对每组码的判断结果说明：为了简化设计，可以假定码字为0,1串2 .问题分析、实现原理判定唯一可译码根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。算法：1、考察C中所有的码字，若Wi是Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中；2、考察C和F

2、i俩个集合，若Wi6C是Wj6F的前缀或WiF是Wj6C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；3、F=UFi即为码C的尾随后缀集合；4、若F中出现了C中的元素，算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素则返回真。3 .源代码：#include<iostream>#includestdlib.h#include<string>usingnamespacestd;structstringschar*string;structstrings*next;structstringsFstr,*Fh,*FP;/输出当前集合voidoutput

3、str(strings*str)docout<<str->string<<endl;str=str->next;while(str);cout<<endl;inlineintMIN(inta,intb)returna>b?b:a;)inlineintMAX(inta,intb)(returna>b?a:b;)#definelength_a(strlen(CP)#definelength_b(strlen(tempPtr)/判断一个码是否在一个码集合中，在则返回，不在返回intcomparing(strings*st_string,ch

4、ar*code)(while(st_string->next)(st_string=st_string->next;if(!strcmp(st_string->string,code)return0;)return1;)/判断两个码字是否一个是另一个的前缀，如果是则生成后缀码voidhouzhui(char*CP,char*tempPtr)(if(!strcmp(CP,tempPtr)(cout<<集合C和集合F中有相同码字尺<<endl<<CP<<endl<<不是唯一可译码码组褪<<endl;exit(

5、1);)if(!strncmp(CP,tempPtr,MIN(length_a,length_b)(structstrings*cp_temp;cp_temp=new(structstrings);cp_temp->next=NULL;cp_temp->string=newcharabs(length_a-length_b)+1;char*longstr;longstr=(length_a>length_b?CP:tempPtr);/将长度长的码赋给longstr/取出后缀for(intk=MIN(length_a,length_b);k<MAX(length_a,le

6、ngth_b);k+)cp_temp->stringk-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;)main()void(/功能提示和程序初始化准备cout<<tt判定唯一可译码展中<<endl;structstringsCstr,*Ch,*CP,*tempP

7、tr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;charc=码字集合？尺；Ch->string=newcharstrlen(c);strcpy(Ch->string,c);Ch->next=NULL;charf=后缀集合？尺；Fh->string=newcharstrlen(f);strcpy(Fh->string,f);Fh->next=NULL;intCnum;/待检测码的个数cout<<输入待检测码字的个数尺；cin>>Cnum;cout<<输入待检测码，每输入一个都按回车键结束：&

8、lt;<endl;for(inti=0;i<Cnum;i+)(cout<<第<<i+1<<个码字是<<:;chartempstr10;cin>>tempstr;CP->next=new(structstrings);CP=CP->next;CP->string=newcharstrlen(tempstr);strcpy(CP->string,tempstr);CP->next=NULL;)outputstr(Ch);CP=Ch;while(CP->next->next)CP=CP-

9、>next;tempPtr=CP;do(tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);)while(tempPtr->next);)outputstr(Fh);structstrings*Fbegin,*Fend;Fend=Fh;while(1)(if(Fend=FP)<<endl;(掘是唯一可译码码组cout<<exit(1);)Fbegin=Fend;Fend=FP;CP=Ch;while(CP->next)(CP=CP->next;tempPtr=Fbe

10、gin;for(;)(tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr=Fend)break;)outputstr(Fh);/输出F集合中全部元素)4 .程序结果截图:编码与译码二、LZW.任务说明：1L<=100内字符构成的输入串，输入序列长度输入：由集合a,b,c,d处理：先编码，再对编码结果译码输出：编码结果，译码结果：in4.txt,含至少两组输入，每组包含满足要求的串输入文件：out4.txt,对每组输入的编码和译码结果输出文件2.问题分析、实现原理编码程序：1().是空的

11、。步骤一：开始时的词典包含所有可能的根，而当前前缀P字符流中的下一个字符。：=步骤二：当前字符CP+C步骤三：判断是否在词典中：。P:=P+。如果“是”，1(如果“否”，则：)2(的码字输出到码字流。把代表当前前缀P添加到词典中。P+C符串-把缀.令P：=Co(3)判断字符流中是否还有字符需要编码：如果“是"，返回到步骤二。如果“否”：输出相应于当前前缀P的码字。结束编码。(2) .译码程序：步骤一：在开始译码时，词典包含所有可能的前缀根。步骤二：当前码字cW:=码字流中的第一个码字。步骤三：输出当前缀-符串string.cW到字符流。步骤四：先前码字pW:=当前码字cWo步骤五：当

12、前码字cW:=码字流中的下一个码字。步骤六：判断当前缀-符串string.cW是否在词典中：(1)如果“是"，则：当前缀-符串string.cW输出到字符流。当前前缀P:=先前缀-符串string.pW。当前字符C:=当前前缀-符串string.cW的第一个字符。把缀-符串P+C添加到词典。(2)如果“否"，则：当前前缀P:=先前缀-符串string.pW。当前字符C:=当前缀-符串string.pW的第一个字符。输出缀-符串P+C到字符流，然后把它添加到词典中。步骤七：判断码字流中是否还有码字要译：(1)如果“是”，就返回到步骤四。(2)如果“否"，结束。3 .

13、源代码：#include<iostream>#include<string>#include<iomanip>usingnamespacestd;stringdic30;/字典中寻找，返回序号intn;intfind(strings)inttemp=-1;for(inti=0;i<30;i+)(if(dici=s)temp=i+1;returntemp;voidinit()(开始时词典包含所有可能的根/;dic1=打；dic2=搜；dic3=授；for(inti=4;i<30;i+)(dici=;voidcode(stringstr)(init(

14、);chartemp2;temp0=str0;temp1='0'stringP=temp;inti=1;intj=4;cout<<编码后的码字为：；while(1)(chart2;t0=stri;t1='0'stringC=t;if(C=)(cout<<?<<find(P);/字典初始憨dic0=/其余为空/初始化/取第一个字符/P为前缀/目前字典存储的最后一个位置/取下一字符/C为字符流中下一个字符/无码字要译，结束/输出代表当前前缀的码字/退出循环，编码结束break;if(find(P+C)>-1)/有码字要译，如

15、果P+磕词典中，则用C扩展P,进行下一步:P=P+C;i+；)else/如果P+C不在词典中，贝ij将P+雕力口至1J词典中，令P:=C(cout<<?<<find(P);stringPC=P+C;dicj+=PC;P=C;i+;)cout<<endl;cout<<生成的词典为：<<endl;for(i=0;i<j;i+)/输出词典中的内容,j为词典的长度(cout<<setw(12)<<i+1<<setw(12)<<dici<<endl;)cout<<en

16、dl;)voiddecode(intc)/译码词典与编码词典相同，将a,b,c设为初始的前缀/pw:先前码字，cw:当前码字/输入码字流的第一个码字，赋给当前码字(init();intpw,cw;cw=c0;intj=3,i;/输出当前字符串到字符流/当前码字赋给先前码字/若当前码字在词典中/输出当前码字锁代表的字符串cout<<译码为：cout<<diccw-1;for(intm=0;m<n-1;m+)(pw=cw;cw=cm+1;if(cw<=j+1)(cout<<diccw-1;chart2;t0=diccw-10;t1='0

17、9;stringk=t;j+;dicj=dicpw-1+k;/将先前码字与当前码字所代表的字符串的首字符连接而成的/字符串添加到词典中)else/若当前码字不在词典中(chart2;t0=dicpw-10;t1='0'stringk=t;j+;/将先前码字与当前码字所代表的字符串的首字符连接而/输出该字符串dicj=dicpw-1+k;/成的字符串添加到词典中cout<<diccw-1;)cout<<endl;cout<<生成的词典为：<<endl;for(i=0;i<j;i+)/输出词典中的内容,j为词典的长度(cout&

18、lt;<setw(12)<<i+1<<setw(12)<<dici<<endl;)cout<<endl;)intmain()/主程序(stringstr;charchoice;while(1)(cout<<瑜H另<<.编码<<IS瑜H另<<.译码H中混;cout<<请选择功能对应的编号：；cin>>choice;if(choice='1')/若选择1则编码(cout<<输入要编码的字符串(由a、b、c、d组成)：;cin>&

19、gt;str;code(str);)elseif(choice='2')/若选择2贝Ll译码(intc30;cout<<准备译码的消息序列的长度是:cin>>n;cout<<准备译码的消息码字依次是：；for(inti=0;i<n;i+)(cin>>ci;)decode(c);)elsereturn0;)/其他选择则退出程序)4 .程序结果截图:三：循环码的编码与译码任务说明：1.，分别实现编码(多项式乘法)和译码，要其中，,g(x)=x3+x+1要求：(7,4)非系统循环码求译码可在伴随式法和标准阵列法中随意选择选择编码时

20、，：in51.txt,包括至少两组待编码的信息元序列输入文件：out51.txt,对每组信息元的编码输出文件选择译码时，串7的0/1输入文件：in52.txt,包括至少2组长为，译码结果输出文件:out52.txt问题分析、实现原理、流程图2.编码过程(1),g(x),也就是从的在编码时，首先需要根据给定循环码的参数确定生成多项式；然后，利用循环码的编码特点，即所有循环码多g(x)次因子中选一个(n-k多项式作为。g(x)式整除，来定义生成多项g(x)都可以被A(x)项式表示信息多项n,k)循环码，m(x)根据上述原理可以得到一个较简单的系统：设要产生除以式，循环码编码方法则其次数必小于k,而

21、m(x)的次数必小于n,用m(x)加到信息位后作监督位，就得到了g(x),可得余数r(x)r(x)(n-k),将，r(x)的次数必小于系统循环码。)译码过程(2对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单，可整除作为依B(x)是否能被生成多项式g(x)以由式(8-37),通过判断接收到的码组多项式，则接收组与发送的码组相同，即A(x)=B(x)据。当传输中未发生错误时，也就是接收的码整除。g(x)wB(x),B(x)不能被B(x)的码组必能被g(x)整除；若传输中发生了错误，则A(x)因此，可以根据余项是否为零来判断码组中有无错码。整除，这时的错码就不能检出了。g(x

22、)需要指出的是，有错码的接收码组也有可能被这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。在接收端为纠错而采用的译码方法自然比检错要复杂许多，因此，对纠错码的研究大都集中在译码算法上。我们知道，校正子与错误图样之间存在某种对应关系。如同其它线性分组码，循环编码和译码可以分三步进行：S(x);B(x)(1)由接收到的码多项式计算校正子(伴随式)多项式；S(x)(2)由校正子确定错误图样E(x)E(x)(3)将错误图样与B(x)相加，纠正错误。)步也上述第(13整除g(x)的余式，第()步运算和检错译码类似，也就是求解B(x)译码器的复杂性主要取决于译码过程的第(2)步。

23、很简单。因此，纠错码所示。错误图样基于错误图样识别的译码器称为梅吉特译码器，它的原理图如图8-7个输入端的逻辑电路，原则上可以采用查表的方法，根据校正识别器是一个具有(n-k)子找到错误图样，利用循环码的上述特性可以简化识3.源代码：<stdio.h>#include<stdlib.h>#include#include<ctime>main()void(aa10000;inti;intN;int0,0,1,0,1,1;定义生成矩阵int/y=0,s=0;intj,k,m;inta4,q7,rr10000/4*7;intp,D=0;intcc2500,dd25

24、00;int0,0,0,1,0,0,int定义错误图样/1,0,0,0,0,0;w10000/4*7;int0,1;intintA=0,M=0,L=8;intf3;intww10000/4*7;printf(tt循环码的编码与译码尺混1!中);printf(请输入你想产生的二进制位数：);scanf(1,&N);/输入想产生的信源的个数while(N<4)(printf(输入无效，请重新输入眇);printf(请输入你想产生的二进制位数：);scanf(W,&N);printf(随机产生的二进制序列为：);srand(unsigned)time(NULL);/产生一个随机

25、序列，并把它放入a口中for(i=0;i<N;i+)(aai=rand()%2;printf(展aai);printf(®混);printf(产生的二进制序列编码后变为：);编码生成码字for(m=0;m<N/4;m+)(for(i=y;i<(y+4);i+)(ai-y=aai;/取出位出来for(j=0；j<7；j+)(qj=0;for(k=0;k<4;k+)qj+=ak*bkj;/与生成矩阵相乘for(i=s;i<(s+7);i+)(rri=0;rri=qi-s%2;printf(l,rri);/将生成的放入rr中y=y+4;/向后移动位s=s+7;/向后移动位printf(®混)；printf(经过信道后变为：);srand(unsigned)time(NULL);for(j=0;j<N/4;j+)(ccj=rand()_x0010_0;/产生一个99的随机数if(ccj<9)/当随机数小于时，一个码字产生个错误(for(i=D;i<(D+7);i+)(wi=0;wi=(rri+e7i-D)%2;printf(眉,wi);elseif(ccj>=9)&&(ccj<=30)当随机数在30时，一个码字产生一个错误(ddj=rand(