信息論程序 半字節(jié) 哈弗曼 重復(fù)碼編譯碼

1、實驗一 英文半字節(jié)壓縮編碼技術(shù)實驗二 Huffman編碼實驗三 重復(fù)碼編譯碼方法 實驗一 英文半字節(jié)壓縮編碼技術(shù)一、實驗?zāi)康?1、理解信源編碼的作用和目的，掌握數(shù)據(jù)壓縮的基本思想；2、掌握數(shù)據(jù)壓縮中常用的比特流操作辦法；3、掌握英文半字節(jié)壓縮編碼技術(shù)。二、實驗內(nèi)容 通過C語言編程，實現(xiàn)對一般英文文本文件的半字節(jié)壓縮編碼與譯碼程序，并觀察編碼、譯碼結(jié)果以及壓縮效果。三、實驗原理 對于一個通信系統(tǒng)來說，信息傳輸?shù)挠行?、可靠性、安全性和認證性是人們的主要目標。其中，信息傳輸?shù)挠行灾傅氖潜M可能的使用較短的時間和較少的設(shè)備等資源來傳送盡可能多的信息，而這一目的主要是通過信源編碼這個環(huán)節(jié)來實現(xiàn)的。 雖

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

3、所有的大寫英文字母變成小寫字母)；2)保留標點符號：“，”、“?！?、“？”“：”和“ ”；3)將“！”和“；”變?yōu)椤??！保渌柸孔兂伞?”。這樣，原來的英文文本就變成了一個新的文本，該文本全部由26個英文字母和“，”、“?！?、“？”、“：”以及“ ”這31種符號組成，而且，文章的大意并沒有發(fā)生大的變化?？梢哉J為這種失真是在允許的失真范圍之內(nèi)的。當然，為了簡化操作，上面的第一步也可省略。雖然這樣會使輸出文件中既有大寫字符，又有小寫字符，但只需在后面的編碼操作時將大、小寫等同處理，則同樣達到了不區(qū)分大小寫的目的。（二）數(shù)據(jù)壓縮 在計算機中，文本文件中的每個符號都是由8位的ASCII碼所構(gòu)成，

4、共有256種取值的可能。既然經(jīng)過上述有損處理后文件中只存在31種不同的符號，所以在壓縮編碼過程中只需對31種符號進行編碼，就可以大大壓縮文本文件的數(shù)據(jù)量?？紤]到各字母以及符號出現(xiàn)的概率，并考慮碼字的可分離性，可以采取以下的編碼方法來進行數(shù)據(jù)的壓縮：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這樣，一些最經(jīng)常出現(xiàn)的符號從原來的8bit變?yōu)?bit，達到了數(shù)據(jù)壓縮的目的。從表中可以看出，后16個符號的碼字中前4比特均為“1111”，因此可先向編碼文件輸出前4比特，然后再輸出后4比特。這樣的好處是：不論是前15種符號還是后16種符號，都可執(zhí)行同一種輸出操作

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

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

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

9、序設(shè)計中發(fā)生的問題以及解決的辦法要加以敘述與總結(jié)；4、附上所設(shè)計的程序清單，并對關(guān)鍵部分進行說明。/*編碼程序*/#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;和"；"變?yōu)?quot;。" 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編碼一、實驗?zāi)康?、熟練掌握Huffman編碼過程；2、掌握C語言遞歸程序的設(shè)計和調(diào)試技術(shù)；3、掌握C語言中的動態(tài)分配內(nèi)存技術(shù)。二、試驗內(nèi)容根據(jù)輸入的信源符號數(shù)及相應(yīng)的概率分布，使用C語言編寫Huffman編碼程序，從而輸出每個信源符號所對應(yīng)的碼字。三、實驗原理在眾多的無失真信道編碼技術(shù)中，Huffman編碼是一種有效的獲得最佳碼

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

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

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

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

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

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

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

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

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

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

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

29、的程序流程圖；3、對程序設(shè)計中發(fā)生的問題以及解決的辦法要加以敘述與總結(jié)；4、附上所設(shè)計的程序清單，并對關(guān)鍵部分進行說明。#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); 實驗三 重復(fù)碼編譯碼方法一、實驗?zāi)康?1、理解信道編碼的作用和目的；2、鞏固“實驗一”中的比特流操作辦法；3、掌握重復(fù)碼的編解碼技術(shù)。二、實驗內(nèi)容通過C語言編程，實現(xiàn)對數(shù)據(jù)文件的（3，1）二元重復(fù)碼編碼與譯碼程序，并對編碼、譯碼結(jié)果進行觀察與比較。三、實驗原理 一般的通信信道中總是不可避免的存在噪聲或者干擾，因此在信息傳輸?shù)倪^程中也就必然會造成信息的損失，或者說，信源符號在有噪信道中的傳輸過程中會產(chǎn)生

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

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

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

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

39、存中的8比特全部讀取完畢，則執(zhí)行下一次向輸入文件的讀取。 2）輸出數(shù)據(jù)時，由于每次向輸出文件的寫入是以字節(jié)（8bit）為單位的，因此需要通過位操作來將需要輸出的每個比特按順序存入緩存中。當緩存湊足8bit（1字節(jié)）有效數(shù)據(jù)時才執(zhí)行一次向輸出文件的寫入操作。四、實驗步驟1、編寫重復(fù)碼的編碼程序，對數(shù)據(jù)文件進行重復(fù)編碼，并觀察編碼后的效果；2、編寫重復(fù)碼的譯碼程序，對編碼后的文件進行譯碼，并與原文件進行比較。五、實驗環(huán)境1、計算機；2、Visual C+編程環(huán)境。六、實驗報告要求1、格式與內(nèi)容應(yīng)符合實驗報告標準；2、對程序設(shè)計的思路以及具體設(shè)計步驟應(yīng)詳細說明，并附上相應(yīng)的程序流程圖；3、對程序設(shè)計中發(fā)生的問題以及解決的辦法要加以敘述與總結(jié)；4、附上所設(shè)計的程序清單，并對關(guān)鍵部分進行說明。# 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",&