某科技大学计算机网络实验二报告.doc

计算机网络课程实验报告实验2：抗干扰编码院系学号实验地点科技楼十二楼机房实验时间实验目的：1. 了解抗干扰编码原理。2、掌握海明编码和CRC编码的原理,能熟练计算实验容：容1：海明编码1.1 海明编码原理将有效信息按某种规律分成若干组，每组安排一个校验位通过异或运算进行校验，得出具体的校验码；在接收端同样通过异或运算看各组校验结果是否正确，并观察出错的校校组，或者个出错的校验组的共同校验位，得出具体的出错比特位；对错误位取反来将其纠正；假设用N表示添加了校验码位后整个传输信息的二进制位数，用K代表其中有效信息位数，r表示添加的校验码位数，它们之间的关系应满足：N=Kr2r1（是为了确保r位校验码能校验全部的数据位，因为r位校验码所能表示的最大十进制数为2r-1，同时也确保各位码本身不被其他校验码校验）。海明码的校验码的位置必须是在2n次方位置（n从0 开始，分别代表从左边数起分别是第1、2、4、8、16），信息码也就是在非2n次方位置第i位校验码从当前校验码位开始，每次连续校验i位后再跳过i位，然后再连续校验i位，再跳过i位，以此类推。确定每个校验码所校验的比特位：1.2 海明编码程序流程图1.3 交互界面设计 编码：原码序列从“输入序列”编辑框输入，点击“编码”按钮在“编码序列”编辑框输出编码序列，对输入编码要求为二进制输入译码：编码序列从“输入序列”编辑框输入，点击“译码”按钮在“译码序列”编辑框输出译码序列，若译码错误会有响应的报错和纠错，对输入序列有不小于三位和二进制序列的要求1.4 核心代码与注释输入序列框callback%做输入检测，检测是否是“0”“1”输入，否则报错temp_str=get(handles.input,'String');num_char=unique(temp_str);%unique函数获得输入字符串中不同字符的字符串if length(num_char)=2 %如果字符串长度为2 if num_char(2)='1' %第二个字符不是“1”说明字符串中有其他字符 else set(handles.input,'String','0000'); errordlg('只能输入1和0','输入错误'); endelseif length(num_char)=1 %如果字符串长度为1，判断“1”还是“0",否则报错 if num_char(1)='0' elseif num_char(1)='1' else set(handles.input,'String','0000'); errordlg('只能输入1和0','输入错误'); end else %如果字符串长度不为2，直接报错 set(handles.input,'String','0000'); errordlg('只能输入1和0','输入错误'); End编码按钮callback（编码核心）%获取输入字符串temp_str=get(handles.input,'string');%获取字符串长度len_str=length(temp_str);%转存原码字符串长度备用k=len_str;%初始化需要插入的校验码的位数r=0;%根据海明编码的2(r)-1)<(k+r)要求，计算校验码位数while(2(r)-1)<(k+r) r=r+1;end%把字符串数组转成0和1的数组，便于处理for i=1:1:len_str if temp_str(i)='1' yuan(i)=1;%原码数组为yuan else yuan(i)=0; endend%把求得相应位数的校验码，用0插入原码中得到新码j=0;m=1;for i=1:1:(k+r) if i=2(j) %如果该位置为2的次方，则插入校验码 xin(i)=0; j=j+1; else xin(i)=yuan(m); m=m+1; endend%进行海明编码odd=0;%用于计算每位校验码负责校验的位置的和for j=1:1:r %共有r位校验码，需要计算r次 n=1; %初始化循环变量 i=1; while(n*2(j-1)+i-1)<=(k+r)%当没有超过数组长度时继续循环 if i>(2(j-1) %如果本段的编码已经加完 i=1; %则调转到下一段，也就是隔一个2(j-1)的段再进行累加 n=n+2; else %累加 odd=odd+xin(n*2(j-1)+i-1); i=i+1; end end if mod(odd,2)=0 %判断是否为偶数 xin(2(j-1)=0; %若为偶数，则在对应的校验位插入0 else xin(2(j-1)=1; %若为奇数，则在对应的校验为插入1 end odd=0;end%编码完毕，把数组转换成字符串用于输出for i=1:1:(k+r) if xin(i)=1 output_str(i)='1' else output_str(i)='0' endendset(handles.out,'String',output_str);译码按钮callback（原理与编码基本相同）%获得译码序列字符串temp_str=get(handles.input,'string');len_str=length(temp_str);%判断输入序列长度是否满足要求，不满足报错返回if len_str<3 errordlg('译码最低输入位数为3位','输入出错');else k=len_str;%编码息码的个数 r=len_str;%编码中校验码的个数 while(2(r)-1)>=len_str) r=r-1; end r=r+1;%找到校验码的个数 k=len_str-r; for i=1:1:len_str%得到所有编码数组 if temp_str(i)='1' xin(i)=1; else xin(i)=0; end end %提取出信息编码数组 m=1; j=0; for i=1:1:(k+r) if i=2(j) j=j+1; else yuan(m)=xin(i); m=m+1; end end %重新偶校验，原理同编码 odd=0; for j=1:1:r n=1; i=1; while(n*2(j-1)+i-1)<=(k+r) if i>(2(j-1) i=1; n=n+2; else odd=odd+xin(n*2(j-1)+i-1); i=i+1; end end if mod(odd,2)=0 check(j)=0; %校验结果存在check数组中 else check(j)=1; end odd=0; end %把check数组也就是校验结果转成十进制数 num_wrong=0; for j=1:1:r num_wrong=num_wrong*2; if check(r-j+1)=1 num_wrong=num_wrong+1; end end %判断校验是否正确，为0则正确 if num_wrong=0 for m=1:1:k if yuan(m)=1 output_str(m)='1' else output_str(m)='0' end end set(handles.ym_out,'String',output_str); else%否则校验错误，对应位置取反后再输出 if xin(num_wrong)=0 xin(num_wrong)=1; else xin(num_wrong)=0; end m=1; j=0; for i=1:1:(k+r) if i=2(j) j=j+1; else yuan(m)=xin(i); m=m+1; end end for m=1:1:k if yuan(m)=1 output_str(m)='1' else output_str(m)='0' end end set(handles.ym_out,'String',output_str); errordlg('校验码第 ',num2str(num_wrong),' 位出错,对应位置取反后得到正确解码为',output_str,'校验出错'); endend1.5 程序执行测试1.5.1 编码测试正常编码1.5.2 译码测试输入报错正常解码解码错误与纠正容2：CRC编码2.1 CRC编码原理在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)*2R），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)*2R 除以生成多项式G(x)得到的余数就是校验码。若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得V(x)=A(x)g(x)=xRm(x)+r(x);其中: m(x)为K次原始的信息多项式， r(x)为R-1次校验多项式（即CRC校验和），g(x)称为生成多项式：g(x)=g0+g1x1+ g2x2+.+g(R-1)x(R-1)+gRxR发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。2.2 CRC编码程序流程图 2.3 交互界面设计 编码：原码序列由“输入序列”编辑框输入，生成式由“生成式子”编辑框输入，点击“编码”按钮，在“输出序列”编辑框输出编码序列，对输入序列有二进制输入的要求，对生成式的输入除二进制输入以外，还有首位与末位不能为0的要求 译码：编码序列由“输入序列”编辑框输入，生成式由“生成式子”编辑框输入，点击“译码”按钮，在“输出序列”编辑框输出译码序列，对输入序列有二进制输入的要求，还有不能小于生成式的长度，否则将报错，对生成式的输入除二进制输入以外，还有首位与末位不能为0的要求2.4 核心代码与注释编码按钮callback（编码核心）temp_str=get(handles.input,'string');len_str1=length(temp_str);for i=1:1:len_str1 %把原码的字符串转成数组，便于后续处理 if temp_str(i)='1' sz(i)=1; temp_sz(i)=1; else temp_sz(i)=0; sz(i)=0; endendtemp_crc=get(handles.crc,'string');len_scs=length(temp_crc)-1; for i=1:1:(len_scs+1) %把生成式的字符串转成数组 if temp_crc(i)='1' scs(i)=1; else scs(i)=0; endend%把原码后面加上CRC冗余编码，位数为CRC生成式长度-1for i=len_str1+1:1:(len_str1+len_scs) temp_sz(i)=0; sz(i)=0;end%从生成式长度位开始往后循环做类似于长除法的运算，实际为异或，注意首位为0时商0for j=(len_scs+1):1:(len_str1+len_scs) if temp_sz(j-len_scs)=0 for i=1:1:(len_scs+1) if temp_sz(j-len_scs-1+i)=0 temp_sz(j-len_scs-1+i)=0; else temp_sz(j-len_scs-1+i)=1; end end else for i=1:1:(len_scs+1) if scs(i)=temp_sz(j-len_scs-1+i) temp_sz(j-len_scs-1+i)=0; else temp_sz(j-len_scs-1+i)=1; end end endend%把得到的冗余码余子式加上原码后面形成编码for i=(len_str1+1):1:(len_str1+len_scs) sz(i)=temp_sz(i);end%把数组转成字符串数组并输出for i=1:1:(len_str1+len_scs) if sz(i)=1 output_str(i)='1' else output_str(i)='0' endendset(handles.output,'String',output_str);译码按钮callback（原理与编码基本相同）temp_str=get(handles.input,'string');len_str1=length(temp_str);for i=1:1:len_str1 if temp_str(i)='1' sz(i)=1; temp_sz(i)=1; else temp_sz(i)=0; sz(i)=0; endendtemp_crc=get(handles.crc,'string');len_scs=length(temp_crc)-1;if len_str1<=len_scs errordlg('输入译码序列长度不能小于生成式序列长度','输入错误'); elsefor i=1:1:(len_scs+1)if temp_crc(i)='1' scs(i)=1;else scs(i)=0; endendfor j=(len_scs+1):1:len_str1if temp_sz(j-len_scs)=0for i=1:1:(len_scs+1) if temp_sz(j-len_scs-1+i)=0 temp_sz(j-len_scs-1+i)=0; else temp_sz(j-len_scs-1+i)=1; endend else for i=1:1:(len_scs+1) if scs(i)=temp_sz(j-len_scs-1+i) temp_sz(j-len_scs-1+i)=0; else temp_sz(j-len_scs-1+i)=1; end endendendfor i=(len_str1-len_scs+1):1:len_str1sz(i)=temp_sz(i);end for i=1:1:(len_str1-len_scs) if sz(i)=1 output_str(i)='1' else output_str(i)='0' end end set(handles.output,'String',output_str); er=0; for i=(len_str1-len_scs+1):1:len_str1 sz(i)=temp_sz(i); if temp_sz(i)=0 er=er+0; else er=er+1; end end if er>0 set(handles.output,'String','NONE'); errordlg('校验错误','校验错误'); endEnd2.5 程序执行测试2.5.1 编码测试正常编码2.5.2 译码测试输入报错正常译码译码报错容3：思考问题3.1 CRC编码和海明编码的主要区别有哪些？3.1.1 CRC和海明的校验码的位置不同，CRC冗余码加在原码序列后面，从而形成编码序列，而海明是插在2的次方位 3.1.2 CRC的冗余码位数和生成式有关，一旦生成式定下来，那么冗余码位数就确定，而海明则是与输入编码序列的位数有关，输入编码序列位数越多，海明校验码的位数越多 3.1.3 CRC和海明的校验原理完全不同，CRC是基于长除法的一种余子式校验，而海明则是基于奇偶校验，而且校验码把原来的信息码分片校验 3.1.4 CRC没有纠错能力，但是易于电路实现，因为异或和以为实现简单，所以广泛用于实际校验，而海明虽然具有纠错能力，但是计算比较复杂，因为需要次方运算，而且只能纠一位错，所以实用性不如前者。3.2 海明编码能纠多位错误吗？ 不能，海明码能校验出两位错误，并能纠正一位错误。3.3 CRC编码的检错能力与生成多项式最高幂次数值有关系吗？ 有，考虑极端情况，如果生成式只有三位，那么余数只有00，01，10，11，四种情况， 所以如果原码信息码错上多位，很有可能导致校验码出现00的情况，也就是正确的。实验过程中遇到的问题如何解决的？问题1： CRC编码的输入和运算的实现 解决:因为输入的是字符串序列，所以不能直接进行运算，而且如果转成十进制数或者二进制数也不好提却出来做位运算，最终采用数组形式，这样0 和 1的提取就很方便问题2：CRC编码在实现过程中的移位和除法问题 解决:使用暂存的原码序列做除法，设置双层循环，外层是除法的次数，层是生成式子的长度，即异或运算的次数问题3：CRC的生成式序列需要检验，不能直接用于编码 解决：对生成式输入序列做检测，如果首位或者末位为1，需要报错问题4：海明在实现过程中，对于每位校验码的计算问题解决：对每位校验码负责的位进行累加，使用两层循环，外层是校验码的位数，也就是需要计算的次数，层是以当前处理位数是否小于总长度的循环，部做加和运算，每次加的位数是2的对应次方位。问题5： 海明在校验时，如何找出错误的位数解决：对序列先做提取校验码位数的计算，然后再对编码进行一次海明校验，把校验结果转化成十进制数，即为错误的位数，此处注意二进制数序列转成十进制时，低位在前高位在后注：实验体会综合在实验四报告中