信息論與編碼實(shí)驗(yàn)四

1、信息論與糾錯(cuò)編碼實(shí)驗(yàn)報(bào)告第四次實(shí)驗(yàn)1 實(shí)驗(yàn)要求：信源編碼和信道編碼的聯(lián)合編譯碼實(shí)現(xiàn)信源符號經(jīng)過信源編碼后在進(jìn)行信道編碼，經(jīng)過信道后碼字產(chǎn)生錯(cuò)誤跳變，體現(xiàn)信道編碼糾檢錯(cuò)的功能，再進(jìn)行信道譯碼和信源譯碼后，輸出譯出的信源符號。理解信源編碼和信道編碼的區(qū)別及聯(lián)系。二實(shí)驗(yàn)代碼：代碼：#include<iostream>#include<algorithm>#include<string>#define MAXNUM 1001#define NUM 9#define Pe 0.0001 using namespace std; string input1();void

2、 inputi();void decode1(string);class HMCoding private: int n,k,r;/漢明碼參數(shù)int i,j;/用于指示循環(huán)次數(shù)int *H,*X,*G,*check_code; string *H_Column,*H_Column_Z,code_str; int code_num,code_num_z; public: void Initializing(int,int); void Show_H(int,int); void Get_G(); void Show_G(int,int); void HM_Efficiency_Analysing

3、();/*對漢明碼進(jìn)行編碼效率分析*/ int Binary_Str_Check(string); void Encoding();/漢明碼編碼void Encoding_Z();/增余漢明碼編碼void Decoding();/漢明碼譯碼void Decoding_Z();/增余漢明碼譯碼void Get_H_Column();/獲取漢明碼監(jiān)督矩陣的每一列void Get_H_Column_Z();/獲取增余漢明碼監(jiān)督矩陣的每一列void Get_Judge_Result();/獲取漢明碼校碼結(jié)果void Get_Judge_Result_Z();/獲取增余漢明碼校碼結(jié)果void Check

4、ing();/漢明碼校碼void Checking_Z();/增余漢明碼校碼void GOTO_HMCding_Z(); ; /* 初始化模塊 */ void HMCoding:Initializing(int _n,int _k) n=_n; k=_k; r=_n-_k; cout<<"請給定（"<<n<<"，"<<k<<"）漢明碼的監(jiān)督矩陣 H"<<r<<""<<n<<":"<&

5、lt;endl; H=new int *r+1; /初始化(n,k)漢明碼監(jiān)督矩陣for(i=0;i<r+1;i+) Hi=new intn+1; for(i=0;i<r;i+) for(j=0;j<n;j+) cin>>Hij; /初始化增余項(xiàng)for(j=0;j<n+1;j+) Hrj=1; for(i=0;i<r;i+) Hin=0; /為 X 分配存儲(chǔ)單元X=new intn+1; for(j=0;j<n+1;j+) Xj=0; Get_H_Column();/獲取監(jiān)督矩陣的每一列Get_H_Column_Z();/進(jìn)一步獲取增余監(jiān)督矩陣的

6、每一列 /獲取監(jiān)督矩陣的每一列，用于漢明碼校碼void HMCoding:Get_H_Column() string temp; H_Column=new stringn+1; for(i=0;i<n;i+) temp="" for(j=0;j<r;j+) if(!Hji) temp+='0' else temp+='1' H_Columni=temp; H_Columnn="000" /獲取增余監(jiān)督矩陣的每一列，用于增余漢明碼校碼void HMCoding:Get_H_Column_Z() H_Column_

7、Z=new stringn+2; for(i=0;i<n+1;i+) H_Column_Zi=H_Columni+'1' H_Column_Zn+1="0000" void HMCoding:Show_H(int x,int y) for(i=0;i<x;i+) for(j=0;j<y;j+) cout<<Hij<<"" cout<<endl; void HMCoding:Get_G() G=new int *k; for(i=0;i<k;i+) Gi=new intn; for

8、(i=0;i<k;i+) for(j=0;j<k;j+) if(i=j) Gij=1; else Gij=0; for(i=0;i<r;i+) for(j=0;j<k;j+) Gji+k=Hij; void HMCoding:Show_G(int x,int y) Get_G(); for(i=0;i<x;i+) for(j=0;j<y;j+) cout<<Gij<<"" cout<<endl; void HMCoding:HM_Efficiency_Analysing() cout<<&q

9、uot;對（"<<n<<"，"<<k<<"）漢明碼的評價(jià)如下："<<endl; cout<<"（"<<n<<"，"<<k<<"）漢明碼的效率 E=k/n*100%="<<k*1.0/n*100<<"%"<<endl; cout<<"（"<<n<<"

10、，"<<k<<"）漢明碼的錯(cuò)誤概率 P=n*(n-1)*Pe*Pe="<<n*(n-1)*Pe*Pe<<endl;inputi(); /* 編碼模塊 */ /二進(jìn)制序列合理性檢測int HMCoding:Binary_Str_Check(string temp) int flag=1;/先假設(shè)輸入的消息串不含除 0、1 外的字符for(int i=0;i<temp.length();i+)if(!(tempi='0'|tempi='1') flag=0;break; return

11、 flag; /漢明碼編碼void HMCoding:Encoding() A: string binary_str; int flag; int binary_num=0; binary_str=input1();/將Huffman編碼后結(jié)果作為信道編碼輸入flag=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*統(tǒng)計(jì)輸入的二進(jìn)制序列所含碼元個(gè)數(shù)*/ if(binary_num%k!=0&&flag)/*序列所含碼元個(gè)數(shù)不是 k 的整數(shù)倍，無法全部編碼*/

12、cout<<"您輸入的二進(jìn)制序列存在冗余，請重新輸入!n" goto A; if(binary_num%k!=0&&!flag)cout<<"您輸入的二進(jìn)制序列存在冗余且含除 0、1 外的字符，請重新輸入!n"goto A; if(binary_num%k=0&&!flag)cout<<"您輸入的二進(jìn)制序列含除 0、1 外的字符，請重新輸入!n"goto A; code_str="" for(i=0;i<binary_num;i=i+k) f

13、or(j=0;j<k;j+)/*獲取 k 位信息元*/if(binary_stri+j='0') Xj=0; else Xj=1; int temp;string partial_str=""for(int t=0;t<n;t+)/*用 k 位信息元組成的向量與生成矩陣作矩陣乘法，得到對應(yīng) n 元碼組*/ temp=0; for(j=0;j<k;j+)temp+=Xj*Gjt; if(temp%2=0)partial_str+='0'else partial_str+='1' code_str+=partia

14、l_str; cout<<"進(jìn)行（"<<n<<"，"<<k<<"）漢明碼編碼后的二進(jìn)制序列為： n"<<code_str<<endl;/增余漢明碼編碼void HMCoding:Encoding_Z()code_str=""A_Z:string binary_str;int flag;int binary_num=0; binary_str=input1();/將Huffman編碼后結(jié)果作為信道編碼輸入flag=Binary_Str

15、_Check(binary_str);while(binary_num<binary_str.length()binary_num+;/*統(tǒng)計(jì)輸入的二進(jìn)制序列所含碼元個(gè)數(shù)*/if(binary_num%k!=0&&flag)/*序列所含碼元個(gè)數(shù)不是 k 的整數(shù)倍，無法全部編碼*/ cout<<"您輸入的二進(jìn)制序列存在冗余，請重新輸入!n"goto A_Z; if(binary_num%k!=0&&!flag) cout<<"您輸入的二進(jìn)制序列存在冗余且含除 0、1 外的字符，請重新輸入!n"

16、goto A_Z;if(binary_num%k=0&&!flag) cout<<"您輸入的二進(jìn)制序列含除 0、1 外的字符，請重新輸入!n"goto A_Z;for(i=0;i<binary_num;i=i+k)for(j=0;j<k;j+)/*獲取 k 位信息元*/ if(binary_stri+j='0') Xj=0; else Xj=1; int temp;string partial_str=""for(int t=0;t<n;t+) /*用 k 位信息元組成的向量與生成矩陣作矩陣乘

17、法，得到對應(yīng) n 元碼組*/temp=0; for(j=0;j<k;j+)temp+=Xj*Gjt; if(temp%2=0)partial_str+='0'Xj+k=0;elsepartial_str+='1'Xj+k=1; /生成增余漢明碼最后一位/監(jiān)督規(guī)則：對原漢明碼所有 n 個(gè)碼元取模 2 和int sum=0; for(j=0;j<n;j+)sum+=Xj;if(sum%2=0)partial_str+='0' else partial_str+='1'code_str+=partial_str; cout&

18、lt;<"進(jìn)行（"<<n+1<<"，"<<k<<"）增余漢明碼編碼后的二進(jìn)制序列為： n"<<code_str<<endl; /* 校碼模塊 */ /利用漢明碼校碼void HMCoding:Checking() B: string binary_str; int flag;int binary_num=0; cout<<"請輸入待譯的二進(jìn)制序列："<<endl;cin>>binary_str; fla

19、g=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*統(tǒng)計(jì)輸入的二進(jìn)制序列所含碼元個(gè)數(shù)*/ if(binary_num%n!=0&&flag)/*序列所含碼元個(gè)數(shù)不是 n 的整數(shù)倍，無法全部譯碼*/ cout<<"您輸入的二進(jìn)制序列存在冗余，請重新輸入!n" goto B;if(binary_num%n!=0&&!flag)cout<<"您輸入的二進(jìn)制序列存在冗余且含除 0、1 外的字符，請重

20、新輸入!n" goto B;if(binary_num%n=0&&!flag)cout<<"您輸入的二進(jìn)制序列含除 0、1 外的字符，請重新輸入!n" goto B;code_num=binary_num/n;/統(tǒng)計(jì) n 元碼組的個(gè)數(shù)check_code=new int*code_num; for(i=0;i<code_num;i+) check_codei=new intn; for(i=0;i<code_num;i+) /*每次取 n 個(gè)碼元進(jìn)行校正*/for(j=0;j<n;j+)check_codeij=bin

21、ary_stri*n+j-'0' Get_Judge_Result();/利用增余漢明碼校碼void HMCoding:Checking_Z() B_Z:string binary_str; int flag;int binary_num=0;cout<<"請輸入待譯的二進(jìn)制序列："<<endl;cin>>binary_str;flag=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*統(tǒng)計(jì)輸入的二進(jìn)制序列

22、所含碼元個(gè)數(shù)*/ if(binary_num%(n+1)!=0&&flag)/*序列所含碼元個(gè)數(shù)不是 n+1 的整數(shù)倍，無法全部譯碼*/ cout<<"您輸入的二進(jìn)制序列存在冗余，請重新輸入!n"goto B_Z; if(binary_num%(n+1)!=0&&!flag) cout<<"您輸入的二進(jìn)制序列存在冗余且含除 0、1 外的字符，請重新輸入!n" goto B_Z; if(binary_num%(n+1)=0&&!flag) cout<<"您輸入的二

23、進(jìn)制序列含除 0、1 外的字符，請重新輸入!n" goto B_Z; code_num_z=binary_num/(n+1);/統(tǒng)計(jì) n+1 元碼組的個(gè)數(shù)check_code=new int*code_num_z; for(i=0;i<code_num_z;i+) check_codei=new intn+2; for(i=0;i<code_num_z;i+) /*每次取 n+1 個(gè)碼元進(jìn)行校正*/for(j=0;j<n+1;j+)check_codeij=binary_stri*(n+1)+j-'0'Get_Judge_Result_Z(); /獲

24、取漢明碼校碼結(jié)果void HMCoding:Get_Judge_Result() int temp;int flag;string partial_str; cout<<"（"<<n<<"，"<<k<<"）漢明碼校碼結(jié)果如下："<<endl; cout<<"碼組狀態(tài)"<<endl;for(int t=0;t<code_num;t+) flag=0;partial_str="" for(i=0;i

25、<r;i+) temp=0;for(j=0;j<n;j+) temp+=Hij*check_codetj; if(temp%2=0) partial_str+='0' else partial_str+='1' /對 partial_str 進(jìn)行判斷校正后for(i=0;i<n+1;i+)if(H_Columni=partial_str)flag=1;break;if(flag&&i<n)/表示第 i 個(gè)碼元出錯(cuò)，將其改正 for(j=0;j<n;j+) cout<<check_codetj; cout&

26、lt;<"第"<<i+1<<"位錯(cuò)，可糾正" check_codeti=(check_codeti+1)%2;/1 變 0，0 變 1 for(j=0;j<n;j+) cout<<check_codetj; if(flag&&i=n)/表示全對for(j=0;j<n;j+) cout<<check_codetj; cout<<"全對" for(j=0;j<n;j+) cout<<check_codetj; cout<&

27、lt;endl; /獲取增余漢明碼校碼結(jié)果void HMCoding:Get_Judge_Result_Z() int temp; int flag; string partial_str; cout<<"（"<<n+1<<"，"<<k<<"）增余漢明碼校碼結(jié)果如下（注：* 表示無法識別的碼元）："<<endl; cout<<"碼組狀態(tài)校正后"<<endl;for(int t=0;t<code_num_z;t+)

28、flag=0;partial_str=""for(i=0;i<r+1;i+) temp=0; for(j=0;j<n+1;j+) temp+=Hij*check_codetj;if(temp%2=0)partial_str+='0' else partial_str+='1' /對 partial_str 進(jìn)行判斷for(i=0;i<n+2;i+)if(H_Column_Zi=partial_str) flag=1;break; if(flag&&i<n+1)/表示第 i 個(gè)碼元出錯(cuò)，將其改正check

29、_codetn+1=1;/表示正確接收for(j=0;j<n+1;j+) cout<<check_codetj; cout<<"第"<<i+1<<"位錯(cuò)，可糾正"check_codeti=(check_codeti+1)%2;/1 變 0，0 變 1 for(j=0;j<n+1;j+)cout<<check_codetj; if(flag&&i=n+1)/表示全對 check_codetn+1=1;/表示正確接收for(j=0;j<n+1;j+)cout<

30、<check_codetj; cout<<"全對" for(j=0;j<n+1;j+) cout<<check_codetj; if(!flag)check_codetn+1=0;/表示兩位出錯(cuò)并無法糾正for(j=0;j<n+1;j+) cout<<check_codetj; cout<<"某兩位出錯(cuò)，無法糾正"for(j=0;j<n+1;j+) cout<<'*'/* 表示無法正確識別的碼元 cout<<endl; /* 譯碼模塊 */ /

31、利用漢明碼譯碼void HMCoding:Decoding() string decstr;cout<<"（"<<n<<"，"<<k<<"）漢明碼譯碼結(jié)果為："<<endl;for(i=0;i<code_num;i+) for(j=0;j<k;j+)cout<<check_codeij;if(!check_codeij)decstr+='0'elsedecstr+='1'cout<<endl; c

32、out<<"Huffman譯碼結(jié)果為："<<endl;decode1(decstr);/將信道譯碼結(jié)果作為信源譯碼的輸入cout<<endl;/利用增余漢明碼譯碼void HMCoding:Decoding_Z()string decstr;cout<<"（"<<n+1<<"，"<<k<<"）增余漢明碼譯碼結(jié)果為（注：* 表示無法識別的碼元，默認(rèn)置為0）："<<endl;for(i=0;i<code_n

33、um_z;i+)if(check_codein+1=1)for(j=0;j<k;j+) cout<<check_codeij;if(!check_codeij)decstr+='0'elsedecstr+='1'elsefor(j=0;j<k;j+) cout<<'*'decstr+='0'cout<<endl; cout<<"Huffman譯碼結(jié)果為："<<endl;decode1(decstr);/將信道譯碼結(jié)果作為信源譯碼的輸入cou

34、t<<endl;HMCoding hmcoding;/全局變量/哈夫曼樹的節(jié)點(diǎn)typedef struct node/樹節(jié)點(diǎn)的標(biāo)志char data; /樹節(jié)點(diǎn)的權(quán)重int weight;/左右孩子int lchild;int rchild;/是否已經(jīng)被放入樹中bool tag; myNode; myNode nodes100;char mycode100;char ch='A','C','I','M','N','P','T','U','S'

35、;int index=-1;int index1=-1;/記錄每個(gè)字母的哈弗曼編碼string strNUM;myNode recordNode;/* Huffman */bool compare(myNode mynode1,myNode mynode2)return mynode1.weight<mynode2.weight; bool judge()int record=0;for(int i=0;i<=index;i+)if(nodesi.tag=false)record+;recordNode=nodesi; if(record=0|(record=1&&

36、recordNode.data='#')return true;return false;int findNode()for(int i=0;i<=index;i+)if(nodesi.tag=false)nodesi.tag=true;return i; return -1;/編碼bool code(myNode *root,char ch1)bool tag=false;if(root->data=ch1)return true; int arr2;arr0=root->lchild;arr1=root->rchild;for(int i=0;i&l

37、t;2;i+)if(arri!=-1) tag=code(&nodesarri,ch1);if(tag)if(i=0)mycode+index1='0' else if(i=1)mycode+index1='1' if(tag)return tag; return tag; /創(chuàng)建哈弗曼樹void createTree()while(!judge()/按照權(quán)重由小到大排序sort(nodes,nodes+index+1,compare); myNode newNode;newNode.data='#'newNode.lchild=find

38、Node();newNode.rchild=findNode();newNode.weight=nodesnewNode.lchild.weight+nodesnewNode.rchild.weight;newNode.tag=false;nodes+index=newNode;/輸出字母對應(yīng)的編碼string outputCode(char cha)string outstr;for(int i=0;i<NUM;i+)if(cha=chi)cout<<stri;outstr+=stri; return outstr;/譯碼void decode1(string inputs

39、tr)int kkindex=-1;int len=inputstr.length()-1;while(kkindex<len)bool find=false;myNode tempNode=nodesindex;char ch;while(!find&&kkindex<len)+kkindex;if(inputstrkkindex='0')tempNode=nodestempNode.lchild; elsetempNode=nodestempNode.rchild;ch=tempNode.data;if(ch!='#')find=

40、true;if(ch!='#')cout<<ch; /* 輔助函數(shù) */ void inputi()cout<<"請給各字符賦權(quán)值n"for(int i=0;i<NUM;i+)int data;cin>>data;nodes+index.data=chi;nodesindex.weight=data;nodesindex.lchild=-1;nodesindex.rchild=-1;nodesindex.tag=false; /構(gòu)造哈夫曼樹createTree();/recordNode故為樹的根for(int i=

41、0;i<NUM;i+)index1=-1;code(&(nodesindex),chi);stri=""for(int j=index1;j>=0;j-)stri+=mycodej; cout<<"對各字符的Huffman編碼為："<<endl;/輸出for(int i=0;i<NUM;i+)cout<<chi<<": "cout<<stri<<endl; string input1()cout<<"請輸入將要編碼的

42、字符串："<<endl;/獲得輸入的字符串string inputstr;string ouputstr;cin>>inputstr;cout<<"Huffman編碼結(jié)果為："<<endl;for(int i=0;i<inputstr.length();i+)ouputstr+=outputCode(inputstri); cout<<endl; return ouputstr;/* 主函數(shù) */ void HMCoding:GOTO_HMCding_Z() char choice1=' &

43、#39;cout<<"n *歡迎進(jìn)入Huffman碼、（"<<n+1<<","<<k<<"）增余漢明碼編碼/校碼/譯碼系統(tǒng)*n"cout<<"由漢明監(jiān)督矩陣導(dǎo)出的增余監(jiān)督矩陣 H"<<r+1<<""<<n+1<<" 為："<<endl;hmcoding.Show_H(r+1,n+1);Z: cout<<"n >>

44、>>>>>>>>>>>>>>>>Huffman碼、（"<<n+1<<","<<k<<"）增余漢明碼編碼/校碼/譯碼系統(tǒng)<<<<<<<<<<<<<<<<<n"cout<<""<<"E.信源、信道編碼"<<""&

45、lt;<"D.信道、信源校碼 /譯碼"<<""<<"R.返回"<<""<<"Q.退出"<<endl; cout<<"請輸入您要操作的步驟："cin>>choice1; if(choice1='E'|choice1='e')/進(jìn)行編碼hmcoding.Encoding_Z();goto Z; else if(choice1='D'|choic

46、e1='d') hmcoding.Checking_Z(); hmcoding.Decoding_Z(); goto Z; else if(choice1='R'|choice1='r') return;else if(choice1='Q'|choice1='q')/退出 exit(0);else/如果選了選項(xiàng)之外的就讓用戶重新選擇cout<<"您沒有輸入正確的步驟，請重新輸入！"<<endl; goto Z;cout<<endl; int main() c

47、har choice=' ' /用于記錄初始化情況int flag=0; int n,k; cout<<"n *信源、信道編碼/ 校碼/ 譯碼系統(tǒng)*n" cout<<"請輸入漢明碼的碼長 n=" cin>>n; cout<<"請輸入漢明碼的信息元個(gè)數(shù) k="cin>>k; while(choice!='Q'&&choice!='q')/當(dāng) choice 的值不為 q 且不為 Q 時(shí)循環(huán)C:cout<<"n >>>>>>>>>>&g