未来索引
开启左侧

从神九用到CAN总线讲起(7)学会检验

[复制链接]
邢远 发表于 2013-7-28 23:23:05 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
国家兴亡匹夫有责,从神九用到CAN总线讲起(7)学会检验
关于第一种错帧漏检的原因,可疑帧重构方法可以参考我以前的文章:杨福宇,“CAN协议的错帧漏检率改进“,《单片机与嵌入式系统应用》,2011,  No.9,p.8-11,详细的英文版见Fuyu YANG, On Residual Error Probability of CAN Protocol, http://www.frogenyozurt.com/wp-c ... or-Probabilioty.pdf
        
没人会否定细节决定成败这一原理,错帧漏检率就是细节,完全是数值决定的。如果算错了,岂不是搞了冤案吗。这是支持本系列博文观点的基础,所以我将这部分公布在这里,用三篇文章:(7)、(8)、(9)讨论CAN的错帧漏检问题。这里是我最新的版本。第一篇是在原有分析的基础上用的新方法论证,给出了第一种情况下的错帧漏检率。好处是你不用计算机也能手算来核实,可以用一天、甚至更少的时间,证明Bosch的数据是错的;第二篇文章是给出第二种错帧漏检原因下的错帧漏检率,它也不需要你花很多时间读懂它、核算它,给出的错帧漏检率也证明Bosch的数据是错的,因为数值虽小,仅此一项也已超过了Bosch的数据;第三篇是探讨可疑数据流(见后面定义)发生在CRC部分时的情况,计算得到的错帧漏检率也相当大,仅此一项也已超过了Bosch的数据。
        

这非常专门,感兴趣的人未必很多,很多杂志会因为读者面窄、版面字数限制等而*毙了它。但是你如果想驳倒我在本系列博文中表达的观点,你至少要指出我的计算有错误,所谓谁主张谁举证。
        
技术的发展也是越来越专门化,就CAN错帧漏检率的事进行研究,全世界也只有数人而已,如果这些人(包括我自己)犯了错,岂不误事?公开之后人人可以复核,便于纠正。特别是我的方法不需要大量机时,复核的条件宽松多了。
        
有人对专门的议题不太感冒,“我又不是干这一行的”。有些人会认为看起来非常纠结,我需不需要花力气读完它?
        
不错,每个人精力有限,不过常识性的东西总不会拒绝的。好比你买了台电视机,开不出来,你会查查电源插了没有,插座好不好,入户总保险烧了没有。当别人说这台电视机有问题,你总要先用常识判断一下。现在我说CAN有错帧漏检率高的问题,你最好也判断一下,我这里没有高深的理论,而仅是技巧,一层窗户纸,捅破了就没什么稀奇。如果我说得对,这就成为你的另一种常识,用到别的需要判断的地方。
        
在以前的文章中我没有给出具体数值的推导过程,这次我采用了更简化的方法,完全手算,证明我的数据是可靠的。
        
0. CAN规定,发送节点在连续5个相同位后自动添加一个反向的值,接收节点在收到连续5个相同位时就把下一个反向的值删去。

        
在一个连续5位的窗口中,由于出现传送位错,会只有一边执行填充位规则,见图0。然后收发二边的位流就有了相位移,会造成许多位错。如果第二个传送错使相位移回来,后面的位流就不再受影响。相移造成的多位错是CAN的CRC失效的原因之一。  
1509476ilfu8yklduzelkl.jpg
图0 CAN填充规则可能造成位流的相移
        
1.可疑数据流的结尾部分存在一个6位的窗口,在这里有一个位错,使填充规则只有一方执行,执行的结果是不再有相位移。图1是发送节点有填充位而接收节点无,图2是发送节点无填充位而接收节点有。

         
150948z35tyiat6r671itu.jpg
图1 第2个传送错造成填充位误读为信息位的5种漏检错序列尾部形式

150948hfz7j1q59hz16z67.jpg
图2 第2个传送错造成信息位误读为填充位的5种漏检错序列尾部形式
        
要知道的是:因为第一个1是用于开始一个5b窗口的“分界符”的作用,处于第2位的0也可能是填充进去的0,所以尾部的形式不止这5种,详见英文稿。其他尾部型式对错帧漏检率的贡献比较小,几乎可忽略不计,所以本文就仅讨论这5种尾部型式。
        
2.我的创新方法得以成功的基本条件是从误差多项式Ec,t重构出对应的Ut,这里下标t表示尾部。
        
Ut是一个多项式,由Ut*G可得到Ec。只要有Ut,并在它的基础上添加x的多项式变成U,就可以由U生成Ec,由Ec生成可疑数据流Tx。这样的Tx在特定位置发生位错时就会生成Ec,因为Ec是G的倍数,就会错帧漏检。

所以由Ec求Ut是关键。做CRC检验的除法时将数据字写为D=(dm dm-1…),生成多项式写为G=(gn gn-1…),商写为Q=(qk qk-1 …)。则有:


            qk=dm*gn
            qk-1=dm-1*gn+dm*gn-1

        
而求对应的尾部有Ec,t= (e5 e4 e3 e2 e1 e0);Ut= (u5 u4 u3 u2 u1 u0).

        e0=g0*u0
        e1=g1*u0+g0*u1

        
所以存在一种逆序的类似性,可用逆序做除法。以Ec,t= (0 0 0 0 0 1)为例,CAN的G的逆序写法为(1001100110100011),除法过程见图3。由于感兴趣的仅是Ec的最后6位,所以除法只要把该6位除尽就可。这种逆序求法可以由CRC反求出在某位置的数据是什么样的,这种方法将来还要用到。如果你把这张图倒过来看(下面的转到上面,左面的转到右面),就可以看到它就是你平时做CRC除法的过程。所以CRC与DATA之间的关系是相互可以求取的,只是你没有注意而已。
         
          150948q453ii94z3vv3ibj.jpg
图3 由CRC逆序求DATA的方法
        
所以只要将Ec,t和G以逆序写法就可以求得Ut的逆序写法。Ut的阶次在5之内,例如对应出错的5个位置有x4+x3+1等(如表1)。

表1
150950kvjf0ad7jn74nk88.jpg

3.可逆数据流的头部也是一个6位的窗口,只有一方执行填充位规则。它的误差多项式与尾部的形式类似(图4)
        
1509503uu7itv3cz59oce1.jpg
图4 头部出错形态

U的头部用多项式来表示如Uh=(uk uk-1 uk-2 uk-3 uk-4),这里只取5项,因为它与G相乘后形成Ec的头部5项,已经足够判断容许的第一个位错发生的位置。因为Ec的第一个1代表第一个位错发生的位置,而第二个1最早发生在可疑Tx的第7位。例如,Uh=(1 1 1 1 1)时,Ec=1000001...,第1个1最早只能在Sh=2。Uh=(1 1 1 1 0)时,Ec=10001...,第2个1最早只能在第7位,所以Sh=3。Uh=(1 1 1 0 *)时,Ec=1001...,第2个1最早只能在第7位,所以Sh=4,此时uk-4的取值已不影响可疑数据流的长度。Uh=(1 1 0 * *)时,Ec=101...,第2个1最早只能在第7位,所以Sh=5,此时uk-3 uk-4的取值已不影响可疑数据流的长度。Uh=(1 0 * * *)时,Ec=11...,第2个1最早只能在第7位,所以Sh=6,此时uk-2uk-3uk-4的取值已不影响可疑数据流的长度。
        
于是可以汇总为表2。这个关系是核查的基础。


表2
150950htqqazawaxge3eap.jpg         

我们知道,Ec的阶次是U的阶次与G的阶次之和,即k+15。Ec的长度是阶次加1,而Ec的最后一位就是可疑数据流的最后一位,所以可疑数据流的长度就是Ec长度加Sh-1,即:

LTx=k+15+Sh                                                    (1)
        
4.由于Ut的系数只到只到x5,就可以从x6开始往上加xk,使Ec不断加长,形成各种漏检实例。

        
当k=6~10时,它与Ut中的项形成的头部就不是简单可确定的,所以我们用表格列出来,对照表2的Uh-Sh关系,以及(1)式,就可以得到添加xk各种组合后的可疑帧长度,以及对应该长度的组合的数目。
        
对表1的5种尾部多项式添加结果如表3~表7,我将表4~7移到注1中,以便愿意深究的朋友复核。一般读者只要看出表3表达的意思即可:在Ut上添加高次项是如何改变U头部类别,从而改变可疑数据流长度L及该长度下可能的可疑数据流数目n的。
        
表3 x4+x3+1

    150954g0nho9of9f0gfs9m.jpg                
        
由这些表可汇总出出现各种可疑数据流的次数,并统计总数如表8
        
表8 在k<=10时各可疑数据流长度出现的总次数

150954731pq311po9930p3.jpg

5.有了U就可以构造出完整的Ec,由Ec就可以构造出整个可疑数据流Tx。
        
例如 U=x6+x4+x3+1,得到Ec=U*G=(1110,1111,0101,1010,0000,01),重构见图5。由Ec可知第一个位错发生在第6位,由Ut=x4+x3+1可知,第二个位错发生在尾部的第一位。在头部的Tx填充位被Rx理解为数据位之后,Rx和Tx就有了相移,所以由Ec7和Rx7就可以决定Tx7=Ec7○+Rx7,然后因为传送中没错,所以Rx8=Tx7,逐位推出,直到第22位,传送中又出第二次错,Rx23=not Tx22,继续无错到第27位,由于Rx方出现填充位删除条件,Tx27被删掉了,Rx与Tx的相移消失,整个可疑数据流就构造完成。


1509547he0n0n7lhd99n5a.jpg
图5 U=x6+x4+x3+1重构出的可疑数据流

这重构出的Tx之所以称为可疑数据流,是因为只有当位错发生在特定位置时(在本例中是第6、22位)才会发生漏检,若不在特定位置,那么产生的Ec就不是生成多项式的倍数,CRC就可以检验出错误,不会漏检。
        
6.可疑数据流Tx处在数据域内的任一段内(图6)。

         
如果可疑数据流Tx流的长度为LTx,那么在可疑数据流Tx以外的帧的其余部分取值(除DLC及格式规定部分外)都是可以任选的。对可疑数据流Tx存在的一段,只有一种与Tx有关的具体数据。这样,与特定位置、特定Tx有关的漏检占所有长度为LTx的各种数据的概率为2-LTx。当Tx在数据域内移动时,因Bit flip位置不同,又构成新的漏错实例,这样的移位会有65-LTx种,头部窗口有100000,011111及填充位规则在发送节点或接收节点处执行共四种,所以对特定Tx(与Ect有关)的漏检概率是:
        
        Pun,L=4*(65-LTx)*2-LTx                                                (2)
        
1509546ks0yowaza306a35.jpg

图6 可疑数据流的位置
        
7.我们根据(2)式以及表8计算k<=10时的漏检概率为:

        
        Pun,L<29=ΣPun,L*n(L)  (L=23~29)
        =2-27*(42*26+41*25*2+40*24*4+39*23*6+38*22*17+37*2*21+36*31)
        =2-27*(2688+2624+2560+1872+2584+1554+1116)
        =2-27*14998=1.11*10-4

        
表8中LTx=30的项的贡献在后面计算,以避免重复。
         
8.对于k>10到容许的最大值时的漏检率贡献以LTx作主线来计算,因为k>10之后Ut的差别已无影响,而Uh的形式起主要作用。这里仍然要用(1)式:

LTx=k+15+Sh。

        
当LTx固定时,不同的Uh=(uk uk-1 uk-2 uk-3 uk-4)就决定不同的Sh,也就决定了k。由表2知道:
        
Uh=11111时Sh=2,k=LTx-17,由k-5到k=6共k-10项可以任意选,用LTx代替k即LTx-27项可以任意选,所以属于这一类的有n1=2(LTx-27)种组合。
        
Uh=11110时Sh=3,k=LTx-18,由k-5到k=6共k-10项可以任意选,即LTx-28项可以任意选,所以属于这一类的有n2=2(LTx-28)种组合。
        
Uh=1110*时Sh=4,k=LTx-19,由k-4到k=6共k-9项可以任意选,即LTx-28项可以任意选,所以属于这一类的有n3=2(LTx-28)种组合。
        
Uh=110**时Sh=5,k=LTx-20,由k-3到k=6共k-8项可以任意选,即LTx-28项可以任意选,所以属于这一类的有n4=2(LTx-28)种组合。
        
Uh=10***时Sh=6,k=LTx-21,由k-2到k=6共k-7项可以任意选,即LTx-28项可以任意选,所以属于这一类的有n5=2(LTx-28)种组合。
        
所以对特定的LTx有nL=n1+n2+n3+n4+n5=3*2(LTx-27)                    (3)

         
种组合。
        
每种LTx的漏检概率还要考虑它在64位数据域内的可移动数目65-LTx、对应LTx长度有一个漏检帧所占的比率2-LTx、5种Ut形式和4种头部形式,于是:

        Pun,L=5*4*(65-LTx)*3*2(LTx-27)*2-LTx=15*(65-LTx)*2-25
        最长的LTx=64,考虑求和直到LTx=30(上节对小于30的已求过了),则有Pun,L=64~30=15*(1+2+...+35)*2-25
        =15*630*2-25=2.81*10-4
        
于是所有不同长度的可疑数据流造成的漏检概率总和是:Pun,L=1.11*10-4+2.81*10-4=3.92*10-4
        
9.位错发生在对LTx特定位置的概率:
        
上述分析是针对位错发生在非填充位时的,所以仅考虑8字节数据的全部帧长就可以了,可算出帧长为107位,二个错分散在107位中的总的组合数是107*106/2=5671种,所以位错发生在特定位置的概率是Pposition=1.76*10-4。
        
由此得到Pun=Pun,L*Pposition=3.92*10-4*1.76*10-4=6.89*10-8。

这个数据并不是漏检的全部(见后面的文章),但是它已经比Bosch声称的4.7*10-11大了1000倍。
        
注1:
表4 x5+x3+1

    150956pwjc7xkz25cikxcp.jpg

表5 x5+x4+1
    150958i5mdlei9azazip5m.jpg
        
表6 x4+x3+x2+1
    150959dpddb22z0td0bpii.jpg
               
表7 x3+x+1
151000k9hh3vnh6zhvz9zk.jpg
  
该会员没有填写今日想说内容.
高级模式
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关注2973

粉丝3237

帖子9934

发布主题
推荐阅读 更多
阅读排行 更多
广告位
!jz_fbzt! !jz_sgzt! !jz_xgzt! 快速回复 !jz_sctz! !jz_fhlb! 搜索

智能技术共享平台 - 未来论

关注服务号

进入小程序

全国服务中心:

运维中心:天津

未来之家:天津 青岛 济南 郑州 石家庄

                商务邮箱:xy@mywll.com

Copyright © 2012-2021 未来派 未来论 (津ICP备16000236号-5)