论坛: 系统集成 标题: 差错检测技术 复制本贴地址    
作者: 带脚镣跳舞 [tuzi]    版主   登录
写一些常见的差错检测技术
抛砖引玉

差错的类型
只要有电磁信号从一方流到另一方,就有可能受到不可预见的干扰
如 热干扰 磁场干扰 其他形式的干扰, 这种干扰可以改变信号的形状和时间关系
比如对于2进制的编码 这个改变会导致整个数据包的错误 最后可能会被丢弃 或者重传
单个位的干扰      1被干扰 变成了0 
多各位的干扰      多个比特位被干扰 

单个位的干扰在串行传输中很少见
设想发送以1Mb/s发送数据 每个位持续的时间为1/1000000秒  而噪声的持续时间远远超过了这个时间
如果我们以并行传输方式发送数据,可能就会出现单个差错
example:8条线同时发送8比特 其中一条线有噪声 那就影响到一个位置
CPU和存储器之间就是这样传输的

突发错误:突发错误不一定是连续的位 突发长度是从第一个受损伤的位到最后一个受损伤的位的长度  可能中间的某些位并没有收到损伤

下面就是要对错误进行检测
如果检测不出来 那无疑 internet上的错误的数据包会层出不穷的

1 我们接受报文  慢慢编码 只到读不懂为止 这样我们知道了 此报文有问题
估计这个方法 SB才会用
2 发送两份报文 两份比较
不过从理论上来说 两份都有可能发生错误 到底相信哪份  再发第三份报文?
这也是SB才用的

3 目前数据通信的使用较多的就是冗余
VRC 垂直冗余校验 也叫做奇偶校验
LRC 纵向冗余校验
CRC 循环冗余校验
checksum  校验和
前3种主要在物理层和数据链路层使用
最后一种 即校验和使用在网络层

下面说说它们是怎么校验的
VRC
这是最常用也是最便宜的校验方法,被称为奇偶位的冗余位添加在每一个数据单元上,使得该数据单元中的1的总数(包括这个奇偶位在内)是偶数
如 发送一个数据单元 1100001 [ASCII a(97)]
通过奇偶校验器 算出1的个数为3 再加一个1就是4个1
发送的数据单元就是11100001 接受方使用校验器 算出4个1  通过
如果是5个1 那就说明有问题了 拒绝接受

注意 本来是4个1  要是中间突发错误 结果1变成了0 0变成了1 这样就是00011110
这样是查不出来的  所以这个方法实在是有点问题

LRC
位块被组织成一个表(有多行和多列)
原始数据  11100111  11011101  00111001  10101001
现在组织成行和列
                      11100111
                      11011101
                      00111001
                      10101001
                      ----------
          LRC-------  10101010
一位对一位 不进位 把上面4行相加
1的个数为偶数 下面的就是O  个数为奇数 下面的就是1  得出了10101010
但是有种差错模式是不能被检测出来的
一个数据单元中有2位受伤 改变了 同样在另一个数据单元同样的位置上也有2位受到损伤
这样 最后的LRC结果是一样的 故不能检测到错误


CRC 和checksum待续

地主 发表时间: 05-09-20 18:10

回复: 天枫 [lqfrla]   论坛用户   登录
小样!!发威了

B1层 发表时间: 05-09-21 08:45

回复: 带脚镣跳舞 [tuzi]   版主   登录
就是写一些大家平时不太好找的文章
没什么技术含量
扫扫盲而已


B2层 发表时间: 05-09-21 16:35

回复: 天枫 [lqfrla]   论坛用户   登录
这些东西一般人也用不着

B3层 发表时间: 05-09-21 17:44

回复: 蓝色 [bluecolor]   论坛用户   登录
这种技术具体用在什么地方,或什么时候才派上用场呢
跳舞你只说检测,我想大多朋友更想知道解决

能不能具体谈谈

支持!

借你的宝地回一下
CRC用于2层frame 看看以太网的帧结构
checksum用于TCP/IP层  比如IP ICMP TCP UDP等首部的校验和

[此贴被 带脚镣跳舞(tuzi) 在 09月24日10时31分 编辑过]

B4层 发表时间: 05-09-22 11:51

回复: 带脚镣跳舞 [tuzi]   版主   登录
哎 这下郁闷了CRC的算法在BBS里 没法大出来
倒哟
让偶想想办法


B5层 发表时间: 05-09-22 23:41

回复: 带脚镣跳舞 [tuzi]   版主   登录
CRC加法运算规则:0+0=0

0+1=1

1+0=1

1+1=0 (注意:没有进位)

CRC减法运算规则:

0-0=0

0-1=1

1-0=1

1-1=0



CRC乘法运算规则:

0*0=0

0*1=0

1*0=0

1*1=1

2进制除法

1/1=0
0/1=1
1/0=1
0/0=0

不过我们用的CRC是2进制除法
CRC首先要确定一个除数 然后在数据单元后面加上比除数个数少1个O
如除数是1101 数据单元是100100 那就在数据单元后面加3个0  现在变成100100000 

以下协议,有的是由ITU-T组织维护,有的是由IEEE
CRC-12对应的除数是13
CRC-16对应的除数是17
CRC-32对应的除数是33(目前使用的。)
CRC-32就是目前使用的
现在以CRC-12做一个列子
除数是13 2进制是1101
现在要测试的数据单元 100100

从左边开始算第一位是1  所以首先上1  因为不能上0 和2 (2进制中最大就是1)
如果某一次算到第一位是0就要上0  只到所有的数被使用过了 CRC算法结束
每次从下一位借一个使用
首先是1  这样就变成了 
-------100100000(后面3个0是添加的)
-------1101
--------------------
1-------1000
--------1101
---------------------
1--------1010
---------1101
---------------------
1---------1110
----------1101
-----------------------
0----------0110
-----------0000
----------------------
1-----------1100
------------1101
----------------------
-------------001(CRC)
1 001就是得到的CRC 
2 CRC 可能全是O     
把OO1替换上面加的000 这样数据就变成了100100001以前是100100000
就样就OK了
得到的数据就可以发送出去了
接受端把这个数(100100001)和除数(1101)相除 得到余数是0就接受 否则就丢弃

加线的目的是让数字定位正确
左边的是商 不过我们不关心商

[此贴被 带脚镣跳舞(tuzi) 在 09月24日10时02分 编辑过]

B6层 发表时间: 05-09-24 09:50

回复: 带脚镣跳舞 [tuzi]   版主   登录
校验和 checksum
在大多数TCP/IP中采取的校验方法就是校验和
在发送端  把分组分为K段 每段N位长 N通常为16
把这些相加 得到的结果取反码  就就是校验和 然后加在数据中发出去
现在举个列子 对IP进行校验和
首先看下IP数据包的格式
如 IP
4(VER)5(HLEN)0(DS)28(TOTAL LENGTH)
4是4位 5也是4位 0是8位  28 (16位)
第一行是这样的
01000101 00000000 ( 4,5,0)
00000000 00011100  (28)
知道怎么排序的吧  全部写成2进制的 由版本开始 16位1行 4是4位 5也是4位 0是8位 所以一共16位  排第一行
发送端校验和没有 全部是0  结果出来后 替换0
1001 1001 0001 0010
0000 1000 0110 1001
1010 1011 0000 0010
0000 1110 0000 1010
0000 0000 0001 0001
0000 0000 0000 1111
0000 0100 0011 1111
0000 0000 0000 1101
0000 0000 0000 1111
0000 0000 0000 0000
0101 0100 0100 0101
0101 0011 0101 0100
0100 1001 0100 1110
0100 0111 0000 0000
---------------------
1001 0110 1110 1001

我们加右边第1列的时候 得到是7(111) 这样 最后一个就是1 把其余的进到第2列和第3列 
第2列要加上1 第3列也要加上1  就这样慢慢一层一层加上去
得到了结果1001 0110 1110 1001
在最右边的第16列加完后 还有2个1没有列可以进了 (因为没有第17列)
所以1001 0110 1110 1001 只能说是部分和(partial sum)
还必须和两个1相加  在第1列相加
1001 0110 1110 1001
                  1
                  1
最后达到和是1001 0110 1110 1011取反码0110 1001 0001 0100
最终反码过后的值就是校验和checksum 替换本来全0的校验和

接受端 就不说了 应该可以明白的


B7层 发表时间: 05-09-24 10:28

回复: 天枫 [lqfrla]   论坛用户   登录
不懂

B8层 发表时间: 05-09-24 22:50

回复: K9999 [yandsd]   论坛用户   登录
偶也不懂

B9层 发表时间: 05-09-25 17:41

论坛: 系统集成

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号