1、實驗一 英文半字節壓縮編碼技術實驗二 Huffman編碼實驗三 重復碼編譯碼方法 實驗一 英文半字節壓縮編碼技術一、實驗目的 1、理解信源編碼的作用和目的，掌握數據壓縮的基本思想；2、掌握數據壓縮中常用的比特流操作辦法；3、掌握英文半字節壓縮編碼技術。二、實驗內容 通過C語言編程，實現對一般英文文本文件的半字節壓縮編碼與譯碼程序，并觀察編碼、譯碼結果以及壓縮效果。三、實驗原理 對于一個通信系統來說，信息傳輸的有效性、可靠性、安全性和認證性是人們的主要目標。其中，信息傳輸的有效性指的是盡可能的使用較短的時間和較少的設備等資源來傳送盡可能多的信息，而這一目的主要是通過信源編碼這個環節來實現的。 雖

2、然有許許多多不同的信源編碼方法，但總的說來，信源編碼主要是通過減少或消除信源的剩余度來提高傳輸效率的。而且，有時人們為了追求更高的傳輸效率，在滿足實際需求的情況下，還允許在編譯碼過程中存在一定程度的失真，這就是所謂的有損壓縮。當然，針對不同的應用要求，可以選擇不同的壓縮編碼辦法，為了方便理解和實現，針對一般的英文文本，可以設計一種半字節壓縮編碼方法來實現數據的壓縮。（一）有損處理 在一般英文文本中，除了大、小寫英文字母外，還有多種不同的標點符號。為了達到在不影響文章大意的前提下，盡可能的減少需編碼的符號數，以提高信息傳輸效率的目的，可采取這樣的處理方法：1)所有的英文字母不區分大、小寫(如：將

3、所有的大寫英文字母變成小寫字母)；2)保留標點符號：“，”、“。”、“？”“：”和“ ”；3)將“！”和“；”變為“。”，其他符號全部變成“ ”。這樣，原來的英文文本就變成了一個新的文本，該文本全部由26個英文字母和“，”、“。”、“？”、“：”以及“ ”這31種符號組成，而且，文章的大意并沒有發生大的變化。可以認為這種失真是在允許的失真范圍之內的。當然，為了簡化操作，上面的第一步也可省略。雖然這樣會使輸出文件中既有大寫字符，又有小寫字符，但只需在后面的編碼操作時將大、小寫等同處理，則同樣達到了不區分大小寫的目的。（二）數據壓縮 在計算機中，文本文件中的每個符號都是由8位的ASCII碼所構成，

4、共有256種取值的可能。既然經過上述有損處理后文件中只存在31種不同的符號，所以在壓縮編碼過程中只需對31種符號進行編碼，就可以大大壓縮文本文件的數據量。考慮到各字母以及符號出現的概率，并考慮碼字的可分離性，可以采取以下的編碼方法來進行數據的壓縮：1)對于概率最大的15個符號分別編以“0000”“1110”的碼字：符號碼字符號碼字符號碼字符號碼字空格0000e0100l1000s1100a0001f0101n1001t1101c0010h0110o1010u1110d0011i0111r10112)對于其余的16個符號分別編以“1111 0000”“1111 1111”的碼字。符號碼字符號碼字

5、符號碼字符號碼字,1111 0000b1111 0100m1111 1000w1111 1100.1111 0001g1111 0101p1111 1001x1111 1101?1111 0010j1111 0110q1111 1010y1111 1110:1111 0011k1111 0111v1111 1011z1111 1111這樣，一些最經常出現的符號從原來的8bit變為4bit，達到了數據壓縮的目的。從表中可以看出，后16個符號的碼字中前4比特均為“1111”，因此可先向編碼文件輸出前4比特，然后再輸出后4比特。這樣的好處是：不論是前15種符號還是后16種符號，都可執行同一種輸出操作

6、（輸出4比特），只是對于后16種符號是連續執行兩次而已。 （三）譯碼譯碼過程是編碼的逆過程，解碼后得到由這31種符號所組成的文本文件。由于后16個符號的碼字中前4比特均為“1111”，因此可設計譯碼過程為：每次讀取4bit。若不為“1111”，則根據此次讀取的4bit譯為相應的前15個符號之一；若為“1111”，則再次讀取4bit，并根據后4bit譯為相應的后16個符號之一。這樣，不論是前15種符號還是后16種符號的譯碼，都可執行同一種讀取操作（讀取4比特），只是對于后16種符號是連續執行兩次而已。（四）半字節操作 在計算機中，所有對數據的操作（不論是數據的存儲還是對文件的讀寫）都是以字節（8

7、bit）為基本單位的，而我們的編碼與解碼都是以半個字節（4bti）為單位的，因此需要運用位操作來進行數據的控制：1）編碼過程中，執行的操作是每次輸出4比特。由于每次向輸出文件的寫入是以字節（8bit）為單位的，因此可定義一個緩存變量來存儲每次輸出的4比特數據。只有當緩存中的有效數據湊足8bit（1字節）時才執行一次向輸出文件的寫入操作。這里需要注意的是，如果待編碼文件中所有符號的碼長之和不是8的整數倍時，就會出現緩存中剩余4比特有效數據不能輸出（因為不能湊夠滿字節）的情況。這時可以在后面補4比特“0000”（即為空格），使其能夠輸出到輸出文件中。2）譯碼過程中，執行的操作是每次讀取4bit。由

8、于每次向輸入文件的讀取是以字節（8bit）為單位的，故需將每次讀取的8bit（1字節）存入緩存，然后使用位操作依次讀取其前后各4比特。四、實驗步驟1、編寫有損處理程序，在不影響文章大意的基礎上對英文文本文件進行有損處理，減少需編碼的符號數，產生待編碼文件；2、編寫半字節編碼程序，對待編碼文件進行半字節壓縮編碼，并計算壓縮比，觀察壓縮效果；3、編寫半字節解碼程序，對壓縮后的文件進行解碼，并與壓縮前的文件進行比較。五、實驗環境1、計算機；2、Visual C+編程環境。六、實驗報告要求1、格式與內容應符合實驗報告標準；2、對程序設計的思路以及具體設計步驟應詳細說明，并附上相應的程序流程圖；3、對程

9、序設計中發生的問題以及解決的辦法要加以敘述與總結；4、附上所設計的程序清單，并對關鍵部分進行說明。/*編碼程序*/#include<stdio.h>#include<stdlib.h>char EditTxt(char a) if(a>='A' && a<='Z') a=a+32; else if(!(a>='a' && a<='z') if(a='' | a='!') a='.' /將"！&q

10、uot;和"；"變為"。" else if(a!=' ' && a!=':' && a!='?' && a!=',' && a!='.') a=' ' return a;int GetId(char *p,char a) int i; for(i=0;i<31;i+) if(pi=a) break; return i;void main() FILE *rfp,*wfp; int i, fl

11、ag; unsigned char ch,term=0; char a31=' ','a','c','d','e','f','h','i','l','n', 'o','r','s','t','u',',','.','?',':','b', 'g','j&#

12、39;,'k','m','p','q','v','w','x','y','z' if(rfp=fopen("file.txt","r")=NULL) printf("Cannot open infile!n"); exit(0); if(wfp=fopen("file2.txt","w")=NULL) printf("Cannot open m

13、idfile!n"); exit(0); flag=1;ch=getc(rfp); while(!feof(rfp) ch=EditTxt(ch); i=GetId(a,ch);if(i<=14)if(flag=0) /緩沖未滿putc(term|i,wfp);flag=1;else /緩沖已滿term=i*16;flag=0;elseif(flag=0) /緩沖未滿putc(term|15,wfp);term=(i-15)*16;flag=0;else /緩沖已滿putc(240|(i-15),wfp);flag=1;ch=getc(rfp);if(flag=0) putc(

14、term,wfp);fclose(rfp);fclose(wfp);/*解碼程序*/#include<stdio.h>#include<stdlib.h>void main() FILE *rfp,*wfp; int flag; unsigned char ch,high,low; char a31=' ','a','c','d','e','f','h','i','l','n', 'o','

15、;r','s','t','u',',','.','?',':','b', 'g','j','k','m','p','q','v','w','x','y','z' if(rfp=fopen("file2.txt","r")=NULL) printf(

16、"Cannot open file!n"); exit(0); if(wfp=fopen("file3.txt","w")=NULL) printf("Cannot open file!n"); exit(0); flag=1;ch=getc(rfp); while(!feof(rfp) high=ch>>4;low=ch&15;if(flag=0)putc(ahigh+15,wfp);flag=1;else if(high=15)flag=0;elseputc(ahigh,wfp);flag=

17、1;if(flag=0)putc(alow+15,wfp);flag=1;else if(low=15)flag=0;elseputc(alow,wfp);flag=1;ch=getc(rfp);fclose(rfp);fclose(wfp); 實驗二 Huffman編碼一、實驗目的1、熟練掌握Huffman編碼過程；2、掌握C語言遞歸程序的設計和調試技術；3、掌握C語言中的動態分配內存技術。二、試驗內容根據輸入的信源符號數及相應的概率分布，使用C語言編寫Huffman編碼程序，從而輸出每個信源符號所對應的碼字。三、實驗原理在眾多的無失真信道編碼技術中，Huffman編碼是一種有效的獲得最佳碼

18、的編碼技術。它能夠充分利用短碼，大幅度降低碼字的平均碼長，從而獲得較高的編碼效率，在保證碼字的可分離性的同時，有效的提高了通信系統的有效性。也正是由于Huffman編碼技術的優越性，目前在有關信源編碼的許多領域中，Huffman編碼作為一項基本技術，得到了極為廣泛的應用。（一）Huffman編碼方法由于目前數字通信中一般都使用二進制符號，因此二進制的Huffman編碼技術最為普遍，其編碼步驟如下：1、將信源符號按概率從大到小進行排列；2、給兩個概率最小的信源符號各分配一個碼元“0”和“1”，然后將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只有（n-1

19、）個信源符號的新信源（假設原來所需編碼的符號數為n），稱為信源的第一次縮減信源S1；3、將縮減信源S1的符號仍按概率從大到小的順序進行排列，重復步驟2，得到只含（n-2）個符號的縮減信源S2；4、重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1，將這兩個符號各分配一個碼元“0”和“1”后，從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的Huffman碼字。（二）方差最小的Huffman碼字縮減信源時，若合并后的新符號概率與其他符號的概率相等，從編碼方法上來講，這幾個符號的次序可任意排列，編出的碼字都是正確的，但不同的編法得到的碼字不同，碼字長度也

20、不盡相同，從而碼長的方差也會不同。若碼長的方差較小，則意味著碼長變化較小，各個碼長都比較接近于平均碼長，這樣對于信息傳輸的實現，特別是對傳輸有實時性要求的時候，會帶來很大的便利，因此也就更好一些。為了得到方差最小的Huffman碼字，在對縮減信源按概率從大到小重新排列時，應使合并后的新符號盡可能地排在靠前的位置，這樣可使合并后的新符號重復編碼次數減少，使短碼得到充分利用，降低碼長的方差。（三）遞歸算法實現Huffman編碼由于在Huffman編碼過程中，每次都是對減少一個符號數的縮減信源進行同樣的操作排序與合并，且最終的碼字是按照編碼路徑逆序返回而得到，因此可利用遞歸的思想實現Huffman的

21、編碼程序。假設對n個符號、概率為pi的信源進行Huffman編碼，則遞歸實現算法的主要思想可簡單描述為：procedure Huffman(n,pi) if n = = 2 then 對兩個符號各分配一個碼元“0”和“1”； else 降序排序； 合并符號，并得到新的概率分布pi； Huffman(n-1, pi)； 對被合并的兩個符號各分配一個碼元“0”和“1”；end procedure（四）動態分配內存由于本程序設計要求根據所輸入的信源符號數與概率分布進行Huffman編碼，在輸入之前并不確定所要編碼的信源符號數，而且編得的碼字長度也不能確定，因此對各符號以及相應碼字的存儲使用固定長度的

22、數組顯然不太合適，而在C語言中使用動態分配內存技術則可以根據需要靈活分配存儲空間，從而有效的解決這個問題。C語言中常用的動態內存管理函數有以下四個：1、函數malloc這是給指針動態分配內存的通用函數。它的原型是：void * malloc (size_t nbytes)其中nbytes 是我們想要給指針分配的內存字節數。這個函數返回一個void*類型的指針，因此我們需要用類型轉換(type cast)來把它轉換成目標指針所需要的數據類型，例如：char * ronny;ronny = (char *) malloc (10);這個例子將一個指向10個字節可用空間的指針賦給ronny。當我們想

23、給一組除char 以外的類型（不是1字節長度的）的數值分配內存的時候，我們需要用元素數乘以每個元素的長度來確定所需內存的大小：int * bobby;bobby = (int *) malloc (5 * sizeof(int);這一小段代碼將一個指向可存儲5個int型整數的內存塊的指針賦給bobby，它的實際長度可能是 2，4或更多字節數，取決于程序是在什么操作系統下被編譯的。2、函數calloccalloc 與malloc 在操作上非常相似，他們主要的區別是在原型上：void * calloc (size_t nelements, size_t size)可見它接收2個參數而不是1個，這兩

24、個參數相乘被用來計算所需內存塊的總長度。通常第一個參數(nelements)是元素的個數，第二個參數 (size) 被用來表示每個元素的長度。例如，我們可以像下面這樣用calloc定義bobby：int * bobby;bobby = (int *) calloc (5, sizeof(int);malloc 和calloc的另一點不同在于calloc 會將所有的元素初始化為0。，而malloc 只管分配內存，并不能對所得的內存進行初始化，所以得到的一片新內存中，其值將是隨機的。3、函數realloc它被用來改變已經被分配給一個指針的內存的長度。其原型為：void * realloc (voi

25、d * pointer, size_t size)參數pointer 用來傳遞一個已經被分配內存的指針或一個空指針，而參數size 用來指明新的內存長度。這個函數給指針分配size 字節的內存。這個函數可能需要改變內存塊的地址以便能夠分配足夠的內存來滿足新的長度要求。在這種情況下，指針當前所指的內存中的數據內容將會被拷貝到新的地址中，以保證現存數據不會丟失，然后返回新的指針地址。如果新的內存尺寸不能夠被滿足，函數將會返回一個空指針，但原來參數中的指針pointer 及其內容保持不變。4、函數 free這個函數用來釋放被前面malloc, calloc 或realloc所分配的內存塊：void

26、free (void * pointer);注意：如果忘記釋放動態分配地內存，程序就會在結束時出現內存泄漏的問題。（五）程序設計問題1、數據存儲根據實驗要求，我們要根據輸入的信源符號數及相應的概率分布輸出每個信源符號所對應的碼字，因此需要定義一個記錄信源符號序號的數組，一個記錄相應符號概率的數組，一個記錄各符號碼字的二維數組，且各數組的長度應根據輸入的信源符號數決定。2、排序從Huffman算法流程來看，第一次排序和對縮減信源的排序略有不同。對縮減信源的排序是在基本有序的情況下進行排序的，也就是說，除了合并符號以外，其他的符號已經是降序排列的，因此只需將合并的符號插入到相應的位置即可。而且為了

27、得到方差最小的Huffman碼字，應使合并后的新符號盡可能地排在靠前的位置。對于第一次排序則沒有這樣的條件與要求。也正是為此，我們可以在上述的遞歸算法中將這兩種排序分開：（主程序）第一次排序；procedure Huffman(n,pi) if n = = 2 then 對兩個符號各分配一個碼元“0”和“1”； else 合并符號，并得到新的概率分布pi； 縮減信源的排序； Huffman(n-1, pi)； 對被合并的兩個符號各分配一個碼元“0”和“1”；end procedure由于對信源符號的描述有三個數組：序號、概率以及碼字，因此排序中的每次改變都需對這三個數組同時進行相應的變動。3、

28、遞歸編碼在遞歸算法中，每次遞歸都需要對參與合并的兩個符號分配碼元。由于對信源符號的描述由數組完成，因此在逐級返回時只是返回指向數組的指針，而其中元素的值不能返回。為了在每次返回上一級遞歸時找到這兩個符號，則需要在每次遞歸時記錄下這兩個符號的序號，以便返回時能正確的對這兩個符號分配碼元。四、實驗步驟1、使用C語言編寫Huffman編碼程序；2、輸入幾種信源的符號數及其概率，將程序輸出的碼字與手動計算的碼字進行比較，驗證程序的正確性。 五、實驗環境1、計算機；2、Visual C+編程環境。六、實驗報告要求1、格式與內容應符合實驗報告標準；2、對程序設計的思路以及具體設計步驟應詳細說明，并附上相應

29、的程序流程圖；3、對程序設計中發生的問題以及解決的辦法要加以敘述與總結；4、附上所設計的程序清單，并對關鍵部分進行說明。#include <stdio.h> #include"stdlib.h"struct NODEfloat w;int parent,lchild,rchild;void Huffman(int *ID,struct NODE *HT,int m,int n)HT2*n-m.w=HTIDm-1.w+HTIDm-2.w;HTIDm-1.parent=2*n-m;HTIDm-2.parent=2*n-m;HT2*n-m.lchild=IDm-1;H

30、T2*n-m.rchild=IDm-2;HT2*n-m.parent=-1;IDm-2=2*n-m;void Select(int *ID,struct NODE *HT,int m)int k,t;t=IDm-1;for(k=0;k<m-1;k+)if(HTIDk.w<=HTIDm-1.w)IDm-1=IDk;IDk=t;t=IDm-1;void main()struct NODE *HT;int *ID,*CODE;char *ch;int n,i,j,t,m,b,f;float sum;printf("Please enter the number of the s

31、ymbols:n");scanf("%d",&n);ID=(int *)malloc(sizeof(int)*n);ch=(char *)malloc(sizeof(char)*n);CODE=(int *)malloc(sizeof(int)*n);HT=(struct NODE*)malloc(sizeof(struct NODE)*(2*n-1);printf("Please enter the symbolsn");for(i=0;i<n;i+)fflush(stdin);scanf("%c",&

32、;chi);printf("Please enter the probabilityn");sum=0;for(i=0;i<n;i+)fflush(stdin);scanf("%f",&HTi.w);HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;sum+=HTi.w;if(sum!=1)printf("ERRORn");exit(-1);for(i=0;i<n;i+) /首次對碼元進行排序t=0;for(j=0;j<n;j+)if(HTi.w<HTj.w) t+;e

33、lse if(HTi.w=HTj.w && i>j)t+;IDt=i;for(i=n;i>1;i-)Huffman(ID,HT,i,n);Select(ID,HT,i-1);printf("Huffman Code Is :n");for(i=0;i<n;i+)m=0;for(b=i;HTb.parent!=-1;b=HTb.parent)f=HTb.parent;if(HTf.lchild=b)CODEm=1;elseCODEm=0;m+;printf("%c-%f-",chi,HTi.w);for(j=m-1;j&g

34、t;=0;j-)printf("%d",CODEj);printf("n");free(ID);free(HT);free(ch);free(CODE); 實驗三 重復碼編譯碼方法一、實驗目的 1、理解信道編碼的作用和目的；2、鞏固“實驗一”中的比特流操作辦法；3、掌握重復碼的編解碼技術。二、實驗內容通過C語言編程，實現對數據文件的（3，1）二元重復碼編碼與譯碼程序，并對編碼、譯碼結果進行觀察與比較。三、實驗原理 一般的通信信道中總是不可避免的存在噪聲或者干擾，因此在信息傳輸的過程中也就必然會造成信息的損失，或者說，信源符號在有噪信道中的傳輸過程中會產生

35、失真。為了降低這種信息損失，就需要我們在信源符號輸入到信道之前，對其進行有效的信道編碼。 信道編碼是通信系統中的一個重要環節，目的就是為了降低傳輸過程中錯誤發生的概率，從而提高通信系統的可靠性。信道編碼的基本思想是附加冗余信息，增加信源的剩余度，這樣在接收端就可以利用相關性進行檢錯或者糾錯。根據有噪信道編碼定理，附加冗余位可以降低信息傳輸率，使錯誤概率減小，當信息傳輸率小于信道容量時，理論上就可以使譯碼錯誤概率任意小，從而幾乎無失真的進行信息傳送。當然，同樣是增加信源剩余度，不同的編碼方法，其檢、糾錯能力也不同。目前，人們對信道編碼的研究有很多，大概可分為線性分組碼、循環碼、卷積碼等等。（一）

36、重復碼重復編碼是一種簡單的信道編碼方法，其實質就是將每個要發送的符號重復發送，或者說是將原來的每一個信源符號編成多個相同的碼元符號，其值與原來的符號取值相同。比如(3，1)二元重復碼，其編碼方法就是將原來二進制序列中的每一個“0”編成“000”，將每一個“1”編成“111”。因此，我們可以設計以下簡單的編碼流程：1、讀取待編碼文件的一個比特；2、重復3次向輸出文件中寫入一個相同的比特；3、重復執行上面兩步，直到待編碼文件的所有數據全部編碼完畢。所謂的譯碼規則就是指接收符號與發送符號之間的映射關系。不同的譯碼規則會造成不同的平均錯誤概率，所以人們一般都根據最小錯誤概率準則來確定譯碼規則。對于二元

37、對稱信道來說，一般總認為出錯概率是小于等于0.5的，所以對于二元重復碼，最小錯誤概率準則與擇多譯碼規則是一致的，也就是說，譯碼時根據碼字中“0”“1”的數目選擇數目多的進行譯碼。比如(3，1)二元重復碼的譯碼，可以將接收到的“000”、“001”、“010”和“100”譯為“0”，將接收到的“011”、“101”、“110”和“111”譯為“1”。這樣，每個碼字對于傳輸過程中發生的任一位錯誤，通過譯碼都可以進行自動糾正。可以證明，一個（n，1）重復碼可以糾正傳輸過程中可能出現的不多于 個差錯。根據上述譯碼思想，我們同樣可設計（3，1）二元重復碼的譯碼流程如下：1、重復3次從文件中讀取1比特，并

38、計算這3比特之和，記為bitsum；2、若bitsum大于等于2，向輸出文件中寫入1比特“1”；否則，向輸出文件中寫入1比特“0”；3、重復執行上面兩步，直到全部譯碼完畢。（二）比特操作 在“實驗一”中，我們已經熟悉了如何將一個字節（8bit）數據進行拆分，并每次針對半個字節（4bit）進行處理。在本實驗中，根據重復碼的編、譯碼原理，我們每次操作的對象是1bit，因此應該對“實驗一”中的方法進行修正，使之能夠對字節中的每個bit進行控制與操作：1）讀取數據時，由于每次向輸入文件的讀取是以字節（8bit）為單位的，故需將讀取的8比特數據存入緩存中，然后通過位操作依次從緩存中讀取每1比特數據。若緩

39、存中的8比特全部讀取完畢，則執行下一次向輸入文件的讀取。 2）輸出數據時，由于每次向輸出文件的寫入是以字節（8bit）為單位的，因此需要通過位操作來將需要輸出的每個比特按順序存入緩存中。當緩存湊足8bit（1字節）有效數據時才執行一次向輸出文件的寫入操作。四、實驗步驟1、編寫重復碼的編碼程序，對數據文件進行重復編碼，并觀察編碼后的效果；2、編寫重復碼的譯碼程序，對編碼后的文件進行譯碼，并與原文件進行比較。五、實驗環境1、計算機；2、Visual C+編程環境。六、實驗報告要求1、格式與內容應符合實驗報告標準；2、對程序設計的思路以及具體設計步驟應詳細說明，并附上相應的程序流程圖；3、對程序設計中發生的問題以及解決的辦法要加以敘述與總結；4、附上所設計的程序清單，并對關鍵部分進行說明。# include"stdio.h"#include<stdlib.h>unsigned char Encode(unsigned char ch)unsigned char code;if(ch=1)code=7;elsecode=0;return code;void main()FILE *rfp,*wfp;unsigned char buf,k,ch,j;int i,flag;flag=0;if(rfp=fopen("file.txt",&