信息论课程设计

1、 J I A N G S U U N I V E R S I T Y信息论课程设计 学院： 计算机科学与通信工程学院 班级： 信息安全1202 姓名： 强娜 学号： 题目一:判断唯一可译码(一) 任务说明 输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果（是/不是）输入文件:in1.txt，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串 参考算法伪代码：For all do if 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中End ifEnd forLoopFor all do For

2、all doif 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中Else if 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中End ifEnd for End forIf thenReturn falseElse if F 中未出现新的元素 thenReturn trueEnd if/能走到这里，说明F中有新的元素出现，需继续End loop(二) 问题分析唯一可译码的判断方法是:将码C中所有码字可能的尾随后缀组成一个集合F,当且仅当集合F中没有包含任一码字,则可判断此码C为唯一可译变长码。(三) 实现原理 根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据

3、类型并利用指针进行编程来实现算法。算法：1、考察C 中所有的码字，若Wi是 Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中； 2、考察C和Fi俩个集合，若Wi C是 WjF的前缀或Wi F是 WjC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； 3、F=Fi即为码C的尾随后缀集合； 4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素，则返回真。(四) 流程图（见下一页） 开始 输入两个要计算尾随后缀的字符串i=0比较ci、di如果ci=di=/0 Y N如果ci=/0,将d的剩余部分放入尾随后缀集合 Y N如果di=/0,将c

4、的剩余部分放入尾随后缀集合 Y如果ci=di N Ni+； Y break(五) 实现源码 #include#include#includechar c10050;char f30050;int N,sum=0; /N为输入码字的个数，sum为尾随后缀集合中码字的个数int flag; /判断是否唯一可译标志位void patterson(char c,char d) /检测尾随后缀 int i,j,k; for(i=0;i+) if(ci=0&di=0)/2字符串一样，跳出 break; if(ci=0) /d比c长，将d的尾随后缀放入f中 for(j=i;dj!=0;j+) fsumj-i

5、=dj; fsumj-i=0; for(k=0;ksum;k+) if(strcmp(fsum,fk)=0) /*查看当前生成的尾随后缀在f集合中是否存在*/ sum-;break; sum+; break; if(di=0) /c比d长，将c的尾随后缀放入f中 for(j=i;cj!=0;j+) fsumj-i=cj; fsumj-i=0; for(k=0;k100)printf(输入码字个数过大，请输入小于的数n); printf(请输入码字的个数（小于）:); scanf(%d,&N); flag=0; printf(请分别输入码字（每个码字长度小于个字符）:n); for(i=0;iN

6、;i+) scanf(%s,&ci); for(i=0;iN-1;i+)/判断如果码本身是否重复 for(j=i+1;jN;j+) if(strcmp(ci,cj)=0) flag=1;break; if(flag=1)/如果码本身有重复，就可以断定它不是唯一可译码 printf(这不是唯一可译码。n); else for(i=0;iN-1;i+) /*此处是根据原始编码生成的尾随后缀集合s1放入f中*/ for(j=i+1;jN;j+) patterson(ci,cj); for(i=0;i+) /根据原始码与si生成si+1也放入fi int s=0; for(j=0;jN;j+) /*判

7、断si+1中的字符串是否与si中一样，重复的则不再添加*/ if(i=sum) s=1;break; else patterson(fi,cj); if(s=1)break; for(i=0;isum;i+) /*判断p里的字符串是否与s 中重复，重复则不是唯一的*/ for(j=0;jN;j+) if(strcmp(fi,cj)=0) flag=1; break; if(flag=1) printf(这不是唯一可译码。n); else printf(这是唯一可译码。n); printf(尾随后缀集合为:);for(i=0;i=sum;i+)printf(n%s,fi); system (pa

8、use);(六) 运行结果:输入、输出 (七) 设计体会没有做课程设计之前，觉得信息论是一门纯理论的学科，所以要上机实践的话，难免心里很慌也很恐惧，无从下手的感觉，可是通过做这三个题目，从网上查阅了很多相关的资料，然后因为大一的时候学过C+的缘故，所以编程的时候稍微不太费力一些，通过对这道题目的编程，我更加深刻地明白了唯一可译码的定义以及如何判断唯一可译码，循环码的编码与译码，学到了许多课堂上学不到的东西，受益颇多。题目二：循环码的编码与译码（一） 任务内容要求：(7,4)非系统循环码,其中,g(x)= x3+x+1，分别实现编码（多项式乘法）和译码，要求译码可在伴随式法和标准阵列法中随意选择

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

10、小于n，用m(x)除以g(x)，可得余数r(x)，r(x)的次数必小于（n-k），将r(x)加到信息位后作监督位，就得到了系统循环码。下面就将以上各步处理加以解释。（1）用乘m(x)。这一运算实际上是把信息码后附加上（n-k）个“0”。例如，信息码为110，它相当于m(x)+x。当n-k7-34时，m（x）+，它相当于。而希望的到得系统循环码多项式应当是A(x) = m(x) + r(x)。（2）求r(x)。由于循环码多项式A(x)都可以被g(x)整除，也就是： 因此，用m(x)除以g(x)，就得到商Q(x)和余式r(x)，即 这样就得到了r(x)。（3）编码输出系统循环码多项式A(x)为：2

11、.译码过程对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单，通过判断接收到的码组多项式B(x)是否能被生成多项式g(x)整除作为依据。当传输中未发生错误时，也就是接收的码组与发送的码组相同，即A(x)=B(x)，则接收的码组B(x)必能被g(x)整除；若传输中发生了错误，则A(x)B(x)，B(x)不能被g(x)整除。因此，可以根据余项是否为零来判断码组中有无错码。需要指出的是，有错码的接收码组也有可能被g(x)整除，这时的错码就不能检出了。这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。在接收端为纠错而采用的译码方法自然比检错要复杂许多，因此，

12、对纠错码的研究大都集中在译码算法上。我们知道，校正子与错误图样之间存在某种对应关系。如同其它线性分组码，循环编码和译码可以分三步进行：（1）由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；（2）由校正子S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加，纠正错误。上述第（1）步运算和检错译码类似，也就是求解B(x)整除g(x)的余式，第（3）步也很简单。因此，纠错码译码器的复杂性主要取决于译码过程的第（2）步。（三） 流程图除法子程序NNYYC xnkm(x),DC,r=n-kGg(x)系数设循环变量B=KC的第B+r位=0?C+GCG右移一位BB+1B=0?D

13、C+D码字D输出编码流程图 YN初始化可纠错误图样种类总数=N,i=0Gg(x)系数CEi(x)系数,D0调除法子程序求Rg(x)Ei(x)SiCi=i+1i=N?将所有的EI(x)系数=Ei及对应SI造表存储待用YNNNNYY初始化Gg(x)系数,i=0,N赋值输入接收矢量R(x)的系数R,CR(x)系数调除法子程序求Rg(x)R(x)SiC,S=0?S=SI?i=i+1,i=N?出现不可纠的错误图样报错,转下一R(x)译码i=0,C=R+EiR(x)元错输出转下一R(x)译码译码流程一译码流程二（四） 实现源码 #include#include#includevoid main() int

14、 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,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 w10

15、000/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=0,L=8;int f3;int ww10000/4*7;printf(循环码的编码与译码程序:n);printf(请输入你想产生的二进制个数：);scanf(%d,&N); /输入想产生的信源的个数while(N4) printf(输入无效，请重新输入 ); printf(请输入你想产生的二进制个数：); scanf(%d,&N); printf(随机产生的二进制序列为：n); srand( (unsigned)time( NULL ) ); /产生一个随机

16、序列，并把它放入a中for(i=0;iN;i+)aai=rand()%2; printf(%d,aai);printf(n);printf(编码后变为：n);/编码生成码字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;/与生成矩阵相乘 for(i=s;i(s+7);i+)rri=0; rri=qi-s%2; printf(%d,rri);/将生成的放入rr中 y=y+4;/向后移动位 s=s+7;/向后移动位 printf(n);printf(经过

17、信道后变为：n);srand( (unsigned)time( NULL ) );for(j=0;jN/4;j+) ccj=rand()%100;/产生一个99的随机数if(ccj9)/当随机数小于时，一个码字产生个错误for(i=D;i=9)&(ccj=30)/当随机数在30时，一个码字产生一个错误ddj=rand()%7; p=ddj; /随机产生一个6的数，以确定是码字一个错误的位置for(i=D;i(D+7);i+)wi=0;wi=(rri+epi-D)%2;printf(%d,wi);else/当随机数在99时，不发生错误for(i=D;i(D+7);i+)wi=0;wi=rri; printf(%d,wi);D=D+7;/向后移动位printf(%6d,ccj);/进行跟踪，以确定码字错几位printf(n);printf(经过译码后变为: n);for(i=0;iN/4;i+)for(j=0;j3;j+)fj=0;for(k=A;kA+7;k+)fj+=wk*H