完整版哈夫曼編碼-漢明編碼

（完整word版）哈夫曼編碼_漢明編碼1課題描述信息論理論基礎的建立，一般來說開始與香農（C.E。5卜2的0門）在研究通信系統(tǒng)時所發(fā)表的論文.信息論是在信息可以度量的基礎上，對如何有效、可靠的傳遞信息進行研究的科學，它涉及信息亮度、信息特性、信息傳輸速率、信道容量、干擾對信息傳輸的影響等方面的知識。通常把上述范圍的信息論稱為狹義信息論，又因為它的創(chuàng)始人是香農，故又稱為香農信息論。廣義信息論則包含通信的全部統(tǒng)計問題的研究，除了香農信息論之外，還包括信號設計、噪聲理論、信號的檢測與估值等。當信息在傳輸、存儲和處理的過程中，不可避免的要受到噪聲或其他無用信號的干擾時，信息理論會為可靠、有效的從數據中提取信息提供必要的根據和方法。因此必須研究噪聲和干擾的性質以及它們與信息本質上的差別，噪聲與干擾往往具有某種統(tǒng)計規(guī)律的隨機特性，信息則具有一定的概率特性，如度量信息量的熵值就是概率性質的.信息論、概率輪、隨機過程和數理統(tǒng)計學是信息論應用的基礎和工具。信息論主要研究如何提高信息系統(tǒng)的可靠性、有效性、保密性和認證性，以使信息系統(tǒng)最優(yōu)化。所謂可靠性高就是要使信源發(fā)出的消息經過信道傳輸以后，盡可能準確的、不失真的再現在接收端；而所謂有效性高，就是經濟效果好，即用盡可能少的資源和盡可能少的設備來傳送一定數量的信息；所謂保密性就是隱蔽和保護通信系統(tǒng)中傳送的信息，使它只能被授權接受者獲取，而不能被未授權者接受和理解；而認證性是指接受者能正確的判斷所接受的消息的正確性，驗證消息的完整性，而不是接收偽造的和被修改的信息.2信源編碼的相關介紹信源編碼分為無失真編碼和限失真編碼。一般稱無失真信源編碼定理為第一極限定理，限失真信源編碼為第三極限定理。由于信源符號之間存在分布不均勻和相關性，使得信源存在冗余（完整word版）哈夫曼編碼_漢明編碼度，信源編碼的主要任務是減少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短碼字序列的方法。信源編碼的基本途徑有兩個：使序列中的各個符號盡可能相互獨立，即解除相關性；使編碼中各個符號出現的概率盡可能相等，即概率均勻化。信源編碼的基礎是信息論中的兩個編碼定理：無失真編碼定理和限失真編碼定理，前者是可逆編碼的基礎?？赡媸侵府斝旁捶栟D換成代碼后，可從代碼無失真的恢復原信源符號。無失真編碼或可逆編碼只適用于離散信源。對于連續(xù)信源，編成代碼后就無法無失真的恢復原來的連續(xù)值，因為后者的取值可以有無限多個。3哈夫曼編碼3。1哈夫曼編碼算法算法步驟如下：1）將信源消息符號按照其出現的概率大小依次排列為p>p> >p2）取兩個概率最小的字母分別配以0和1這兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進制符號的字母重新排隊；3）對重新排列后的兩個概率最小的符號重復步驟2）的過程；4）不斷繼續(xù)上述操作，直到最后兩個符號配以0和1為止；5）從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字.3。2哈夫曼編碼特點哈夫曼編碼（HuffmanCoding）是一種用于無損數據壓縮的熵編碼算法，是可變長編碼的一（完整word版）哈夫曼編碼_漢明編碼種。由于經過哈夫曼編碼所編成的碼是具有唯一碼性質的即時碼，即各個相異字元所編出的哈夫曼碼都不相同，解碼時能夠看到編碼就立即解出原碼用?？偨Y得哈夫曼編碼具有以下特點：1）編出來的碼都是異字頭碼，保證了編碼的唯一可譯性；2）由于編碼長度可變，哈夫曼編碼與還原耗時很長；；3）由于編碼過程中0，1的指定是任意的，所以哈夫曼編碼的結果不唯一；4）哈夫曼編碼不同的結果平均碼長都相同。4哈夫曼編碼的。語言程序實現4.1程序設計流程圖：全部代碼:（完整word版）哈夫曼編碼_漢明編碼#include〈string。h>#include〈stdio。h>#include<malloc.h>typedefunsignedcharU8;typedefunsignedshortU16;typedefunsignedlongU32;//定義哈夫曼樹的結構體typedefstructHuffmanNode(doubleprob;structHuffmanNode^left;structHuffmanNode*right;}huffmancode;voidInit(U32*,double**);huffmancode*Encode(double*,U32);huffmancode*CreateBinaryTree(huffmancode**,int);voidPrint(huffmancode*,char*);voidDeleteBinaryTree(huffmancode*);voidDeleteBinaryTree(huffmancode*pHuffman){if(pHuffman一>left!二NULL)DeleteBinaryTree(pHuffman->left);if(pHuffman一〉right!=NULL)DeleteBinaryTree(pHuffman->right);free(pHuffman);return;)//輸出結果：給定值轉換為哈夫曼編碼voidPrint(huffmancode*pHuffman,char*code)(intnumChild=0;intstrLen=strlen(code);char*nextCode二(char*)malloc(strLen+2);if(pHuffman一〉left!=NULL){numChild++;strcpy(nextCode,code);nextCode[strLen]二'1';nextCode[strLen+1]二'\0’;Print(pHuffman一〉left,nextCode);}if(pHuffman一>right!=NULL)(numChild++;strcpy(nextCode,code);nextCode[strLen]二'0';（完整word版）哈夫曼編碼_漢明編碼nextCode[strLen+1]二’\0';Print(pHuffman-〉right,nextCode);}if(numChild=0)(printf("%lf哈夫曼編碼：％s\n"，pHuffman—〉prob,code);)free(nextCode);return;)huffmancode*Encode(double*p，U32n)(U32i；huffmancode*pRes;huffmancode**ppHuffman;ppHuffman=(huffmancode**)malloc(sizeof(huffmancode*)*n);for(i=0;i<n;i++)(ppHuffman[i]=(huffmancode*)malloc(sizeof(huffmancode));ppHuffman[i]一〉prob=p[i];ppHuffman[i]一〉left=NULL;ppHuffman[i]一〉right二NULL;}pRes=CreateBinaryTree(ppHuffman,n);free(ppHuffman);returnpRes;)huffmancode*CreateBinaryTree(huffmancode**ppHuffman,intn)(inti;intmini=0,min2=1; /*mini<min2*/huffmancode*tmp,*pRes;pRes=(huffmancode*)malloc(sizeof(huffmancode));if(ppHuffman[0]-〉prob>ppHuffman[1]一〉prob)mini=1,min2二0;for(i=2;i<n;i++){if(ppHuffman[i]-〉prob〈ppHuffman[min2]一>prob){if(ppHuffman[i]->prob〈ppHuffman[min1]-〉prob)(min2=min1;min1二i;)else{（完整word版）哈夫曼編碼_漢明編碼min2二i；})}pRes―〉prob=ppHuffman[mini]—〉prob+ppHuffman[min2]—>prob;pRes-〉left=ppHuffman[mini];pRes一>right=ppHuffman[min2]；if(mini=n-1)ppHuffman[min2]=pRes;elseif(min2==n-1)ppHuffman[minl]二pRes;else{ppHuffman[minl]二pRes;ppHuffman[min2]=ppHuffman[n一1];)if(n!=2)pRes=CreateBinaryTree(ppHuffman,n一1);returnpRes;)voidInit(U32*n,double**pp)(inti;*n二7;floata[7];*pp二(double*)malloc(sizeof(double)?(?n));for(i=0;i<*n;i++)(scanf("%f”,&a[i]);(大pp)[i]二a[i];)return;)voidmain(){U32n;double*p;huffmancodePpHuffman;Init(&n,&p);pHuffman=Encode(p,n);Print(pHuffman,"");DeleteBinaryTree(pHuffman);}（完整word版）哈夫曼編碼_漢明編碼4.2運行結果5漢明編碼5.1漢明編碼算法通用算法：1）從1開始給數字的數據位（從左到右）標上序號：1,2,3,4,5等；2）將這些數據位的位置序號換成二進制：1,10,11,100,101等；3）數據位的位置序號中所有為二的冪次方的位是校驗位；4）所有其他位置的數據位是數據位；5）每一位的數據包含在特定的兩個或兩個以上的較驗位中，這些校驗位取決于這些數據位的位置數值的二進制表示：（1）校驗位1覆蓋所有數據位位置序號的二進制表示倒數第一位是1的數據；（2）校驗位2覆蓋所有數據位位置序號的二進制表示倒數第二位是1的數據；（3）校驗位4覆蓋所有數據位位置序號的二進制表示倒數第三位是1的數據；即所有校驗位覆蓋數據位置和該校驗位位置的二進制相與的值不為0的值。（完整word版）哈夫曼編碼_漢明編碼5。2漢明編碼特點漢明編碼是一種性能良好的碼，它是在糾錯編碼的實踐中較早發(fā)現的一類具有單個糾錯能力的糾錯碼，在通信和計算機工程中都有應用。漢明碼利用奇偶檢驗位的概念，通過在數據位后面增加一些比特驗證數據的有效性.奇偶校驗是一種添加一個奇偶位用來指示之前的數據中包含有奇數還是偶數個1的檢驗方式。利用一個以上的校驗位，漢明碼不僅可以驗證數據是否有效，還可以在數據出錯的情況下指明出錯位置。6漢明編碼的C++程序實現程序設計流程圖：結果全部源代碼:#include<stdiooh〉（完整word版）哈夫曼編碼_漢明編碼#include〈math.h>voidhanming(){inti，n，k=2；inth[20];for(i=0；i<20;i++)h[i]=0；printf("請輸入要轉換的有效位的位數：\n”)；scanf("%d",&n);while(pow(2,k)<n+k+1)k++；printf(”請輸入要轉換的有效碼字：\n”)；for(i=1；i〈二n+k；i++){if(i!=1&&i!=2&&i!=4&&i!=8)scanf("%d",&h[i]);)h[1]=(h[3]+h[5]+h[7]+h[9]+h[11]+h[13]+h[15])%2;h[2]二(h[3]+h[6]+h[7]+h[10]+h[11]+h[14]+h[15])%2；h[4]=(h[5]+h[6]+h[7]+h[12]+h[13]+h[14]+h[15])%2;h[8]=(h[9]+h[10]+h[11]+h[12]+h[13]+h[14]+h[15])%2;for(i=1；i〈=n+k;i++)printf("%d”,&h[i])；}intjiaoyan(inta[],intn){inti,p1,p2,p4,p8,m；inth[20];for(i=0;i<n;i++)h[i+1]=a[i];for(i=n+1;i〈20;i++)h[i]=0；if(n==3){//k=2；p1=(h[1]+h[3])%2；p2=(h[2]+h[3])%2;m=2*p2+p1;returnm；)if(n>=5&&n<=7){//k=3;p1=(h[1]+h[3]+h[5]+h[7])%2;p2=(h[2]+h[3]+h[6]+h[7])%2；p4=(h[4]+h[5]+h[6]+h[7])%2;m=4*p4+2*p2+p1;returnm;（完整word版）哈夫曼編碼_漢明編碼if(n>=9&&n<二15){//k=4；p1=(h[1]+h[3]+h[5]+h[7]+h[9]+h[11]+h[13]+h[15])%2；p2=(h[2]+h[3]+h[6]+h[7]+h[10]+h[11]+h[14]+h[15])%2；p4=(h[4]+h[5]+h[6]+h[7]+h[12]+h[13]+h[14]+h[15])%2；p8=(h[8]+h[9]+h[10]+h[11]+h[12]+h[13]+h[14]+h[15])%2；m=8*p8+4*p4+2*p2+p1；returnm;)else{printf("查錯出錯！")；return-1;)}//主函數intmain(){hanming();intcoco;inti,n,m,h[20];printf("\n請輸入要查錯的碼字的位數：\n");scanf("%d",&n);printf("請輸入要查錯的碼字：\n");for(i=0