信息论课程设计报告.docx
《信息论课程设计报告.docx》由会员分享，可在线阅读，更多相关《信息论课程设计报告.docx（31页珍藏版）》请在冰点文库上搜索。
成绩：
2016-2017学年第1学期
《信息论》课程设计
学院名称：
班级学号：
学生姓名：
教师姓名：
2016年12月
一、判定唯一可译码
1.任务说明
输入：
任意的一个码（即已知码字个数及每个具体的码字）
输出：
判决结果（是/不是）
输入文件:
in1.txt，含至少2组码，每组的结尾为”$”符
输出文件:
out1.txt，对每组码的判断结果
说明：
为了简化设计，可以假定码字为0，1串
2.实现原理
判断方法：
将码C中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有
包含任一码字，则可判断此码C为唯一可译变长码。
构成集合F：
首先观察码C中最短的码字是否是其他码字的前缀。
若是，将其所有可能
的尾随后缀排列出。
就是将其他码字序列中截去与其最短码字相同的前缀
部分，将余下的序列为尾随后缀。
而这些尾随后缀又可能是某些码字的前
缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生
的新的尾随后缀列出。
然后再观察这些新的尾随后缀是否是某些码字的前
缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后
缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随
后缀产生为止。
这样，首先获得的是由最短码字能引起的所有尾随后缀。
接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部
列出。
由此得到由码C的所有可能的尾随后缀组成的集合F。
参考算法伪代码：
Foralldo
if是的前缀then
将相应的后缀作为一个尾随后缀放入集合中
Endif
Endfor
Loop
Foralldo
Foralldo
if是的前缀then
将相应的后缀作为一个尾随后缀放入集合中
Elseif是的前缀then
将相应的后缀作为一个尾随后缀放入集合中
Endif
Endfor
Endfor
Ifthen
Returnfalse
ElseifF中未出现新的元素then
Returntrue
Endif
//能走到这里，说明F中有新的元素出现，需继续
Endloop
3.实现源码
#include
#include
#include
#include
usingnamespacestd;
#pragmawarning（disable:
4996）
charc[100][50];//保存码字
charf[300][50];//保存尾随后缀
intN,sum=0;//N为码字的个数，sum为尾随后缀个数
intflag;//判断是否唯一可译标志位
//检测尾随后缀
voidpatterson（charc[],chard[]）
{
inti,j,k;
for（i=0;;i++）
{
If（c[i]=='\0'&&d[i]=='\0'）//两字符串一样长，跳出
break;
if（c[i]=='\0'）//d比c长，将d的尾随后缀放入f中
{
for（j=i;d[j]!
='\0';j++）
f[sum][j-i]=d[j];
f[sum][j-i]='\0';
for（k=0;k {
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中
是否存在*/
{
sum--;break;
}
}
sum++;
break;
}
if（d[i]=='\0'）//c比d长，将c的尾随后缀放入f中
{
for（j=i;c[j]!
='\0';j++）
f[sum][j-i]=c[j];
f[sum][j-i]='\0';
for（k=0;k {
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中
是否存在*/
{
sum--;break;
}
}
sum++;
break;
}
if（c[i]!
=d[i]）//字符不一样了也退出（前缀不同）
break;
}
}
voidmain（）{
intk=0,N=0,m=0,a[50],z=0;
a[m]=N;m++;
fstreamfile1;
file1.open（"out1.txt"）;
//码字读取
FILE*file;
file=fopen（"in1.txt","r+"）;
intnum=fgetc（file）-48;
for（intn=0;n inti=0,j;
if（fgetc（file）==''）
N+=（fgetc（file）-48）;
elseN+=（fgetc（file）-48）;
a[m]=N;m++;
fgetc（file）;
for（k;k for（intq=0;;q++）{
chartemp=fgetc（file）;
c[k][q]=temp;
if（temp==''||temp=='$'）{
c[k][q]='\0';
break;
}
}
}
//生成尾随后缀
flag=0;
for（i=a[z];i for（j=i+1;j {
if（strcmp（c[i],c[j]）==0）
{
flag=1;break;
}
}
if（flag==1）//如果码本身有重复，就可以断定它不是唯一可译码
{
for（inty=a[z];y file1< file1<<"不是唯一可译码。
\n";
}
else
{
for（i=a[z];i中*/
{
for（j=i+1;j {
patterson（c[i],c[j]）;
}
}
for（i=0;;i++）//根据原始码与s[i]生成s[i+1]也放入f[i]
{
ints=0;
for（j=a[z];j样，重复的则不再添加*/
{
if（i==sum）
{
s=1;break;
}
else
patterson（f[i],c[j]）;
}
if（s==1）break;
}
for（i=0;i相同则不是唯一可译码*/
{
for（j=a[z];j {
if（strcmp（f[i],c[j]）==0）
{
flag=1;
break;
}
}
}
if（flag==1）
{
for（inty=a[z];y file1< file1<<"不是唯一可译码。
\n";
}
else{
for（inty=a[z];y file1< file1<<"是唯一可译码。
\n";
}
}
file1<<"尾随后缀集合为：
";
for（i=0;i file1< file1<<"\n";
z++;
sum=0;
}
}
4.运行结果
输入文件：
in1.txt
说明：
输入文件中第一个数字表示码的组数，第二个数字表示一组码码字的个数，一组码结束以“$”符号结尾；“$”符号后的数字表示下一组码的码字个数。
此例以两组码输入为例，多组码判断同上。
输出文件：
out1.txt
结果分析：
程序首先读取第一组码，进行是否唯一可译码的判断，在输出文件第一行输出判断结果，在第二行输出该码字产生的尾随后缀集合（若只是输出是否唯一可译码的判断结果，不能完全说明程序的正确性，可能存在偶然性；若是输出的尾随后缀集合是正确的，则能说明程序的正确性，由于选取的两组数据来自课本，可以准确的知道尾随后缀集合是否正确，则可验证此程序的正确性，即可用于判断码是否为唯一可译码）。
5.设计体会
通过此实验的设计，进一步加深了我对唯一可译码判别方法的理解。
此实验在设计完成的过程中出现两大难点，第一点就是，作为此程序的核心，两个码字生成尾随后缀的函数编写，选取两个字符数组保存码字和后缀，通过码字长度和单个字符比较来生成尾随后缀；第二个难点是码字的文件读取，起初考虑的是整个码字一起读取，发现实现过程较为复杂，经过修改，改为单个字符读取能简化程序的设计。
其他部分按照唯一可译码的判断方法进行设计，关键部分调用尾随后缀生成函数即可，再将判断结果输出到输出文件。
此实验总体而言较为简单，实现时注意细节、没有逻辑误区即可。
二、游程编码+Huffman码
1.任务说明
要求：
一无记忆二元信源，0符号的出现概率为1/4,1符号的出现概率为3/4。
现要求
对该信源连续出现的n个符号序列，先进行游程编码，再对结果进行Huffman
编码。
然后，再进行Huffman译码和游程译码。
假定，连续出现的0或1序列
的长度不超过16，n不小于256。
输入：
长为n的0/1串
输出：
1.游程编码结果，2.Huffman编码结果，3.Huffman译码结果4.游程译码结果
输入文件:
in2.txt，含至少两组输入
输出文件:
out2.txt，对每组输入的处理结果
2.实现原理
游程编码：
信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，
这种字符串的长度称为游程。
游程编码（RLC）就是将信源输出的这种字符
序列映射成由串的字符，串的长度和串的位置三个标志组成的标志序列。
知
道了串的字符、串的长度和串的位置的标志序列，就可以完全恢复出原来的
字符序列。
在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连
“0”这一段称为“0”游程，连“1”这一段称为“1”游程。
它们的长度分
别称为游程长度L（0）和L（l）。
“0”游程和“l”游程总是交替出现的。
如果规
定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游
程，第三个又是“0”游程等等。
对于随机的二元序列，各游程长度将是随
机变量，其取值可为1，2，3，„，直到无限。
Huffman码：
（1）将q个信源符号按概率分布P（si）的大小，以递减次序排列起来，
设p1>=p2>=p3>=...>=pq
（2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个
概率最小的信源符号合并成一个信服好，并用这两个最小概率之和
作为新符号的概率，从而得到只包含q-1个服啊后的新信源，称为
S信源的缩减信源S1。
（3）把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两
个概率最小的符号合并成一个新符号，并分别用0和1码符号表示，
这样又形成了q-2个符号的缩减信源S2。
（4）依次继续下去，直至缩减信源最后只剩两个符号为止。
将这最后两
个符号分别用0和1码符号表示。
最后这两个符号的概率之和必为
1。
然后从最后一级缩减信源开始，依编码路径由后向前返回，就得
出各信源符号所对应的码符号序列，即得对应的码字。
Huffman码参考算法伪代码：
ifq=2then
Return
Else
降序排序
缩减信源：
创建一个符号以取代，其概率
递归调用Huffman算法以得到的编码（相应的概率分布为）
Return
Endif
3.实现源码
#include
#include
#include
#include
#include
#pragmawarning（disable:
4996）
#defineN100
#defineM2*N-1
typedefchar*HuffmanCode[2*M];//haffman编码
usingnamespacestd;
charx[100];
chary[100];
fstreamin（"in2.txt"）;
fstreamout（"out2.txt"）;
voidyouchengbianma（chara[100]）
{
charyc[100];
inti=0,j=0,jishu=1;
yc[0]=a[0];
for（i=0;a[i]!
='\0';i++）
{
if（a[i]==a[i+1]）
jishu++;
else
{
yc[j+1]=jishu+48;
j=j+2;
yc[j]=a[i+1];
jishu=1;
}
}
yc[j]='\0';
cout<<"游程编码后：
"< strcpy_s（x,yc）;
}
voidyouchengyima（chara[100]）
{
charbz=0,jieya[100],j,jishu;
for（inti=0;a[i]!
='\0';i=i+2）
{
jieya[bz]=a[i];
for（j=bz,jishu=1;jishu<=a[i+1]-48;jishu++,j++）
jieya[j]=a[i];
bz=j;
}
jieya[j]='\0';
cout<<"游程译码后：
"< out<<"游程译码后：
"<}
typedefstruct
{
intweight;//权值
intparent;//父节节点
intLChild;//左子节点
intRChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedefstructNode
{
intweight;//叶子结点的权值
charc;//叶子结点
intnum;//叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
voidCreateWeight（charch[],int*s,WeightNodeCW,int*p）
{
inti,j,k;
inttag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for（i=0;ch[i]!
='\0';i++）
{
tag=1;
for（j=0;j if（ch[j]==ch[i]）
{
tag=0;
break;
}
if（tag）
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for（k=i+1;ch[k]!
='\0';k++）
if（ch[i]==ch[k]）
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
voidCreateHuffmanTree（Huffmanht,WeightNodew,intn）
{
inti,j;
ints1,s2;
//初始化哈夫曼树
for（i=1;i<=n;i++）
{
ht[i].weight=w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for（i=n+1;i<=2*n-1;i++）
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for（i=n+1;i<=2*n-1;i++）
{
for（j=1;j<=i-1;j++）
if（!
ht[j].parent）
break;
s1=j;//找到第一个双亲为零的结点
for（;j<=i-1;j++）
if（!
ht[j].parent）
s1=ht[s1].weight>ht[j].weight?
j:
s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for（j=1;j<=i-1;j++）
if（!
ht[j].parent）
break;
s2=j;//找到第二个双亲为零的结点
for（;j<=i-1;j++）
if（!
ht[j].parent）
s2=ht[s2].weight>ht[j].weight?
j:
s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
voidCrtHuffm
升级会员 