matlab(74)汉明码和(74)循环码的编程设计

二、创新实验设计

创新实验一：（7,4）汉明码的编码与译码实现

1、实验目的

实现（7,4）汉明码的编码与译码，通过这次实验不但加深了对汉明码编码和译码原理了解，而且对线性分组码有所了解。

2、实验原理

线性分组码的构造方法比较简单、理论较为成熟，应用比较广泛。汉明码是一种能够纠正一个错码的效率比较高的线性分组码，下面以（7,4）码为例就汉明码的编码与译码分别进行介绍：

（1）编码原理

一般来说，若汉明码长为n，信息位数为k，则监督位数r=n-k。若希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求

2r1n或21kr1 (1)

设汉明码（n,k）中k=4，为了纠正一位错码，由式（1）可知，要求监督位数r≥3。若取r=3,则n=k+r=7。这样就构成了（7,4）码。用示这7个码元，用

a6a5a4a3a2a1a0r来表

s1s2s3的值表示3个监督关系式中的校正子，则

s1s2s3的值与

错误码元位置的对应关系可以规定如表1所列。

表2.1 校正子和错码位置的关系

s1s2s3 错码位置 s1s2s3 错码位置 001 a0a1 101 a4a5a6 010 100 011 110 111 000 a2a3 无错码 则由表1可得监督关系式：

2

sa6a5a3a13 2

sa6a4a3a04 3

s1a6a5a4a2

在发送端编码时，信息位监督位a2、

1

a6a5a4a3的值决定于输入信号，因此它们是随机的。

a1、a0应根据信息位的取值按监督关系来确定，为使所编的码中无

-

错码，则S1,S2,S3等于0，即

a6a5a4a20a6a5a3a10aaaa04306方程组（5）可等效成如下矩阵形式

(5)

a6a51110100a401101010a031011001a20a1a0 （6）式(6)可简化为HAT0T，H为监督矩阵，则由式(6)可得到监督矩阵

1110100=[PI] H1101010r1011001(7)

因为生成矩阵G=[IkQ]=[IkP']，所以由(7)得生成矩阵G如下：

1000101001GIkQ[IkP']00101000101110 0111然后利用信息位和生成矩阵G相乘产生整个码组，即有

A=a6a5a4a3a2a1a0a6a5a4a3G其中A为整个码组矩阵，a6a5a4a3是信息位。 根据上述原理可以得到(7,4)汉明码的整个码组。

(8)

（2）译码与检错、纠错原理

当数字信号编码成汉明码后，由于信道噪声的存在，使得经过信道后的汉明码会发生差错，使得接收端接收到错码，因此需要多错码进行纠正，以提高通信系统的抗干扰能力及可靠性。下面分析纠错译码原理。

设B为接收码组，它是一行7列的矩阵，即B=[b1b2b3b4b5b6b7]，B中可能含

2

-

有错码，错误图样EAB=[e7e6e5e4e3e2e1]，在E的表达式中，有

0ei1当biai时当biai时(i0,1,2,7)

若ei0，表示该码元没错；若ei1，表示该码元为错码。 由EAB得

ABE(9)

(9)表示接收码组和错误图样之和等于正确码组U，通过（9）式就可以实现纠错。可以用标准阵来表示所有可能的2n个n元码组的接收矢量，(n,k)码的标准阵形式如下：

A1E2E3EjE2nkA2A2E2A2E3A2EjA2E2nkA3A3E2A3E3A3EjA3E2nkA4A4E2A4E3A4EjA4E2nkA5A5E2A5E3 A5EjA5E2nk应该注意到，码组A1（全0码字）起两个作用：既是其中一个正确码组，也是错误图样E1,代表A1所在行没有错误。标准阵中的A1,E2,E3E2nk是陪集首，

陪集首的选择是有规定的，第j行的陪集首是在前j-1行中没有出现的最小码组，即错误图样E，如果不选错误图样作为陪集首，译码将会产生错误。

d1对于(7,4)汉明码，其最小码重是3，设码的纠错能力为t，根据公式tmin2得该码的纠错能力为1，即能纠错一位错码。由于根据完备码的定义有

2nknj0jt(12)

将(7,4)码代入(12)可以得知，(7,4)汉明码为完备码组，只能纠错和检错一位错码。

对于正确码组A而言，有

AHT0(10)

当接收到错码变成码组B时，有

SBHT(AE)HTAHTEHTEHT(11)

其中S为校正子所构成的校正矩阵，由于S和E如（11）所示的一一对应的关系，对于(7,4)码，错误图样与伴随式的对应关系如下

表2.2 伴随式查询表

3

-

错误图样 0000000 00000001 0000010 0000100 0001000 0010000 0100000 1000000 伴随式 000 001 010 100 011 101 110 111 通过伴随式查询表，可以由伴随式得到错误图样，从而实现检错，进而实现纠错。 3、实验内容

由于编码涉及到矩阵的运算，而matlab在处理矩阵运算方面有独特优势，所以这次选择用matlab工具来实现（7,4）汉明码的编码和译码。

(7,4)码的编码比较简单，已知监督矩阵H，可以通过函数求生成矩阵G，然后信息位和生成矩阵G相乘就可得到所有的码组，(7,4)汉明码的编码程序如下：

%%%（7,4）汉明码编码——2012.11.10 clear all; clc;

H=[1 1 1 0 1 0 0 ; 1 1 0 1 0 1 0;

1 0 1 1 0 0 1];%(7,4)码的监督矩阵 G=gen2par(H)%(7,4)码的生成矩阵

m=[0 0 0 0;0 0 0 1;0 0 1 0;0 0 1 1;0 1 0 0; 0 1 0 1;0 1 1 0;0 1 1 1;1 0 0 0;1 0 0 1;

1 0 1 0;1 0 1 1;1 1 0 0;1 1 0 1;1 1 1 0;1 1 1 1];%%所有的信息位 U=[rem(m*G,2)];

disp('(7,4)汉明码的编码结果：'); disp(U);

由原理分析可知，要实现纠错和检错译码，关键在于伴随式查询表，因此如何实现伴随式查询表是编程的关键，(7,4)汉明码的译码程序如下：

%%%下面是(7,4)码译码

A=input('请输入接收码组：'); [r,l]=size(A);

E=[0 0 0 0 0 0 0;0 0 0 0 0 0 1;0 0 0 0 0 1 0;0 0 0 0 1 0 0;0 0 0 1 0 0 0;0 0 1 0 0 0 0;0 1 0 0 0 0 0;1 0 0 0 0 0 0]; %%%%%求校正子，然后将其转化成十进制数 for i=1:r

Sx=S(i,1)*4+S(i,2)*2+S(i,3); end

%%%%下面是（7,4）码检错 for i=1:r

switch(Sx) 4

-

case 0

disp('此接收码字没错') case 1

disp('注意：此接收码字的第一位有错，请纠正') case 2

disp('注意：此接收码字的第二位有错，请纠正') case 4

disp('注意：此接收码字的第三位有错，请纠正') case 3

disp('注意：此接收码字的第四位有错，请纠正') case 5

disp('注意：此接收码字的第五位有错，请纠正') case 6

disp('注意：此接收码字的第六位有错，请纠正') case 7

disp('注意：此接收码字的第七位有错，请纠正') end end

%%%下面为在知道哪位出错的情况下，进行纠正 for i=1:r

switch(Sx) case 0

B(i,:)=A(i,:)+E(1,:); case 1

B(i,:)=A(i,:)+E(2,:); case 2

B(i,:)=A(i,:)+E(3,:); case 4

B(i,:)=A(i,:)+E(4,:); case 3

B(i,:)=A(i,:)+E(5,:); case 5

B(i,:)=A(i,:)+E(6,:); case 6

B(i,:)=A(i,:)+E(7,:); case 7

B(i,:)=A(i,:)+E(8,:); end end

B=rem(B,2);

disp('纠错后的码字'); disp(B);

由于可能在纠错过程中会产生错误，在此，我们设计了检错纠错是否产生错误的程序，程序如下：

5

-

%%%%下面为检查纠错是否产生错误 k=1;

for k=1:16

if (U(k,:)==B) flag=1; break end end

if flag==1

disp('纠错无误'); else

disp('注意：纠错有误，请检查') End

由于译码的目的就是找出信息位c，所以，需要从纠错后的码组中提取出信息位，提取信息位的程序如下：

%%%下面为提取码的信息位 for j=1:4

c(:,j)=B(:,j); end

disp('信息位c如下：') disp(c)

4、实验结果分析

运行编码程序后，得到如下结果

通过理论计算，可以得出实验结果和理论编码结果吻合，可以发现，（7,4）码的最小码重是3。

当接收码组为[1 1 0 1 1 0 0]时，译码结果如下

6

-

运行程序后，可以看到：当接收码组为[1 1 0 1 1 0 0]时，会出现“注意：此接收码字的第六位有错，请纠正”的提示，在程序中，为防止纠错错误，我设置了纠错后的码和编码结果的比较，如果纠错后的码和编码结果当中的某个码组相同，说明纠错无误，否则纠错有误。当接收码组为[1 1 0 1 1 0 0]时，经过纠错后出现纠错无误的结果，说明纠错后的码是正确码组。然后提取纠错后的码组的信息位c，从运行结果可以看出，c=1001。

当接收码组为[0 1 0 1 1 0 1]时，运行结果如下：

此接收码组本来就是一个正确码组，所以通过运行程序后，会出现“此接收码字没错”的提示，纠错后的码字和接收的码组是相同的，检查到纠错无误，然后提取信息位c，信息位c=0101，整个译码完成。

5、改进建议

(7,4)汉明码的编码与译码相对比较简单，可以通过matlab编程实现对信道编码性能的分析，可以编程实现比较编码后的误码率和没编码的误码率，也可以编程实现在有噪声的情况下来进行译码。

创新实验二：（7,4）循环码的编码与译码

1．实验编码原理： 根据循环码的代数性质建立系统编码的过程，可以把消息矢量用如下多项式表示：

7

m(x)mk1xk1mk2xk2...m1xm0 -

要编码成系统循环码形式，把消息比特移入码字寄存器的最右边k位，而把监督

nknk比特加在最左边的n-k个中，则要用x乘以m(x)得到x m(x)=

n1n2nk1nkmxmx...mxmxk1k210

xnk m(x)= q(x) g(x)+ p(x)，其中p(x)可以表示为

nk1...p1xp0p(x)= pnk1xnk，则p(x)+ x m(x)

n1n2...m1xnk1m0xnk+ pnk1xnk1...p1xp0= mk1xmk2xnkmpp另U(x)= p(x)+ x m(x)，则U=（0，p1，p2，···，nk1，0 ，m1，···，

mk1）。

3 本实验根据以上原理，用matlab实现书上例6.8系统形式的循环码，生成多

1xx项式为g(x)=

2．实验译码原理：译码的实验原理 g(x)= ，在（n，k）循环码中，

nx1可分解成g(x)和其他因式的乘积，记为 由于g(x)能除尽,因此

1xx3 即可写成

x1g(x)h(x)

nxh(x)1n

*43hh(x)xxx 则 =  1，其中

g(x)即h (x) =

x4x2x1*(x)式h(x)的逆多项式。

监督矩阵多项式可表示为

x2h*(x)*H(x)xh(x)h*(x) ，

3．（7,4）循环码的编码（4位）的程序：

clear; clc;

a=input('请输入消息矢量：'); %高次项系数在前的生成多项式 Gx=[1 0 1 1];

%将数组a的高位依次放在数组Data的低位 Data=zeros(1,7); Data(1)=a(4); 8

-

Data(2)=a(3); Data(3)=a(2); Data(4)=a(1);

%Data除以Gx得到余数Rx [Qx,Rx]=deconv(Data,Gx); b=Rx+Data;

%将数组b的高位放在后面 c=b(1); b(1)=b(7); b(7)=c; c=b(2); b(2)=b(6); b(6)=c; c=b(3); b(3)=b(5); b(5)=c;

%将数组b校正 for i=1:7

if rem(abs(b(i)),2)==0 b(i)=0;end end for i=1:7

if rem(abs(b(i)),2)==1 b(i)=1;end end

disp('输入序列：'); a

disp('编码输出序列：'); b

程序运行结果为：

9

-

改变输入序列

运行结果的编码如下： 序号 1 2 3 4 5 6 7 输入序列 0000 0001 0010 0011 0100 0101 0110 输出序列 000 0000 101 0001 111 0010 010 0011 011 0100 110 0101 100 0110 序号 9 10 11 12 13 14 15 输入序列 1000 1001 1010 1011 1100 1101 1110 1111 输出序列 110 1000 011 1001 001 1010 100 1011 101 1100 000 1101 010 1110 111 1111 8 0111 001 0111 16 4．相对应的译码和纠错（7位）程序： clear; clc;

r=[1 0 0 1 1 1 1];

h=[1,0,0;1,1,0;1,1,1;0,1,1;1,0,1;0,1,0;0,0,1]; b=flipud(h); s=r*b; for i=1:3

if rem(abs(s(i)),2)==0 s(i)=0;end

10

-

end for i=1:3

if rem(abs(s(i)),2)==1 s(i)=1;end end

if s==[0 0 0]

e=[0 0 0 0 0 0 0 ]; elseif s==[1 0 0]

e=[0 0 0 0 0 0 1]; elseif s==[1 1 0]

e=[0 0 0 0 0 1 0]; elseif s==[1 1 1]

e=[0 0 0 0 1 0 0]; elseif s==[0 1 1]

e=[0 0 0 1 0 0 0]; elseif s==[1 0 1]

e=[0 0 1 0 0 0 0]; elseif s==[0 1 0]

e=[0 1 0 0 0 0 0]; else s==[0 0 1]

e=[1 0 0 0 0 0 0]; end u=r+e; for i=1:7

if rem(abs(u(i)),2)==0 u(i)=0;end end for i=1:7

if rem(abs(u(i)),2)==1 u(i)=1;end end

Data=zeros(1,4); Data(1)=u(4); Data(2)=u(5); Data(3)=u(6); Data(4)=u(7); if e==[0 0 0 0 0 0 0] disp('没有错误：') k=0,else

disp('第几位错误：') k=find(e) ;end

disp('接收码字')

11

-

r

disp('译码输出序列：') Data

第几位错误：k = 5 接收码字

r = 1 0 0 1 1 1 1 译码输出序列：

Data =1 0 1 1

以上编码有个缺点，就是它只能对一个消息矢量（4位）进行编码，我又在这个基础上编写了一个可以同时对位数是4的倍数的消息矢量进行编码。 5．多位循环码（4的倍数）的编码程序如下： clear; clc;

a=[1 1 0 0 1 0 1 1]; [X,N]=size(a);

%将信息码分为M帧，1帧4个信息码

M=ceil(N/4); d=zeros(1,4); b=zeros(1,7*M); Data=zeros(1,7); for k=1:M for j=1:4

d(j)=a(j+(k-1)*4);end %生成多项式 Gx=[1 0 1 1]; Data(1)=d(4); Data(2)=d(3); Data(3)=d(2); Data(4)=d(1);

%Data除以Gx得到余数Rx [Qx,Rx]=deconv(Data,Gx); e=Rx+Data;

b(7*k-6:7*k)=e(1:7); c=b(1+(k-1)*7);

b(1+(k-1)*7)=b(7+(k-1)*7); b(7+(k-1)*7)=c; c=b(2+(k-1)*7);

b(2+(k-1)*7)=b(6+(k-1)*7); b(6+(k-1)*7)=c; c=b(3+(k-1)*7);

b(3+(k-1)*7)=b(5+(k-1)*7); b(5+(k-1)*7)=c; end

for i=1:M*7

12

-

if rem(abs(b(i)),2)==0 b(i)=0;end end

for i=1:M*7

if rem(abs(b(i)),2)==1 b(i)=1;end end

disp('输入序列：'); a

disp('编码输出序列：'); b

程序运行结果如下：输入序列：a =

1 1 0 0 1 0 1 编码输出序列：b = Columns 1 through 13

1 0 1 1 1 0 0 1

Column 14 1

6．多位译码（7的倍数）纠错程序： clear; clc;

r=[1 0 0 1 1 0 0 1 0 0 1 0 0 1 ]; [X,N]=size(r);

%将接收到的码分为M帧，1帧7个信息位 M=ceil(N/7);

h=[1,0,0;1,1,0;1,1,1;0,1,1;1,0,1;0,1,0;0,0,1]; b=flipud(h); d=zeros(1,7); U=zeros(1,4*M); Data1=zeros(1,7*M); Data=zeros(1,7*M); for i=1:M for j=1:7

d(j)=r(j+(i-1)*7);end s=d*b;

for k=1:3

if rem(abs(s(k)),2)==0 s(k)=0;end end for k=1:3

if rem(abs(s(k)),2)==1 s(k)=1;end

13

1 0 0 1 0 1 -

end

if s==[0 0 0]

e=[0 0 0 0 0 0 0 ]; elseif s==[1 0 0]

e=[0 0 0 0 0 0 1]; elseif s==[1 1 0]

e=[0 0 0 0 0 1 0]; elseif s==[1 1 1]

e=[0 0 0 0 1 0 0]; elseif s==[0 1 1]

e=[0 0 0 1 0 0 0]; elseif s==[1 0 1]

e=[0 0 1 0 0 0 0]; elseif s==[0 1 0]

e=[0 1 0 0 0 0 0]; else s==[0 0 1]

e=[1 0 0 0 0 0 0]; end u=d+e; for k=1:7

if rem(abs(u(k)),2)==0 u(k)=0;end end for k=1:7

if rem(abs(u(k)),2)==1 u(k)=1;end end

Data(1+7*(i-1))=e(1); Data(2+7*(i-1))=e(2); Data(3+7*(i-1))=e(3); Data(4+7*(i-1))=e(4); Data(5+7*(i-1))=e(5); Data(6+7*(i-1))=e(6); Data(7+7*(i-1))=e(7); U(1+(i-1)*4)=u(4); U(2+(i-1)*4)=u(5); U(3+(i-1)*4)=u(6); U(4+(i-1)*4)=u(7); end

if Data== Data1 disp('没有错误：') m=0,else

disp('第几位错误：') m=find(Data)

14

-

;end

disp('接收到的码字：'); r

disp('译码输出序列：'); U

运行结果：

第几位错误：m =3 13

接收到的码字：r =Columns 1 through 13

1 0 0 1 1 0 0 1 0 0 1 0 0

Column 14 1

译码输出序列：

U = 1 1 0 0 1 0 1 1

若把接受序列r改为r=[ 1 0 1 1 0 0 1]，即1100的编码1011100的第5位和第7位同时该变，则运行结果为：第几位错误： m = 4

接收到的码字： r =

1 0 1 1 0 0 1 译码输出序列： U =

0 0 0 1 而0001的编码为1010001 分析总结：这两组实验基本上完成了循环码的编码和译码，但是该实验的缺点就

是不能同时对7位信息码进行两位的纠错，即只能完成一位信息码的纠错。

15