信息论与编码实验四重点讲义

1、信息论与纠错编码实验报告第四次实验1 实验要求：信源编码和信道编码的联合编译码实现信源符号经过信源编码后在进行信道编码，经过信道后码字产生错误跳变，体现信道编码纠检错的功能，再进行信道译码和信源译码后，输出译出的信源符号。理解信源编码和信道编码的区别及联系。二实验代码：代码：#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;/汉明码参数int i,j;/用于指示循环次数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、();/*对汉明码进行编码效率分析*/ int Binary_Str_Check(string); void Encoding();/汉明码编码void Encoding_Z();/增余汉明码编码void Decoding();/汉明码译码void Decoding_Z();/增余汉明码译码void Get_H_Column();/获取汉明码监督矩阵的每一列void Get_H_Column_Z();/获取增余汉明码监督矩阵的每一列void Get_Judge_Result();/获取汉明码校码结果void Get_Judge_Result_Z();/获取增余汉明码校码结果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<<"）汉明码的监督矩阵 H"<<r<<""<<n<<":"<&

5、lt;endl; H=new int *r+1; /初始化(n,k)汉明码监督矩阵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; /初始化增余项for(j=0;j<n+1;j+) Hrj=1; for(i=0;i<r;i+) Hin=0; /为 X 分配存储单元X=new intn+1; for(j=0;j<n+1;j+) Xj=0; Get_H_Column();/获取监督矩阵的每一列Get_H_Column_Z();/进一步获取增余监督矩阵的

6、每一列 /获取监督矩阵的每一列，用于汉明码校码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" /获取增余监督矩阵的每一列，用于增余汉明码校码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<<"）汉明码的评价如下："<<endl; cout<<"（"<<n<<"，"<<k<<"）汉明码的效率 E=k/n*100%="<<k*1.0/n*100<<"%"<<endl; cout<<"（"<<n<<"

10、，"<<k<<"）汉明码的错误概率 P=n*(n-1)*Pe*Pe="<<n*(n-1)*Pe*Pe<<endl;inputi(); /* 编码模块 */ /二进制序列合理性检测int HMCoding:Binary_Str_Check(string temp) int flag=1;/先假设输入的消息串不含除 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编码后结果作为信道编码输入flag=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*统计输入的二进制序列所含码元个数*/ if(binary_num%k!=0&&flag)/*序列所含码元个数不是 k 的整数倍，无法全部编码*/

12、cout<<"您输入的二进制序列存在冗余，请重新输入!n" goto A; if(binary_num%k!=0&&!flag)cout<<"您输入的二进制序列存在冗余且含除 0、1 外的字符，请重新输入!n"goto A; if(binary_num%k=0&&!flag)cout<<"您输入的二进制序列含除 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 位信息元组成的向量与生成矩阵作矩阵乘法，得到对应 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<<"进行（"<<n<<"，"<<k<<"）汉明码编码后的二进制序列为： 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编码后结果作为信道编码输入flag=Binary_Str

15、_Check(binary_str);while(binary_num<binary_str.length()binary_num+;/*统计输入的二进制序列所含码元个数*/if(binary_num%k!=0&&flag)/*序列所含码元个数不是 k 的整数倍，无法全部编码*/ cout<<"您输入的二进制序列存在冗余，请重新输入!n"goto A_Z; if(binary_num%k!=0&&!flag) cout<<"您输入的二进制序列存在冗余且含除 0、1 外的字符，请重新输入!n"

16、goto A_Z;if(binary_num%k=0&&!flag) cout<<"您输入的二进制序列含除 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、法，得到对应 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; /生成增余汉明码最后一位/监督规则：对原汉明码所有 n 个码元取模 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;<"进行（"<<n+1<<"，"<<k<<"）增余汉明码编码后的二进制序列为： n"<<code_str<<endl; /* 校码模块 */ /利用汉明码校码void HMCoding:Checking() B: string binary_str; int flag;int binary_num=0; cout<<"请输入待译的二进制序列："<<endl;cin>>binary_str; fla

19、g=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*统计输入的二进制序列所含码元个数*/ if(binary_num%n!=0&&flag)/*序列所含码元个数不是 n 的整数倍，无法全部译码*/ cout<<"您输入的二进制序列存在冗余，请重新输入!n" goto B;if(binary_num%n!=0&&!flag)cout<<"您输入的二进制序列存在冗余且含除 0、1 外的字符，请重

20、新输入!n" goto B;if(binary_num%n=0&&!flag)cout<<"您输入的二进制序列含除 0、1 外的字符，请重新输入!n" goto B;code_num=binary_num/n;/统计 n 元码组的个数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 个码元进行校正*/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<<"请输入待译的二进制序列："<<endl;cin>>binary_str;flag=Binary_Str_Check(binary_str); while(binary_num<binary_str.length() binary_num+;/*统计输入的二进制序列

22、所含码元个数*/ if(binary_num%(n+1)!=0&&flag)/*序列所含码元个数不是 n+1 的整数倍，无法全部译码*/ cout<<"您输入的二进制序列存在冗余，请重新输入!n"goto B_Z; if(binary_num%(n+1)!=0&&!flag) cout<<"您输入的二进制序列存在冗余且含除 0、1 外的字符，请重新输入!n" goto B_Z; if(binary_num%(n+1)=0&&!flag) cout<<"您输入的二

23、进制序列含除 0、1 外的字符，请重新输入!n" goto B_Z; code_num_z=binary_num/(n+1);/统计 n+1 元码组的个数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 个码元进行校正*/for(j=0;j<n+1;j+)check_codeij=binary_stri*(n+1)+j-'0'Get_Judge_Result_Z(); /获

24、取汉明码校码结果void HMCoding:Get_Judge_Result() int temp;int flag;string partial_str; cout<<"（"<<n<<"，"<<k<<"）汉明码校码结果如下："<<endl; cout<<"码组状态"<<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 进行判断校正后for(i=0;i<n+1;i+)if(H_Columni=partial_str)flag=1;break;if(flag&&i<n)/表示第 i 个码元出错，将其改正 for(j=0;j<n;j+) cout<<check_codetj; cout&

26、lt;<"第"<<i+1<<"位错，可纠正" 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; /获取增余汉明码校码结果void HMCoding:Get_Judge_Result_Z() int temp; int flag; string partial_str; cout<<"（"<<n+1<<"，"<<k<<"）增余汉明码校码结果如下（注：* 表示无法识别的码元）："<<endl; cout<<"码组状态校正后"<<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 进行判断for(i=0;i<n+2;i+)if(H_Column_Zi=partial_str) flag=1;break; if(flag&&i<n+1)/表示第 i 个码元出错，将其改正check

29、_codetn+1=1;/表示正确接收for(j=0;j<n+1;j+) cout<<check_codetj; cout<<"第"<<i+1<<"位错，可纠正"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;/表示两位出错并无法纠正for(j=0;j<n+1;j+) cout<<check_codetj; cout<<"某两位出错，无法纠正"for(j=0;j<n+1;j+) cout<<'*'/* 表示无法正确识别的码元 cout<<endl; /* 译码模块 */ /

31、利用汉明码译码void HMCoding:Decoding() string decstr;cout<<"（"<<n<<"，"<<k<<"）汉明码译码结果为："<<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译码结果为："<<endl;decode1(decstr);/将信道译码结果作为信源译码的输入cout<<endl;/利用增余汉明码译码void HMCoding:Decoding_Z()string decstr;cout<<"（"<<n+1<<"，"<<k<<"）增余汉明码译码结果为（注：* 表示无法识别的码元，默认置为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译码结果为："<<endl;decode1(decstr);/将信道译码结果作为信源译码的输入cou

34、t<<endl;HMCoding hmcoding;/全局变量/哈夫曼树的节点typedef struct node/树节点的标志char data; /树节点的权重int weight;/左右孩子int lchild;int rchild;/是否已经被放入树中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;/记录每个字母的哈弗曼编码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; /创建哈弗曼树void createTree()while(!judge()/按照权重由小到大排序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;/输出字母对应的编码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; /* 辅助函数 */ void inputi()cout<<"请给各字符赋权值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; /构造哈夫曼树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编码结果为："<<endl;for(int i=0;i<inputstr.length();i+)ouputstr+=outputCode(inputstri); cout<<endl; return ouputstr;/* 主函数 */ void HMCoding:GOTO_HMCding_Z() char choice1=' &

43、#39;cout<<"n *欢迎进入Huffman码、（"<<n+1<<","<<k<<"）增余汉明码编码/校码/译码系统*n"cout<<"由汉明监督矩阵导出的增余监督矩阵 H"<<r+1<<""<<n+1<<" 为："<<endl;hmcoding.Show_H(r+1,n+1);Z: cout<<"n >>

44、>>>>>>>>>>>>>>>>Huffman码、（"<<n+1<<","<<k<<"）增余汉明码编码/校码/译码系统<<<<<<<<<<<<<<<<<n"cout<<""<<"E.信源、信道编码"<<""&

45、lt;<"D.信道、信源校码 /译码"<<""<<"R.返回"<<""<<"Q.退出"<<endl; cout<<"请输入您要操作的步骤："cin>>choice1; if(choice1='E'|choice1='e')/进行编码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/如果选了选项之外的就让用户重新选择cout<<"您没有输入正确的步骤，请重新输入！"<<endl; goto Z;cout<<endl; int main() c

47、har choice=' ' /用于记录初始化情况int flag=0; int n,k; cout<<"n *信源、信道编码/ 校码/ 译码系统*n" cout<<"请输入汉明码的码长 n=" cin>>n; cout<<"请输入汉明码的信息元个数 k="cin>>k; while(choice!='Q'&&choice!='q')/当 choice 的值不为 q 且不为 Q 时循环C:cout<<"n >>>>>>>>>>&g