计算机通信课设汉明码附程序.docx

计算机通信课设汉明码附程序.docx

《计算机通信课设汉明码附程序.docx》由会员分享，可在线阅读，更多相关《计算机通信课设汉明码附程序.docx（22页珍藏版）》请在冰点文库上搜索。

计算机通信课设汉明码附程序

摘要

在通信系统中，要提高信息传输的有效性，我们将信源的输出经过信源编码用较少的符号来表达信源消息，这些符号的冗余度很小，效率很高，但对噪声干扰的抵抗能力很弱。

为了提高信息传输的准确性，我们引进了差错控制技术。

而该技术采用可靠的，有效的信道编码方法来实现的。

纠错码是一种差错控制技术，目前已广泛应用于各种通信系统和计算机系统中，纠错编码主要用于数字系统的差错控制，对于保证通信、存储、媒体播放和信息转移等数字传递过程的质量有着重要意义，是通信、信息类科知识结构中不可缺少的一部分。

本文系统地介绍了纠错码在数字系统中的应用和发展，以及纠错码的基本原理和含义,常用纠错码的简介和分类,同时也介绍了Vc++6.0的基本知识，以及如何应用Vc++实现hamming码编码器和译码器。

关键字：

通信系统、信道编码、线性分组码、Hamming码

前言.............................................................................................................................................3

前言

近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。

因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计的重要课题。

目前，绝大多数的数字计算机和数字通信系统中广泛采用二进制形式的码。

而线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。

差错控制编码就是在发送端的信息码无序列中，以某种确定的编码规则加入一些监督码元，使信息码元与监督码元之间具有某种相关性。

接收端通过检验这种相关性是否存在来判断在传输过程中是否出现了误码。

线性分组码具有编/译码过程简单，封闭性好等特点，是目前较为流性的差错控制编码技术之一。

设计数字通信系统时,应首先合理选择信道编译码码组种类，这样才可以在信号的传输，以及接收环节达到较好的效果，线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。

线性分组码是一组固定长度的码组，可表示为（n,k），通常它用于前向纠错。

在分组码中，监督位被加到信息位之后，形成新的码。

在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。

第1章计算机通信中的编码原理

1.1计算机通信系统的组成

通信系统是传递信息所需的一切技术设备的总和，包括信息源、发送设备、传输介质、信息接收者和接收设备。

数字通信系统传输的数据是数字化了的信息。

简化的系统模型，如图1所示。

图1.1简化的通信系统模型

信息源中，模拟信息源（如模拟式电话机、电视摄像机）输出的是幅度连续变化的信号，离散信息源（如计算机）输出的是离散的符号序列或文字。

通过采样和量化可以将模拟信息变换为离散信息。

发送设备的基本功能是使不同种类和速率的信息源与传输媒介相匹配，通常是将信息源产生的信息经过编码，并变换为便于传送的信号形式，送往传输介质。

编码包括信源编码与信道编码两部分。

信源编码把连续消息变换为数字信号，信道编码则使数字信号与传输介质匹配，提高传输的可靠性和有效性。

调制是多种变换方式中最常见的一种。

发送设备还包括为达到某些特殊要求所进行的各种处理，如多路复用、保密处理、纠错编码处理等。

传输介质是发送设备到接收设备之间信号传递所经过的媒介。

例如：

电磁波、红外线等无线传输介质，各种电缆、光缆、双绞线等有线传输介质。

传输过程中必然会引入热噪声、衰减、脉冲等干扰。

介质的固有特性和干扰特性直接关系到编码方式的选取。

接收设备的基本功能是完成对发送的反变换（解调、译码、解密等），从带有干扰的信号中恢复出正确的原始信息；对于多路复用信号还包括解除多路复用和实现正确分路（或称输出扫描）。

双向通信要求通信双方都有发送设备和接收设备，如果两个方向共用一个传输媒介，则必须采用分频或分时的办法。

信息的传输系统和交换系统组成完整的通信系统，直至构成复杂的通信网络。

1.2编码信道模型

1、调制信道的模型

在通信中，我们所关心的是已调信号经过信道后的结果，而不关心调制信道包括了什么样的转换器，也不管选用了什么样的传输媒质，以及发生了怎样的传输过程。

也就是说，只关心调制信道的输入与输出。

因此，可以用一个二端对网络表示调制信道。

这个二端对网络包括了发，收转换器及传输媒质，然而，它具有什么性质呢？

应注意，它相当于一个线性时变网络，如图2所示。

图1.2调制信道模型

其输入与输出的关系：

公式1.1

式中：

n（t）是信道内噪声，加性干扰。

k（t）是乘性干扰（与ei（t）呈现非线性关系）。

也可用多端对网络表示调制信道，如图3所示。

图1.3调制信道模型

恒参信道的定义：

如果k（t）不随时间t变化或基本不变化,则称恒参信道;

随参信道的定义：

如果k（t）是随机快变化的,则称信道为随参信道。

2、编码信道的模型

由于编码信道传输的是编码后的数字信号，所以我们关心的是数字信号经信道传输后的差错情况，即误码特性，所以编码信道的模型用数字转移概率来表示。

1.无记忆信道:

（信道内只存在起伏噪声）

特点：

任意一个码元的差错与前后码元的差错不发生任何依赖关系。

对于二进制码，模型如图4所示。

图1.4二进制编码信道模型

当P（1/0）＝P（0/1）＝1/2时，信道称为二元对称信道（BSC）。

2.有记忆信道:

（信道内除起伏噪声外,还存在衰落效应等）。

特点：

信号的传输与前后码元有依赖关系,需用马尔科夫链描述。

1.3信道编码概述

数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。

所以通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中误码的发生。

误码的处理技术有纠错、交织、线性内插等。

信道编码理论是指通过信道编码器和译码器实现的用于提高信道可靠性的理论和方法，是信息论的内容之一。

提高数据传输效率，降低误码率是信道编码的任务。

信道编码的本质是增加通信的可靠性。

但信道编码会使有用的信息数据传输减少，信道编码的过程是在源数据码流中加插一些码元，从而达到在接收端进行判错和纠错的目的，这就是我们常常说的开销。

这就好象我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000各玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。

同样，在带宽固定的信道中，总的传送码率也是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。

将有用比特数除以总比特数就等于编码效率了，不同的编码方式，其编码效率有所不同。

例如，数字电视中常用的纠错编码，通常采用两次附加纠错码的前向纠错（FEC）编码。

前向纠错码（FEC）的码字是具有一定纠错能力的码型，它在接收端解码后，不仅可以发现错误，而且能够判断错误码元所在的位置，并自动纠错。

这种纠错码信息不需要储存，不需要反馈，实时性好。

所以在广播系统（单向传输系统）都采用这种信道编码方式。

信道编码大致分为两类：

①信道编码定理，从理论上解决理想编码器、译码器的存在性问题，也就是解决信道能传送的最大信息率的可能性和超过这个最大值时的传输问题。

②构造性的编码方法以及这些方法能达到的性能界限。

一方面，无线信道的恶劣性使接受信号展现出非常差的错误率，迫使译码器在非常低的信噪比下工作。

另一方面，“频带”是无线通信系统宝贵而紧张的资源，尤其是在用户密集的闹市区和室内通信系统中。

为此，对编译码器的设计提出了很高的要求，驱使译码要充分用到所以已知的信号特点；而且，会占用带宽信息的“冗余”必须谨慎使用。

与此同时，集成电路技术的快速发展也使得信道编译码器四要素，即系统性能、宽带资源、传输约束条件和实现复杂度可以再更高层次上获得平衡，这促使了信道编译码技术应用于民用数字通信系统中，尤其是无线通信系统中。

第2章线性分组码

2.1线性分组码的基本概念

通信的根本任务是远距离传递信息,因而如何准确地传输数字信息是数字通信的一个重要组成部分。

而线性码具有纠错能力,目前已广泛用于各种通信系统和计算机系统中。

线性分组码（n，k）中许用码字（组）为2k个。

定义线性分组码的加法为模2和，乘法为二进制乘法。

即1+1=0、1+0=1、0+1=1、0+0=0；1×1=1、1×0=0、0×0=0、0×1=0。

且码字

与码字

的运算在各个相应比特位上符合上述二进制加法运算规则。

线性分组码具有如下性质（n，k）的性质：

1、封闭性。

任意两个码组的和还是许用的码组。

2、码的最小距离等于非零码的最小码重。

对于码组长度为n、信息码元为k位、监督码元为r＝n－k位的分组码，常记作（n，k）码，如果满足2r－1≥n，则有可能构造出纠正一位或一位以上错误的线性码。

一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。

所以，选择码距要取决于特定系统的参数。

线性码具有很多优点。

首先，线性码比非线性码更容易编码和译码。

其次，线性码传送信息更快。

而且码的所有码字可由它的基底表示，线性码的最小距离和它的最小重量相等。

2.2线性码的编码和译码

下面的图5叙述的是通信系统的一个基本模式，它表示了信道编码、译码的基本流程。

图2.1信道编译码基本流程

信息源的信息m1m2…mk编码为码字c1c2…cn,通过可能受到干扰的信道传送,这时收到的码字可能不是发送的码字,译码器将决定并尽可能纠正出现的错误,最后终端收到理想的结果。

2.2.1线性码的编码

在通信中信息一般是用一串长度固定的符号序列来表示的。

编码就是把字符（letter）转变成数码。

设长度为n,空间维数k的线性码,有生成矩阵G,则

xG=x1g1+x2g2+…xngn,

其中G=

且

例设C是长度5,空间维数3的线性码,其生成矩阵为

设下列码字各表示一个字母000100010001110101011111

ASTYEBHF将信息“SAFETY”编码为

S　（100）G=10110

A　（000）G=00000

F　（111）G=11000

E　（110）G=11101

T　（010）G=01011

Y　（001）G=00101

于是所得的码为

101100000011000111010101100101。

2.2.2　线性码的译码

假设码字x=x1x2…xn是沿着信道传送的码字,假如收到的字是y=y1y2…yn。

我们定义误差为e=y-x=e1e2…en。

这时编码器必须决定这里的y就是信源集发送的码字x。

该过程在线性码的译码过程中，将完成如何把出现的误差化为零,或者说如何把码字y纠正为x。

如图6所示。

图2.2　线性码通信模型

例设C为一个[4,2]-code,其生成矩阵为

事实上码C是线性码,于是可以找出它的基底就是{1011,0101}因此,易知码C为C={0000,1011,0101,1110}。

下面可以求码C的陪集a+C,即

　　→0000　1011　0101　1110

1000　0011　1101　0110

0100　1111　0001　1010

0010　1001　0111　1100

不难看出,第一行就是码C,第一列的选择是具有最小重量码字，称之为陪集首（cosetleader）。

假设发送的信息为10，编码为x=1011,而通过信道传送接收的是y=1111,处在上面矩阵的第三行,于是译码器决定出现的错误是0100，与y具有相同的行,此时将收到y的被译码为x=y-e=1111-0100=1011,而它处在与y相同例的第一个元素。

这个就是发送的信息,于是终端收到了理想的结果。

因此,在线性码的译码过程中需要算出码C的陪集a+C,通常选0为码C的陪集首（cosetleader）。

0+C作为上面表格的第一行,收到的码字从上面的表中查出所处的位置。

2.3Hamming（汉明）码

当计算机存储或移动数据时，可能会产生数据位错误，这时可以利用汉明码来检测并纠错，简单的说，汉明码是一个错误校验码码集，由Bell实验室的R.W.Hamming发明，因此定名为汉明码。

以典型的4位数据编码为例，汉明码将加入3个校验码，从而使实际传输的数据位达到7个（位），如表1。

表14位数据编码

数据位

1

2

3

4

5

6

7

代码

P1

P2

D8

P3

D4

D2

D1

说明

第1个汉明码

第2个汉明码

第1个数据码

第3个汉明码

第2个数据码

第3个数据码

第4个数据码

注：

Dx中的x是2的整数幂结果，多少幂取决于码位，D1是0次幂，D8是3次幂。

现以数据码1101为例，阐述汉明码的编码原理。

此时D8=1、D4=1、D2=0、D1=1。

在P1编码时，先将D8、D4、D1的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1。

D8+D2+D1=2，为偶数，那么P2值为0。

D4+D2+D1=2，为偶数，P3值为0。

这样参照上文的位置表，汉明码处理的结果就是1010101。

在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码。

它们的对应关系如表2所示。

表2对应关系

汉明码

编码用的数据码

P1

D8、D4、D1

P2

D8、D2、D1

P3

D4、D2、D1

从编码形式上，可以发现汉明码是一种校验很严谨的编码方式。

在这个例子中，通过对4个数据位的3个位的3次组合检测，来达到具体码位的校验与修正目的。

在校验时，则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1），则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算，来确定具体是哪个位出了问题。

还是刚才的1101的例子，正确的编码应该是1010101，如果第三个数据位在传输途中因干扰而变成了1，就成了1010111。

检测时，P1+D8+D4+D1的结果是偶数4，第一位纠错代码为0，正确。

P1+D8+D2+D1的结果是奇数3，第二位纠错代码为1，有错误。

P3+D4+D2+D1的结果是奇数3，第三位纠错代码代码为1，有错误。

那么具体是哪个位有错误呢？

三个纠错代码从高到低排列为二进制编码110，换算成十进制就是6，也就是说第6位数据错了，而数据第三位在汉明码编码后的位置正好是第6位。

那么汉明码的数量与数据位的数量之间有何比例呢？

上面的例子中数据位是4位，加上3位汉明码是7位，而2的3次幂是8。

这其中就存在一个规律，即2P≥P+D+1，其中P代表汉明码的个数，D代表数据位的个数，比如4位数据，加上1就是5，而能大于5的2的幂数就是3（23=8，22=4）。

这样，我们就能算出任何数据位时所需要的汉明码位数：

7位数据时需要4位汉明码（24＞4+7+1），64位数据时就需要7位汉明码（27＞64+7+1），可以依此推算。

另外，汉明码加插的位置也是有规律的。

以四位数据为例，第一个是汉明码是第一位，第二个是第二位，第三个是第四位，1、2、4都是2的整数幂结果，而这个幂次数是从0开始的整数。

这样可以推断出来，汉明码的插入位置为1（20）、2（21）、4（22）、8（23）、16（24）、32（25）……。

第3章Hamming码的编程实现

3.1程序流程图

主程序一开始就有欢迎界面主要显示用户信息及编码信息，并对用户显示出了输入提示性语句，可以先进行编码然后译码、纠错和退出三个步骤，当用户按要求输入信息码后程序按一定的规则给出相应的编码；当用户按要求输入信息码后程序按一定的规则给出相应的纠错码，并提示出错的位数，整个主程序的流程如下：

图3.1主程序流程图

3.2VC++6.0开发环境

C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。

它支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。

严格的来说VC++不是门语言，虽然它和C++之间有密切的关系,如果形象点比喻的话，可以C++看作为一种”工业标准”，而VC++则是某种操作系统平台下的”厂商标准”,而”厂商标准”是在遵循”工业标准”的前提下扩展而来的。

VC++是微软公司开发的一个IDE（集成开发环境）,换句话说,就是使用c++的一个开发平台，是Windows平台上的C++编程环境。

VisualC++6.0是微软公司推出的开发Win32应用程序（Windows98/2000/XP）的、面向对象的可视化集成工具。

它的最大优点就是提供了功能强大的MFC类库，MFC是一个很大的C++类层次结构，其中封装了大量的类及其函数，很多Windows程序所共有的标准内容可以由MFC的类来提供，MFC类为这些内容提供了用户接口的标准实现方法，程序员所要做的就是通过预定义的接口把具体应用程序特有的东西填入这个轮廓，这将简化编程工作，大大的减少程序员编写的代码数量，使编程工作变得更加轻松容易。

VisualC++6.0开发环境如图8所示。

图3.2VisualC++6.0开发环境

从主体上看VC++6.0可以分为三大部分DeveloperStudio、MFC、PlatformSDK。

这是一个集成开发环境，我们日常工作的99%都是在它上面完成的。

3.3Hamming码编译码器的设计

汉明码编码可遵循以下四个步骤：

（1）由信息位数根据汉明不等式确定校验位数；

（2）确定校验码位置；

　　（3）确定校验码的值；

（4）求出汉明码；

汉明码译码（纠错）可遵循以下规则：

在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1）则说明当前汉明码所对应的数据位中有错误，此时再通过其他汉明码各自的运算的二进制按从打到小的顺序排列其计算所得的十进制数来确定具体是哪个位出了问题。

汉明码编码与译码-07250111吉小平.cpp部分代码如下：

{

inti,n,k=2;

inth[20];

for（i=0;i<20;i++）h[i]=0;

cout<<"请输入要转换的有效位的位数（n）:

"<

cin>>n;

while（pow（2,k）

cout<<"请输入要转换的有效码字（每输入一位按一次回车其输入顺序从低位位到高位）:

"<

for（i=1;i<=n+k;i++）{

if（i!

=1&&i!

=2&&i!

=4&&i!

=8）cin>>h[i];

}

h[1]=（h[3]+h[5]+h[7]+h[9]+h[11]+h[13]+h[15]）%2;

h[2]=（h[3]+h[6]+h[7]+h[10]+h[11]+h[14]+h[15]）%2;

h[4]=（h[5]+h[6]+h[7]+h[12]+h[13]+h[14]+h[15]）%2;

h[8]=（h[9]+h[10]+h[11]+h[12]+h[13]+h[14]+h[15]）%2;

for（i=1;i<=n+k;i++）cout<

}

intjiaoyan（inta[],intn）

{

inti,p1,p2,p4,p8,m;inth[20];

for（i=0;i

for（i=n+1;i<20;i++）h[i]=0;

if（n==3）{

//k=2;

p1=（h[1]+h[3]）%2;

p2=（h[2]+h[3]）%2;

m=2*p2+p1;

returnm;

}

if（n>=5&&n<=7）{

//k=3;

p1=（h[1]+h[3]+h[5]+h[7]）%2;

p2=（h[2]+h[3]+h[6]+h[7]）%2;

p4=（h[4]+h[5]+h[6]+h[7]）%2;

m=4*p4+2*p2+p1;

returnm;

}

if（n>=9&&n<=15）{

//k=4;

p1=（h[1]+h[3]+h[5]+h[7]+h[9]+h[11]+h[13]+h[15]）%2;

p2=（h[2]+h[3]+h[6]+h[7]+h[10]+h[11]+h[14]+h[15]）%2;

p4=（h[4]+h[5]+h[6]+h[7]+h[12]+h[13]+h[14]+h[15]）%2;

p8=（h[8]+h[9]+h[10]+h[11]+h[12]+h[13]+h[14]+h[15]）%2;

m=8*p8+4*p4+2*p2+p1;

returnm;

}

else{

cout<<"!

!

!

!

查错错误!

!

!

!

"<

return-1;

}

}

3.4编译结果

编译结果如图9所示。

图3.3编译结果

结计总结

通过对线性分组码中的Hamming码的编译码编程实现，了解到线性分组码的构成方式是把信息序列中加入汉明码序列使原有的信息码变成被处理过的编码，并由这k个码元按一定规则产生r个校验位，组成长度为n=k+r的码字，用（n，k）表示。

信息码元与校验位之间为线性关系。

并且知道了线性分组码中的Hamming码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的.

对于码组长度为n、信息码元为k位、监督码元为r＝n－k位的分组码，如果满足k+r+1

2r，则有可能构造出纠正一位和错误的线性码。

就像本设计的（7，3）分组码的（n，k）中，n=7，k=3，r≥4能纠正一位误码，检测到两位误码。

线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术之一。

参考文献

[1]冯桂林其伟陈东华编著,《信息论与编码技术》.清华大学出版社

[2]王琳徐位凯编著,《高效信道编译码技术及其应用》.人民邮电出版社

[3]刘振安等编著，《C++程序设计》.机械工业出版社

[4]（英）PeterSweeney著，俞越张丹译，《差错控制编码》.清华大学出版社

[5]宋祖顺.现代通信原理.电子工业出版社，2001，2

[6]黄新亚，米央等.信息编码技术及其应用大全.电子工业出版社，1994，8

[7]孙丽华。

信息论与纠错编码。

电子工业出版社，2005，3

[8]潘新民.计算机通信技术.电子工业出版社，2003，7

[9]吴玲达，李国辉，杨冰等.计算机通信原理与技术.国防科技大学出版社，2003，3

[10]曹志刚，钱压生。

现代通信原理.清华大学出版社，1992

[11]樊昌兴.通信原理.国防工业出版社，1999，10

附录

线形分组