1、精選優質文檔-傾情為你奉上信息與編碼實驗教案數學與計算科學學院信息教研室 2009年10月10日信息編碼理論是信息計算科學專業的一門重要的專業基礎課，對于提高學生的信息科學基礎知識具有重要的作用。信息編碼實驗，是為了提高學生的應用技能，融匯計算機編程能力培養與信息編碼基礎理論的一個重要環節。實驗包括四個：。l 信源熵的計算l 香農編碼l 循環碼l 有限域上插值多項式的構造信息編碼實驗要求用C語言完成。實驗一、信源熵的計算實驗背景：根據信源熵的性質，英語的信源熵的最大值為(比特/符號)，但事實上，由于在英語中的字母并非等概出現(表1)，實際的離散信源熵大概為(比特/符號），有些字母之間還有較強的

2、依賴關系，為了進一步逼近實際情況，可對英語信源進行2維、三維等形式的統計，求得實際的熵，其中（比特/符號），（比特/符號）。容易推知，有依賴關系的字母數越多，輸出的序列越接近于實際情況，當依賴關系延伸到無窮遠時，信源輸出的就是真正的英語。此時可求出馬爾可夫信源的極限熵（比特/符號）。表1 27個英語符號出現的概率符號 概率符號 概率符號 概率空格 0.2S   0.052Y,W  0.012E  0.105H   0.047G   0.011T   0.072D   0.035B  0.0105O  0.

3、0654L   0.029V   0.008A  0.063C  0.023K  0.003N  0.059F,U  0.0225X   0.002I  0.055M  0.021J,Q,Z  0.001R   0.054P  0.0175實驗內容：1. 將一大段英文文章作為要統計的樣本文件2. 對樣本文件進行一維概率統計，并計算出信源熵及冗余度3. 對樣本文件進行二維概率統計，并計算出信源熵及冗余度在進行統計時，首先要在程序中打開文件，然后對文件中的字符讀入程序中

4、，進行統計。而在二維統計時，尤其要求對文件的指針操作要熟悉。如讀入 “newspaper”時，應該依次讀入 “ne ew ws sp pa ap pe er”，而如果使用fgetc()等命令讀文件時，讀入的是 “ne ws pa pe” 為了依次讀入“ne ew ws sp pa ap pe er”，就要求在每次調入fgetc()等命令后，再將文件指針往后退一步，即要求學生能熟練使用fseek()命令進行指針定位操作。二維信源熵程序如下：#include <stdio.h>#include <math.h>#include <stdlib.h>#define

5、 NULL 0int charge(char c)int n; if(c>=65&&c<=90) c=c+32; if( c>+97&&c<=122) n=c-97; return n; else return -1;void main() int count2626=0; char zifu1,zifu2; int i,n,m,j; int sum=0; float q, sum1=0; FILE *fp; If(fp=fopen(“file”, “rb”)=NULL) printf(“ cant open file!n”); exit

6、(0); while(!feof(fp) zifu1=fgetc(fp); n=charge(zifu1); if(n!= -1) zifu2=fgetc(fp); m=charge(zifu2); if(m!= -1) countnm+; fseek(fp,-1,1); fclose(fp); for(i=0;i<26;i+) for(j=0;j<26;j+) sum=sum+countij; printf(“the number of all the code is %dn”, sum); q=(float)sum; for(i=0;i<26;i+) for(j=0;j&

7、lt;26;j+) if(j%3=0) printf(“n”); printf(“%c%c,%4d, %6.5f% ”,i+97,j+97,countij,countij*100/q); printf(“n”); for(i=0;i<26;i+) for(j=0;j<26;j+) if(countij)sum1=sum1+(float)(countij/q)*log10(1/(double)(countij /q)/log10(double)(2); printf(“n 信息熵為： H(x)=%fn”, sum1);實驗要求：1） 自己生成一個英文文件，可以在網上找，也可以自己生成

8、。為了保證實驗數據的可靠性，數據的量要比較大。為了保證二維信源統計的可靠性，建議文件的英文字符在十萬以上。2） 編寫一維信源統計程序，得出一維統計頻次，計算信源熵及剩余度。3） 編寫二維信源統計程序，得出二維統計頻次，計算信源熵及剩余度。4） 提交二維信源剩余度的實驗報告，及實驗體會心得。實驗二、香農編碼實驗背景：Hfffman編碼、Fano編碼以及 Shannon編碼是重要的統計編碼形式，在信源編碼中具有重要的作用。由于 Huffman 編碼在數據結構課程中已經出現。 因此，選用 Shannon編碼為主要練習對象。實驗內容：Shannon 碼編碼步驟為：1. 將信源的所有符號按概率從大到小排

9、列：2. 對第個信源符號取整數碼長, 為取整運算3. 計算累加概率4. 將變換成二進制數，并按步驟2中計算的長度取的二進制系數，組合起來即為的香農碼字.程序如下：#include<stdio.h>#include<iostream.h>#include<math.h>double P6=0.25,0.1,0.2,0.25,0.15,0.05,Pax6,machang6;void main() double temp; for(int a=1;a<6;a+) for(int i=0;i<6-a;i+) if(Pi<Pi+1) temp=Pi;

10、 Pi=Pi+1; Pi+1=temp; for(int i=0;i<6;i+) cout<<Pi<<" " cout<<endl; for(i=0;i<6;i+) Pax0=0.0; Paxi+1=Paxi+Pi; cout<<"概率累加和為:"<<endl; for(i=0;i<6;i+) cout<<Paxi<<" " cout<<endl; for(i=0;i<6;i+) double m=log(1/Pi)

11、/log(2); if(m-int(m)=0) machangi=log(1/Pi)/log(2); else machangi=int(m)+1; cout<<Pi<<"的碼長為:"<<machangi<<endl; for(i=0;i<6;i+) for(int j=0;j<machangi;j+) int n=int(Paxi*2); cout<<n;if(Paxi*2-1)>0) Paxi=Paxi*2-1; continue;if(Paxi*2-1)=0)Paxi=Paxi*2-1;el

12、sePaxi=Paxi*2; cout<<endl; 實驗要求：1） 熟練掌握香農編碼的原理2） 掌握二進制小數的輸出方法3） 如果時間允許，建議完成Huffman編碼的程序設計。4） 完成香農編碼的實驗報告及實驗心得體會。實驗三、循環碼實驗背景：循環碼是線性分組碼的一種，具有較好的數學特征，可以用代數理論對循環碼進行研究。在循環碼的編碼與校驗過程中，上多項式的除法是重要環節。在徐士良的常用算法程序集（C語言描述）中，有實系數的多項式除法。對其進行改進，使其系數定義在上，可很好地實現循環編碼及校驗的要求。實驗內容：完成二進制多項式除法的設計，程序中 其中 其中, 在循環碼中，只需保

13、留多項式相除的余式即可。下面的程序中， ，最后余式#include "stdio.h"jiajian(a,b)int a,b; if(a=1&&b=1) return(0); if(a=0&&b=1) return(1); if(a=1&&b=0) return(1); if(a=0&&b=0) return(0);cheng(a,b)int a,b; if(a=1&&b=1) return(1); if(a=0&&b=1) return(0); if(a=1&&

14、b=0) return(0); if(a=0&&b=0) return(0); chu(a,b)int a,b; if (a=1&&b=1) return(1); if(a=0) return(0);void pdiv(p, m, q, n, s, k, r, l)int m,n,k,l,p ,q ,s ,r ; int i,j,mm,ll,kk; for(i=0; i<=k-1; i+) si=0; ll=m-1; for(i=k; i>=1; i-) si-1=chu(pll,qn-1); mm=ll; for (j=1; j<n; j+)

15、 kk=cheng(si-1,qn-j-1);pmm-1=jiajian(pmm-1,kk);mm=mm-1; ll=ll-1; for (i=0; i<=l-1; i+) ri=pi; printf("%d ",ri); return;main() int i;static int p6=1,1,0,0,0,1;static int q4=1,1,0,1;int s3,r3;pdiv(p,6,q,4,s,3,r,3);實驗要求：1） 熟練掌握CRC編碼的原理2） 領會二進制除法在CRC編碼中的作用3） 完成上多項式的除法的程序設計4） 鼓勵學生在以上程序的基礎上，完

16、成CRC編碼、CRC譯碼的程序設計5） 提交上多項式的除法的實驗報告、實驗心得體會實驗四、有限域上插值多項式的構造實驗背景：依據個點構造次插值多項式，實質上是求解無非線性方程組，當插值點數不是很多的時候，可以在較短的時間內計算出插值多項式的系數，使之滿足。但通常的實數域上的計算，無法解決誤差問題，為了避免誤差問題，我們將插值多項式定義在有限域上，構造出無誤差的插值多項式。當為素數時，為有限域，記為有限域上的多項式。實驗內容：例如：設,滿足, 的插值多項式.即求解方程組得解有限域上范德蒙方程組算法思想：Step0 輸入向量組素數p.Step1 對k=1, 2,n-1, 執行（i） 對執行 ；對執

17、行 （ii） 如果abs (yi) > p，yi % = p ；如果yi < 0；yi += p；（確保運算的對象范圍均在( 0, p ) 上）（iii） 對 執行Step2 對k=1, 2,n-1, 執行(i) ;對執行（ii） 如果abs (yi) > p，yi % = p ；如果yi < 0；yi += p；對 執行（iii） 對執行Step3 輸出范德蒙方程組的解x=b./ 看程序之前，請仔細閱讀解有限域上范德蒙方程組算法思想，如上/ 運算過程確保每一步運算的數均在(0, p )內./#include "stdio.h"#include &q

18、uot;malloc.h"#include "stdlib.h"int prime=7 ; /全局變量，確定上限素數void Vandermond(int n,int* x,int* y); /函數解范德蒙方程組，解即為所要求的系數int Inverse(int xx); /求逆元void main() /主函數入口int n=3;int x3=1, 2, 4;int y3=2, 6, 5;Vandermond(n, x, y); /調用函數求解系數，并存入數組y中void Vandermond(int n,int *x,int *y) /解范德蒙方程組，以獲取系數，并存入原數組y中 int yy, xx; /定義中間變量, 以確保每一步運算中間產生的數均在（0，p）范圍內. int temp; / for(int k=0;k<n-1;+k) for(int i=n-1;i>k;-i) yy=yi-yi-1; xx=xi-xi-k-1; if(yy%xx=0) yi=yy/xx; /判斷xx是否整除yy，否則取yy乘以其逆元 if(yi<0) yi%=prime; yi+=prime; else yi=yy*Inverse(xx); if(yi>prime) yi%=p