信息论与编码实验报告

          

20##年12月29日

实验一 唯一可译码判别准则

实验目的：

1.进一步熟悉唯一可译码判别准则；

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

实验内容：

1.已知：信源符号数和码字集合C；

2.输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入；

3.输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1循环判决，否则输入0结束运行）。

实验原理：

根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。  

    算法：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中没有出现新的元素，则返回真。

实验环境及实验文件存档名：

1.实验环境：visual C++ 6.0 

2.文件名  ：weiyikeyi.cpp

实验结果及分析：

1.源代码：

#include<stdio.h>

#include<string.h>

char c[100][50];

char f[300][50]; 

int N,sum=0; //N为输入码字的个数，sum为尾随后缀集合中码字的个数

int flag;//判断是否唯一可译标志位

void patterson(char c[],char d[]) //检测尾随后缀

{

       int i,j,k; 

    for(i=0;;i++)

       { 

              if(c[i]=='\0'&&d[i]=='\0')//2字符串一样，跳出

        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<sum;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<sum;k++)

                     {  

                            if(strcmp(f[sum],f[k])==0) //查看当前生成的尾随后缀在 f集合中是否存在

                            {

                                   sum--;break;

                            }

                     } 

                     sum++;

                     break;

              } 

              if(c[i]!=d[i])//字符不一样了也退出

                     break;

       }

}

void yima()

{ 

       int i,j;

       printf("                       ********唯一可译码判别********\n");

       printf("请输入码字的个数:");//输入码得个数

       scanf("%d",&N);

       while(N>100)

       {

              printf("输入码字个数过大，请输入小于100的数\n");

              printf("请输入码字的个数:");

              scanf("%d",&N);

       } 

       flag=0; 

       printf("请分别输入码字:\n");

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

       { 

              scanf("%s",&c[i]);

       } 

       for(i=0;i<N-1;i++)//判断如果码本身是否重复

              for(j=i+1;j<N;j++)

              { 

                     if(strcmp(c[i],c[j])==0)

                     {flag=1;break;}

              } 

              if(flag==1)//如果码本身有重复，就可以断定它不是唯一可译码

              { 

                     printf("这不是唯一可译码。\n");

              }

              else

              { 

                     for(i=0;i<N-1;i++) //此处是根据原始编码生成的尾随后缀集合s[1]放 入f中

                     { 

                            for(j=i+1;j<N;j++)

                            { 

                                   patterson(c[i],c[j]);

                            }

                     } 

                     for(i=0;;i++) //根据原始码与s[i]生成s[i+1]也放入f[i]

                     { 

                            int s=0; 

                            for(j=0;j<N;j++)//判断s[i+1]中的字符串是否与s[i]中一样 ， 重复的则不再添加

                            { 

                                   if(i==sum) 

                                   { s=1;break;}

                                   else 

                                          patterson(f[i],c[j]);

                            } 

                            if(s==1)break;

                     } 

                     for(i=0;i<sum;i++) //判断p里的字符串是否与s 中重复， 重复则不是唯一的

                     { 

                            for(j=0;j<N;j++)

                            { 

                                   if(strcmp(f[i],c[j])==0)

                                   { 

                                          flag=1;

                                          break;

                                   }

                            }

                     } 

                     if(flag==1)

                     { 

                            printf("这不是唯一可译码！\n");

                     }

                     else 

                            printf("这是唯一可译码！\n");

              } 

}

void main()

{

       int flag=1;

       while(flag){

              yima();

              printf("是否继续判别？1/0\n");

              scanf("%d",&flag);

       }

}

2.运行结果

（1）输入0,01,001时：

（2）继续执行，输入1,01,10,1010

（3）结束执行

实验二 霍夫曼编码

实验目的：

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

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

实验内容：

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

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

实验原理：

1.将q个信源符合按概率大小递减排列;

2.用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源；

3.把缩减信源的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源；

4.依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；

5.然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。

实验环境及实验文件存档名：

1.实验环境：visual C++ 6.0 

2.文件名  ：Huffman.cpp

实验结果及分析：

1.程序源代码：

#include<stdio.h>

#define N 50 

#define maxval 10000.0

#define maxsize 100 

typedef struct

{

 char ch;

 float weight;

 int lchild,rchild,parent;

}hufmtree;

typedef struct

{

 char bits[N];   //位串

 int start;      //编码在位串中的起始位置

 char ch;        //字符

}codetype;

void huffman(hufmtree tree[]);//建立哈夫曼树

void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码

int n;

int m;

void main()

{  

       printf("输入信源符号个数\n");

       scanf("%d",&n);

       getchar();

       m = 2*n-1;

 printf("                         *****霍夫曼哈夫曼编码*****\n");

 printf("总共有%d个字符\n",n);

 hufmtree tree[2*N-1];

 codetype code[N];

 int i,j;//循环变量

 huffman(tree);//建立哈夫曼树

 huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码

 printf("输出每个字符的哈夫曼编码\n");

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

 {

  printf("%c: ",code[i].ch);

  for(j=code[i].start;j<n;j++)

   printf("%c ",code[i].bits[j]);

  printf("\n");

 }

}

void huffman(hufmtree tree[])//建立哈夫曼树

{

 int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标

 float small1,small2,f;

 char c;

 for(i=0;i<m;i++)    //初始化

 {

  tree[i].parent=0;

  tree[i].lchild=-1;

  tree[i].rchild=-1;

  tree[i].weight=0.0;

 }

 printf("依次读入前%d个结点的字符及权值(中间用空格隔开)\n",n);

 for(i=0;i<n;i++)  //读入前n个结点的字符及权值

 {

  printf("输入第%d个字符为和权值",i+1);

  scanf("%c %f",&c,&f);

  getchar();

  tree[i].ch=c;

  tree[i].weight=f;

 }

 for(i=n;i<m;i++)      //进行n-1次合并，产生n-1个新结点

 {

  p1=0;p2=0;

  small1=maxval;small2=maxval;   //maxval是float类型的最大值

  for(j=0;j<i;j++)    //选出两个权值最小的根结点

   if(tree[j].parent==0)

    if(tree[j].weight<small1)

    {

     small2=small1;  //改变最小权、次小权及对应的位置

     small1=tree[j].weight;

     p2=p1;

     p1=j;

    }

    else

     if(tree[j].weight<small2)

     {

      small2=tree[j].weight;  //改变次小权及位置

      p2=j;

     }

  tree[p1].parent=i;

  tree[p2].parent=i;

  tree[i].lchild=p1;  //最小权根结点是新结点的左孩子

  tree[i].rchild=p2;  //次小权根结点是新结点的右孩子

  tree[i].weight=tree[p1].weight+tree[p2].weight;

 }

}//huffman

void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码

//codetype code[]为求出的哈夫曼编码

//hufmtree tree[]为已知的哈夫曼树

{

 int i,c,p;

 codetype cd;   //缓冲变量

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

 {

  cd.start=n;

  cd.ch=tree[i].ch;

  c=i;       //从叶结点出发向上回溯

  p=tree[i].parent;   //tree[p]是tree[i]的双亲

  while(p!=0)

  {

   cd.start--;

   if(tree[p].lchild==c)

    cd.bits[cd.start]='0';   //tree[i]是左子树，生成代码'0'

   else

    cd.bits[cd.start]='1';   //tree[i]是右子树，生成代码'1'

   c=p;

   p=tree[p].parent;

  }

  code[i]=cd;    //第i+1个字符的编码存入code[i]

 }

}

2.运行结果

 

第二篇：信息论与编码理论课程实验报告

信息论与编码理论课程实验报告

实验：无失真信源编码技术在数据压缩中的应用