这是 walking 1 算法的替代方案吗？

Question

好吧，这是一篇很长的文章，所以请耐心等待。问题在最后一段。

我的应用程序从 100 多个离散输入读取布尔数据并将它们打包成一堆整数，这些整数稍后通过串行输出。我正处于开发的测试阶段，需要检查每个输入是否都放置在输出的正确位中。我的第一直觉是使用 walking 1 的算法。这会生成数百个测试用例，这需要花费时间和精力来创建、维护、审查等。所以我被鼓励将测试数量减少到我觉得合适的程度，即使这意味着某些案例不会不会被覆盖（大概它们会被其他团队的测试覆盖）。我对没有彻底测试我的代码感到不舒服，但我认识到如果可能的话希望减少测试用例的数量。步行 1 的测试将产生 N 个测试用例，其中 N 是输入的数量。

想了想，想出了以下3个测试。如果其中任何一个失败，则输入转换有问题。

Odds test - 将每个奇数输入设置为 "on"，在输出中产生交替位模式。
偶数测试 - 将每个偶数输入设置为 "on"，在输出中产生交替位模式。
步行 3 的测试 - 这是我自己为测试命名的，因为它与步行 1 的测试相似。将前两个输入设置为 "on"。然后将接下来的两个输入设置为"on"，依此类推，直到剩下0个或1个输入。

对于每个测试，将输出与输入进行比较以查看是否匹配。如果不匹配，可以使用异或来得到错误的位。

想法是奇数和偶数测试证明这些位独立于它们的相邻位。如果 10101 是输入（奇数测试），则输出 10101 表示在设置奇数位时未设置偶数位（独立于奇数位）。偶数位也是如此。这将可能的相关位集减少了一半。然后通过测试 3，我们可以证明其余位的独立性。例如，如果输入是 00011，输出是 00011，我们从 odds/evens 测试中知道位 1 独立于位 0，现在我们从 3 的测试中知道位 0 和 1 独立于其余位位，否则这些位中至少有一个为 1。继续这个例子，如果输入 00011 给我们输出 00111，我们通过 XOR 知道位 2 依赖于位 0（记住偶数和奇数测试通过了，所以位 0 是唯一可能的依赖源）。或者如果输入 00011 给我们输出 00110，我们通过 XOR 再次知道位 0 和 2 再次是问题所在（在这种情况下，它们似乎被交换了）。

下面是一个 5 位序列的示例（在我的应用程序中，它实际上是一系列 19 位序列）。这些示例考虑交换两个位的情况。卡住或关闭的位只能通过奇数和偶数测试来检测。

与步行 1 的测试相比，这 3 个测试产生 floor(N/2) + 2 个测试用例。但这些是否可以有效替代步行 1 的测试？我的示例似乎表明了这一点（至少就我的目的而言），但我不确定。我本来希望在其他地方看到这种技术，但我还没有找到。当然，我不知道我应该找什么名字。

Swap bits 0 and 1
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10110  | Yes       |
| 01010 | evens   | 01001  | Yes       |
| 00011 | 3's (1) | 00011  | No        |
| 01100 | 3's (2) | 01100  | No        |


Swap bits 0 and 2
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10101  | No        |
| 01010 | evens   | 01010  | No        |
| 00011 | 3's (1) | 00110  | Yes       |
| 01100 | 3's (2) | 01100  | No        |


Swap bits 0 and 3
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 11100  | Yes       |
| 01010 | evens   | 00011  | Yes       |
| 00011 | 3's (1) | 01010  | Yes       |
| 01100 | 3's (2) | 00101  | Yes       |


Swap bits 0 and 4
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10101  | No        |
| 01010 | evens   | 01010  | No        |
| 00011 | 3's (1) | 10010  | Yes       |
| 01100 | 3's (2) | 01100  | No        |


Swap bits 1 and 2
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10011  | Yes       |
| 01010 | evens   | 01100  | Yes       |
| 00011 | 3's (1) | 00101  | Yes       |
| 01100 | 3's (2) | 01010  | Yes       |


Swap bits 1 and 3
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10101  | No        |
| 01010 | evens   | 01010  | No        |
| 00011 | 3's (1) | 01001  | Yes       |
| 01100 | 3's (2) | 00110  | Yes       |


Swap bits 1 and 4
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 00111  | Yes       |
| 01010 | evens   | 11000  | Yes       |
| 00011 | 3's (1) | 10001  | Yes       |
| 01100 | 3's (2) | 01100  | No        |


Swap bits 2 and 3
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 11001  | Yes       |
| 01010 | evens   | 00110  | Yes       |
| 00011 | 3's (1) | 00011  | No        |
| 01100 | 3's (2) | 01100  | No        |


Swap bits 2 and 4
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10101  | No        |
| 01010 | evens   | 01010  | No        |
| 00011 | 3's (1) | 00011  | No        |
| 01100 | 3's (2) | 11000  | Yes       |


Swap bits 3 and 4
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 01101  | Yes       |
| 01010 | evens   | 10010  | Yes       |
| 00011 | 3's (1) | 00011  | No        |
| 01100 | 3's (2) | 10100  | Yes       |

Answer 1

您需要考虑合理的错误是什么，决定单个测试成本的因素，以及有时在测试失败的情况下诊断潜在问题的难易程度。在某些设备上，走一测试非常容易输入，因为您只需清除一个开关并设置其邻居即可走 1，并且非常容易检查，因为它会在输出上产生独特的模式。它会检查许多看似合理的错误接线和未接线。（步行 1s 和步行 3s 似乎需要相同数量的开关动作）

如果最合理的错误是您的打包代码中的某个错误，那么生活会更加复杂 - 像在您应该使用 & 的地方使用 + 这样的错误可能只有在设置了足够多的输入导致溢出时才会出现。您可以尝试少量完全随机的输入模式，或者查看 https://en.wikipedia.org/wiki/All-pairs_testing。这样做的问题是，您然后需要将开关设置为明显完全随机的模式，这可能比简单地沿着它们走 1 更令人沮丧和容易出错。

在使用更复杂的测试之前或同时使用更复杂的测试，您可以看到可以通过显示或自动警报提供哪些支持，以使测试人员的工作更轻松、更不容易出错。

Answer 2

使用 n 位，您可以使用 ceil(log2(n + 2)) 测试来检测排列和卡住的位，其中在测试 i 中（范围从 0 到 ceil(log2(n + 2)) - 1），bitj的值（范围从1到n）是j的二进制表示中2**i对应的bit。

test 0: 10101010101010
test 1: 01100110011001
test 2: 00011110000111
test 3: 00000001111111

Answer 3

回答我的问题，不，这不是走 1 的替代方法。走 1 可以检测位之间的耦合。例如，位 4 也打开位 2，步行 1 将检测到这一点。我的算法不会在所有情况下都检测到这一点。

Walking 1's
Bit 4 also turns on bit 2
| Input | i | Output | Detected? |
|-------|---|--------|-----------|
| 00001 | 0 | 00001  | No        |
| 00010 | 1 | 00010  | No        |
| 00100 | 2 | 00100  | No        |
| 01000 | 3 | 01000  | No        |
| 10000 | 4 | 10100  | Yes       |


My algorithm
Bit 4 also turns on bit 2
| Input | Method  | Output | Detected? |
|-------|---------|--------|-----------|
| 10101 | odds    | 10101  | No        |
| 01010 | evens   | 01010  | No        |
| 00011 | 3's (1) | 00011  | No        |
| 01100 | 3's (2) | 01100  | No        |


David Eisenstat's algorithm
Bit 0 also turns on bit 2
| Input | i | Output | Detected? |
|-------|---|--------|-----------|
| 10101 | 0 | 10101  | No        |
| 00110 | 1 | 00110  | No        |
| 11000 | 2 | 11000  | No        |

所以我想这取决于您需要什么级别的检查。如果您需要检查耦合位，走 1 似乎是可行的方法。如果您只需要检查固定位和排列，David Eisenstat 的算法会比我的算法更有效。

在我的例子中，我做了很多位操作，而且我可能不小心耦合了 2 个位，所以我认为它必须是走 1。

编辑实际上，在更仔细地检查了我的应用程序的行为之后，我决定采用 David Eisenstat 的算法。在我的应用程序中，如果位操作错误，比如位 0 打开位 2，位 2 也不可能按预期打开，并且算法会检测到该错误。

这是 walking 1 算法的替代方案吗？

Is this an alternative to the walking 1's algorithm?

algorithm

testing

bit-manipulation