文档库 最新最全的文档下载
当前位置:文档库 › 汉明码

汉明码

摘要

本文主要利用MATLAB通信系统仿真模型库进行汉明码建模仿真,并调用通信系统功能函数对外界输入的信息进行汉明码的编、译码,绘制时域波形及误码率与信噪比关系曲线图。在此基础上,对汉明码的性能进行分析,得出汉明码能降低噪声干扰的结论。

Hamming码中文称作汉明码。汉明码是由汉明于1950年提出的,是一种能够自动检测并纠正一位错码的线性纠错码, 它的突出特点是:编译码电路简单,易于硬件实现;用软件实现编译码算法时,软件效率高;而且性能比较好.

关键词:MATLAB 汉明码编码译码

目录

一、前言 (1)

二、设计原理 (2)

2.1 纠错编码原理 (2)

2.2 汉明码编码 (2)

2.2.1 汉明码的定义 (2)

2.2.2 汉明码的构造特点 (2)

2.2.3 汉明码编码的主要算法 (3)

2.3 汉明码的构造原理 (3)

2.4 监督矩阵H (4)

2.5 生成矩阵G (5)

2.6 校正子(伴随式) (6)

三、汉明码编码的设计 (7)

3.1 汉明码编码方法 (7)

3.2 编码流程图 (8)

3.3 汉明码编码程序设计 (8)

3.4 汉明码编码仿真波形 (9)

四、汉明码的译码器的设计 (10)

4.1 汉明码译码方法 (10)

4.2译码程序设计的流程图 (11)

4.3 汉明码译码程序的设计 (12)

4.4 汉明码译码仿真波形 (13)

五、总结 (15)

六、参考文献 (16)

附录 (17)

一、前言

数字信号在传输过程中,由于受到干扰的影响,码元波形将变坏。接收端收到后可能发生错误判决。由于乘性干扰引起的码间串扰,可以采用均衡的办法来纠正。而加性干扰的影响则需要用其他办法解决。在设计数字通信系统时,应该首先从合理选择调制制度,解调方法以及发送功率等方面考虑,使加性干扰不足以影响到误码率要求。在仍不能满足要求时,就要考虑采用差错控制措施了。

从差错控制角度看,按加性干扰引起的错码分布规律不同,信道可以分为3类,即随机信道,突发信道和混合信道。在随机信道中,错码的出现是随机的,而且错码之间是统计独立的。在突发信道中,错码是成串集中出现的,而且在短促的时间段之间存在较长的无错码区间。把既存在随机错码又存在突发错码的的信道称为混合信道。对于不同类型的信道,应该采用不同的差错控制技术。

本次课程设计运用MATLAB进行汉明码的编译码设计与仿真,MATLAB通信工具箱是一套用于在通信领域进行理论研究、系统开发、分析设计和仿真的专业化工具软件包。MATIAB通信工具箱由两大部分组成:通信系统功能函数库和SIMULINK通信系统仿真模型库。 MATLAB 通信系统功能函数库由七十多个函数组成,每个函数有多种选择参数、函数功能覆盖了现代通信系统的各个方面。这些函数包括:信号源产生函数、信源编码/解码函数、纠错控制编码/解码函数、调制/解调函数(基带和通带)、滤波器函数、传输信道模型函数(基带和通带)、TDMA、FDMA、CDMA函数、同步函数、工具函数等。以纠错控制编解码函数为例:函数库提供了线性分组码、汉明码、循环码、BCH码、里德一索洛蒙码(REED—SOLOMON)、卷积码等6种纠错控制编码,每种编码又有编码、解码、矢量输入输出、序列输入输出等四种形式的函数表达。

二、设计原理

2.1 纠错编码原理

我们把信息码分组,为每组信息码附加若干监督码的编码称为分组码(block code).在分组码中,监督码元仅监督本码组中的信息码元。分组码一般用符号(n,k)表示,其中n是码组的总位数,又称为码组的长度(码长),k是码组中信息码元的数目,n-k=r为码组中的监督码元的数目,或者称为监督位数目,分组码的结构如图1所示,图中前k位为信息位,

后面附加r个监督位。其中a

n-1到a

r

为k个信息位,a

r-1

到a

为r个监督位。

图1 分组码的结构

在分组码中,把码组中“1”的个数称为码组的重量,简称码重。把两个码组中对应位上数字不同的位数称为码组的距离,简称为码距,码距又称为汉明距离。我们把某种编码中各个码组之间距离的最小值称为最小码距(d

)。

一种编码的最小距离的大小直接关系着这种编码的检错与纠错能力:

(1)为检测e个错码,要求最小码距d

大于等于e+1;

(2)为了纠正t个错码,要求最小码距d

大于等于2t+1;

(3)为纠正t个错码同时检测e个错码,要求最小码距d

大于等于e+t+1(e>t).

2.2 汉明码编码

2.2.1 汉明码的定义

若一致监督矩阵H 的列是由不全为0且互不相同的所有二进制m(m≥2的正整数)重组成,则由此H矩阵得到的线性分组码称为[2m-1,2m-1-m,3]汉明码。

2.2.2 汉明码的构造特点

1).绐定一个m,我们由二进制m 重组成线性分组码的监督矩阵H,由二进制m重来标定一个发生错误的位置。由此可知,二进制m 重共有2 种位组合,去掉一个全为0的位组合,则余下共有2m-1种位组合。故汉明码的最大码长n=2m-1。

2).由上面分析,我们可以知道:m 即是汉明码监督位的位数。故一个汉明码中,信息位的位数k=n —m=2m

-1-m

3).汉明码的距离为3,因此可以纠正1位错误,检出2位错误。 2.2.3 汉明码编码的主要算法

汉明码的编码就是如何根据信息位数k ,求出纠正一个错误的监督矩阵H ,然后根据H 求出信息位所对应的码字。构造汉明码监督矩阵H 的方法很多,这里仅介绍一种。 1)根据已知的信息位数k ,从汉明不等式中求出校验位数m=n-k ;

2)在每个码字C :(C 1,C 2,? ,C 2m -1)中,用c 02 ,c 12 ,c n-12作为监督位,剩下的位作为信息位;

3)用二进制数字表示2m-1 列,得到2m-1列和m 行监督矩阵H ; 4)用3步的H 形成HC T =0,从而得出m 个监督方程;

5)将已知的信息代入方程组,然后求出满足上述方程组的监督位c (i=0,1,? ,m 一1)。

2.3 汉明码的构造原理

线性分组码是一类重要的纠错码,应用很广泛。在(n ,k )分组码中,若监督码元是按线性关系模2相加而得到的,则称其为线性分组码。

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

112++≥-r k r ,现在以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=[6a ,

012345,,,,,a a a a a a ],前4位是信息元,后3位是监督元,可用下列线性方程组来描述该分组码产生监督元:

????

???⊕⊕=⊕⊕=⊕⊕=346035614562a a a a a a a a a a a a (式2.3.1)

显然,这3个方程是线性无关的。代入上述公式可得(7,4)码的全部码组,如表1所示。

表1 (7,4)汉明码的全部码组

由上表可知:(7,4)汉明码的最小码距0d =3,它能纠1位错或检2位错。由此可见,汉明码是能够纠正单个错误的线性分组码,其特点是:最小码距0d =3,码长n 与监督位r 满足关系式:n r ≥-12,说明上述所说的(7,4)线性分组码就是汉明码。同时,由于码率

n r n r n n k -=-=1)(,故当n 很大和r 很小时,码率接近1,可见,汉明码是一种高效码。

2.4 监督矩阵H

式(2.3.1)所示的(7,4)汉明码的监督方程可以改写为:

??

??

???=⊕⊕⊕=⊕⊕⊕=⊕⊕⊕000

034613562456a a a a a a a a a a a a (式2.4.1)

用矩阵的形式可以将上式表示为:

?????

?????=????????

??

?

??????????????????????0001011001110101011101000123456a a a a a a a (式2.4.2)

上式可以简记为:T T A H 0=?或0=?A H T (式2.4.3)

式中 ??

??

?

?????=101100111010101110100H ,[]

0123456a a a a a a a A = , 0=[0 0 0] 右上标“T ”表示将矩阵转置。例如,H T 是H 的转置,即H T 的第一行为H 的第一列,H T

的第二行为H 的第二列等等。

其中,H 成为监督矩阵,只要监督矩阵H 给定,编码时信息位和监督位的关系也就随即确定下来了。

2.5 生成矩阵G

上面汉明码例子中的监督位公式为???

??=⊕⊕⊕=⊕⊕⊕=⊕⊕⊕0

00

034613562456a a a a a a a a a a a a (式2.5.1)

也可改写成矩阵形式: ???

??

?

????????????????=????

??????34

56012101111011110a a a a a a a (式2.5.2)

或者写成 [][][]Q a a a a a a a a a a a 34563456012011101110111=????

??

??????= (式2.5.3)

式中,Q 为一个k*r 阶矩阵,它为P 的转置,即Q=P T

上式表示,在信息位给定后,用信息位的行矩阵车乘矩阵Q 就产生出监督位。 若将(2.2.1式)的监督方程补充完整并写成矩阵的形式:

?

??

???????????

????????

??

??????????

?=??????????????????????345601234561011110111100001001001001000a a a a a a a a a a a (式2.5.4)

即:[]

M G a a a a G A ?=?=3456

上式中????

?

????

???=0001011001010101001101000111G (式2.5.5) G 为生成矩阵,根据式2.5.4知:由G 和信息码就能产生所有码字。生成矩阵也可分为两部分,即

G=[]Q I k , (式2.5.6)

上式中

Q=T P =????

?

?

???

???011101110111 (式2.5.7) Q 为r k ?阶矩阵,

k

I 为k 阶单位阵。

因此,如果找到了码的生成矩阵G ,则编码的方法就完全确定了。具有[KQ]形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A 中,信息位的位置不变,监督位附加于其后,这种形式的码称为系统码。

2.6 校正子(伴随式)

设一发送码组A=[

0121,,...,a a a a n n --],在传输的过程中可能发生误码。接受码组

[]0121,,...,b b b b B n n --=,收发码组之差定义为错误图样E 。其中[]0121,,,e e e e E n n --=,令

T

T T H

E H E A H B S ?=+=?=)( 式中S 称为校正子,他用来表示错码位置。

可见:校正子S 与错误图样E 之间由确定的线性变换关系。若S和E之间一一对应,则S将能代表错码位置。

(7,4)汉明码的校正子和错误图样之间的对应关系如表2所示。

表2 (7,4)汉明码S 与E 对应关系

由上表可知:

当S=001时,则出错在1 位,即b0 出错; 当S=010时,则出错在2 位,即b1 出错; 当S=100时,则出错在3 位,即b2 出错; 当S=011时,则出错在4 位,即b3 出错; 当S=101时,则出错在5 位,即b4 出错; 当S=110时,则出错在6 位,即b5 出错; 当S=111时,则出错在7 位,即b6 出错; 当S=000时,则无错。

三、汉明码编码的设计

3.1 汉明码编码方法

(7,4)汉明码的编码就是将输入的4 位信息码M=[

3

456a a a a ]加上3 位监督码

12b b b 从而

编成7位汉明码[

6a 0

12345,,,,,a a a a a a ],编码输出B=[

6a 5a 4a 3a 2a 1a 0

a ].由式 A =

M ·G=[3456a a a a ]·G 可知,信息码M 与生成矩阵G 的乘积就是编好以后的(7,4)汉明码。

3.2 编码流程图

首先输入信息码,再编出监督位,接下来根据信息位和监督位输出(7,4)汉明码,其编码流程图如图1所示:

图1 编码流程图

3.3 汉明码编码程序设计

根据(7,4)汉明码的编码原理,将上式计算所得的监督位和输入的信息位一起输出,则此次编码就算完成了。 (7,4)汉明码的编码源程序见下: (7,4)汉明码编码源程序: function f=hammingencod(a)

G=[1 0 0 0 1 1 1;0 1 0 0 1 1 0;0 0 1 0 1 0 1;0 0 0 1 0 1 1]; a=input('输入信息元序列:'); c=mod(a*G,2); disp('编码后序列为:'); disp(c); x=.01:.01:4;

[m,n]=size([a]'*ones(1,100));

y=reshape(([a]'*ones(1,100))',1,m*n);

plot(x,y)

axis([0 4 0 1.5]);

set(gca,'XTick',0:1:4);

set(gca,'YTick',0:0.5:1.5);

title('hanmingencode')

xlabel('value')

ylabel('value')

end

3.4 汉明码编码仿真波形

输入信息元序列:[1 0 1 0]

编码后序列为:

1 0 1 0 0 1 0

波形如图2所示:

图2 编码仿真波形

四、汉明码的译码器的设计

4.1 汉明码译码方法

(7,4)汉明码的译码器的功能就是把输入的7 位汉明码B=[2

3456b b b b b 0

1b b ] 译为4位信

息码

3a 2a 1a 0

a ,并且根据伴随矩阵S 从而纠正编码中可能出现的1 位错码。根据监督矩阵

H 和生成矩阵G 的关系,即:H = [P r I ] ,其中r I 是33?的单位阵, G = [k I Q ] ,其中

k

I 是44?的单位阵,

T Q P = (式4.1.1) 生成矩阵

[]Q I G k ,0110001101001011001001111000=?

????????

???= 由式(4.1.1),得

????

??????=101111011110P

监督矩阵

(式4.1.2)

由式(2.2.2)知:T

T T H E H E A H B S ?=+=?=)(,其中E=[0121,,...,,e e e e n n --]

从而即可得到校正子S 与(7,4)汉明码各位之间的关系:

???

??+++=+++=+++=03460

135612

4562a

a a a S a a a a S a a a a S (式4.1.3)

算出校正子S (012S S S )后,对照表2,即可判断出哪位出错,并纠正出错的那位,从而输出正确的码字。

[]r PI H =??

??

?

?????=001101101011011001110

表3 (7,4)汉明码译码输入、输出对应关系

4.2译码程序设计的流程图

首先输入七位码,再根据输入求出校正子,判断校正子是否为零,若不为零则根据S与E的关系纠正错码,若S=0则输出四位信息码,其译码流程图如图3所示:

图3 译码流程图

4.3 汉明码译码程序的设计

根据前面分析的译码原理,在程序中,C 表示错误在哪一位。若第1 位(a0)出错,则C 输出0;若第2 位出错,则C 输出1;……;若无错,则C 输出0。这样译码程序就可以编出来了。译码源程序如下:

function g=hammingdecod(B)

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

B=input('输入接收序列B=');

S=mod(B*H',2); %计算B的伴随式

if S==0

disp('接收到的码字无错误。');

E=dec2bin(0,7);

end

for i=1:1:7

if S==H(:,i)'

E=dec2bin(2^(7-i),7); %计算R的错误图样 fprintf('错误出现在第%1.0f位\n',i);

break;

end

end

a=mod(B-E,2); %计算原发送码序列 disp('原发送码字为:');

disp(a)

x=.01:.01:7;

[m,n]=size([a]'*ones(1,100));

y=reshape(([a]'*ones(1,100))',1,m*n);

[m,n]=size([B]'*ones(1,100));

z=reshape(([B]'*ones(1,100))',1,m*n);

plot(x,y)

hold on;

plot(x,z,'--r')

axis([0 7 0 1.5]);

set(gca,'XTick',0:1:7);

set(gca,'YTick',0:0.5:2.5);

set(gca,'ZTick',0:0.5:2.5);

title('hanmingdecode')

xlabel('value')

ylabel('value')

zlabel('value')

End

4.4 汉明码译码仿真波形

输入接收序列B=[1 0 1 0 0 1 0]

接收到的码字无错误。

原发送码字为: 1 0 1 0 0 1 0 波形如图4所示:

图4 译码仿真波形图

输入接收序列B=[1 0 1 0 0 1 1 ]

错误出现在第7位

原发送码字为:

1 0 1 0 0 1 0

波形如图5所示:

图5 译码仿真波形图

五、总结

这次通信系统仿真课程设计的题目是汉明码的编码、译码的仿真。通过到图书馆查阅相关的资料,得知汉明码的编码、译码仿真可以用MATLAB来做。

通过本次学习,我再一次体会到MATLAB的强大。丰富的库函数(本次仿真就直接采用MATLAB自带的库函数encode和decode,通过open命令了解到encode还可以进行线性编码和循环编码)、强大的数据处理能力,出色的绘图功能(查看误码率与信噪比的关系曲线),友好的工作平台,简单一用的操作语言等等,这些优点都促使MATLAB成为数学处理软件发展史上的巅峰之作,难怪MATLAB会成为各行各业的首选处理软件。当然,这也激发了我今后继续深入学习MATLAB的决心。

本文从差错控制编码理论的基本思想出发,在简要介绍汉明码编译原理的基础上,采用线性代数的方法,以矩阵为基本分析与设计工具,重点探讨了汉明码编码电路的实现,并使用VHDL语言编制了程序,验证了算法的可行性,从而达到理论与实践的相融合。随着计算机技术的发展和VHDL的出现,硬件设计和软件设计的界限已经被打破。本设计是利用VHDL实现高性能可编程采集系统设计的方法。通过仿真结果表明,应用可编程逻辑器件,具有速度更快、可靠性更高、调试更方便的优点。

差错控制编码,不仅能检测出单个码组中任意一位的错误,还能对错码进行纠正,并能检测出多位错码。但是从对汉明码的分析过程看,传输的准确性是靠牺牲速度来换取的,因为数据在传输过程中被分成了几次进行,且数码的位数越多,速度就越慢。但其编译码方案都是由软件实现的,所以完全可以满足应用系统对速度的要求。从分析过程以及仿真结果看,用硬件可编程语言VHDL进行数字系统的设计,可以提高数字系统的工作效率,降低消耗,保证系统的稳定性和可靠性。

知识的构架是千枝交错的。学到大学,知识之间相互渗透的现象可谓比比皆是,这启发我们不仅要发散思维的领域,也要拓宽知识的领域。对与本专业相关的领域多加了解百利而无一害。

在这次课程设计的过程中,我深深的感触到了团队合作的重要性,尤其是在当今的社会工作中,一个人的力量在一个巨大的任务前是那么的渺小,必须靠多人合作才能共同完成。在设计规划过程,我们小组四个人亲密无间的合作,使得本次课程设计能够非常顺利地完成,在课程设计的过程中,每个人都能按要求很好的完成分配给自己的任务,最后大家一起通过讨论把所有任务串连起来完成总的设计任务。

六、参考文献

【1】李建新现代通信系统分析与仿真—MATLAB通信工具箱.西安:西安电子科技大学出版社,2000

【2】樊昌信通信原理.北京:国防工业出版社,2002

【3】刘敏 MATLAB通信仿真与应用国防工业出版社

【4】曹志刚等著现代通信原理北京:清华大学出版社,2001 5

【5】吴伟陵等著移动通信原理北京:电子工业出版社,2005

【6】韩利竹,王华 MATLAB电子仿真与应用北京:国防工业出版社,2003年.

【7】赵静基于MATLAB的通信系统仿真北京:北京航空航天大学出版社,2008年.

【8】葛哲学精通MATLAB 北京:电子工业出版社,2008年.

附录

一、(7,4)汉明码编码源程序

function f=hammingencod(a)

G=[1 0 0 0 1 1 1;0 1 0 0 1 1 0;0 0 1 0 1 0 1;0 0 0 1 0 1 1]; a=input('输入信息元序列:');

c=mod(a*G,2);

disp('编码后序列为:');

disp(c);

x=.01:.01:4;

[m,n]=size([a]'*ones(1,100));

y=reshape(([a]'*ones(1,100))',1,m*n);

plot(x,y)

axis([0 4 0 1.5]);

set(gca,'XTick',0:1:4);

set(gca,'YTick',0:0.5:1.5);

title('hanmingencode')

xlabel('value')

ylabel('value')

end

二、(7,4)汉明码译码源程序

function g=hammingdecod(B)

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

B=input('输入接收序列B=');

S=mod(B*H',2); %计算B的伴随式

if S==0

disp('接收到的码字无错误。');

E=dec2bin(0,7);

end

for i=1:1:7

if S==H(:,i)'

E=dec2bin(2^(7-i),7); %计算R的错误图样

fprintf('错误出现在第%1.0f位\n',i);

break;

end

end

a=mod(B-E,2); %计算原发送码序列 disp('原发送码字为:');

disp(a)

x=.01:.01:7;

[m,n]=size([a]'*ones(1,100));

y=reshape(([a]'*ones(1,100))',1,m*n);

[m,n]=size([B]'*ones(1,100));

z=reshape(([B]'*ones(1,100))',1,m*n);

plot(x,y)

hold on;

plot(x,z,'--r')

axis([0 7 0 1.5]);

set(gca,'XTick',0:1:7);

set(gca,'YTick',0:0.5:2.5);

set(gca,'ZTick',0:0.5:2.5);

title('hanmingdecode')

xlabel('value')

ylabel('value')

zlabel('value')

end

相关文档