2023年12月11日发(作者：ipad air1)

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

《信息论与编码》

课 程 实 验

湖南大学计算机与通信学院

2010年5月1日

第 1 页 共 34 页 <<信息论与编码原理>>课程实验

目 录

课程实验大纲 ……………………………………………3

实验一 信道容量的迭代算法程序设计………………….4

实验二 唯一可译码判决准则…………………………… 9

实验三 Huffman 编码方案程序设计…………………15

实验四 LZW编码方案程序设计…………………… 20

实验五 Shanoon编码方案程序设计………………… 23

实验六 循环码的软件编、译码实验…………………….27

实验七 BCH码最大似然译码器设计………………… 31

第 2 页 共 34 页 <<信息论与编码原理>>课程实验

课程实验大纲

课程

名称

软件包

C语言软件包

湖南大学

通信工程实验条件和设备

实验地点 设备名称 实验验收

学生在自行计算机上完成实验，在由老师组织验收检查报告，在实验周进行统一时间考核。

信息论与

计算机

编码原理

VHDL语言

软件包

实验室

实验项目内容和要求

序号

实验内容

信道容量迭代算法

实验一

程序设计 计算程序的设计和调试

相应软件与实验要求

掌握相应实验原理和算法C语言数值

唯一可译码判决准则

掌握相应实验原理和算法C语言字符串实验二

程序设计

Huffman编码方案

实验三

程序设计 程序的设计调试

掌握相应实验原理和算法C语言设计和实验四

LZW编码方案程序设计

调试中进制转换、数值与字符串之间的

处理程序的设计和调试

掌握相应实验原理和算法C语言递归

第 3 页 共 34 页 <<信息论与编码原理>>课程实验

转换等技术

掌握相应实验原理和算法C语言设计和Shanoon编码方案

实验五

程序设计

转换等技术

掌握相应实验原理和算法工程

实现方法研究

掌握相应实验原理和算法工程

实现方法研究

调试中进制转换、数值与字符串之间的

(15、7)循环码一般编、实验六

译码电路实现研究

大数逻辑可译码编、译码实验七

算法实现研究

实验一 信道容量的迭代算法程序设计

一、实验目的

（1）进一步熟悉信道容量的迭代算法；

（2）学习如何将复杂的公式转化为程序；

（3）掌握C语言数值计算程序的设计和调试技术。

二、实验要求

（1）已知：信源符号个数r、信宿符号个数s、信道转移概率矩阵P。

（2）输入：任意的一个信道转移概率矩阵。信源符号个数、信宿符号个数和每个具体的转移概率在运行时从键盘输入。

（3）输出：最佳信源分布P*，信道容量C。

三、信道容量迭代算法

1：procedure CHANNEL CAPACITY(r,s,(2：initialize:信源分布pji))

pi=1/r，相对误差门限，C=—

第 4 页 共 34 页 <<信息论与编码原理>>课程实验

3：repeat

4：

ij5：

pipjippii1rji

spi6：

exp(pjilog2ij)j1exp(pr1j1rsrsjilog2ij)

C 

log2[exp(pjilog2ij)]r1j1

C7：until

C

8：output P*=

(pi)r,C

9：end procedure

-------------------------------------------------------------------------------------------------------

四、参考代码

/*********************************************************************Author: Hop Lee

*Date : 2003.06.25

*Copyright: GPL

Purpose: Caculate the capacity of a given channel

*********************************************************************/

#include

#include

#include

#include

#include

#define DELTA 1e -6 /* delta,the threshold */

int main( void)

{

register int i,j;

register int k;

第 5 页 共 34 页 <<信息论与编码原理>>课程实验

int 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 number of input symbol:r,

* and the mumber of output symbol:s*/

fscanf(stdin,"%d",&r);

fscanf(stdin,"%d",&s);

/*Allocation 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;i

p_ji[i]=(float *)calloc(s,sizeof(float));

phi_ij=(float **)calloc(r,sizeof(float*));

for(i=0;i

phi_ij[i]=(float *)calloc(s,sizeof(float))

/*Read the channel transition probability matrix p_ji */

for(i=0;i

for(j=0;j

fscanf(stdin,"%f",&p_ji[i][j]);

/*Validate the input data */

for(i=0;i

{

validate=0.0;

for(j=0;j

{

validate +=p_ji[i][j];

}

if(fabs(validate -1.0)>DELTA)

{

fprintf(stdout,"invalid input data.n");

exit(-1);

}

第 6 页 共 34 页 <<信息论与编码原理>>课程实验

}

fprintf(stdout,””);

/*initialize the p_i and phi_ij*/

for(i=0;i

{

p_i[i]=1.0/(float)r;

}

/* initialize C and iteration counter :k,and temprory variable*/

C=-MAXFLOAT;/*MAXFLOAT was defined in

k=0;

sum=(float *)calloc(r,sizeof(float));

/*Start iterate*/

do

{

k++;

/* Calculate phi_ij(k) first */

for(j=0;j

{

p_j=0.0;

for(i=0;i

p_j+=p_i[i]*p_ji[i][j];

if(fabs(p_j)>=DELTA)

for(i=0;i

phi_ij[i][j]=p_i[i]* phi_ji[i][j]/p_j;

else

for(i=0;i

phi_ij[i][j]=0.0;

}

/*calculate p_i(k+1) then*/

p_j=0.0;

for(i=0;i

{

sum[i]=0.0;

for(j=0;j

{

/* prevent divided by zero*/

if(fabs(phi_ij[i][j])>=DELTA)

第 7 页 共 34 页 <<信息论与编码原理>>课程实验

sum[i]+=p_ji[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

{

p_i[i]=sum[i]/p_j;

}

/*and C(k+1)*/

C_pre=C;

C= log2(p_j)/ log2(2.0);

}

while(fabs(C-C_pre)/C>DELTA);

free(sum);

sum=NULL;

/*Output the result*/

fprint(stdout,”The iteration number is %”,k);

fprint(stdout,”The capacity of the channel is %.6f bit/”,C);

fprint(stdout,”The best input probability distribution is :n”);

for(i=0;i

fprint(stdout,”%.6f”,p_i[i]);

fprint(stdout,”n”);

/* Free the memory we allocation before with stack sequence*/

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);

第 8 页 共 34 页 <<信息论与编码原理>>课程实验

p_ji=NULL;

free((p_i);

p_i=NULL;

exit(0);

}

实验二 唯一可译码判决准则

一、实验目的

（1）进一步熟悉唯一可译码判决准则；

（2）掌握C语言字符串处理程序的设计和调试技术。

二、实验要求

（1）已知：信源符号个数q、码字集合C。

（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。

（3）输出：判决（是唯一可译码/不是唯一可译码）。

三、唯一可译码判决准则算法

1： procedure U NIQUE D ECODABLE(C)

2: for all Wi,Wj∈C do

3: if Wi是Wj的前缀 then

第 9 页 共 34 页 <<信息论与编码原理>>课程实验

4: 将相应的后缀作为一个尾随后缀码放入集合F0中

5: end if

6: end for

7: loop

8: for all Wi∈C do

9: for all Wj∈Fn do

10: if Wi是Wj的前缀 then

11: 将相应的后缀作为一个尾随后缀码放入集合Fn1中

12：else if Wj是Wi的前缀 then

13: 将相应的后缀作为一个尾随后缀码放入集合Fn1中

14: end if

15: end for

16: end for

17: F←Fii

18： ifWi∈F, Wi∈C then

19: return False

20: else if F 中没有出现新的元素 then

21: reture Ture

22: end if

23: end loop

24: end procedure

----------------------------------------------------------------------------

四、参考代码

/********************************************************************

* Author: Chen Min Ru

*Date: 2004.03.16

*Copyright：GPL

*Purpose ： Find out whether a code is unique decodable or not

****************************************************

# include

# include

# include

# include

第 10 页 共 34 页 <<信息论与编码原理>>课程实验

# include

# include

# include”ourhdr.h”

int scomp(char **C,int n,int *l);

void compline(char *C, int cline,char *D,

int dline,char **E,int *elinenum);

int judge(char **C,int crow,char **E);

int erow;

int main(void)

{

register int i;

int n,l;

int *l_i;

char **C;

/*Read the number of input symbol:n*/

fscanf(stdin,”%d”,&n);

/*Allocation memory for l_i and *C[i]*/

l_i=(int *)calloc(n,sizeof(int));

C=(char **)calloc(n,sizeof(char *));

/* Read the code and its length in*/

for (i=0;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…nn”);

i=scomp(C,n,l_i);

/*Output the result*/

if(i==0)

fprintf(stdout,”The is unique decodable.n”);

else if (i==1)

fprintf(stdout,”The is NOT unique decodable.n”);

else

fprintf(stderr,”Error!n”);

第 11 页 共 34 页 <<信息论与编码原理>>课程实验

/*Free the memory we allocation before with stack sequeue*/

for(i=n-1;i>=0;i--)

{

free(C[i]);

}

free(*C);

free(l_i);

exit(0);

}

/*Compare C,D and E */

int scomp(char **C,int n,int *l)

{

int i;

int crow,drow;

char **D,**E;

int *dlinenum,* elinenum;

int drownum;

/* Allocation soace to dlinenum [i] and elinenum[i]*/

dlinenum=(int *)calloc(n,sizeof(int));

/* For the first time,D has the same length with C */

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;

/* For the first time ,let D = C */

for(i = 0;i < n;i + +)

strcpy(D[i],C[i]);

/* Compare C and D */

compare :

erow = 1;

E = ( char * * )calloc(n,sizeof( char * ));

第 12 页 共 34 页 <<信息论与编码原理>>课程实验

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);

}

}

/* Compare D and C */

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) /* Let D = E and go on comparing */

{

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]);

第 13 页 共 34 页 <<信息论与编码原理>>课程实验

}

free( *E );

free( elinenum );

goto compare;

}

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’s NOT unique decodable*/

return 1;

else if(i==0)/*It’s unique decodable*/

return 0

}

}

int judge(char **C,int crow,char **E)

{

int i,j;

if(ero==1)

return 0;/* Stop the processing*/

for(i=0;i

for(j=0;j

if(strcmp(C[i],E[j])==0)

return 1;/* Stop the processing*/

return2;

第 14 页 共 34 页 <<信息论与编码原理>>课程实验

}

void compline(char *C,

int cline,

char *D,

int dline,

char **E,

int *elinenum)

{

if(cline

{

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);

/*Copy the last dline-cline code into E*/

strncpy(E[erow-1],&D[cline],dline-cline+1);

erow ++;

}

}

}

实验三 Huffman 编码方案程序设计

一、实验目的

（1）进一步熟悉Huffman编码过程；

（2）掌握C语言递归程序的设计和调试技术。

二、实验要求

（1）输入：信源符号个数r、信源的概率分布P；

（2）输出：每个信源符号对应的Huffman编码的码字。

三、Huffman编码算法描述

1：procedure HUFFMAN({si},{pi})

2：if q==2 then

3：return s0→0，s1→1

4：else

第 15 页 共 34 页 <<信息论与编码原理>>课程实验

5： 降序排序{pi}

6： 缩减信源：创建一个符号s’ 以取代sq2,sq1,其概率为p’=pq2+pq1

7： 递归调用Huffman算法以得到s0，…，sq3，s’的编码：w0，…，wq3，w’，相应的

概率分布为p0，…，pq3，p’

8： return s0→w0，…，sq3→wq3,sq2→w’0，sq1→w’1

9： end if

10：end procedure

-------------------------------------------------------------------------------

四、参考代码

/********************************************************************

*Author : Chen Min Ru

*Date: 2004.03.15

*Copyright: GPL

*Purpose: Huffman recursive coding algorithm

********************************************************************/

# include

# include

# include

# include

# define DELTA 1.0e-6

void sort(double *,char **,int *,int);

void code(double *,char **,int *,int);

int

main(void)

{

float *p_i,*p;

float sum;

float temp;

char **c;

int *idx;

int q;

int i;

第 16 页 共 34 页 <<信息论与编码原理>>课程实验

/* Read the number of source symbol in */

fscanf(stdin,”%d”,&q);

/*Allocation memory*/

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

{

c[i]=(char *)calloc(1,sizeof(char));

c[i][0]=’0’;

}

/*Read the probability of each symbol in and validate them*/

sum=0.0;

for(i=0;i

{

fscanf(stdin,”%f”,&p[i]);

p_i[i]=p[i];

idx[i]=i;

sum +=p_i[i];

}

if(fabs(sum-1.0)>DELTA)

{

fprintf(stderr,”p_i error n”);

exit(-1);

}

/*Coding*/

code(p_i,c,idx,q);

/*Output result*/

for(i=0;i

{

fprintf(stdout,”%d%.6f%sn”,idx[i],p[idx[i]],c[idx[i]]);

}

/*Free the memory*/

for(i=q;i>0;--i)

{

free(c[i]);

第 17 页 共 34 页 <<信息论与编码原理>>课程实验

}

free(c);

free(p);

free(p_i);

free(idx);

exit(0);

}

/*

*Sorting algorithm

*/

void

sort(float *p,char **c,int *idx,int q)

{

int finish=0;

int i,j;

int l1,l2;

char *s;

float t;

while(i

{

finish=1;

for(j=0;j

{

if(p[j]

{

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]);

第 18 页 共 34 页 <<信息论与编码原理>>课程实验

realloc(c[j+1],l1+1);

strcpy(c[j+1],s);

free (s);

}

}

i++;

}

}

/*

* Huffman recursive coding algorithm

*/

void code(float *p,char **c,int *idx,int q)

{

int l1,l2;

char *s;

/*If q=2,return the code words*/

if (q==2)

{

realloc(c[0],3);

realloc(c[1],3);

strcat(c[0],”0”);

strcat(c[1],”1”);

}

else

{

/*if q>2,reduce the source.*/

p[q-2]=p[q-1]+p[q-2];

/*Call the coding algorithm recursively*/

sort(p,c,idx,q-1);

code(p,c,idx,q-1);

/*Resume the source and return the code words*/

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);

第 19 页 共 34 页 <<信息论与编码原理>>课程实验

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：procedure LZW

2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF）一次分配给0x00到0xFF的256个单字节字符。

3：动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如第 20 页 共 34 页 <<信息论与编码原理>>课程实验

P=256（即0x100），读入被压缩文件的第一个字符cha，作为待处理单词W。单词的前缀Q为空，即Q=4095，尾字符就是cha，序号（码字）就是cha的序号。

4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W1。

5：如果字典中已有W1，则将W1看做当前单词W，返回第三步。如果字典中没有W1（发现一个新单词），先将原单词W的序号输出，再加新单词W1，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回第三步。

6:end procedure

--------------------------------------------------------------------------------------------------------------------

四、参考代码

/********************************************************************

*Author:

*Date:

*Copyright :

*Purpose：Use LZW algorithm to code the source symbols

***********************************************************

#include

#include

#include

struct word {

unsigned int n;

unsigned char c;

}w,wd[4096];//Dictionary

unsigned int p,n;

unsigned char h,m,l,f;

/*Out put the code */

void out(int n)

{

if(f==0){

h=n/16;

m=(n<<4)&0xf0;

f=1;

}

else{

m+=n/256;

l=n&0xff;

第 21 页 共 34 页 <<信息论与编码原理>>课程实验

fputc(h,stdout);

fputc(m,stdout);

fputc(l,stdout);

h=m=l=f=0;

}

}

/* Main copress program */

void lzw()

{

int c,i;

unsigned char ch;

fprintf(stderr,"nnbegin compress ,please wait!n");

for(i=0;i<256;i++){//Initialize first 256 word

wd[i].n=4095; //in dictionary

wd[i].c=i;

}

p=256;

w.n=4095;

w.c=n=fgetc(stdin);

h=m=l=f=0

for(;;){

c=fgect(stdin);

if(c==-1){

out(n);

if(f)

out(4095);

fprintf(stderr,"nn compression is over!n");

return;

}

ch=c;

for(i=n+1;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);

第 22 页 共 34 页 <<信息论与编码原理>>课程实验

if(p<4095){

wd[p].n=n;

wd[p].c;

p++;

}

w.n=4095;

n=w.c=ch;

}

}

}

void main(void)

{

lzw();

}

实验五 Shanoon编码方案程序设计

一、实验目的

（1）进一步熟悉Shannon编码算法；

（2）掌握C语言程序设计和调试过程中数值的进制转换、数值与字符串之间的转换等技术。

二、实验要求

（1）输入：信源符号个数q、信源的概率分布p；

（2）输出：每个信源符号对应的Shannon编码的码字。

三、Shannon编码算法

1：procedure SHANNON(q,｛Pi｝)

第 23 页 共 34 页 <<信息论与编码原理>>课程实验

2: 降序排列｛Pi｝

3: for i=1 q do

4: F(5：lsi)



p

(s

)

i1k1ki

[1/p(si)]log

26：将累加概率F(7：取小数点后si)（十进制小数）变换成二进制小数。

i个消息的码字。

li个二进制数字作为第8：end for

9：end procedure

------------------------------------------------------------------------------------------------------------------

四、参考代码

/********************************************************************

*Author : Chen Min Ru

*Date : 2004.03.15

*Copyright : GPL

*Purpose :Use shannon algorithm to code the source symbols

***********************************************************

# include

# include

# include

# include

# include

# include

# define DELTA 1e -6

void sort(float*,int);

int main(void)

{

register int i,j;

int n; /*Number of the total words*/

int temp;

float *p_i; /*Probability of the word*/

float *P_i; /*Cumulate probability*/

int *l_i; /*Code length*/

char * *C; /*Code set*/

/*Use sum to test the data and p to store the temp data*/

float sum,p;

/*Read the nubmer ofinput symbol: n*/

fscanf(stdin,"%d",&n);

第 24 页 共 34 页 <<信息论与编码原理>>课程实验

/*Allocation memory for p_i and *C[i] */

p_i=(float *)calloc(n,sizeof(float));

P_i=(float *)calloc(n,sizeof(float));

l_i(int *)calloc(n,sizeof(int));

/* Read the channel transition probability matrix p_i in*/

for(i=0;i

fscanf(stdin,”%f”,&p_i[i]);

/*Validate the input data*/

sum=0.0;

for(i=0;i

sum+=p_i[i];

if(fabs(sum-1.0)>DELTA)

fprintf(stderr,”Invalid input data n”);

fprintf(stdout,”Starting…nn”);

/*Sorting the p_i descend*/

sort (p_i,n);

/*Calculate the binary number’s length*/

for(i=0;i

{

p=(-(log2（p_i[i]）))/log2(2.0);

l_i[i]=(int)ceil(p);

}

/*Allocate C[i]*/

C=(char **)calloc(n,sizeof(char *));

for(i=0;i

{

C[i]=(char *)calloc(l_i[i]+1,sizeof(char));

C[i][0]=’0’;

}

/*Calculate the P_i[i]*/

P_i[0]=0.0

for(i=1;i

P_i[i]=P_i[i-1]+p_i[i-1];

/*Transform P_i to binary mode*/

for(i=0;i

第 25 页 共 34 页 <<信息论与编码原理>>课程实验

{

for(j=0;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”);

else

C[i]=strcat(C[i],”1”)

}

}

/*Output the result*/

fprintf(stdout,”The output coding is :n”);

for(i=0;i

fprintf(stdout,”%s”,C[i]);

fprintf(stdout,”nn”);

/*Free the memory we allocation*/

for(i=n-1;i>=0;i--)

free(C[i]);

free(C);

free(p_i);

free(P_i);

free(l_i);

exit(0);

}

/*Bubble sorting*/

void sort(float *k,int m)

{

int i=1;

int j=1;

int finish=0;

float temp;

while(i

{

finish=1;

for(j=0;j

{

第 26 页 共 34 页 <<信息论与编码原理>>课程实验

if(k[j]

{

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）考查和分析该码检、纠一、二位错误的能力情况。

第 27 页 共 34 页 <<信息论与编码原理>>课程实验

（4）整理好所有的程序清单，变量名尽量用程序框图所给名称，并作注释。

(5) 出示软件报告.

三、实验设计原理

循环码是一类很重要的线性分组码纠错码类，循环码的主要优点是编、译码器较简单，编码和译码能用同样的反馈移存器重构，在多余度相同的条件下检测能力较强，不检测的错误概率随多余度增加按指数下降。另外由于循环码具有特殊的代数结构，使得循环码的编、译码电路易于在微机上通过算法软件实现。

1、循环码编码原理

设有一（ｎ，ｋ）循环码，码字Ｃ＝[Cn-1…CrCr-1…C0]，其中r=n-k。码字多项式为：

n-1n-2

C (x ) = Cn-1x+ Cn-2x+… +C1x+C0。

码字的生成多项式为：

g（x）= gr-1xr-1+gr-2xr-2+…+g1x+g0

K-1 待编码的信息多项式为：

m（x）=mK-1x

xn-k+…+m0

.m（x）=Cn-1xn-1+…+Cn-Kxn-K

对于系统码有：

Cn-1=mK-1，Cn-2=mK-2，…Cn-K=Cr=m0

设监督多项式为：

r（x）=Cr-1Xr-1+…+C1x+C0

n-K 根据循环码的定义，则有C（x）=xm（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)

4 生成多项式为:

g(x)=x信息多项式为:

设：

+x2+x+1

m(x)=m2x2+m1x+m0

(k=3),

m(x)=x2+x

r-1 监督多项式为:

r(x)= Cr-1X+…+C1x+C0

n-K根据循环码的定义：生成多项式的倍式均是码字，编码实际上是做xm(x)除以g(x)第 28 页 共 34 页 <<信息论与编码原理>>课程实验

所得的余式运算求得r(x)。

编码程序框图见图1，二进制多项式除法示意图见图2

C← xnkm(x),D←C,r=n-k

—G←g(x)系数

设循环变量B=K

……

C的第B+r位=0?

N

除法子程序

Y

C+G→C

G右移一位

B←B-1

N

……

B=0?

Y

D←C+D

码字D输出

图1 编码计算程序框图

111 ...商数

┌─────

g(x): 10111 | 1100000 .............xm(x)

+ 10111 ................第一步

─────

11110

+ 10111 ...............第二步

────

10010

+ 10111 ...........第三步

────

101 ..........余式:x2+1

图2 二进制多项式除法示意图

r 编码步骤：

（１）n-k=r=7-3=4,用x乘m(x)•的运算实际上相当于在信息码110后附上

4个0，变为1100000

第 29 页 共 34 页

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

（２） 用xm(x)=x(x+x)=x+x除以g(x)，如图1所示,得到监督余式r(x)=x+1。

r （３）编出相应的发送码字为：

C(x)=xm(x)+r(x)

C=1100000+101=1100101

（4） 按上述步骤，将得到下述码表：

1

2

3

4

5

6

7

8

信息位

000

101

010

011

100

101

110

111

监督位

0000

0111

1110

1001

1011

1100

0101

0010

r42652

２、译码原理

设R(x)为接收码字多项式，E(x)为错误图样多项式，S(x)为伴随式，则根据循环码的性质有：

S(x)=Ｒg(x)[R(x)]=Ｒ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)的伴随式，

Si(x)=Ｒg(x)[E(x)]

将其作作为本地数据表存储好。

根据已接收码字多项式R(x)，计算相应的伴随式：

S(x)=Ｒg(x)[R(x)]

将实际接收码字求出的S(x)与本地存储的各Si(x)相比较，查出两者相等的那个唯一匹配的Si(x)，找出并得到相应的错误图样E(x)。

纠错:

C(x)=R(x)+E(x)

否则由S(x)找不出唯一匹配的Si(x)，则报出错信息，表示出现不可纠错的错误图样，即码元出错的个数超出该循环码的纠错能力。

译码流程图3所示:

第 30 页 共 34 页 <<信息论与编码原理>>课程实验

初始化

初始化

可纠错误图样种类总数=N,i=0

G→g(x)系数,i=0,N赋值

G←g(x)系数

输入接收矢量R(x)的系数

C←Ei(x)系数,D←0

调除法子程序

求Rg(x)[Ei(x)]

Si→C

R(x)元错输出转下一R(x)译码

Y

R,C←R(x)系数

调除法子程序

求Rg(x)[R(x)]

N

Si→C,S=0?

N

i=i+1 i=0,C=R+Ei

Y

S=SI?

N

N

N

i=N?

i=i+1,i=NY

Y

将所有的EI(x)系数=Ei

及对应SI造表存储待用

译码流程一

出现不可纠的错误图样报错,转下一R(x)译码

译码流程二

图3 译码程序流程图

实验七 BCH码最大似然译码器设计

一、实验目的

1、通过实验了解最大似然译码思想。

第 31 页 共 34 页 <<信息论与编码原理>>课程实验

2、掌握最大似然译码的设计步骤。

3、了解错误图样的设计与纠、检错能力之间的关系。

4、分析（11，7）BCH码的纠错能力。

二、实验要求

采用VHDL语言或集成电路查表法进行软件仿真设计，完成一个（11，7） BCH码最大似然译码器，接口功能如下：

(1) 编、译码工作速率为50kb/s～10Mb/s不等;

(2) 接收部分具有误码选择功能；

(3) 所有输入、输出接口都与TTL兼容；

(4) 具有内部编、译码自环测试能力。

三、实验设计原理

BCH码是一种具有较强纠错能力的线性分组码。（11，7） BCH码是（15，11） BCH码的缩短码，其生成多项式：

g(x)=χ4+χ+1

其最小码矩dmin=3，纠错能力t=1。（11，7）BCH码的前七位是信息码，后四位是校验码，它可以传送2=128个消息码字。但在我们所接收的实际信号中，只有前六位是信息码，第七位是控制码。所以在设计纠错译码器时，只考虑第七位是“1”的情况。这样，实际信号就只有2=64种不同的消息。实际的（11，7）BCH码码表详见表1。设计（11，7）BCH码译码器，我们首先考虑采用通用译码器（Meggitt Decoder）译码。（11，7）BCH纠错码通用译码器如图1所示。

设计通用译码器大致包括以下三个基本步骤：

1．计算接收序列R(x)的伴随式S(X)，根据S（x）是否为零来判别R（x）中有无错误。

2．寻找S（x）与可纠正错误图样的对应关系，确定错误位置。

3．确定终点状态，形成纠错位，并与缓冲移位寄存器中的R（x）模二加纠错。

其中，g（x）除法器用以计算伴随式S（x）。选通电路将算得的S（x）的值置入M序列产生器。M序列产生器的生成多项式g（x）与（11，7）BCH码的g（x）相同。S（x）在M序列产生器中自环移位的结果与错误图样建立了对应关系。状态识别电路确定终点状态。将其输出与11位移位寄存器的输出模二加即完成了纠错。

按上述方法设计的通用译码器，不仅电路复杂，使用元器件较多，而且本身有一定局限性，对多数纠错码而言，实现比较困难。为了寻找较好的译码方案，设计简单实用、纠错能力较强的译码器，希望以 27256/27512 EPROM芯片为主利用查表法设计了（11，7） BCH码的最大似然译码器。

67第 32 页 共 34 页 <<信息论与编码原理>>课程实验

R(x)

计算伴随式S(x)=Rg(x)[R(x)]

时序

控制T

E(x)

错误状态识别电路

伴随式自发运算电路

11位移位寄存器

R(x)

C(x)

图1 （11，7）BCH码通用译码器原理图

设C=[C0C1C2……Cn-1] 为（n、k）线性分组码的码字，R＝[r0、r1、r2……rn-1为信道输出端的接收序列。由于信道的噪声干扰等原因，接收序列可能与发送码字不同。在译码器中对发送码字作出判决就是译码。若所有码字等概发送，则最佳的译码方案为：在收到序列 R后，译码器对所有2个码字计算它们的条件概率P（R／C）。若概率 P（R／Ci）最大，则认为Ci就是发送码字。这种译码方案称为最大似然泽码。



R(x)

TTL

CP

11位

C

移位

寄存器

11 A10

10 A9

9 A8

8 A7

7 A6

6 A5

5 A3

4 A3

3 A2

2 A1

1 A0

D0 E

D1 m1

D2 m2

D3 m3

27256/

D m

4427512

D5 m5

D6 m6

EPROM

D7 m7

K

T



图2 (11,7)BCH码最大似然译码器逻辑设计原理图

最大似然泽码器要存储发送码字C中的所有2个码字，并将接收码字R与所有2个码字逐个比较，把相差位数最少的一组［P（R／Ci）最大的一组］Ci输出。对某实用（11，7）BCH码而言，消息组M包含6比特信息位。发码C共有2＝64个码字。而收码R可以是2=2048个n重中的任何一个。若能用最大似然译码器从2个n重中分出2个互不相交的子集D0、D1、D2……D2-1。每个子集的输出与对应消息码字M0、M1、M2……M2-1相同。任何一个子集Di中的码字与对应发送码字Ci之间的码距d小于或等于t，这里t为该码的纠错能力，则会第 33 页 共 34 页

66116611KK<<信息论与编码原理>>课程实验

出现下面三种情况：

（1）若接收码字R位于对应子集Di之中，则译码器认为Ci就是发送码字。小于t的错误被纠正。译码器输出正确的消息码字Mi．

（2）若按收码字R不在任何子集Di中，则译码器设计输出“告警显示信号”。这表明误码大于t，超出了该码的纠错能力，译码器只能检错。对凡不在任何子集Di中的码字，译码器输出“告警显示信号”，做到“宁空勿错”，从而避免可能造成的错误译码。这一点是其它类型的译码器不能做到的。

（3）若接收码字R落入其它非对应子集中，则译码器产生错误译码。事实上，错误译码现象在任何类型的译码器中都是存在的，但其概率远比正确译码的概率小得多。对信道各部份指标均在规定范围之内的正常通信，这种情况可以忽略不计。对于异常干扰情况，例如较长时间的突发干扰，通信系统将采取其它纠错措施，这已超出了本文的讨论范围。

采用EPROM芯片的十一条地址线可提供 211=2048个地址。它有八条输出线可以提供28=256个输出状态。将11条地址线与11位接收码字R相对应；将8条输出线中的6条与消息码字M相对应；按照上述原则对EPRON4片的各地址内容编程，就可以实现（11，7）BCH码的最大似然译码器。

这里采用码表存储法：该方法是将编码和译码变换表（对应关系表）写入可编程只读存储器（PROM）表中，将待转变的码字作为地址码，在数据线上即可得到变换后的码。对于译码器，在地址上输入编码字，则在数据线上为还原了原码。实际应用时，考虑到变换表的写入与修改方便，一般是采用EPROM（可改写的只读存储器）来存放变换表。

第 34 页 共 34 页