在位阵列中找到'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'的位置有效

回答

相关问题