Not16 Incomplete Truth Table?

[Nick Lee]

Hi guys,

So I noticed  that for the Not16 gate, it's "Truth Table" is different from the previous gates that we've previously built so far in Project 1 (Not, And, Or, Xor, Mux, DMux) in that for those chips the truth tables we were supplied actually covered all possible combinations of inputs and outputs.

However in the Not16.cmp file, the "truth table" is the following:

|        in        |       out        |
| 0000000000000000 | 1111111111111111 |
| 1111111111111111 | 0000000000000000 |
| 1010101010101010 | 0101010101010101 |
| 0011110011000011 | 1100001100111100 |
| 0001001000110100 | 1110110111001011 |

However if my understanding is correct a 16 bit Not chip should be able to take 65,536 (i.e. 2^16) different binary combinations, so the Truth Table should be 65,536 lines long.

So am I right to assume that the Not16.cmp file that we were supplied was deliberately truncated for ease of testing and also for practical purposes? Because there could easily be an extra line that is:

|        in        |       out        |
| 0000100001000010 | 1111011110111101 |
and so on.....

[ybakos]

In short, yes.

[Nick Lee]

Fantastic thanks for the clarification ybakos!

Btw I was stuck on Mux then I watched your vimeo video on DMux and Mux, good stuff man, appreciate it.

[cadet1620]

You are correct that there are 2^16 possible input values for Not16.

Test Cases is a better description of the inputs used in the test scripts. The dilemma when writing test code is that very quickly, the possible number of test cases grows beyond the possibility of exhaustive testing. Consider the Mux8Way16 which has 8 16-bit data inputs and a 3-bit select input for a total of 131 inputs. At 1,000,000 tests per second, it would take about 10^26 years to exhaustively test the part!

The test engineer needs to determine what are likely failure scenarios for the part and build an appropriate set of test cases to catch those failures.

Think about Not16 and the way it is normally written -- using 16 tested and verified Nots.  The things that can commonly go wrong are: Not has not been implemented, missing one or more of the Nots, and typos in subscripts.

If I were to write a test script for Not16, here's what I've had tested:

0000000000000000 -> 1111111111111111    Test that all output bits are connected and that Not has been implemented.
1111111111111111 -> 0000000000000000    Test that all input bits are connected.
0000000000000001 -> 1111111111111110    Test that each input bit affects the correct output bit.
0000000000000010 -> 1111111111111101
0000000000000100 -> 1111111111111011
0000000000001000 -> 1111111111110111
0000000000010000 -> 1111111111101111
0000000000100000 -> 1111111111011111
0000000001000000 -> 1111111110111111
0000000010000000 -> 1111111101111111
0000000100000000 -> 1111111011111111
0000001000000000 -> 1111110111111111
0000010000000000 -> 1111101111111111
0000100000000000 -> 1111011111111111
0001000000000000 -> 1110111111111111
0010000000000000 -> 1101111111111111
0100000000000000 -> 1011111111111111
1000000000000000 -> 0111111111111111

If the test was intended for a real hardware part, I'd include a "walking 0's" test -- the opposite of the "walking 1's" test used above -- so that the individual Not gates would have been tested as well.

--Mark

[Nick Lee]

Wow that's a very good explanation. I get it now, so in reality we don't get the "luxury" of having complete Truth Tables like we get when dealing with simple elementary gates (e.g. Not, And, Or, Xor etc). In fact for more complicated chips you probably can't generate their Truth Table at all.

I looked up Test Cases and I know what you mean now. With complicated software for example, they can't possibly test every single possible user input or interaction, so they just design test cases, which by definition aren't 100% exhaustive or comprehensive. Which explains why sometimes programs still crash in the middle of you using them (these are the edge cases that weren't tested I'm guessing).

It all makes more sense now. Many thanks for clearing that up Mark!