|
作者：楊福宇 關于第一種錯幀漏檢的原因，可疑幀重構方法可以參考我以前的文章：楊福宇,“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錯幀漏檢率的事進行研究，全世界也只有數人而已，如果這些人（包括我自己）犯了錯，豈不誤事？公開之后人人可以復核，便于糾正。特別是我的方法不需要大量機時，復核的條件寬松多了。 有人對專門的議題不太感冒，“我又不是干這一行的”。有些人會認為看起來非常糾結，我需不需要花力氣讀完它？ 不錯，每個人精力有限，不過常識性的東西總不會拒絕的。好比你買了臺電視機，開不出來，你會查查電源插了沒有，插座好不好，入戶總保險燒了沒有。當別人說這臺電視機有問題，你總要先用常識判斷一下�，F在我說CAN有錯幀漏檢率高的問題，你最好也判斷一下，我這里沒有高深的理論，而僅是技巧，一層窗戶紙，捅破了就沒什么稀奇。如果我說得對，這就成為你的另一種常識，用到別的需要判斷的地方。 在以前的文章中我沒有給出具體數值的推導過程，這次我采用了更簡化的方法，完全手算，證明我的數據是可靠的。 0. CAN規定，發送節點在連續5個相同位后自動添加一個反向的值，接收節點在收到連續5個相同位時就把下一個反向的值刪去。 在一個連續5位的窗口中，由于出現傳送位錯，會只有一邊執行填充位規則，見圖0。然后收發二邊的位流就有了相位移，會造成許多位錯。如果第二個傳送錯使相位移回來，后面的位流就不再受影響。相移造成的多位錯是CAN的CRC失效的原因之一。 
圖0 CAN填充規則可能造成位流的相移 1.可疑數據流的結尾部分存在一個6位的窗口，在這里有一個位錯，使填充規則只有一方執行，執行的結果是不再有相位移。圖1是發送節點有填充位而接收節點無，圖2是發送節點無填充位而接收節點有。
圖1 第2個傳送錯造成填充位誤讀為信息位的5種漏檢錯序列尾部形式
圖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之間的關系是相互可以求取的，只是你沒有注意而已。
圖3 由CRC逆序求DATA的方法 所以只要將Ec,t和G以逆序寫法就可以求得Ut的逆序寫法。Ut的階次在5之內，例如對應出錯的5個位置有x4+x3+1等（如表1）。 表1
3.可逆數據流的頭部也是一個6位的窗口，只有一方執行填充位規則。它的誤差多項式與尾部的形式類似（圖4）
圖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
我們知道，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
由這些表可匯總出出現各種可疑數據流的次數，并統計總數如表8 表8 在k<=10時各可疑數據流長度出現的總次數
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的相移消失，整個可疑數據流就構造完成。
圖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)
圖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
表5 x5+x4+1
表6 x4+x3+x2+1
表7 x3+x+1
|
