信息论与编码实验四

1、信息论与纠错编码实验报告第四次实验 一实验要求：信源编码和信道编码的联合编译码实现信源符号经过信源编码后在 进行信道编码，经过信道后码字产生错误跳变，体现信道编码纠检错的功能，再进 行信道译码和信源译码后，输出译出的信源符号。理解信源编码和信道编码的区别 及联系。二实验代码：代码： #include #include #include #define MAXNUM 1001 #define NUM 9 #define Pe 0.0001 using namespace std;string input1();void inputi();void decode1(string);class HM

2、Codingprivate: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();/* 对汉明码进行编码效率分析 */int Binary_Str_Check(strin

3、g);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 Checking();/ 汉明码校码void Checking_Z();/ 增余汉

4、明码校码 void GOTO_HMCding_Z();*初始化模块*void HMCoding:Initializing(int _n,int _k)n=_n;k=_k;r=_n-_k;cout 请给定( n ，k )汉明码的监督矩阵 Hrn:endl;H=new int *r+1; / 初始化 (n,k) 汉明码监督矩阵 for(i=0;ir+1;i+)Hi=new intn+1;for(i=0;ir;i+) for(j=0;jHij; / 初始化增余项 for(j=0;jn+1;j+)Hrj=1;for(i=0;ir;i+)Hin=0; / 为 X 分配存储单元X=new intn+1;

5、for(j=0;jn+1;j+)Xj=0;Get_H_Column();/ 获取监督矩阵的每一列 Get_H_Column_Z();/ 进一步获取增余监督矩阵的每一列 /获取监督矩阵的每一列，用于汉明码校码 void HMCoding:Get_H_Column()string temp;H_Column=new stringn+1; for(i=0;in;i+)temp=; for(j=0;jr;j+) if(!Hji)temp+=0;elsetemp+=1;H_Columni=temp;H_Columnn=000;/获取增余监督矩阵的每一列，用于增余汉明码校码 void HMCoding:G

6、et_H_Column_Z()H_Column_Z=new stringn+2;for(i=0;in+1;i+)H_Column_Zi=H_Columni+1;H_Column_Zn+1=0000;void HMCoding:Show_H(int x,int y)for(i=0;ix;i+)for(j=0;jy;j+)coutHij;coutendl;void HMCoding:Get_G()G=new int *k;for(i=0;ik;i+)Gi=new intn;for(i=0;ik;i+) for(j=0;jk;j+) if(i=j)Gij=1;else Gij=0; for(i=0;

7、ir;i+)for(j=0;jk;j+)Gji+k=Hij;void HMCoding:Show_G(int x,int y)Get_G();for(i=0;ix;i+) for(j=0;jy;j+) coutGij;coutendl;void HMCoding:HM_Efficiency_Analysing()cout 对( n ， k )汉明码的评价如下： endl;cout ( n ， k )汉明码的效率 E=k/n*100%=k*1.0/n*100%endl; cout( n ，k )汉明码的错误概率 P=n*(n-1)*Pe*Pe=n*(n-1)*Pe*Peendl; inputi(

8、);*编码模块 */二进制序列合理性检测 int HMCoding:Binary_Str_Check(string temp)int flag=1;/ 先假设输入的消息串不含除 0、 1 外的字符 for(int i=0;itemp.length();i+)if(!(tempi=0|tempi=1)flag=0;break;return flag;/汉明码编码 void HMCoding:Encoding()A: string binary_str;int flag;int binary_num=0;binary_str=input1();/ 将 Huffman 编码后结果作为信道编码输入 f

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

10、的二进制序列含除 0、1 外的字符，请重新输入 !n; goto A;code_str=;for(i=0;ibinary_num;i=i+k)for(j=0;jk;j+)/* 获取 k 位信息元 */ if(binary_stri+j=0)Xj=0; else Xj=1;int temp;string partial_str=;for(int t=0;tn;t+)/* 用 k 位信息元组成的向量与生成矩阵作矩阵乘法，得到对应 n 元码组 */ temp=0;for(j=0;jk;j+) temp+=Xj*Gjt;if(temp%2=0) partial_str+=0;else partial_

11、str+=1;code_str+=partial_str;cout 进行( n ， k )汉明码编码后的二进制序列为： ncode /增余汉明码编码void HMCoding:Encoding_Z() code_str=;A_Z:string binary_str;int flag;int binary_num=0;binary_str=input1();/ 将 Huffman 编码后结果作为信道编码输入 flag=Binary_Str_Check(binary_str);while(binary_numbinary_str.length()binary_num+;/* 统计输入的二进制序列所

12、含码元个数 */ if(binary_num%k!=0&flag)/* 序列所含码元个数不是 k 的整数倍，无法全部编码 cout 您输入的二进制序列存在冗余，请重新输入 !n;goto A_Z; if(binary_num%k!=0&!flag)cout 您输入的二进制序列存在冗余且含除0、 1 外的字符，请重新输入goto A_Z; if(binary_num%k=0&!flag)cout 您输入的二进制序列含除 0、1 外的字符，请重新输入 !n; goto A_Z; for(i=0;ibinary_num;i=i+k)for(j=0;jk;j+)/* 获取 k 位信息元 */if(bi

13、nary_stri+j=0)Xj=0;else Xj=1;strendl;*/!n;int temp;string partial_str=;for(int t=0;tn;t+)/* 用 k 位信息元组成的向量与生成矩阵作矩阵乘法，得到对应 n 元码组 */ temp=0;for(j=0;jk;j+) temp+=Xj*Gjt;if(temp%2=0) partial_str+=0; Xj+k=0;else partial_str+=1; Xj+k=1; / 生成增余汉明码最后一位 /监督规则：对原汉明码所有n 个码元取模 2 和int sum=0;for(j=0;jn;j+)sum+=Xj;

14、 if(sum%2=0)partial_str+=0;elsepartial_str+=1; code_str+=partial_str;cout 进 行 ( n+1 ， k ) 增 余 汉 明 码 编 码 后 的 二 进 制 序 列 为 ： ncode_strendl;校码模块 *endl;/*/利用汉明码校码void HMCoding:Checking()B: string binary_str;int flag;int binary_num=0;coutbinary_str;flag=Binary_Str_Check(binary_str); while(binary_numbinary

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

16、 统计 n 元码组的个数 check_code=new int*code_num;for(i=0;icode_num;i+)check_codei=new intn; for(i=0;icode_num;i+) /* 每次取 n 个码元进行校正 */for(j=0;jn;j+) check_codeij=binary_stri*n+j-0; Get_Judge_Result();/利用增余汉明码校码void HMCoding:Checking_Z()B_Z:string binary_str;int flag;int binary_num=0; cout 请输入待译的二进制序列： binary

17、_str;flag=Binary_Str_Check(binary_str); while(binary_numbinary_str.length()binary_num+;/* 统计输入的二进制序列所含码元个数 */ 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_n

18、um%(n+1)=0&!flag) cout 您输入的二进制序列含除 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;icode_num_z;i+)check_codei=new intn+2; for(i=0;icode_num_z;i+)/* 每次取 n+1 个码元进行校正 */ for(j=0;jn+1;j+)check_codeij=binary_stri*(n+1)+j-0; Get_Judge_Result

19、_Z();/获取汉明码校码结果 void HMCoding:Get_Judge_Result()int temp;int flag;string partial_str;cout ( n ， k )汉明码校码结果如下： endl;cout 码组状态 endl;for(int t=0;tcode_num;t+)flag=0;partial_str=;for(i=0;ir;i+)temp=0;for(j=0;jn;j+)temp+=Hij*check_codetj;if(temp%2=0)partial_str+=0;elsepartial_str+=1; / 对 partial_str 进行判断

20、校正后for(i=0;in+1;i+)if(H_Columni=partial_str)flag=1;break;if(flag&in)/ 表示第 i 个码元出错，将其改正 for(j=0;jn;j+)coutcheck_codetj;cout 第 i+1 位错，可纠正 ; check_codeti=(check_codeti+1)%2;/1 变 0， 0 变 1 for(j=0;jn;j+)coutcheck_codetj;if(flag&i=n)/ 表示全对 for(j=0;jn;j+)coutcheck_codetj;cout 全对 ;for(j=0;jn;j+)coutcheck_co

21、detj; coutendl;/获取增余汉明码校码结果void HMCoding:Get_Judge_Result_Z()int temp;int flag;string partial_str;cout ( n+1 ，k )增余汉明码校码结果如下(注：endl;cout 码组状态校正后 endl;for(int t=0;tcode_num_z;t+)flag=0;partial_str=;for(i=0;ir+1;i+)temp=0;for(j=0;jn+1;j+)temp+=Hij*check_codetj;if(temp%2=0)partial_str+=0;elsepartial_st

22、r+=1;/对 partial_str 进行判断for(i=0;in+2;i+)if(H_Column_Zi=partial_str)flag=1;break;if(flag&in+1)/ 表示第 i 个码元出错，将其改正check_codetn+1=1;/ 表示正确接收 for(j=0;jn+1;j+)coutcheck_codetj;cout 第 i+1 位错，可纠正 ; check_codeti=(check_codeti+1)%2;/1 变 0， 0 for(j=0;jn+1;j+)coutcheck_codetj;* 表示无法识别的码元）变1if(flag&i=n+1)/ 表示全对c

23、heck_codetn+1=1;/ 表示正确接收for(j=0;jn+1;j+) coutcheck_codetj;cout 全对 ;for(j=0;jn+1;j+) coutcheck_codetj;if(!flag)check_codetn+1=0;/ 表示两位出错并无法纠正for(j=0;jn+1;j+) coutcheck_codetj;cout 某两位出错，无法纠正 ;for(j=0;jn+1;j+)cout*;/* 表示无法正确识别的码元coutendl;*译码模块 */利用汉明码译码 void HMCoding:Decoding()string decstr;cout ( n ，

24、 k )汉明码译码结果为： endl;for(i=0;icode_num;i+)for(j=0;jk;j+)coutcheck_codeij;if(!check_codeij)decstr+=0;elsedecstr+=1;coutendl;coutHuffman 译码结果为： endl;decodel(decstr);/将信道译码结果作为信源译码的输入 coutendl;/利用增余汉明码译码void HMCoding:Decoding_Z()string decstr;* 表示无法识别的码元，默cout ( n+1 ，k )增余汉明码译码结果为(注：认置为 0)： endl;for(i=0;

25、icode_num_z;i+)if(check_codein+1=1)for(j=0;jk;j+)coutcheck_codeij;if(!check_codeij)decstr+=0;elsedecstr+=1;elsefor(j=0;jk;j+) cout*;decstr+=0;coutendl;coutHuffman 译码结果为： endl;decodel(decstr);/将信道译码结果作为信源译码的输入 coutendl;HMCoding hmcoding;/ 全局变量/哈夫曼树的节点typedef struct node/树节点的标志char data;/树节点的权重int wei

26、ght;/左右孩子int lchild;int rchild; /是否已经被放入树中bool tag;myNode;myNode nodes100;char mycode100;char ch=A,C,I,M,N,P,T,U,S;int index=-1;int index1=-1; /记录每个字母的哈弗曼编码 string strNUM; myNode recordNode;* Huffman *bool compare(myNode mynode1,myNode mynode2)return mynode1.weightmynode2.weight;bool judge()int reco

27、rd=0;for(int i=0;i=index;i+)if(nodesi.tag=false)record+; recordNode=nodesi;if(record=0|(record=1&recordNode.data=#)return true;return false;int findNode()for(int i=0;idata=ch1)return true;int arr2;arr0=root-lchild;arr1=root-rchild;for(int i=0;i2;i+)if(arri!=-1)tag=code(&nodesarri,ch1);if(tag)if(i=0)

28、 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=findNode();newNode.rchild=findNode();newNode.weight=nodesnewNode.lchild.weight+nodesnewNode.rchil

29、d.weight; newNode.tag=false;nodes+index=newNode;/输出字母对应的编码string outputCode(char cha)string outstr;for(int i=0;iNUM;i+)if(cha=chi)coutstri; outstr+=stri;return outstr;/译码void decode1(string inputstr)int kkindex=-1;int len=inputstr.length()-1;while(kkindexlen)bool find=false;myNode tempNode=nodesinde

30、x;char ch;while(!find&kkindexlen)+kkindex;if(inputstrkkindex=0)tempNode=nodestempNode.lchild;elsetempNode=nodestempNode.rchild;ch=tempNode.data;if(ch!=#)find=true;if(ch!=#)coutch;*辅助函数 *void inputi()cout 请给各字符赋权值 n;for(int i=0;idata;nodes+index.data=chi; nodesindex.weight=data; nodesindex.lchild=-1;

31、 nodesindex.rchild=-1; nodesindex.tag=false;/构造哈夫曼树createTree();/recordNode 故为树的根for(int i=0;i=0;j-)stri+=mycodej;cout 对各字符的 Huffman 编码为： endl;/输出for(int i=0;iNUM;i+)coutchi: ;coutstriendl;string input1()cout 请输入将要编码的字符串： inputstr;coutHuffman 编码结果为： endl;for(int i=0;iinputstr.length();i+)ouputstr+=o

32、utputCode(inputstri); coutendl; return ouputstr;*主函数*void HMCoding:GOTO_HMCding_Z()char choice1= ;欢迎进入 Huffman码、( n+1,k )增余汉明码编码 /校码coutn */ 译码系统 *n;cout 由汉明监督矩阵导出的增余监督矩阵 hmcoding.Show_H(r+1,n+1);Z: coutHuffman/ 译码系统 n; coutE. 信源、信道编码 D.退出 endl;cout 请输入您要操作的步骤：Hr+1n+1为： endl;码、( n+1,k )增余汉明码编码 /校码信道

33、、信源校码 /译码 R. 返回 choice1; if(choice1=E|choice1=e)/ 进行编码 hmcoding.Encoding_Z(); goto Z;else if(choice1=D|choice1=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/如果选了选项之外的就让用户重新选择endl;cout 您没有输入正确的步骤，请重新输入！ goto Z

34、;coutendl;int main() char choice= ; / 用于记录初始化情况int flag=0;int n,k;coutn * 信 源 、 信 道 编 码 / 校 码 / 译 码 系 统 *n;coutn;coutk; while(choice!=Q&choice!=q)/ 当 choice 的值不为 q 且不为 Q 时循环 C: coutHuffman 码、( n,k )汉明码编码 /校码 / 译码系统 n;coutI. 输入建立 E. 信源、信道编码 D. 信道、信源校码 /译码 n; coutZ. 进入相应的增余汉明码系统 Q. 退出 n; coutchoice;if(choice=I|choice=i)/ 初始化if(!flag) /初次执行初始化操作 flag=1;hmcoding.Initializing(n,k); cout 您输入的监督矩阵 Hn-kn 为 :endl; hmcoding.Show_H(n-k,n);cout 该监督矩阵对应的生成矩阵 Gkn 为 :endl; hmcoding.Show_G(k,n); hmcoding.HM_Efficiency_Analysing();els