mardi 30 juin 2015

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

Ok, this is a long one, so please bear with me. The question is in the last paragraph.

My application reads boolean data from 100+ discrete inputs and packs them into a bunch of integers, which are later output over serial. I'm in the testing phase of development, and need to check that each input gets placed into the correct bit of the output. My first instinct was to use the walking 1's algorithm. This would generate several hundred test cases though, which takes time and effort to create, maintain, review, etc. So I've been encouraged to reduce the number of tests to what I feel comfortable with, even if it means some cases wouldn't get covered (presumably they'd be covered by tests by other teams). I don't feel comfortable not thoroughly testing my code, but I recognize the desire to reduce the number of test cases if possible. The walking 1's test would produce N test cases, where N is the number of inputs.

After thinking about it for a while, I came up with the following 3 tests. If any one of them fail, there is something wrong with the input conversion.

  1. Odds test - Set every odd input to "on", yielding an alternating bit pattern in the output.

  2. Evens test - Set every even input to "on", yielding an alternating bit pattern in the output.

  3. Walking 3's test - This is my own name for the test, due to its similarity to the walking 1's test. Set the first two inputs to "on". Then set the next two inputs to "on", and so on, until there are 0 or 1 inputs left.

For each test, the output is compared to the input to see if it matches. If they don't match, XOR can be used to get the erroneous bits.

The idea is that the odds and even tests prove that the bits are independent of their neighboring bits. If 10101 is the input (odds test), an output of 10101 indicates that the even bits are not set (are independent of the odd bits) when an odd bit is set. Same goes for the even bits. That reduces the set of possible dependent bits by half. Then by testing the 3's, we can prove independence of the rest of the bits. For example, if input is 00011 and output is 00011, we know from the odds/evens test that bit 1 is independent of bit 0, and now we know from the 3's test that bits 0 and 1 are independent of the rest of the bits, otherwise at least one of those bits would be 1. Continuing the example, if input 00011 gives us 00111 for output, we know via XOR that bit 2 is dependent on bit 0 (remember that the evens and odds test passed, so bit 0 is the only possible source of dependence). Or if input 00011 gives us 00110 for output, we know again via XOR that once again bits 0 and 2 are the problem (in this case, they appear to be swapped).

An example of this for a 5-bit sequence is below (in my application it's actually a series of 19-bit sequences). These examples consider the case where two bits are swapped. Bits that are stuck on or off can be detected solely by the odd and even tests.

Compared to the walking 1's test, these 3 tests yield floor(N/2) + 2 test cases. But do these make a valid replacement for the walking 1's test? My example seems to indicate so (at least for my purposes), but I'm not sure. I would've expected to see this technique elsewhere, but I haven't found it. Of course, I don't know what name I should be looking for.

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       |

Aucun commentaire:

Enregistrer un commentaire