|
作者：楊福宇 關(guān)于第一種錯(cuò)幀漏檢的原因，可疑幀重構(gòu)方法可以參考我以前的文章：楊福宇,“CAN協(xié)議的錯(cuò)幀漏檢率改進(jìn)“，《單片機(jī)與嵌入式系統(tǒng)應(yīng)用》，2011, No.9，p.8-11，詳細(xì)的英文版見(jiàn)Fuyu YANG, On Residual Error Probability of CAN Protocol, http://www.frogenyozurt.com/wp-c ... or-Probabilioty.pdf。 沒(méi)人會(huì)否定細(xì)節(jié)決定成敗這一原理，錯(cuò)幀漏檢率就是細(xì)節(jié)，完全是數(shù)值決定的。如果算錯(cuò)了，豈不是搞了冤案嗎。這是支持本系列博文觀(guān)點(diǎn)的基礎(chǔ)，所以我將這部分公布在這里，用三篇文章：（7）、（8）、（9）討論CAN的錯(cuò)幀漏檢問(wèn)題。這里是我最新的版本。第一篇是在原有分析的基礎(chǔ)上用的新方法論證，給出了第一種情況下的錯(cuò)幀漏檢率。好處是你不用計(jì)算機(jī)也能手算來(lái)核實(shí)，可以用一天、甚至更少的時(shí)間，證明Bosch的數(shù)據(jù)是錯(cuò)的；第二篇文章是給出第二種錯(cuò)幀漏檢原因下的錯(cuò)幀漏檢率，它也不需要你花很多時(shí)間讀懂它、核算它，給出的錯(cuò)幀漏檢率也證明Bosch的數(shù)據(jù)是錯(cuò)的，因?yàn)閿?shù)值雖小，僅此一項(xiàng)也已超過(guò)了Bosch的數(shù)據(jù)；第三篇是探討可疑數(shù)據(jù)流（見(jiàn)后面定義）發(fā)生在CRC部分時(shí)的情況，計(jì)算得到的錯(cuò)幀漏檢率也相當(dāng)大，僅此一項(xiàng)也已超過(guò)了Bosch的數(shù)據(jù)。 這非常專(zhuān)門(mén)，感興趣的人未必很多，很多雜志會(huì)因?yàn)樽x者面窄、版面字?jǐn)?shù)限制等而*斃了它。但是你如果想駁倒我在本系列博文中表達(dá)的觀(guān)點(diǎn)，你至少要指出我的計(jì)算有錯(cuò)誤，所謂誰(shuí)主張誰(shuí)舉證。 技術(shù)的發(fā)展也是越來(lái)越專(zhuān)門(mén)化，就CAN錯(cuò)幀漏檢率的事進(jìn)行研究，全世界也只有數(shù)人而已，如果這些人（包括我自己）犯了錯(cuò)，豈不誤事？公開(kāi)之后人人可以復(fù)核，便于糾正。特別是我的方法不需要大量機(jī)時(shí)，復(fù)核的條件寬松多了。 有人對(duì)專(zhuān)門(mén)的議題不太感冒，“我又不是干這一行的”。有些人會(huì)認(rèn)為看起來(lái)非常糾結(jié)，我需不需要花力氣讀完它？ 不錯(cuò)，每個(gè)人精力有限，不過(guò)常識(shí)性的東西總不會(huì)拒絕的。好比你買(mǎi)了臺(tái)電視機(jī)，開(kāi)不出來(lái)，你會(huì)查查電源插了沒(méi)有，插座好不好，入戶(hù)總保險(xiǎn)燒了沒(méi)有。當(dāng)別人說(shuō)這臺(tái)電視機(jī)有問(wèn)題，你總要先用常識(shí)判斷一下。現(xiàn)在我說(shuō)CAN有錯(cuò)幀漏檢率高的問(wèn)題，你最好也判斷一下，我這里沒(méi)有高深的理論，而僅是技巧，一層窗戶(hù)紙，捅破了就沒(méi)什么稀奇。如果我說(shuō)得對(duì)，這就成為你的另一種常識(shí)，用到別的需要判斷的地方。 在以前的文章中我沒(méi)有給出具體數(shù)值的推導(dǎo)過(guò)程，這次我采用了更簡(jiǎn)化的方法，完全手算，證明我的數(shù)據(jù)是可靠的。 0. CAN規(guī)定，發(fā)送節(jié)點(diǎn)在連續(xù)5個(gè)相同位后自動(dòng)添加一個(gè)反向的值，接收節(jié)點(diǎn)在收到連續(xù)5個(gè)相同位時(shí)就把下一個(gè)反向的值刪去。 在一個(gè)連續(xù)5位的窗口中，由于出現(xiàn)傳送位錯(cuò)，會(huì)只有一邊執(zhí)行填充位規(guī)則，見(jiàn)圖0。然后收發(fā)二邊的位流就有了相位移，會(huì)造成許多位錯(cuò)。如果第二個(gè)傳送錯(cuò)使相位移回來(lái)，后面的位流就不再受影響。相移造成的多位錯(cuò)是CAN的CRC失效的原因之一。 
圖0 CAN填充規(guī)則可能造成位流的相移 1.可疑數(shù)據(jù)流的結(jié)尾部分存在一個(gè)6位的窗口，在這里有一個(gè)位錯(cuò)，使填充規(guī)則只有一方執(zhí)行，執(zhí)行的結(jié)果是不再有相位移。圖1是發(fā)送節(jié)點(diǎn)有填充位而接收節(jié)點(diǎn)無(wú)，圖2是發(fā)送節(jié)點(diǎn)無(wú)填充位而接收節(jié)點(diǎn)有。
圖1 第2個(gè)傳送錯(cuò)造成填充位誤讀為信息位的5種漏檢錯(cuò)序列尾部形式
圖2 第2個(gè)傳送錯(cuò)造成信息位誤讀為填充位的5種漏檢錯(cuò)序列尾部形式 要知道的是：因?yàn)榈谝粋�(gè)1是用于開(kāi)始一個(gè)5b窗口的“分界符”的作用，處于第2位的0也可能是填充進(jìn)去的0，所以尾部的形式不止這5種，詳見(jiàn)英文稿。其他尾部型式對(duì)錯(cuò)幀漏檢率的貢獻(xiàn)比較小，幾乎可忽略不計(jì)，所以本文就僅討論這5種尾部型式。 2.我的創(chuàng)新方法得以成功的基本條件是從誤差多項(xiàng)式Ec,t重構(gòu)出對(duì)應(yīng)的Ut，這里下標(biāo)t表示尾部。 Ut是一個(gè)多項(xiàng)式，由Ut*G可得到Ec。只要有Ut，并在它的基礎(chǔ)上添加x的多項(xiàng)式變成U，就可以由U生成Ec，由Ec生成可疑數(shù)據(jù)流Tx。這樣的Tx在特定位置發(fā)生位錯(cuò)時(shí)就會(huì)生成Ec，因?yàn)镋c是G的倍數(shù)，就會(huì)錯(cuò)幀漏檢。 所以由Ec求Ut是關(guān)鍵。做CRC檢驗(yàn)的除法時(shí)將數(shù)據(jù)字寫(xiě)為D=(dm dm-1…)，生成多項(xiàng)式寫(xiě)為G=(gn gn-1…)，商寫(xiě)為Q=(qk qk-1 …)。則有： qk=dm*gn qk-1=dm-1*gn+dm*gn-1 而求對(duì)應(yīng)的尾部有Ec,t= (e5 e4 e3 e2 e1 e0);Ut= (u5 u4 u3 u2 u1 u0). e0=g0*u0 e1=g1*u0+g0*u1 所以存在一種逆序的類(lèi)似性，可用逆序做除法。以Ec,t= (0 0 0 0 0 1)為例，CAN的G的逆序?qū)懛椋?001100110100011），除法過(guò)程見(jiàn)圖3。由于感興趣的僅是Ec的最后6位，所以除法只要把該6位除盡就可。這種逆序求法可以由CRC反求出在某位置的數(shù)據(jù)是什么樣的，這種方法將來(lái)還要用到。如果你把這張圖倒過(guò)來(lái)看（下面的轉(zhuǎn)到上面，左面的轉(zhuǎn)到右面），就可以看到它就是你平時(shí)做CRC除法的過(guò)程。所以CRC與DATA之間的關(guān)系是相互可以求取的，只是你沒(méi)有注意而已。
圖3 由CRC逆序求DATA的方法 所以只要將Ec,t和G以逆序?qū)懛ň涂梢郧蟮肬t的逆序?qū)懛āt的階次在5之內(nèi)，例如對(duì)應(yīng)出錯(cuò)的5個(gè)位置有x4+x3+1等（如表1）。 表1
3.可逆數(shù)據(jù)流的頭部也是一個(gè)6位的窗口，只有一方執(zhí)行填充位規(guī)則。它的誤差多項(xiàng)式與尾部的形式類(lèi)似（圖4）
圖4 頭部出錯(cuò)形態(tài) U的頭部用多項(xiàng)式來(lái)表示如Uh=(uk uk-1 uk-2 uk-3 uk-4)，這里只取5項(xiàng)，因?yàn)樗cG相乘后形成Ec的頭部5項(xiàng)，已經(jīng)足夠判斷容許的第一個(gè)位錯(cuò)發(fā)生的位置。因?yàn)镋c的第一個(gè)1代表第一個(gè)位錯(cuò)發(fā)生的位置，而第二個(gè)1最早發(fā)生在可疑Tx的第7位。例如，Uh=(1 1 1 1 1)時(shí)，Ec=1000001...，第1個(gè)1最早只能在Sh=2。Uh=(1 1 1 1 0)時(shí)，Ec=10001...，第2個(gè)1最早只能在第7位，所以Sh=3。Uh=(1 1 1 0 *)時(shí)，Ec=1001...，第2個(gè)1最早只能在第7位，所以Sh=4，此時(shí)uk-4的取值已不影響可疑數(shù)據(jù)流的長(zhǎng)度。Uh=(1 1 0 * *)時(shí)，Ec=101...，第2個(gè)1最早只能在第7位，所以Sh=5，此時(shí)uk-3 uk-4的取值已不影響可疑數(shù)據(jù)流的長(zhǎng)度。Uh=(1 0 * * *)時(shí)，Ec=11...，第2個(gè)1最早只能在第7位，所以Sh=6，此時(shí)uk-2uk-3uk-4的取值已不影響可疑數(shù)據(jù)流的長(zhǎng)度。 于是可以匯總為表2。這個(gè)關(guān)系是核查的基礎(chǔ)。 表2
我們知道，Ec的階次是U的階次與G的階次之和，即k+15。Ec的長(zhǎng)度是階次加1，而Ec的最后一位就是可疑數(shù)據(jù)流的最后一位，所以可疑數(shù)據(jù)流的長(zhǎng)度就是Ec長(zhǎng)度加Sh-1，即： LTx=k+15+Sh (1) 4.由于Ut的系數(shù)只到只到x5，就可以從x6開(kāi)始往上加xk，使Ec不斷加長(zhǎng)，形成各種漏檢實(shí)例。 當(dāng)k=6~10時(shí)，它與Ut中的項(xiàng)形成的頭部就不是簡(jiǎn)單可確定的，所以我們用表格列出來(lái)，對(duì)照表2的Uh-Sh關(guān)系，以及（1）式，就可以得到添加xk各種組合后的可疑幀長(zhǎng)度，以及對(duì)應(yīng)該長(zhǎng)度的組合的數(shù)目。 對(duì)表1的5種尾部多項(xiàng)式添加結(jié)果如表3~表7，我將表4~7移到注1中，以便愿意深究的朋友復(fù)核。一般讀者只要看出表3表達(dá)的意思即可：在Ut上添加高次項(xiàng)是如何改變U頭部類(lèi)別，從而改變可疑數(shù)據(jù)流長(zhǎng)度L及該長(zhǎng)度下可能的可疑數(shù)據(jù)流數(shù)目n的。 表3 x4+x3+1
由這些表可匯總出出現(xiàn)各種可疑數(shù)據(jù)流的次數(shù)，并統(tǒng)計(jì)總數(shù)如表8 表8 在k<=10時(shí)各可疑數(shù)據(jù)流長(zhǎng)度出現(xiàn)的總次數(shù)
5．有了U就可以構(gòu)造出完整的Ec，由Ec就可以構(gòu)造出整個(gè)可疑數(shù)據(jù)流Tx。 例如 U=x6+x4+x3+1，得到Ec=U*G=(1110，1111，0101，1010，0000，01)，重構(gòu)見(jiàn)圖5。由Ec可知第一個(gè)位錯(cuò)發(fā)生在第6位，由Ut=x4+x3+1可知，第二個(gè)位錯(cuò)發(fā)生在尾部的第一位。在頭部的Tx填充位被Rx理解為數(shù)據(jù)位之后，Rx和Tx就有了相移，所以由Ec7和Rx7就可以決定Tx7=Ec7○+Rx7，然后因?yàn)閭魉椭袥](méi)錯(cuò)，所以Rx8=Tx7，逐位推出，直到第22位，傳送中又出第二次錯(cuò)，Rx23=not Tx22，繼續(xù)無(wú)錯(cuò)到第27位，由于Rx方出現(xiàn)填充位刪除條件，Tx27被刪掉了，Rx與Tx的相移消失，整個(gè)可疑數(shù)據(jù)流就構(gòu)造完成。
圖5 U=x6+x4+x3+1重構(gòu)出的可疑數(shù)據(jù)流 這重構(gòu)出的Tx之所以稱(chēng)為可疑數(shù)據(jù)流，是因?yàn)橹挥挟?dāng)位錯(cuò)發(fā)生在特定位置時(shí)（在本例中是第6、22位）才會(huì)發(fā)生漏檢，若不在特定位置，那么產(chǎn)生的Ec就不是生成多項(xiàng)式的倍數(shù)，CRC就可以檢驗(yàn)出錯(cuò)誤，不會(huì)漏檢。 6．可疑數(shù)據(jù)流Tx處在數(shù)據(jù)域內(nèi)的任一段內(nèi)（圖6）。 如果可疑數(shù)據(jù)流Tx流的長(zhǎng)度為L(zhǎng)Tx，那么在可疑數(shù)據(jù)流Tx以外的幀的其余部分取值(除DLC及格式規(guī)定部分外)都是可以任選的。對(duì)可疑數(shù)據(jù)流Tx存在的一段，只有一種與Tx有關(guān)的具體數(shù)據(jù)。這樣，與特定位置、特定Tx有關(guān)的漏檢占所有長(zhǎng)度為L(zhǎng)Tx的各種數(shù)據(jù)的概率為2-LTx。當(dāng)Tx在數(shù)據(jù)域內(nèi)移動(dòng)時(shí)，因Bit flip位置不同，又構(gòu)成新的漏錯(cuò)實(shí)例，這樣的移位會(huì)有65-LTx種，頭部窗口有100000，011111及填充位規(guī)則在發(fā)送節(jié)點(diǎn)或接收節(jié)點(diǎn)處執(zhí)行共四種，所以對(duì)特定Tx（與Ect有關(guān)）的漏檢概率是： Pun,L=4*(65-LTx)*2-LTx (2)
圖6 可疑數(shù)據(jù)流的位置 7．我們根據(jù)（2）式以及表8計(jì)算k<=10時(shí)的漏檢概率為： 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的項(xiàng)的貢獻(xiàn)在后面計(jì)算，以避免重復(fù)。 8．對(duì)于k>10到容許的最大值時(shí)的漏檢率貢獻(xiàn)以L(fǎng)Tx作主線(xiàn)來(lái)計(jì)算，因?yàn)閗>10之后Ut的差別已無(wú)影響，而Uh的形式起主要作用。這里仍然要用（1）式： LTx=k+15+Sh。 當(dāng)LTx固定時(shí)，不同的Uh=(uk uk-1 uk-2 uk-3 uk-4)就決定不同的Sh，也就決定了k。由表2知道： Uh=11111時(shí)Sh=2，k=LTx-17，由k-5到k=6共k-10項(xiàng)可以任意選，用LTx代替k即LTx-27項(xiàng)可以任意選，所以屬于這一類(lèi)的有n1=2(LTx-27)種組合。 Uh=11110時(shí)Sh=3，k=LTx-18，由k-5到k=6共k-10項(xiàng)可以任意選，即LTx-28項(xiàng)可以任意選，所以屬于這一類(lèi)的有n2=2(LTx-28)種組合。 Uh=1110*時(shí)Sh=4，k=LTx-19，由k-4到k=6共k-9項(xiàng)可以任意選，即LTx-28項(xiàng)可以任意選，所以屬于這一類(lèi)的有n3=2(LTx-28)種組合。 Uh=110**時(shí)Sh=5，k=LTx-20，由k-3到k=6共k-8項(xiàng)可以任意選，即LTx-28項(xiàng)可以任意選，所以屬于這一類(lèi)的有n4=2(LTx-28)種組合。 Uh=10***時(shí)Sh=6，k=LTx-21，由k-2到k=6共k-7項(xiàng)可以任意選，即LTx-28項(xiàng)可以任意選，所以屬于這一類(lèi)的有n5=2(LTx-28)種組合。 所以對(duì)特定的LTx有nL=n1+n2+n3+n4+n5=3*2(LTx-27) (3) 種組合。 每種LTx的漏檢概率還要考慮它在64位數(shù)據(jù)域內(nèi)的可移動(dòng)數(shù)目65-LTx、對(duì)應(yīng)LTx長(zhǎng)度有一個(gè)漏檢幀所占的比率2-LTx、5種Ut形式和4種頭部形式，于是： Pun,L=5*4*（65-LTx）*3*2(LTx-27)*2-LTx=15*（65-LTx）*2-25 最長(zhǎng)的LTx=64，考慮求和直到LTx=30（上節(jié)對(duì)小于30的已求過(guò)了），則有Pun,L=64~30=15*(1+2+...+35)*2-25 =15*630*2-25=2.81*10-4 于是所有不同長(zhǎng)度的可疑數(shù)據(jù)流造成的漏檢概率總和是：Pun,L=1.11*10-4+2.81*10-4=3.92*10-4 9．位錯(cuò)發(fā)生在對(duì)LTx特定位置的概率： 上述分析是針對(duì)位錯(cuò)發(fā)生在非填充位時(shí)的，所以?xún)H考慮8字節(jié)數(shù)據(jù)的全部幀長(zhǎng)就可以了，可算出幀長(zhǎng)為107位，二個(gè)錯(cuò)分散在107位中的總的組合數(shù)是107*106/2=5671種，所以位錯(cuò)發(fā)生在特定位置的概率是Pposition=1.76*10-4。 由此得到Pun=Pun,L*Pposition=3.92*10-4*1.76*10-4=6.89*10-8。 這個(gè)數(shù)據(jù)并不是漏檢的全部（見(jiàn)后面的文章），但是它已經(jīng)比Bosch聲稱(chēng)的4.7*10-11大了1000倍。 注1： 表4 x5+x3+1
表5 x5+x4+1
表6 x4+x3+x2+1
表7 x3+x+1
|
