shannon coding.cpp

来自「以香农编码定理为依据,采用二进制香农编码方法,利用C语言在VC++平台上进行软件」· C++ 代码 · 共 158 行

/*程序中通过修改宏定义#define max_PN 6，是消息符号的个数具有可变性，在一定意义上说有灵活性*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define max_CL 10    /*maxsize of length of code*/
#define max_PN 20 /*输入序列的个数*/
typedef float datatype;
typedef struct SHNODE {
        datatype pb;  /*第i个消息符号出现的概率*/
 datatype p_sum;  /*第i个消息符号累加概率*/
        int kl;   /*第i个消息符号对应的码长*/
 int code[max_CL]; /*第i个消息符号的码字*/
 struct SHNODE *next;
        }shnolist;
datatype sym_arry[max_PN];     /*序列的概率*/

void pb_scan();             /*得到序列概率*/
void pb_sort();      /*序列概率排序*/
void valuelist(shnolist *L);  /*计算累加概率，码长，码字*/
void codedisp(shnolist *L);

 

void pb_scan()
{
     datatype sum=0;
     int i,x;
	 printf("输入编码长度x: ");
	 scanf("%d",&x);          
           printf("input %d possible!\n",x);
           for(i=0;i<x;i++)
		   {  printf(">>");
           scanf("%f",&sym_arry[i]);
           sum=sum+sym_arry[i];	
		        }

/*判断序列的概率之和是否等于1，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.99<sum<1.0001出现的误差是允许的*/
     if(sum>1.0001||sum<0.99)
     { printf("sum=%f,sum must (<0.999<sum<1.0001)",sum);
       pb_scan();
     }
}
/*选择法排序*/
void pb_sort()
     {
     int i,j,pos,x;
     datatype max;
     printf("输入编码长度x: ");
	 scanf("%d",&x);          
       for(i=0;i<x-1;i++)
        {
         max=sym_arry[i];
         pos=i;
           for(j=i+1;j<x;j++)
     if(sym_arry[j]>max)
              {
                max=sym_arry[j];
                pos=j;
               }
          sym_arry[pos]=sym_arry[i];
  sym_arry[i]=max;
    }
}

void codedisp(shnolist *L)
     {
     int i,j,x;
     printf("输入编码长度x: ");
	 scanf("%d",&x);          
     shnolist *p;
     datatype hx=0,KL=0;   /*hx存放序列的熵的结果，KL存放序列编码后的平均码字的结果*/
  p=L->next;
  printf("num\tgailu\tsum\t-lg(p(ai))\tlenth\tcode\n");
  printf("\n");
     for(i=0;i<x;i++)
  {
   printf("a%d\t%1.3f\t%1.3f\t%f\t%d\t",i,p->pb,p->p_sum,-3.332*log10(p->pb),p->kl);
   j=0;
   for(j=0;j<p->kl;j++)
    printf("%d",p->code[j]);
   printf("\n");
   hx=hx-p->pb*3.332*log10(p->pb);  /*计算消息序列的熵*/
   KL=KL+p->kl*p->pb;   /*计算平均码字*/
   p=p->next;    
  }
 printf("H(x)=%f\tKL=%f\nR=%fbit/code",hx,KL,hx/KL); /*计算编码效率*/
}
shnolist *setnull()
{  shnolist *head;
   head=(shnolist *)malloc(sizeof(shnolist));
   head->next=NULL;
   return(head);
}
shnolist *my_creat(datatype a[],int n)
 {
 shnolist *head,*p,*r;
 int i;
     head=setnull();
     r=head;
     for(i=0;i<n;i++)
 {  p=(shnolist *)malloc(sizeof(shnolist));
    p->pb=a[i];
    p->next=NULL;
    r->next=p;
    r=p;
 }
     return(head);
}

void valuelist(shnolist *L)
 {
	int x;
    printf("输入编码长度x: ");
	scanf("%d",&x);          
 shnolist *head,*p;
 int j=0;
 int i;
 datatype temp,s;
 head=L;
 p=head->next;
 temp=0;
 while(j<x)
 {
 p->p_sum=temp;
 temp=temp+p->pb;
 p->kl=-3.322*log10(p->pb)+1;
/*编码，*/
 {
   s=p->p_sum;
  for(i=0;i<p->kl;i++)
   p->code[i]=0;
  for(i=0;i<p->kl;i++)
  {
   p->code[i]=2*s;
   if(2*s>=1)
    s=2*s-1;
   else if(2*s==0)
    break;
   else s=2*s;
  }
 }
 j++;
 p=p->next;
 }
 }

void main(void)
    {
     shnolist *head;
     setnull();
     pb_scan();
     pb_sort();
     head=my_creat(sym_arry,max_PN);
     valuelist(head);
     codedisp(head);
    }