信息论与编码原理课程实验

《信息论与编码》课程实验湖南大学计算机与通信学院2010年5月1日目录TOC\o"1-5"\h\z\o"CurrentDocument"课程实验大纲3\o"CurrentDocument"实验一信道容量的迭代算法程序设计4\o"CurrentDocument"实验二唯一可译码判决准则9实验三Huffman编码方案程序设计15实验四LZW编码方案程序设计20\o"CurrentDocument"实验五Shanoon编码方案程序设计23实验六循环码的软件编、译码实验27\o"CurrentDocument"实验七BCH码最大似然译码器设计31

课程实验大纲课程名称实验条件和设备软件包实验地点设备名称实验验收信息论与编码原理C语言软件包湖南大学通信工程实验室计算机学生在自行计算机上完成实验，在由老师组织验收检查报告，在实验周进行统一时间考核。VHDL语言软件包实验项目内容和要求序号实验内容相应软件与实验要求实验一信道容量迭代算法程序设计掌握相应实验原理和算法C语言数值计算程序的设计和调试实验二唯一可译码判决准则程序设计掌握相应实验原理和算法C语言字符串处理程序的设计和调试实验三Huffman编码方案程序设计掌握相应实验原理和算法C语言递归程序的设计调试实验四LZW编码方案程序设计掌握相应实验原理和算法C语言设计和调试中进制转换、数值与字符串之间的

转换等技术实验五Shanoon编码方案程序设计掌握相应实验原理和算法C语言设计和调试中进制转换、数值与字符串之间的转换等技术实验六（15、7）循环码一般编、译码电路实现研究掌握相应实验原理和算法工程实现方法研究实验七大数逻辑可译码编、译码算法实现研究掌握相应实验原理和算法工程实现方法研究实验一信道容量的迭代算法程序设计一、实验目的（1）进一步熟悉信道容量的迭代算法；（2）学习如何将复杂的公式转化为程序；（3）掌握C语言数值计算程序的设计和调试技术。二、实验要求（1）已知：信源符号个数r、信宿符号个数s、信道转移概率矩阵P。（2）输入：任意的一个信道转移概率矩阵。信源符号个数、信宿符号个数和每个具体的转移概率在运行时从键盘输入。（3）输出：最佳信源分布P*，信道容量C。三、信道容量迭代算法P1：procedureCHANNELCAPACITY(r,s,(ji))2：initialize:信源分布Pi=1/r，相对误差门限°，C=—"

3:repeat4：JPjiJ寸旗PPijii=15：exp(£plog8)ji2ijJ=1£exp(£plog8)ji2ijr=1J=16：log[&xp(£Plog8)]2ji2ijCr=1j=1AC<cC7:until8：outputP*=^P^r,C9:endprocedure四、参考代码2十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十/********************************************************************HopLee2003.06.25GPLCaculatethecapacityofagivenHopLee2003.06.25GPLCaculatethecapacityofagivenchannel*Date:^Copyright:Purpose:十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个/#include<stdio.h>#include<math.h>#include<stdlib.h>#include<unistd.h>#include<values.h>#defineDELTA1e-6/*delta,thethreshold*/intmain(void){registerinti,j;registerintk;intr,s;float*p_i=NULL;float**p_ji=NULL;float**phi_ij=ij=NULL;floatC,C_pre,validate;float*sum=NULL;floatp_j;/*Readthenumberofinputsymbol:r,*andthemumberofoutputsymbol:s*/fscanf(stdin,”%d”,&r);fscanf(stdin,”%d”,&s);/*Allocationmemoryforp_i,p_jiandphi_ij*/p_i=(float*)calloc(r,sizeof(float));p_ji=(float**)calloc(r,sizeof(float));for(i=0;i<r;i++)p_ji[i]=(float*)calloc(s,sizeof(float));phi_ij=(float**)calloc(r,sizeof(float*));for(i=0;i<r;i++)phi_ij[i]=(float*)calloc(s,sizeof(float))/*Readthechanneltransitionprobabilitymatrixp_ji*/for(i=0;i<r;i++)for(j=0;j<s;j++)fscanf(stdin,”%f”,&p项[i][j]);/*Validatetheinputdata*/for(i=0;i<r;i++){validate=0.0;for(j=0;j<s;j++){validate+=p_ji[i][j];}if(fabs(validate-1.0)>DELTA){fprintf(stdout,"invalidinputdata.\n");exit(-1);fprintf(stdout,"Starting..\n");/^initializethep_iandphi_ij*/for(i=0;i<r;i++){p_i[i]=1.0/(float)r;}/*initializeCanditerationcounter:k,andtemproryvariable*/C=-MAXFLOAT;/*MAXFLOATwasdefinedin<values.h>k=0;sum=(float*)calloc(r,sizeof(float));/*Startiterate*/do{k++;/*Calculatephi_ij(k)first*/for(j=0;j<s;j++){p_j=0.0;for(i=0;i<r;i++)p_j+=p_i[i]*p_ji[i][j];if(fabs(p_j)>=DELTA)for(i=0;i<r;i++)phi_ij[i][j]=p_i[i]*phi_ji[i][j]/p_j;elsefor(i=0;i<r;i++)phi_ij[i][j]=0.0;}/*calculatep_i(k+1)then*/p_j=0.0;for(i=0;i<r;i++){sum[i]=0.0;for(j=0;j<s;j++){/*preventdividedbyzero*/if(fabs(phi_ij[i][j])>=DELTA)sum[i]+=p项[i][j]*log2(phi_ij[i][j])/log2(2.0);}sum[i]=pow(2.0,sum[i]);p_j+=sum[i];}for(i=0;i<r;i++){p_i[i]=sum[i]/p_j;}/*andC(k+1)*/C_pre=C;C=log2(p_j)/log2(2.0);}while(fabs(C-C_pre)/C>DELTA);free(sum);sum=NULL;/*Outputtheresult*/fprint(stdout,"Theiterationnumberis%d.\n\n",k);fprint(stdout,"Thecapacityofthechannelis%.6fbit/symbol.\n\n",C);fprint(stdout,"Thebestinputprobabilitydistributionis:\n");for(i=0;i<r;i++)fprint(stdout,”％.6f”,p_i[i]);fprint(stdout,”\n”)；/*Freethememoryweallocationbeforewithstacksequence*/for(i=s-1;i>=0;i--){free(phi_ij[i]);phi_ij[i]=NULL;}free(phi_ij);phi_ij=NULL;for(i=r-1;i>=0;i--){free(p_ji[i]);p_ji[i]=NULL;}free(p_ji);p_ji=NULL;free((p_i);p_i=NULL;exit(0);}实验二唯一可译码判决准则一、实验目的（1）进一步熟悉唯一可译码判决准则；（2）掌握C语言字符串处理程序的设计和调试技术。二、实验要求（1）已知：信源符号个数q、码字集合C。（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3）输出：判决（是唯一可译码/不是唯一可译码）。三、唯一可译码判决准则算法1：procedureUNIQUEDECODABLE(C)2:forallW.,W.ECdo3:ifW.是W.的前缀then

4:将相应的后缀作为一个尾随后缀码放入集合F0中5:endif6:endfor7:loop8:forallW.ECdo9:forallW.EFdo10:ifW.是Wj的前缀then11:将相应的后缀作为一个尾随后缀码放入集合F中n+112：elseifWj是W.的前缀then13:将相应的后缀作为一个尾随后缀码放入集合F中n+114:endif15:endfor16:endfor17:F—Fii18：if3W.EF,W.ECthen19:returnFalse20:elseifF中没有出现新的元素then21:retureTure22:endif23:endloop24:endprocedure四、参考代码/********************************************************************ChenMinRuChenMinRu2004.03.16GPLFindoutwhetheracodeisuniquedecodableornot*Date:*Copyright：*Purpose:““““““““““““““““““““““““““““““““““““““““““““““““““““小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小include<stdio.h>include<math.h>include<stdlib.h>include<unistd.h>include<values.h>include<string.h>include"ourhdr.h"intscomp(char**C,intn,int*l);voidcompline(char*C,intcline,char*D,intdline,char**E,int*elinenum);intjudge(char**C,intcrow,char**E);interow;intmain(void){registerinti;intn,l;int*l_i;char**C;/*Readthenumberofinputsymbol:n*/fscanf(stdin,”％d”,&n);/^Allocationmemoryforl_iand*C[i]*/l_i=(int*)calloc(n,sizeof(int));C=(char**)calloc(n,sizeof(char*));/*Readthecodeanditslengthin*/for(i=0;i<n;i++){fscanf(stdin,”％d”,&l_i[i]);l=l_i[i];一C[i]=(char*)calloc(l,sizeof(char));fscanf(stdin,”％s”,C[i]);}fprintf(stdout,”Starting...\n\n”)；i=scomp(C,n,l_i);/*Outputtheresult*/if(i==0)fprintf(stdout,”Theisuniquedecodable.\n”)；elseif(i==1)fprintf(stdout,”TheisNOTuniquedecodable.'n");elsefprintf(stderr,"Error!\n");/*Freethememoryweallocationbeforewithstacksequeue*/for(i=n-1;i>=0;i--){free(C[i]);}free(*C);free(l_i);exit(0);}/^CompareC,DandE*/intscomp(char**C,intn,int*l){inti;intcrow,drow;char**D,**E;int*dlinenum,*elinenum;intdrownum;/*Allocationsoacetodlinenum[i]andelinenum[i]*/dlinenum=(int*)calloc(n,sizeof(int));/*Forthefirsttime,DhasthesamelengthwithC*/D=(char**)calloc(n,sizeof(char*));for(i=0;i<n;i++){dlinenum[i]=l[i];D[i]=(char*)calloc(l[i],sizeof(char));}drownum=n;/*Forthefirsttime,letD=C*/for(i=0;i<n;i++)strcpy(D[i],C[i]);/*CompareCandD*/compare:erow=1;E=(char**)calloc(n,sizeof(char*));for(i=0;i<n;i++){E[i]=(char*)calloc(n,sizeof(char));}elinenum=(int*)calloc(n,sizeof(int));for(crow=0;crow<n;crow++){for(drow=0;drow<drownum;drow++){compline(C[crow],l[crow],D[crow],dlinenum[drow],E,elinenum);}}/*CompareDandC*/for(drow=0;drow<drownum;drow++){for(crow=0;crow<n;crow++){compline(D[drow],dlinenum[drow],C[drow],l[crow],E,elinenum);}}i=judge(C,crow,E);if(i!=1&&i!=0)/*LetD=Eandgooncomparing*/{drownum=erow-1;realloc(D,drownum);realloc(dlinenum,drownum);for(i=drownum-1;i>=0;i--){dlinenum[i]=elinenum[i];realloc(D[i],dlinenum[i]);strcpy(D[i],E[i]);free(E[i]);}free(*E);free(elinenum);gotocompare;}else{for(i=erow-2;i>=0;i--){free(E[i]);}for(i=drownum-1;i>=0;i--){free(D[i]);}free(*D);free(*E);free(dlinenum);free(elinenum);if(i==1)/*It’sNOTuniquedecodable*/return1;elseif(i==0)/*It’suniquedecodable*/return0}}intjudge(char**C,intcrow,char**E){inti,j;if(ero==1)return0;/*Stoptheprocessing*/for(i=0;i<crow;i++)for(j=0;j<erow-1;j++)if(strcmp(C[i],E[j])==0)return1;/*Stoptheprocessing*/return2;voidcompline(char*C,intcline,char*D,intdline,char**E,int*elinenum){if(cline<dline){if(strncmp(C,D,cline)==0){/^Reallocate*/realloc(E,erow);realloc(elinenum,erow);elinenum[eorw-1]=dline-cline;realloc(E[erow-1],dline-cline+1);/*Copythelastdline-clinecodeintoE*/strncpy(E[erow-1],&D[cline],dline-cline+1);erow++;}}}实验三Huffman编码方案程序设计一、实验目的进一步熟悉Huffman编码过程；掌握C语言递归程序的设计和调试技术。二、实验要求输入：信源符号个数r、信源的概率分布P；输出：每个信源符号对应的Huffman编码的码字。三、Huffman编码算法描述1：procedureHUFFMAN({s.},{p.})2：ifq==2then3：returns0f0,s厂14：else5：降序排序｛p「6：缩减信源：创建一个符号s’以取代sq_2,sq_1，其概率为p’=pq_2+Pq_17：递归调用Huffman算法以得到s0，…，s3，s’的编码：w0，…，w3,w’，相应的概率分布为p0，…，p3,p’8：returns0fw0，…，s3-^w3,s2^w'0，s1^w'19：endif10：endprocedure四、参考代码/*********************************************************************Author:ChenMinRu*Date:2004.03.15^Copyright:GPL*Purpose:Huffmanrecursivecodingalgorithm********************************************************************/#include<stdio.h>include<stdlib.h>include<string.h>include<math.h>#defineDELTA1.0e-6voidsort(double*,char**,int*,int);voidcode(double*,char**,int*,int);intmain(void){float*p_i,*p;floatsum;floattemp;char**c;int*idx;intq;inti;/*Readthenumberofsourcesymbolin*/fscanf(stdin,”％d”,&q);/^Allocationmemory*/idx=(int*)calloc(q,sizeof(int));p_i=(float*)calloc(q,sizeof(float));p=(float*)calloc(q,sizeof(float));c=(char**)calloc(q,sizeof(char*));for(i=0;i<q;i++){c[i]=(char*)calloc(1,sizeof(char));c[i][0]=’\0’；}/*Readtheprobabilityofeachsymbolinandvalidatethem*/sum=0.0;for(i=0;i<q;i++){fscanf(stdin,”％仁&p[i]);p_i[i]=p[i];idx[i]=i;sum+=p_i[i];}if(fabs(sum-1.0)>DELTA){fprintf(stderr,”p_ierror\n”)；exit(-1);}/*Coding*/code(p_i,c,idx,q);/*Outputresult*/for(i=0;i<q;i++){fprintf(stdout,”％d%.6f%s\n”,idx[i],p[idx[i]],c[idx[i]]);}/*Freethememory*/for(i=q;i>0;--i){free(c[i]);}free(c);free(p);free(p_i);free(idx);exit(0);}/**Sortingalgorithm*/voidsort(float*p,char**c,int*idx,intq){intfinish=0;inti,j;intl1,l2;char*s;floatt;while(i<q&&!finish){finish=1;for(j=0;j<q-i;j++){if(p[j]<p[j+1]){t=p[j];p[j]=p[j+1];p[j+1]=t;l1=idx[j];idx[j]=idx[j+1];idx[j+1]=l1;l1=strlen(c[j]);l2=strlen(c[j+1]);s=(char*)calloc(l1+1,sizeof(char));strcpy(s,c[j]);realloc(c[j],l2+1);strcpy(c[j],c[j+1]);realloc(c[j+1],l1+1);strcpy(c[j+1],s);free(s);}}i++；}}/**Huffmanrecursivecodingalgorithm*/voidcode(float*p,char**c,int*idx,intq){intl1,l2;char*s;/*Ifq=2,returnthecodewords*/if(q==2){realloc(c[0],3);realloc(c[1],3);strcat(c[0],”0”)strcat(c[1],”1”)}else{/*ifq>2,reducethesource.*/p[q-2]=p[q-1]+p[q-2];/*Callthecodingalgorithmrecursively*/sort(p,c,idx,q-1);code(p,c,idx,q-1);/*Resumethesourceandreturnthecodewords*/l1=strlen(c[q-2]);l2=strlen(c[q-1]);s=(char*)calloc(l1+2,sizeof(char*));strcpy(s,c[q-2]);realloc(c[q-2],l1+2);strcat(c[q-2],”0”)realloc(c[q-1],l2+2);strcat(s,”1”)strcpy(c[q-1],s);free(s);}}实验四LZW编码方案程序设计一、实验目的（1）进一步熟悉通用编码算法；（2）掌握C语言程序设计和调试过程中数值进制转换、数值与字符串之间的转换等技术。二、实验要求（1）输入：本程序将从标准输入中读入待压缩的数据流；（2）输出：将压缩结果输出到标准输出上去。三、LZW算法描述1：procedureLZW2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF）一次分配给0x00到0xFF的256个单字节字符。3：动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256（即0x100），读入被压缩文件的第一个字符cha,作为待处理单词W。单词的前缀Q为空，即Q=4095,尾字符就是cha，序号（码字）就是cha的序号。4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W］。5：如果字典中已有W］，则将W］看做当前单词W，返回第三步。如果字典中没有W］（发现一个新单词），先将原单词W的序号输出，再加新单词wi，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回第三步。6:endprocedure四、参考代码/*********************************************************************Author:*Date:^Copyright:*Purpose:UseLZWalgorithmtocodethesourcesymbols“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小#include<stdio.h>#include<stdlib.h>#include<conio.h>structword{unsignedintn;unsignedcharc;}w,wd[4096];//Dictionaryunsignedintp,n;unsignedcharh,m,l,f;/*Outputthecode*/voidout(intn){if(f==0){h=n/16;m=(n<<4)&0xf0;f=1;}else{m+=n/256;l=n&0xff;fputc(h,stdout);fputc(m,stdout);fputc(l,stdout);h=m=l=f=0;}}/*Maincopressprogram*/voidlzw(){intc,i;unsignedcharch;fprintf(stderr,"\n\nbegincompress,pleasewait!\n");for(i=0;i<256;i++){//Initializefirst256wordwd[i].n=4095;//indictionarywd[i].c=i;}p=256;w.n=4095;w.c=n=fgetc(stdin);h=m=l=f=0for(;;){c=fgect(stdin);if(c==-1){out(n);if(f)out(4095);fprintf(stderr,"\n\ncompressionisover!\n");return;}ch=c;for(i=n+1;i<p;i++){if(wd[i].n!=n)continue;if(wd[i].c==ch)break;}if(i!=p){w.n=n;w.c=ch;n=i;}else{out(n);if(p<4095){wd[p].n=n;wd[p].c;p++；}w.n=4095;n=w.c=ch;}}}voidmain(void){lzw();}实验五Shanoon编码方案程序设计一、实验目的（1）进一步熟悉Shannon编码算法；（2）掌握C语言程序设计和调试过程中数值的进制转换、数值与字符串之间的转换等技术。二、实验要求（1）输入：信源符号个数q、信源的概率分布p；（2）输出：每个信源符号对应的Shannon编码的码字。三、Shannon编码算法1：procedureSHANNON(q,{Pi})2:降序排列{Pi}3:fori=1►qdo4:F('•)—2冲)5l—lo叩/p(si)]6：将累加概率F(Si)(十进制小数)变换成二进制小数。l7：取小数点后i个二进制数字作为第i个消息的码字。8:endfor9:endprocedure四、参考代码2十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十十/*********************************************************************Author:ChenMinRu*Date:2004.03.15^Copyright:GPL*Purpose:Useshannonalgorithmtocodethesourcesymbolsa、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上vt>个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个include<stdio.h>include<math.h>include<stdlib.h>include<unistd.h>include<values.h>include<string.h>defineDELTA1e-6voidsort(float*,int);intmain(void){registerinti,j;intn;/*Numberofthetotalwords*/inttemp;float*p_i;/^Probabilityoftheword*/float*P_i;/*Cumulateprobability*/int*l_i;/*Codelength*/char**C;/*Codeset*//*Usesumtotestthedataandptostorethetempdata*/floatsum,p;/*Readthenubmerofinputsymbol:n*/fscanf(stdin,"%d",&n);/^Allocationmemoryforp_iand*C[i]*/p_i=(float*)calloc(n,sizeof(float));P_i=(float*)calloc(n,sizeof(float));l_i(int*)calloc(n,sizeof(int));/*Readthechanneltransitionprobabilitymatrixp_iin*/for(i=0;i<n;i++)fscanf(stdin,”％仁&p_i[i]);/*Validatetheinputdata*/sum=0.0;for(i=0;i<n;i++)sum+=p_i[i];if(fabs(sum-1.0)>DELTA)fprintf(stderr,”Invalidinputdata\n”)；fprintf(stdout,”Starting...\n\n”)；/*Sortingthep_idescend*/sort(p_i,n);/^Calculatethebinarynumber’slength*/for(i=0;i<n;i++){p=(-(log2(p_i[i])))/log2(2.0);l_i[i]=(int)ceil(p);}/*AllocateC[i]*/C=(char**)calloc(n,sizeof(char*));for(i=0;i<n;i++){C[i]=(char*)calloc(l_i[i]+1,sizeof(char));C[i][0]=’\0’；}/*CalculatetheP_i[i]*/P_i[0]=0.0for(i=1;i<n;i++)P_i[i]=P_i[i-1]+p_i[i-1];/*TransformP_itobinarymode*/for(i=0;i<n;i++)for(j=0;j<l_i[i];j++){P_i[i]=P_i[i]*2;temp=(int)(P_i[i]);P_i[i]=P_i[i]-temp;if(temp==0)C[i]=strcat(C[i],”0”)；elseC[i]=strcat(C[i],”1”)}}/*Outputtheresult*/fprintf(stdout,”Theoutputcodingis:\n”)；for(i=0;i<n;i++)fprintf(stdout,”％s”,C[i]);fprintf(stdout,”\n\n”)；/*Freethememoryweallocation*/for(i=n-1;i>=0;i--)free(C[i]);free(C);free(p_i);free(P_i);free(l_i);exit(0);}/*Bubblesorting*/voidsort(float*k,intm){inti=1;intj=1;intfinish=0;floattemp;while(i<m&&!finish){finish=1;for(j=0;j<m-i;j++){if(k[j]<k[j+1]){temp=k[j];k[j]=k[j+1];k[j+1]=k[j];finish=0;}i++;}}}实验六循环码的软件编、译码实验一、实验目的（1）通过实验了解循环码的工作原理。（2）了解生成多项式g（x）与编码、译码的关系。（3）了解码距d与纠、检错能力之间的关系。（4）分析（7.3）循环码的纠错能力。二、实验要求用你熟悉的某种计算机高级语言或单片机汇编语言，编制一（7,3）循环码的编、译码程序，并改变接受序列R（x）和错误图样E（x），考查纠错能力情况。设（7，3）循环码的生成多项式为：g（x）=x4+x3+x2+1对应（11101）（1）按编、译码计算程序框图编写编、译码程序（2）计算出所有的码字集合，可纠的错误图样E（x）表和对应的错误伴随式表。（3）考查和分析该码检、纠一、二位错误的能力情况。整理好所有的程序清单，变量名尽量用程序框图所给名称，并作注释。出示软件报告.三、实验设计原理循环码是一类很重要的线性分组码纠错码类，循环码的主要优点是编、译码器较简单，编码和译码能用同样的反馈移存器重构，在多余度相同的条件下检测能力较强，不检测的错误概率随多余度增加按指数下降。另外由于循环码具有特殊的代数结构，使得循环码的编、译码电路易于在微机上通过算法软件实现。1、循环码编码原理设有一(n，k)循环码，码字C=[Cn_i^CrCr_i^C0]，其中r=n-ko码字多项式为:C(X)=Cn_ixn-1+如*+…+CiX+C0°码字的生成多项式为：g(X)=gr_1Xr-1+gr.2Xr-2+^+g1X+g0待编码的信息多项式为：m(X)fE+fm。xn-k.m(x)=Cn1xn-1+・・・+CnKxn-K对于系统码有：Cn-1f，Cn-2=mK-2，^Cn-K=Cr=m0设监督多项式为：r(X)宣尸+…今+乌根据循环码的定义，则有C(x)=xn-Km(x)+r(x)=q(x).g(x)Xn-Km(x)=q(x).g(x)+r(x)r(x)=Rg(x)[xn-Km(x)]即监督多项式是将多项式xn-Km(x)除以g(x)所得的余式。编码过程就是如何根据生成多项式完成除法运算求取监督多项式的过程。设循环码(7.3)码的字多项式为：C(x)=C6x6+C5x5+C4x4+C3x3+C2x2+C1x+C0(n=7)生成多项式为：g(x)=x4+x2+x+1信息多项式为：m(x)=m2x2+m1x+m0(k=3),设：m(x)=x2+x监督多项式为：r(x)=Cr-1Xr-1+^+C1x+C0根据循环码的定义:生成多项式的倍式均是码字，编码实际上是做xn-Km(x)除以g(x)

所得的余式运算求得r(x)。编码程序框图见图1,二进制多项式除法示意图见图2图1编码计算程序框图除法子程序111...商数Ig(x):10111I1100000.xrm(x)+10111第一步11110+10111第二步10010+10111第三步101余式:x2+1图2图1编码计算程序框图除法子程序编码步骤：(1)n-k=r=7-3=4,用x4乘m(x)的运算实际上相当于在信息码110后附上4个0,变为1100000用xm(x)=x4(x2+x)=x6+x5除以g(x),如图1所示,得到监督余式r(x)=x2+1。编出相应的发送码字为：C(x)=xrm(x)+r(x)C=1100000+101=1100101按上述步骤，将得到下述码表：2、译码原理设R(x)为接收码字多项式，E(x)为错误图样多项式，S(x)为伴随式，则根据循环码的性质有：S(x)=Rg(x)[R(x)]=Rg(x)[E(x)]当R(x)=C(x)时，有E(x)=0,S(x)=0当R(x)不等于C(x)时，有E(x)为非0,S(x)为非0译码过程如下：计算每一种可能被纠的错误图样E(x)的伴随式，S.(x)=Rg(x)[E(x)]将其作作为本地数据表存储好。根据已接收码字多项式R(x)，计算相应的伴随式：S(x)=Rg(x)[R(x)]将实际接收码字求出的S(x)与本地存储的各S.(x)相比较，查出两者相等的那个唯一匹配的S.(x)，找出并得到相应的错误图样E(x)。1纠错：C(x)=R(x)+E(x)否则由S(x)找不出唯一匹配的S.(x)，则懒出错信息，表示出现不可纠错的错误图样，即码元出错的个数超出该循环码的纠错能力。译码流程图3所示：译码流程一译码流程二图3译码程序流程图实验七BCH码最大似然译码器设计一、实验目的1、通过实验了解最大似然译码思想。2、掌握最大似然译码的设计步骤。3、了解错误图样的设计与纠、检错能力之间的关系。4、分析(11，7)BCH码的纠错能力。二、实验要求采用VHDL语言或集成电路查表法进行软件仿真设计，完成一个(11，7)BCH码最大似然译码器，接口功能如下：编、译码工作速率为50kb/s〜10Mb/s不等；接收部分具有误码选择功能；所有输入、输出接口都与TTL兼容；具有内部编、译码自环测试能力。三、实验设计原理BCH码是一种具有较强纠错能力的线性分组码。(11,7)BCH码是(15,11)BCH码的缩短码，其生成多项式：g(x)=X4+X+1其最小码矩dmin=3,纠错能力t=1。(11,7)