数字数据通信的错误检测与修正

在数字数据通信中,由发送器发送的数据信号祯(Frame)在经由网络传到接收器后,由于多种原因可能导致错误位(bit errors)的出现,因此必须由接收器采取一定的措施探测出所有的错误位,并进而采取一定的措施予以修正。

一、错误检测的基本原理(Principle of Error Check)
  发送器向所发送的数据信号祯添加错误检验码(Check Bits),并取该错误检测码作为该被传输数据信号的函数;接收器根据该函数的定义进行同样的计算,然后将两个结果进行比较:如果结果相同,则认为无错误位;否则认为该数据祯存在有错误位。
一般说来,错误检测可能出现三种结果:
  1. 在所传输的数据祯中未探测到,也不存在错误位
  2. 所传输的数据祯中有一个或多个被探测到的错误位,但不存在未探测到的错误位
  3. 被传输的数据祯中有一个或多个没有被探测到的错误位。
  显然我们希望尽可能好地选择该检测函数,使检测结果可靠,即:所有的错误最好都能被检测出来;如检测出现无错结果,则应不再存在任何未被检测出来的错误。
  实际采用的错误检测方法主要有两类:奇偶校验(Parity)和CRC循环冗余校验(Cyclic Redundancy Check)。

二、奇偶校验(Parity)
1.单向奇偶校验
  单向奇偶校验(Row Parity)由于一次只采用单个校验位,因此又称为单个位奇偶校验(Single Bit Parity)。发送器在数据祯每个字符的信号位后添一个奇偶校验位,接收器对该奇偶校验位进行检查。典型的例子是面向ASCII码的数据信号祯的传输,由于ASCII码是七位码,因此用第八个位码作为奇偶校验位。
单向奇偶校验又分为奇校验(Odd Parity)和偶校验(Even Parity),发送器通过校验位对所传输信号值的校验方法如下:奇校验保证所传输每个字符的8个位中1的总数为奇数;偶校验则保证每个字符的8个位中1的总数为偶数。
  显然,如果被传输字符的7个信号位中同时有奇数个(例如1、3、5、7)位出现错误,均可以被检测出来;但如果同时有偶数个(例如2、4、6)位出现错误,单向奇偶校验是检查不出来的。
  一般在同步传输方式中常采用奇校验,而在异步传输方式中常采用偶校验。

2.双向奇偶校验
  为了提高奇偶校验的检错能力,可采用双向奇偶校验(Row and Column Parity),也可称为双向冗余校验(Vertical and Longitudinal Redundancy Checks)。

三、CRC循环冗余校验(Cyclic Redundancy Check)
1.CRC循环冗余校验的基本原理
  发送器和接收器约定选择同一个由n+1个位组成的二进制位列P作为校验列,发送器在数据祯的K个位信号后添加n个位(n < K)组成的FCS祯检验列(Frame Check Sequence),以保证新组成的全部信号列值可以被预定的校验二进制位列P的值对二取模整除;接收器检验所接收到数据信号列值(含有数据信号祯和FCS祯检验列)是否能被校验列P对二取模整除,如果不能,则存在传输错误位。P被称为CRC循环冗余校验列,正确选择P可以提高CRC冗余校验的能力。(注:对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算,即:1 XOR 1=0,0 XOR 0=0,1 XOR 0=1)。可以证明,只要数据祯信号列M和校验列P是确定的,则可以唯一确定FCS祯检验列(也称为CRC冗余检验值)的各个位。
  FCS帧检验列可由下列方法求得:在M后添加n个零后对二取模整除以P所得的余数。
  例如:如要传输的M=7位列为1011101,选定的P校验二进制位列为10101(共有n+1=5位),对应的FCS帧校验列即为用1011101 0000(共有M+n=7+4=11位)对二取模整除以10101后的余数0111(共有n=4位)。因此,发送方应发送的全部数据列为10111010111。接收方将收到的11位数据对二取模整除以P校验二进制位列10101,如余数非0,则认为有传输错误位。
2.CRC循环冗余校验标准多项式P(X)
  为了表示方便,实用时发送器和接收器共同约定选择的校验二进制位列P常被表示为具有二进制系数(1或0)的CRC标准校验多项式P(X)。
  (1)CRC循环冗余校验常用的标准多项式P(X)
  常用的CRC循环冗余校验标准多项式如下:
  CRC(16位) = X^16+X^15+X^2+1
  CRC(CCITT) = X^16+X^12+X^5+1
  CRC(32位) =X^32+X^26+X^23+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1
  以CRC(16位)多项式为例,其对应校验二进制位列为1 1000 0000 0000 0101。
  注意:这儿列出的标准校验多项式P(X)都含有(X+1)的多项式因子;各多项式的系数均为二进制数,所涉及的四则运算仍遵循对二取模的运算规则。
  (2)CRC循环冗余校验标准多项式P(X)的检错能力
  CRC循环冗余校验具有比奇偶校验强得多的检错能力。可以证明:它可以检测出所有的单个位错、几乎所有的双个位错、低于P(X)对应二进制校验列位数的所有连续位错、大于或等于P(X)对应二进制校验列位数的绝大多数连续位错。
但是,当传输中发生的错误多项式E(X)能被校验多项式P(X)对二取模整除时,它就不可能被P(X)探测出来,例如当E(X)=P(X)时。

四、错误修正(Error Correction)
  对数据信号祯传输过程中的位错进行修正的方法主要有两种:
  1. 由发送器提供错误修正码,然后由接收器自己修正错误
  2. 在接收器发现接收到的错误祯中有位错误时,通知发送器重新发送数据信号祯。
  前一种方法中的错误修正码需要发送器由被传送数据信号祯计算得到,然后添加到数据祯的后面,其长度几乎等于数据位数,导致效率降低50%,实际采用不多;一般采用后一种较为有效的重发送方法。


数据交换技术(Data Switching Technology)

  在数据通信线路中,最简单的形式是在由某种传输介质直接连接的两台设备之间进行通信。但在长距离通信中,从源站发出的数据一般还需要经过网络中一个或多个用作交换设备的中间结点,由相应结点的交换设备把数据从一个结点传送到另一个结点,直至到达目的站。通常我们将交换网络中所有通信的发送方与接收方的主机均简称为站,而将通信交换设备简称为结点。这些结点以不规则的网状结构用传输线路互相连接起来,而每个站点都连接到某个结点上。
  在交换网络中,站点之间需要通过有关结点之间的数据交换才能实现数据通信,基本的交换技术有两类:电路交换与存储转发,存储转发又可以分为报文交换和分组交换,分组交换则可分为面向连接的虚电路传输和无连接的数据报传输。目前,最具有发展前景的是高速分组交换技术。

posted on 2007-01-03 11:26 Timothy 阅读(867) 评论(0)  编辑  收藏 所属分类: 经典概念


只有注册用户登录后才能发表评论。


网站导航:
 
<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

公告

语义Web : 网络就是计算机,软件就是服务!

常用链接

留言簿(4)

随笔档案(20)

文章分类(25)

文章档案(25)

新闻分类(4)

新闻档案(4)

相册

收藏夹(27)

个人主页

网络博客

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜