在位陣列中找到'1'的位置有效

我正在佈線測試一組導線是否開路或短路的程序。該程序運行在AVR上，將測試矢量（步行'1'）驅動到電線上並接收結果。它將此結果向量與已存儲在SD卡或外部EEPROM上的預期數據進行比較。在位陣列中找到'1'的位置有效

下面是一個例子，假設我們有一組8根導線，它們都是直通的，即它們沒有連接點。所以如果我們開車0b00000010，我們應該收到0b00000010。

假設我們收到0b11000010。這意味着線7,8和線2之間存在短路。我可以通過0b00000010^0b11000010 = 0b11000000來檢測我感興趣的位。這清楚地告訴我線7和線8有問題，但是如何在大比特陣列中有效地找到這些'1'的位置。使用位掩碼只需要8根電線即可輕鬆完成此操作，但我正在開發的系統必須能夠處理多達300根電線（位）。在我開始像以下這樣使用宏並在300 * 300位數組中測試每一位之前，我想問問這裏是否有更優雅的解決方案。

#define BITMASK(b) (1 << ((b) % 8)) 
#define BITSLOT(b) ((b/8)) 
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) 
#define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) 
#define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b)) 
#define BITNSLOTS(nb) ((nb + 8 - 1)/8)

只是爲了進一步展示如何檢測開路。預期數據：0b00000010，收到數據：0b00000000（電線未拉高）。 0b00000010^0b00000000 = 0b0b00000010 - 電線2打開。

注意：我知道測試300線不是AVR Mega 1281內部的小型RAM可以處理的，這就是爲什麼我將它分成組，即測試50根線，比較，顯示結果然後向前移動。

來源

2012-02-15 saad

許多體系結構都提供了用於定位字中第一組位的具體指令，或者用於計數設置位的數量。編譯器通常爲這些操作提供內在的特性，所以您不必編寫內聯彙編。例如，GCC提供了__builtin_ffs,__builtin_ctz, __builtin_popcount等，它們中的每一個都應該映射到目標架構上的適當指令，利用位級並行性。

如果目標架構不支持這些，編譯器會發出高效的軟件實現。在軟件中逐位測試矢量的幼稚方法效率不高。

如果你的編譯器沒有實現這些，你仍然可以使用de Bruijn sequence編碼你自己的實現。

來源

2012-02-15 15:27:31

我通過de Brujin鏈接閱讀，它似乎需要連續0。不能保證故障是連續的。我的編譯器是AVR-GCC。要去做一些研究，看看它是否實現了這些。 – saad 2012-02-15 15:32:18

您可以使用查找表。例如對數底數爲2的查找的255個字節表可以被用來找到在字節中的最顯著1位：

uint8_t bit1 = log2[bit_mask];

其中的log 2被定義爲如下：

uint8_t const log2[] = { 
    0,    /* not used log2[0] */ 
    0,    /* log2[0x01] */ 
    1, 1    /* log2[0x02], log2[0x03] */ 
    2, 2, 2, 2,  /* log2[0x04],..,log2[0x07] */ 
    3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ 
    ... 
}

在大多數處理器的這樣的查找表將轉到ROM。但是AVR是哈佛機器，並且要將數據放置在代碼空間（ROM）中需要特殊的非標準擴展，這取決於編譯器。例如，IAR AVR編譯器需要使用擴展關鍵字__flash。在WinAVR（GNU AVR）中，您需要使用PROGMEM屬性，但它比這更復雜，因爲您還需要使用特殊的宏來從程序空間讀取數據。

來源

2012-02-16 04:04:01

您多長時間一次指望故障？如果你不經常這樣想，那麼優化「故障存在」情況似乎毫無意義 - 唯一對速度影響重大的部分是「無故障」情況。

要優化無故障情況，只需將實際結果與預期結果以及input^expected == 0測試進行異或，以確定是否設置了任何位。

您可以使用類似的策略來優化「少量故障」情況，如果您還希望故障數量在存在時通常很小 - 屏蔽input^expected值以獲取前8位，只需第二個8位等等，並將這些結果中的每一個結果都歸零。然後，您只需搜索那些不等於零的位，這應該縮小搜索空間，使其可以很快完成。

來源

2012-02-16 12:58:36

我覺得只有一個辦法做到這一點：

創建一個數組出「outdata」。陣列的每一項可以例如對應一個8位端口寄存器。
發送電線上的outdata。
將此數據回寫爲「indata」。
將indata存儲在與outdata完全匹配的陣列中。
在循環中，將outdata的每個字節與indata的每個字節進行異或。

我會強烈建議內聯函數來代替這些宏。

爲什麼你的MCU不能處理300根電線？

300/8 = 37.5字節。需要存儲兩次，outdata和indata，38 * 2 = 76字節。

你不能備用76字節的RAM？

來源

2012-02-16 14:31:15 Lundin

我想你錯過了樹林。看起來像一個釘牀測試。首先測試一些假設： 1）您知道每個測試/通電引腳應該具有哪些引腳。 2）你有一個網錶轉換爲步驟1到SD上的文件

如果你操作的字節級別和位，它簡化了問題。如果您激活一個引腳，則會在您的文件中存儲預期的模式。首先找到不匹配的字節;識別字節中的不匹配引腳;最後存儲帶有故障引腳號的通電引腳。

您不需要用於搜索或結果的數組。總體思路：

numwires=300; 

numbytes=numwires/8 + (numwires%8)?1:0; 

for(unsigned char currbyte=0; currbyte<numbytes; currbyte++) 
{ 
    unsigned char testbyte=inchar(baseaddr+currbyte) 
    unsigned char goodbyte=getgoodbyte(testpin,currbyte/*byte offset*/); 
    if(testbyte^goodbyte){ 
    // have a mismatch report the pins 
    for(j=0, mask=0x01; mask<0x80;mask<<=1, j++){ 
     if((mask & testbyte) != (mask & goodbyte)) // for clarity 
      logbadpin(testpin, currbyte*8+j/*pin/wirevalue*/, mask & testbyte /*bad value*/); 

    } 

}

來源

2012-02-16 18:57:29 Dtyree

在位陣列中找到'1'的位置有效

回答

相關問題