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

1、 课程实验信息论与编码课程实验湖南大学计算机与通信学院2010年5月1日第15页共34页目 录课程实验大纲 3实验一信道容量的迭代算法程序设计.4实验二唯一可译码判决准则9实验三Hufma n 编码方案程序设计 15实验四LZW编码方案程序设计 20实验五 Shanoon编码方案程序设计23实验六 循环码的软件编、译码实验 .27实验七 BCH码最大似然译码器设计31课程实验大纲课程名称实验条件和设备软件包实验地点设备名称实验验收信息论与编码原理C语言软件包湖南大学通信工程实验室计算机学生在自行计算机上完成实验，在由老师组织验收检查报 告，在实验周进行统一时间考 核。VHDL语言软件包实验项目

2、内容和要求序号实验内容相应软件与实验要求实验一信道容量迭代算法程序设计掌握相应实验原理和算法C语言数值计算程序的设计和调试实验二唯一可译码判决准则程序设计掌握相应实验原理和算法C语言字符串处理程序的设计和调试实验三Huffman编码方案程序设计掌握相应实验原理和算法C语言递归程序的设计调试实验四LZW编码方案程序设计掌握相应实验原理和算法 C语言设计和调试中进制转换、数值与字符串之间的转换等技术实验五Shanoon编码方案程序设计掌握相应实验原理和算法 C语言设计和调试中进制转换、数值与字符串之间的转换等技术实验六（15、7）循环码一般编、译码电路实现研究掌握相应实验原理和算法工程实现方法研究

3、实验七大数逻辑可译码编、译码算法实现研究掌握相应实验原理和算法工程实现方法研究一、实验目的（1）进一步熟悉信道容量的迭代算法；（2 ）学习如何将复杂的公式转化为程序；（3）掌握C语言数值计算程序的设计和调试技术。二、实验要求（1）已知：信源符号个数 r、信宿符号个数s、信道转移概率矩阵 P。（2 ）输入：任意的一个信道转移概率矩阵。信源符号个数、信宿符号个数和每个具体的转 移概率在运行时从键盘输入。（3）输出：最佳信源分布 P*，信道容量C。三、信道容量迭代算法1: procedure CHANNEL CAPACITY(r,s,(Pji)实验一信道容量的迭代算法程序设计2： initializ

4、e:信源分布Pi=1/r，相对误差门限，C=5:3： repeat4：Pi Pjirp Pjii 1exp(Pji log 2 ij)j 1rsexp( Pji log2 ij)r 1j 16:rsIog2【 exp( pji log2r 1j 1C7： untilC& output P*= ( A )r ,C9: end procedure四、参考代码/*Author:*Date :Hop Lee2003.06.25*Copyright:GPLPurpose:Caculate the capacity of a give n cha nnel*/#i nclude#in clude#i nc

5、lude#i nclude#in clude#define DELTA 1e -6 /* delta,the threshold */int main( void)register int i,j; register int k;in t r,s;float *p_i=NULL;float *p_ji=NULL;float *phi_ij=ij=NULL;float C,C_pre,validate;float * sum=NULL;float p_j;/*Read the nu mber of in put symbols,* and the mumber of output symbols

6、*/fsca nf(stdi n,%d,&r);fsca nf(stdi n,%d,&s);/*Allocati on memory for p_i,p_ji and phi_ij */ p_i=(float *)calloc(r,sizeof(float);p_ji=(float *)calloc(r,sizeof(float);for(i=0;ir;i+)p_jii=(float *)calloc(s,sizeof(float);phi_ij=(float *)calloc(r,sizeof(float*);for(i=O;ir;i+)phi_iji=(float *)calloc(s,s

7、izeof(float)/*Read the channel transition probability matrix p_ji */ for(i=0;ir;i+)for(j=0;js;j+)fsca nf(stdi n,%f,&p_jiij);/*Validate the input data */ for(i=0;ir;i+)validate=0.0;for(j=0;jDELTA)fpri ntf(stdout, in valid in put data. n); exit(-1);fpri ntf(stdout, Start in g.n”/*initialize the p_i an

8、d phi_ij*/for(i=0;ir;i+)P_ii=1.0/(float)r;/* initialize C and iteration counter :k,and temprory variable*/ C=-MAXFLOAT;/*MAXFLOAT was defi ned ink=0;sum=(float *)calloc(r,sizeof(float);/*Start iterate*/dok+;/* Calculate phi_ij(k) first */for(j=0;js;j+)p_j=0.0;for(i=0;i=DELTA)for(i=0;ir;i+)phi_ijij=p

9、_ii* phi_jiij/p_j;elsefor(i=0;ir;i+)phi_ijij=0.0;/*calculate p_i(k+1) the n*/p_j=0.0;for(i=0;ir;i+)sumi=0.0;for(j=0;j=DELTA)sumi+=piij*log 2 ( phi_ijij)/log 2 (2.0);sumi=pow(2.0,sumi);p_j+=sumi;for(i=0;iDELTA);free(sum);sum=NULL;/*Output the result*/fprin t(stdout, ” The iterati on nu mber is %d.nr”

10、k);fpri nt(stdout, ” The capacity of the cha nnel is %.6f bit/symbol.nr”C); fpri nt(stdout, ” The best in put probability distributi on is :n”; for(i=0;i=0;i-)free(phi_iji);phi_iji=NULL;free(phi_ij);phi_ij=NULL;for(i=r-1;i=0;i-)free(p_jii);p_jii=NULL;free(p_ji);p_ji=NULL; free(p)； p_i=NULL;exit(O);实

11、验二唯一可译码判决准则一、实验目的(1) 进一步熟悉唯一可译码判决准则；(2) 掌握C语言字符串处理程序的设计和调试技术。实验要求(1) 已知：信源符号个数 q、码字集合C。(2) 输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。(3) 输出：判决(是唯一可译码 /不是唯一可译码)。三、唯一可译码判决准则算法1: procedure U NIQUE D ECODABLE(C)2: for all W i ,W j C do3: if Wi是 W j的前缀then4:将相应的后缀作为一个尾随后缀码放入集合F0中5: end if6: end for7: loop8: for al

12、lWi C do9: for allW j Fn do10: if Wi 是 W j 的前缀 then11:将相应的后缀作为一个尾随后缀码放入集合Fn 1中12： else if W j 是 W i 的前缀 then13:将相应的后缀作为一个尾随后缀码放入集合Fn 1中14: e nd if15: end for16: end for17: F J Fii18: if Wi F, Wi C then19: retur n False20: else if F 中没有出现新的元素 then21: reture Ture22: e nd if23: end loop24: end procedur

13、e四、参考代码/*# Author:Che n Min Ru*Date:2004.03.16*Copyright: GPL*Purpose : Find out whether a code is unique decodable or not*# in clude# in clude# in clude# in clude# in clude# in clude# in elude ” ourhdr.h ”int scomp(char *C,i nt n ,i nt *1);void compli ne(char *C, i nt cli ne,char *D,int dline,char

14、*E,int *elinenum);int judge(char *C,i nt crow,char *E);int erow;int main(v oid)register int i;int n,l;int *1；char *C;/*Read the nu mber of in put symbol: n*/ fscanf(stdin,” %d，&n);/*Allocation memory for l_i and *Ci*/l_i=(i nt *)calloc( n,sizeof(i nt);C=(char *)calloc( n,sizeof(char *);/* Read the c

15、ode and its len gth in*/for (i=0;i=0;i-)free(Ci);free(*C);free(l_i);exit(0);/*Compare C,D and E */int scomp(char *C,i nt n ,i nt *l)int i;int crow,drow;char *d,*E;int *dli nenu m,* eli nenum;int drow num;/* Allocation soace to dlinenum i and elinenumi*/ dli nenum=(i nt *)calloc( n,sizeof(i nt);/* Fo

16、r the first time,D has the same len gth with C */D = ( char * *)calloc( n, sizeof( char *);for(i = 0;i n;i + +)dli nenum i = li;Di = ( char *)calloc(li,sizeof( char );drow num = n;/* For the first time ,let D = C */for(i = 0;i n;i + +)strcpy(Di,Ci);/* Compare C and D */compare :erow = 1;E = ( char *

17、 * )calloc( n,sizeof( char * );for (i = 0;i n;i + +)Ei = ( char * )calloc( n,sizeof( char );elinenum = ( int * )calloc(n,sizeof( int);for( crow = 0;crow n ;crow +)for( drow = 0;drow drow nu m;drow +)compli ne(Ccrow,lcrow,Dcrow,dli nenu mdrow,E,eli nenu m);/* Compare D and C */for( drow = 0;drow drow

18、 nu m;drow +)for( crow = 0;crow = 0;i -)dli nenu mi = eli nenu mi;realloc(Di,dli nenu mi);strcpy(Di,Ei);free(Ei);free( *E );free( eli nenum );goto compare;elsefor(i = erow 2;i =0;i -)free(Ei);for(i = drow num 1;i = 0;i -)free( Di);free(*D);free(*E);free(dli nenu m);free(eli nenu m);if(i=1) /* It s N

19、OT unique decodable*/ return 1;else if(i=O)/*lt s unique decodable*/ return 0int judge(char *C,i nt crow,char *E)int i,j;if(ero=1)return 0;/* Stop the process ing*/for(i=0;icrow;i+)for(j=0;jerow-1;j+)if(strcmp(Ci,Ej)=0)retur n 1;/* Stop the process ing*/return2; 课程实验void compli ne(char *C,int cline,

20、char *D,int dli ne,char *E, int *eli nenum)if(cli nevdli ne)if(strncmp(C,D,cli ne)=0)/*Reallocate*/realloc(E,erow);realloc(eli nenu m,erow);eli nenu meorw -1=dli ne-cli ne;realloc(Eerow-1,dli ne-cli ne+1);/*Copy the last dline-cline code into E*/strncpy(Eerow-1,&Dcli ne,dli ne-cli ne+1);erow +;实验三Hu

21、ffma n编码方案程序设计一、实验目的(1) 进一步熟悉 Huffman编码过程；(2) 掌握C语言递归程序的设计和调试技术。二、实验要求(1) 输入：信源符号个数 r、信源的概率分布 P；(2) 输出：每个信源符号对应的Huffman编码的码字。三、Huffman编码算法描述1: procedure HUFFMAN(s i ,p i)2： if q=2 then3: return s 00, s 115:降序排序p i 6:缩减信源：创建一个符号 s以取代sq 2,sq !,其概率为p =pq 2+pq 17:递归调用Huffman算法以得到s 0，s q 3,s 的编码：W0，Wq 3

22、, W，相应的概率分布为p0，pq 3，p&return s。w0,，sq 3wq 3 ,s q 2w0, sq 1 T W19：end if10：end procedure四、参考代码/*Author :Che n Min Ru*Date:2004.03.15*Copyright: GPL*Purpose:Huffma n recursive cod ing algorithm *# in clude# in clude# in clude# in clude# define DELTA 1.0e-6void sort(double *,char *,i nt *,i nt); void c

23、ode(double *,char *,i nt *,i nt);intmai n(void)float *p_i,*p; float sum; float temp;char *c; int *idx;int q;int i;/* Read the nu mber of source symbol in */ fscanf(stdin,” %d，&q);/*Allocati on memory*/idx=(i nt *)calloc(q,sizeof(i nt);P_i=(float *)calloc(q,sizeof(float);p=(float *)calloc(q,sizeof(fl

24、oat);c=(char *)calloc(q,sizeof(char *);for(i=0;iq;i+)ci=(char *)calloc(1,sizeof(char);ci0= O;/*Read the probability of each symbol in and validate them*/ sum=0.0;for(i=0;iDELTA)” ”fprintf(stderr,” p_n er)orexit(-1);/*Cod in g*/ code(p_i,c,idx,q);/*Output result*/for(i=0;i0;-i)free(ci);free(c);free(p

25、);free(p_i);free(idx);exit(O);/*Sort ing algorithm*/voidsort(float *p,char *c,i nt *idx,i nt q)int fini sh=0;int i,j;int 11,12;char *s;float t;while(i q&!fin ish)fini sh=1;for(j=0;jq-i;j+)if(pj2,reduce the source.*/ pq-2=pq-1+pq-2;/*Call the coding algorithm recursively*/ sort(p,c,idx,q-1);code(p,c,

26、idx,q-1);/*Resume the source and return the code words*/ l1=strle n(cq-2);l2=strle n(cq-1);s=(char *)calloc(l1+2,sizeof(char *);strcpy(s,cq-2);realloc(cq-2,l1+2);strcat (cq-2, ” 0”)realloc(cq-1,l2+2); strcat(s, ” 1” );strcpy(cq-1,s);free(s);实验四LZW编码方案程序设计一、实验目的（1）进一步熟悉通用编码算法；（2）掌握C语言程序设计和调试过程中数值进制转换

27、、数值与字符串之间的转换等技术。二、实验要求（1）输入：本程序将从标准输入中读入待压缩的数据流；（2）输出：将压缩结果输出到标准输出上去。三、LZW算法描述1: procedure LZW2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF） 次分配给 0x00到0xFF的256个单字节字符。3:动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256 （即0x100），读入被压缩文件的第一个字符cha,作为待处理单词 W。单词的前缀Q为空，即Q=4095，尾字符就是cha，序号（

28、码字）就是 cha的序号。4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W1。5：如果字典中已有 W1，则将W1看做当前单词 W，返回第三步。如果字典中没有 W1 （发现一个新单词），先将原单词 W的序号输出，再加新单词W1，增加到字典中，然后把刚刚读入的字符 CH作为当前单词 W，返回第三步。6:e nd procedure四、参考代码/*Author:*Date:*Copyright :*Purpose : Use LZW algorithm to code the sour

29、ce symbols*#i nclude#i nclude#in cludestruct word un sig ned int n; un sig ned char c;w,wd4096;/Dictio nary un sig ned int p,n;un sig ned char h,m,l,f;/*Out put the code */ void out(i nt n)if(f=O) 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

30、=l=f=0;/* Main copress program */void lzw()int c,i;un sig ned char ch;fprin tf(stderr,nnbegi n compress ,please wait!n); for(i=0;i256;i+)/l ni tialize first 256 word wdi.n=4095; /in dictionary wdi.c=i;p=256;w.n=4095;w.c=n=fgetc(std in);h=m=l=f=0for(;)c=fgect(stdi n); if(c=-1)out( n);if(f)out(4095);f

31、prin tf(stderr,nn compressi on is over!n); return;ch=c;for(i=n+1;ip;i+)if(wdi. n!=n)con ti nue;if(wdi.c=ch)break;if(i!=p)w. n=n;w.c=ch;n=i;else out( n);if(p4095) wdp. n=n; wdp.c; p+；w.n=4095; n= w.c=ch;void ma in (void)lzw();实验五Shanoon编码方案程序设计一、实验目的（1）进一步熟悉 Sha nnon编码算法；（2）掌握C语言程序设计和调试过程中数值的进制转换、数值与

32、字符串之间的转换等 技术。二、实验要求（1） 输入：信源符号个数 q、信源的概率分布 p；（2） 输出：每个信源符号对应的Sha nnon编码的码字。三、Shannon编码算法1: procedure SHANNON( q, Pi )2:降序排列 Pi 3: for i=1 q -do*i 14： F( Si )g)k 15： h - log/ p(si)6:将累加概率F( S )(十进制小数)变换成二进制小数。7:取小数点后h个二进制数字作为第i个消息的码字。8： end for9： end procedure四、参考代码/*Author: Che n Min Ru*Date: 2004.0

33、3.15*Copyright : GPL*Purpose:Use sha nnon algorithm to code the source symbols*# in clude# in clude# in clude# in clude# in clude# in clude# defi ne DELTA 1e -6void sort(float*,i nt);int main(v oid)register int i,j;int n; /*Number of the total words*/int temp;float *p_i; /*Probability of the word*/f

34、loat *P_i; /*Cumulate probability*/int *l_i; /*Code len gth*/char * *C; /*Code set*/*Use sum to test the data and p to store the temp data*/float sum,p;/*Read the n ubmer ofin put symbol: n*/fsca nf(std in ,%d,&n);/*Allocatio n memory for p_i and *Ci */ p_i=(float *)calloc( n,sizeof(float); P_i=(flo

35、at *)calloc (n ,sizeof(float);l_i(i nt *)calloc( n,sizeof(i nt);/* Read the channel transition probability matrix p_i in*/ for(i=0;i n;i+)fscanf(stdi n, ” f”，&p_ii);/*Validate the in put data*/ sum=0.0;for(i=0;i DELTA) fpri ntf(stderr, ” In valid in pirt”atafprintf(stdout, ” Starting -n” );/*Sort in

36、g the p_i desce nd*/sort (p_i, n);/*Calculate the binary number s length*/ for(i=0;i n ;i+)p=(-(log 2 (p_ii) )/log 2 (2.0);l_ii=( in t)ceil(p);/*Allocate Ci*/C=(char *)calloc( n,sizeof(char *);for(i=0;i n;i+)Ci=(char *)calloc(l_ii+1,sizeof(char);Ci0= 0; 一/*Calculate the P_ii*/P0=0.0for(i=1;i n;i+)P_

37、ii=P_ii-1+p_ii-1;/*Transform Pto bi nary mode*/for(i=0;i n;i+)for(j=0;jv|i;j+)P_ii=P_ii*2； temp=(i nt)(P_ii); P_ii=Pi-temp;if(temp=0)Ci=strcat(Ci,” 0” );elseCi=strcat(Ci, ” 1”)/*Output the result*/fprintf(stdout, ” The output coding )s :for(i=0;i =0;i-) free(Ci);free(C);free(p_i);free(P _i);free(l_i

38、);exit(0);/*Bubble sorting*/void sort(float *k,i nt m)int i=1;int j=1;int fini sh=0;float temp;while(im&!fin ish)fini sh=1;for(j=0;jm-i;j+)if(kjkj+1) temp=kj; kj=kj+1; kj+1=kj; fini sh=O; i+；实验六 循环码的软件编、译码实验一、实验目的（1）通过实验了解循环码的工作原理。（2 ）了解生成多项式 g（x）与编码、译码的关系。（3）了解码距d与纠、检错能力之间的关系。（4）分析（7.3）循环码的纠错能力。二、实

39、验要求用你熟悉的某种计算机高级语言或单片机汇编语言，编制一 （7， 3）循环码的编、译码程序，并改变接受序列 R（ x）和错误图样E （ x），考查纠错能力情况。设（7，3）循环码的生成多项式为：g（x） =x4+x3+x2+1对应 （11101）（1）按编、译码计算程序框图编写编、译码程序（2） 计算出所有的码字集合，可纠的错误图样E（x）表和对应的错误伴随式表。（3）考查和分析该码检、纠一、二位错误的能力情况。(4 )整理好所有的程序清单，变量名尽量用程序框图所给名称，并作注释。(5) 出示软件报告.三、实验设计原理循环码是一类很重要的线性分组码纠错码类，循环码的主要优点是编、译码器较简单

40、， 编码和译码能用同样的反馈移存器重构，在多余度相同的条件下检测能力较强，不检测的错误概率随多余度增加按指数下降。另外由于循环码具有特殊的代数结构，使得循环码的编、 译码电路易于在微机上通过算法软件实现。1、循环码编码原理设有一 (n,k)循环码，码字c = C n-icrCr-iCo，其中r=n-k。码字多项式为:码字的生成多项式为：C (X )= Cn-1 Xn-1+ Cn-2xn-2 +C1X+C。g ( X) = gr-1Xr-1+gr-2Xr-2 +g1X+g0待编码的信息多项式为：m (x) =mK-1 xK-1 + +moXn-k.m (X) =Cn-1Xn-1 + +Cn-K

41、Xn-K对于系统码有：Cn-1=m K-1 , Cn-2=m K-2，Cn-K =Cr = mo设监督多项式为：r (x) =Cr-1Xr-1+C1X+C0根据循环码的定义，则有C (x) =xn-Km (x) +r (x) =q (x) .g(x)即监督多项式是将多项式Xn-K m(x)=q(x).g(x)+r(x) r(x)=Rg(x)x n-K m(x) xn-K m(x)除以g(x)所得的余式。编码过程就是如何根据生成多项式完成除法运算求取监督多项式的过程。设循环码(7.3)码的字多项式为：C(x)=C 6X6+C5X5+C4X4+C3X3+C2X2+C ix+C o(n=7)生成多项

42、式为：g(x)=x4+x2+x+1信息多项式为：m(x)=m 2X2+m1X+m0(k=3),设：m(x)=x 2+x监督多项式为：r(x)= C r-1Xr-1 + +C1X+C 0根据循环码的定义：生成多项式的倍式均是码字， 编码实际上是做 xnKm(x)除以g(x)第34页共34页所得的余式运算求得r(x)。编码程序框图见图1, 二进制多项式除法示意图见图2图1编码计算程序框图除 法 子 程 序111 .商数Irg(x): 10111 | 1100000 x m(x)+ 10111第一步11110+ 10111第二步10010+ 10111第三步101 余式:x2+1图2二进制多项式除法

43、示意图编码步骤：110后附上(1) n-k=r=7-3=4,用x4乘m(x)?的运算实际上相当于在信息码4 个 0,变为 1100000(2) 用 xrm(x)=x4(x2+x)=x6+x5 除以 g(x),如图 1 所示，得到监督余式 r(x)=x2+1。(3) 编出相应的发送码字为：C(x)=xrm(x)+r(x)0=1100000+101=1100101(4) 按上述步骤，将得到下述码表：信息位监督位10000000210101113010111040111001510010116101110071100101811100102、译码原理 设R(x)为接收码字多项式，E(x)为错误图样多项式，S(x)为伴随式，则根据循环码的性 质有：S(x)=R g(x)R(x)= R g(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)= R g(x)E(x)将其作作为本地数据表存储好。根