信息論三種編碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上LZW編碼LZW壓縮算法的基本原理：提取原始文本文件數(shù)據(jù)中的不同字符，基于這些字符創(chuàng)建一個編譯表，然后用編譯表中的字符的索引來替代原始文本文件數(shù)據(jù)中的相應字符，減少原始數(shù)據(jù)大小。看起來和調(diào)色板圖象的實現(xiàn)原理差不多，但是應該注意到的是，我們這里的編譯表不是事先創(chuàng)建好的，而是根據(jù)原始文件數(shù)據(jù)動態(tài)創(chuàng)建的，解碼時還要從已編碼的數(shù)據(jù)中還原出原來的編譯表.LZW編碼的流程圖：LZW編碼的源代碼：#include<string.h>#include<stdio.h>void copy1(char *prefix,char *s,int i,int j) in

2、t k; for(k=0;k<20;k+) prefixk=0; for(k=i;k<i+j;k+) prefixk-i=sk; void main()int i ,j,k,n,t,m;char s30,prefix30,dic2030="A","B","C",c20;k=3;m=0;j=1;i=0;printf(“Please input some words:n");gets(s);while(i<strlen(s) copy1(prefix,s,i,j); for(n=0;n<k;n+) if(

3、strcmp(prefix,dicn)=0) /比較兩字符串 j+; m=n; if( (i+j)<=strlen(s) ) copy1(prefix,s,i,j);else strcpy(prefix,""); printf(“%dn",m); if(strlen(prefix)!=0)/求字符串長度 strcpy(dick,prefix);/把后面的字符復給到前面 printf("%sn",dick); k=k+1; i=i+j-1; j=1; getch();實驗結(jié)果：Huffman編碼Huffman編碼原理簡介： 

4、60;  霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統(tǒng)計編碼。屬于無損壓縮編碼。霍夫曼編碼的碼長是變化的，對于出現(xiàn)頻率高的信息，編碼的長度較短；而對于出現(xiàn)頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。Huffman編碼過程的幾個步驟：l）將信號源的符號按照出現(xiàn)概率遞減的順序排列。2）將最下面的兩個最小出現(xiàn)概率進行合并相加，得到的結(jié)果作為新符號的出現(xiàn)概率。3）重復進行步驟1和2直到概率相加的結(jié)果等于1為止。4）在合并運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。5）記錄下概率為1處到當前信號源符號之間的0，l序列，

5、從而得到每個符號的編碼。Huffman編碼源代碼：#include <stdio.h>#include <math.h>#define sy_max 100#define sy_max2 30#define sy_max3 59#define DEEP 10 /*定義sycode1類*/typedef struct float weight; int flag;int father;int leftchilde;int rightchilde;sycode1; /*定義類sycode2類*/typedef struct int sy_arraysy_max2;int s

6、tart;sycode2;int main(void) sycode1 sy1sy_max3; sycode2 sy2sy_max2,cd; int i,j,x1,x2,n,c,p; float m1,m2,temp,hx=0,KL=0; printf("please input the signal's lengthn"); scanf("%d",&n); /*根據(jù)輸入長度，初始化編碼變量*/ for(i=0;i<=2*n-1;i+) sy1i.weight=0; sy1i.father=0; sy1i.flag=0; sy1i.

7、leftchilde=-1; sy1i.rightchilde=-1; printf("input the probability for every signal:n");/*根據(jù)輸入長度，接收相應數(shù)目的概率數(shù)*/ for(i=0;i<n;i+) printf("input %dth probability:",i+1); scanf("%f",&temp); sy1i.weight=temp; hx=hx-temp*3.332*log10(temp); for(i=0;i<n-1;i+) m1=m2=sy_ma

8、x; x1=x2=0; for(j=0;j<n+i;j+) if(sy1j.weight<m1&&sy1j.flag=0) m2=m1; x2=x1; m1=sy1j.weight; x1=j; else if(sy1j.weight<m2&&sy1j.flag=0) m2=sy1j.weight; x2=j; sy1x1.father=n+i; sy1x2.father=n+i; /*將找出的兩棵子樹合并為一棵子樹*/ sy1x1.flag=1; sy1x2.flag=1; sy1n+i.weight=sy1x1.weight+sy1x2.w

9、eight; sy1n+i.leftchilde=x1; sy1n+i.rightchilde=x2; for(i=0;i<n;i+) cd.start=n; c=i; p=sy1c.father; while(p!=0) if(sy1p.leftchilde=c) cd.sy_arraycd.start=1; else cd.sy_arraycd.start=0; cd.start=cd.start-1; c=p; p=sy1p.father; cd.start+; for(j=cd.start;j<=n;j+) sy2i.sy_arrayj=cd.sy_arrayj; sy2i

10、.start=cd.start; printf("nweightthuffmancoden"); for(i=0;i<n;i+) printf("%2.3f:t",sy1i.weight); for(j=sy2i.start;j<=n;j+) printf("%d",sy2i.sy_arrayj);/*計算平均碼長以及信源熵*/ KL=KL+(n-sy2i.start+1)*sy1i.weight; printf("n"); printf("nH(X)=%ftKL=%fnR=%f",

11、hx,KL,hx/KL);getch();實驗結(jié)果：Shannon編碼Shannon編碼源代碼#include <stdio.h>#include <math.h>#include <stdlib.h>#define sy_CL 10 /*最大碼長*/#define sy_PN 100 /*最大碼數(shù)*/typedef float sy_type;typedef struct SHNODE sy_type pb;sy_type sy_sum;int kl;int codesy_CL;struct SHNODE *next;sy_class;sy_type sy

12、m_arrysy_PN; /*序列的概率*/int sy; /*定義全局變量sy代表碼數(shù)也就是符號數(shù)*/void sy_pb_scan() int i;sy_type sum=0;printf("Think you for using this Shannon program!nPlease input lengthn");scanf("%d",&sy);printf("input%dsignal's probability:n",sy);printf(">>");for(i=0;i&l

13、t;sy;i+)scanf("%f",&sym_arryi);sum=sum+sym_arryi;if(sum>1.0001|sum<0.99) printf("sum=%f,sum must(<0.999<sum<1.0001)",sum);sy_pb_scan(); /*定義函數(shù)sy_pb_scan()，輸入數(shù)據(jù)，并且檢驗輸入概率和是否等于1*/void sy_sort() int i,j,pos;sy_type max;for(i=0;i<sy-1;i+)max=sym_arryi;pos=i;for(j

14、=i+1;j<sy;j+)if(sym_arryj>max)max=sym_arryj;pos=j;sym_arrypos=sym_arryi;sym_arryi=max; /*定義函數(shù)sy_sort()，對輸入概率進行由小到大排序*/void valuelist(sy_class *L)sy_class *head,*p;int j=0;int i;sy_type temp,s;head=L; temp=0;p=head->next;while(j<sy)p->sy_sum=temp;temp=temp+p->pb;p->kl=-3.322*log1

15、0(p->pb)+1;s=p->sy_sum;for(i=0;i<p->kl;i+)p->codei=0;for(i=0;i<p->kl;i+)p->codei=2*s;if(2*s>=1)s=2*s-1;else if(2*s=0)break;else s=2*s;j+;p=p->next; /*算法函數(shù)*/void codedisp(sy_class *L) int i,j; sy_class *p; sy_type hx=0,KL=0; p=L->next; printf("numtgailvtsumt-lb(p

16、(ai)tlenthtcoden"); printf("n"); for(i=0;i<sy;i+)printf("a%dt%1.3ft%1.3ft%ft%dt",i,p->pb,p->sy_sum,-3.332*log10(p->pb),p->kl); j=0; for(j=0;j<p->kl;j+) printf("%d",p->codej); printf("n"); hx=hx-p->pb*3.332*log10(p->pb); /*計算信

17、源序列的熵*/ KL=KL+p->kl*p->pb; /*計算平均碼字*/ p=p->next; printf("H(x)=%ftKL=%fnR=%fbit/code",hx,KL,hx/KL); /*計算編碼效率*/sy_class *setnull() sy_class *head; head=(sy_class *)malloc(sizeof(sy_class); head->next=NULL; return(head);sy_class *my_creat(sy_type a,int n) sy_class *head,*p,*r; int i; head=setnull(); r=head