信息论课程设计报告.docx
《信息论课程设计报告.docx》由会员分享，可在线阅读，更多相关《信息论课程设计报告.docx（23页珍藏版）》请在冰点文库上搜索。
信息论课程设计报告
xx大学
信息论课程设计
姓名：
学号：
学院：
指导老师：
完成日期：
2015.01.04
一、判定唯一可译码
1．任务说明：
输入：
任意的一个码（即已知码字个数及每个具体的码字）
输出：
判决结果（是/不是）
输入文件:
in1.txt，含至少2组码，每组的结尾为”$”符
输出文件:
out1.txt，对每组码的判断结果
说明：
为了简化设计，可以假定码字为0，1串
2．问题分析、实现原理
判定唯一可译码根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。
算法：
1、考察C中所有的码字，若Wi是Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中；
2、考察C和Fi俩个集合，若Wi∈C是Wj∈F的前缀或Wi∈F是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；
3、F=∪Fi即为码C的尾随后缀集合；
4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素则返回真。
3.源代码：
#include
#includestdlib.h
#include
usingnamespacestd;
structstrings
{
char*string;
structstrings*next;
};
structstringsFstr,*Fh,*FP;//输出当前集合
voidoutputstr（strings*str）
{
do
{
cout<string<str=str->next;}while（str）;
cout<}
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,char*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中有相同码字尺<exit
（1）;
}
if（!
strncmp（CP,tempPtr,MIN（length_a,length_b）））
{
structstrings*cp_temp;
cp_temp=new（structstrings）;
cp_temp->next=NULL;
cp_temp->string=newchar[abs（length_a-length_b）+1];
char*longstr;
longstr=（length_a>length_b?
CP:
tempPtr）;//将长度长的码赋给longstr
//取出后缀
for（intk=MIN（length_a,length_b）;kcp_temp->string[k-MIN（length_a,length_b）]=longstr[k];
cp_temp->string[abs（length_a-length_b）]=NULL;
//判断新生成的后缀码是否已在集合F里，不在则加入F集合
if（comparing（Fh,cp_temp->string））
{
FP->next=cp_temp;
FP=FP->next;
}
}
}
main（）
void
{
//功能提示和程序初始化准备
cout<<\\t\t判定唯一可译码屜屮<structstrings
Cstr,*Ch,*CP,*tempPtr;
Ch=&Cstr;
CP=Ch;
Fh=&Fstr;
FP=Fh;
charc[]=码字集合?
尺;
Ch->string=newchar[strlen（c）];
strcpy（Ch->string,c）;
Ch->next=NULL;
charf[]=后缀集合?
尺;
Fh->string=newchar[strlen（f）];
strcpy（Fh->string,f）;
Fh->next=NULL;
intCnum;//待检测码的个数
cout<<输入待检测码字的个数尺;
cin>>Cnum;
cout<<输入待检测码，每输入一个都按回车键结束：
<for（inti=0;i{
cout<<第<;
chartempstr[10];
cin>>tempstr;
CP->next=new（structstrings）;
CP=CP->next;
CP->string=newchar[strlen（tempstr）];
strcpy（CP->string,tempstr）;
CP->next=NULL;
}
outputstr（Ch）;
CP=Ch;
while（CP->next->next）
{
CP=CP->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）
{
<尡是唯一可译码码组cout<<
exit
（1）;
}
Fbegin=Fend;
Fend=FP;
CP=Ch;
while（CP->next）
{
CP=CP->next;
tempPtr=Fbegin;
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（）.是空的。
步骤一：
开始时的词典包含所有可能的根，而当前前缀P字符流中的下一个字符。
：
=步骤二：
当前字符CP+C步骤三：
判断是否在词典中：
。
P:
=P+C）如果“是”，1（如果“否”，则：
）2（的码字输出到码字流。
把代表当前前缀①P添加到词典中。
P+C符串-把缀②．
③令P：
=C。
（3）判断字符流中是否还有字符需要编码：
①如果“是”，返回到步骤二。
②如果“否”：
输出相应于当前前缀P的码字。
结束编码。
（2）.译码程序：
步骤一：
在开始译码时，词典包含所有可能的前缀根。
步骤二：
当前码字cW：
=码字流中的第一个码字。
步骤三：
输出当前缀-符串string.cW到字符流。
步骤四：
先前码字pW：
=当前码字cW。
步骤五：
当前码字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.源代码：
#include
#include
#include
usingnamespacestd;
stringdic[30];
intn;
intfind（strings）//字典中寻找,返回序号
{
inttemp=-1;
for（inti=0;i<30;i++）
{
if（dic[i]==s）
temp=i+1;
}
returntemp;
}
voidinit（）//字典初始
{
开始时词典包含所有可能的根//;慜dic[0]=
dic[1]=扜;
dic[2]=捜;
dic[3]=摜;
for（inti=4;i<30;i++）//其余为空
{
dic[i]=\;
}
}
voidcode（stringstr）
{
init（）;//初始化
chartemp[2];
temp[0]=str[0];//取第一个字符
temp[1]='\0';
stringP=temp;//P为前缀
inti=1;
intj=4;//目前字典存储的最后一个位置
cout<<编码后的码字为：
;
while
（1）
{
chart[2];
t[0]=str[i];//取下一字符
t[1]='\0';
stringC=t;//C为字符流中下一个字符
if（C==\）//无码字要译，结束
{
cout<
<break;
}//退出循环,编码结束
if（find（P+C）>-1）//有码字要译，如果P+C在词典中，则用C扩展P，进行下一步：
{
P=P+C;
i++;
}
else//如果P+C不在词典中，则将P+C添加到词典中，令P:
=C
{
cout<
<stringPC=P+C;
dic[j++]=PC;
P=C;
i++;
}
}
cout<cout<<生成的词典为：
<for（i=0;i{
cout<}
cout<}
voiddecode（intc[]）
{
init（）;//译码词典与编码词典相同，将a,b,c设为初始的前缀
intpw,cw;//pw：
先前码字，cw：
当前码字
cw=c[0];//输入码字流的第一个码字，赋给当前码字
intj=3,i;
cout<<译码为：
;
cout<for（intm=0;m{
pw=cw;//当前码字赋给先前码字
cw=c[m+1];
if（cw<=j+1）//若当前码字在词典中
{
cout<chart[2];
t[0]=dic[cw-1][0];
t[1]='\0';
stringk=t;
j++;
dic[j]=dic[pw-1]+k;//将先前码字与当前码字所代表的字符串的首字符连接而成的
//字符串添加到词典中
}
else//若当前码字不在词典中
{
chart[2];
t[0]=dic[pw-1][0];
t[1]='\0';
stringk=t;
j++;
dic[j]=dic[pw-1]+k;//将先前码字与当前码字所代表的字符串的首字符连接而
//成的字符串添加到词典中
cout<}
}
cout<cout<<生成的词典为：
<for（i=0;i{
cout<}
cout<}
intmain（）//主程序
{
stringstr;
charchoice;
while
（1）
{
cout<<屜湜屜屮瑜屜屴<<.编码<<屜瑜屜屴<<.译码屜屮湜;
cout<<请选择功能对应的编号：
;
cin>>choice;
if（choice=='1'）//若选择1则编码
{
cout<<\
输入要编码的字符串（由a、b、c、d组成）：
;
cin>>str;
code（str）;
}
elseif（choice=='2'）//若选择2则译码
{
intc[30];
cout<<\
准备译码的消息序列的长度是：
;
cin>>n;
cout<<\
准备译码的消息码字依次是：
;
for（inti=0;i{
cin>>c[i];
}
decode（c）;
}
else
return0;//其他选择则退出程序
}
}
4.程序结果截图：
三：
循环码的编码与译码任务说明：
1.，分别实现编码（多项式乘法）和译码，要其中,,g（x）=x3+x+1要求：
（7,4）非系统循环码求译码可在伴随式法和标准阵列法中随意选择选择编码时，:
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，而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）≠B（x），B（x）不能被B（x）的码组必能被g（x）整除；若传输中发生了错误，则A（x）因此，可以根据余项是否为零来判断码组中有无错码。
整除，这时的错码就不能检出了。
g（x）需要指出的是，有错码的接收码组也有可能被这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。
在接收端为纠错而采用的译码方法自然比检错要复杂许多，因此，对纠错码的研究大
都集中在译码算法上。
我们知道，校正子与错误图样之间存在某种对应关系。
如同其它线性分组码，循环编码和译码可以分三步进行：
S（x）；B（x）
（1）由接收到的码多项式计算校正子（伴随式）多项式；S（x）
（2）由校正子确定错误图样E（x）E（x）（3）将错误图样与B（x）相加，纠正错误。
）步也上述第（13整除g（x）的余式，第（）步运算和检错译码类似，也就是求解B（x）译码器的复杂性主要取决于译码过程的第
（2）步。
很简单。
因此，纠错码所示。
错误图样基于错误图样识别的译码器称为梅吉特译码器，它的原理图如图8-7
个输入端的逻辑电路，原则上可以采用查表的方法，根据校正识别器是一个具有（n-k）子找到错误图样，利用循环码的上述特性可以简化识
3.源代码：
#include#include#includemain（）void
{
aa[10000];
inti;int
N;
int
0,0,1,0,1,1}};定义生成矩阵int//y=0,s=0;intj,k,m;
int
a[4],q[7],rr[10000/4*7];intp,D=0;
int
cc[2500],dd[2500];
int0,0,0,1,0,0},int
定义错误图样//1,0,0,0,0,0}};
w[10000/4*7];
int0,1}};int
intA=0,M=0,L=8;
intf[3];
intww[10000/4*7];
printf（\\t\t循环码的编码与译码尺湜屜屮）;
printf（请输入你想产生的二进制位数：
）;
scanf（╜層,&N）;//输入想产生的信源的个数
while（N<4）
{
printf（输入无效，请重新输入尠）;
printf（请输入你想产生的二进制位数：
）;
scanf（╜層,&N）;}
printf（随机产生的二进制序列为：
）;
srand（（unsigned）time（NULL））;//产生一个随机序列，并把它放入a[]中
for（i=0;i{
aa[i]=rand（）%2;
printf（╜層,aa[i]）;
}
printf（屜湜）;
printf（产生的二进制序列编码后变为：
）;//编码生成码字
for（m=0;m{
for（i=y;i<（y+4）;i++）
{
a[i-y]=aa[i];
}//取出位出来
for（j=0;j<7;j++）
{
q[j]=0;
for（k=0;k<4;k++）
q[j]+=a[k]*b[k][j];//与生成矩阵相乘
}
for（i=s;i<（s+7）;i++）
{
rr[i]=0;
rr[i]=q[i-s]%2;
printf（╜層,rr[i]）;//将生成的放入rr[]中
}
y=y+4;////向后移动位
s=s+7;///向后移动位
printf（屜湜）;
}
printf（经过信道后变为：
）;
srand（（unsigned）time（NULL））;
for（j=0;j{
cc[j]=rand（）_x0010_0;//产生一个~99的随机数
if（cc[j]<9）//当随机数小于时，一个码字产生个错误
{
for（i=D;i<（D+7）;i++）
{
w[i]=0;
w[i]=（rr[i]+e[7][i-D]）%2;
printf（╜層,w[i]）;
}
}
elseif（（cc[j]>=9）&&（cc[j]<=30））//当随机数在~30时，一个码字产生一个错误
{
dd[j]=rand（）%7;
p=dd[j];///随机产生一个~6的数，以确定是码字一个错误的位置
for（i=D;i<（D+7）;i++）
{
w[i]=0;
w[i]=（rr[i]+e[p][i-D]）%2;
printf（╜層,w[i]）;
}
}
else//当随机数在~99时，不发生错误
{
for（i=D;i<（D+7）;i++）{w[i]=0;w[i]=rr[i];
printf（╜層,w[i]）;
}
}
D=D+7;//向后移动位
printf（╜搶,cc[j]）;//进行跟踪，以确定码字错几位
printf（屜湜）;}
printf（编码结果经过译码后变为?
）;
for（i=0;i{
for（j=0;j<3;j++）
{
f[j]=0;
for（k=A;kf[j]+=w[k]*H[k-A][j];//计算伴随式
}
for（m=0;m<7;m++）
{
for（j=0;j<3;j++）
{
if（（f[j]%2）==H[m][j]）
M=M+1;
if（M==3）
L=m;
M=0;//
升级会员 