Test Cases for 16-bit Ripple Carry Adder

Question

I'm working on a lab for a course I have on VHDL, and part of it is to implement an n-bit ripple carry adder and then test it as a 16 bit adder. My problem is that I don't really know HOW to test it, or rather what inputs to give it to test it thoroughly. This is the first time I've ever done anything like this so I'm sorry if it comes across like I have no idea what I'm talking about.

My first thought was that since the adder is just a bunch of identical full adders chained together, if I could show that the individual adder blocks work fine, then it would be trivial to show that the 16 bit adder worked properly since it has such a simple design. So my two inputs would be XXXXXXXX01101010 and XXXXXXXX01011100 with an initial Cin of 0. Using these initial values, the first 8 adders in the chain would each perform a unique addition (as a function of both inputs and Cin) which would fully cover the truth table for a full adder. So if the corresponding bits in the sum are correct and the carry doesn't screw up along the way, it would show that the adder works properly.

I have a bunch of reasons to think this is the wrong approach though. First off, it just seems too simple. The lab manual refers to test CASES, but obviously I've only done one case. It also mentions that you should get timing information from the simulation, but I don't understand how that would work with only a single case. And most importantly, the strategy just doesn't make sense to me. All I'm really doing is finding a really awkward way to test a full adder by chaining a bunch of them together and forcing the Cin for each test case to be linked to the previous test case. I'm not testing the functionality of the whole thing.

As you can probably tell I'm pretty confused. I don't really have any idea how to properly test a 16 bit adder aside from testing the individual parts making it up. Should I just treat it as a black box and only concern myself with the final carry out and sum? But since the sum is 16 bits, how much testing do I actually need to do to show it operates properly?

Answer 1

Whenever feasible, a full test is a safe choice. With 2\$^{32}\$ input permutations, a fast chip, and some patience this might just be feasible. (At 1 test per us it would take less than 2 hours.)

When just 'testing an adder' and no time for a full test, I would go for a random test.

But in your case you know that i is a ripple adder, and you could include the carrys in your output. That means that you can test each section independently, by choosing suitable inputs. That means only about 16 * ( 2 ^ 3 ) test vectors (each combination of A B and carry, and that for each section). That is a small test test, but because you can check the carries it still has full coverage.

Answer 2

Let's say that we want to do a good job of testing this, but without going through the entire 2^32 space of possible operands. (It is not possible for such adder to have such a bug that it only affects a single combination of operands, requiring an exhaustive search of the 2^32 space, so it is inefficient to test it that way.)

If the individual adders are working correctly, and the ripple propagation between them works correctly, then it is correct.

I would giver priority to some test cases which focus on stressing the carry rippling, since the adders have been individually tested.

My first test case would be adding 1 to 1111..1111 which causes a carry out of every bit. The result should be zero, with a carry out of the highest bit.

(Every test case should be tried over both commutations: A + B and B + A, by the way.)

The next set set of test cases would be adding 1 to various "lone zero" patterns like 011...111, 1011...11, 110111..111, ..., 1111110. The presence of a zero should "eat" the carry propagation correctly at that bit position, so that all bits in the result which are lower than that position are zero, and all higher bits are 1 (and, of course, there is no final carry out of the register).

Another set of test cases would add these "lone 1" power-of-two bit patterns to various other patterns: 000...1, 0000...10, 0000...100, ..., 1000..000. For instance, if this is added to the operand 1111.1111, then all bits from that bit position to the left should clear, and all the bits below that should be unaffected.

Next, a useful test case might be to add all of the 16 powers of two (the "lone 1" vectors), as well as zero, to each of the 65536 possible values of the opposite operand (and of course, commute and repeat).

Finally, I would repeat the above two "lone 1" tests with "lone 11": all bit patterns which have 11 embedded in 0's, in all possible positions. This way we are hitting the situations that each adder is combining two 1 bits and a carry, requiring it to produce 1 and carry out 1.

Answer 3

There are several semi-automated test bench tool suites for VHDL; I believe the field is called "equivalence testing" -- but I assume you want to develop something from scratch.

We have fast computers that can itterate through all possible combinations very quickly, so I'd recommend you don't overthink it: just test every case. Since you're talking about a 16-bit adder, that means 65536 combinations for the first input, and 65536 for the second input. A 32-bit counter wired up to the inputs of the adder will cycle through every possible input combination -- wire the lower 16 bits to one input and the upper 16 to the other input. Trigger the counter off a clock signal generated from a stimulus process (out <= '1' after 10 ns; out <= '0' after 10 ns;)

Now, you need to test to see if the output of your adder is correct. The tools you have avaialable is largely dependent upon your environment. The easiest to comprehend is probably to take the output of your adder, and subtract the first input, and then subtract the second input, and then look at the result; if it's not all zeros, raise a flag. VHDL has math and comparrison functions built-in, so building a VHDL block that does this operation should be pretty trivial. Add in a latch at the end to hold the value, and then you can just simulate it and then look at the last value from your simulation result -- if it's 0, it works, if it's 1, it does't work.

Answer 4

This is an academic exercise. As such, the problem itself is easy so what matters is the lesson, not the specifics of the problem. In this trivial case, you can come up with many ad hoc ways of testing it with the confidence that it will prove or disprove that the module works as intended. But the real lesson in this case is about figuring out how to produce test coverage for something that may be too complex to be sure that an intuitively constructed 'shortcut' way of testing will be reliable for completeness. Not that those aren't useful skills, in fact they are necessary when full coverage is computationally impractical, but that is not the lesson here, otherwise the example problem would have been formulated as such.

So write a testbench, wire up your uut (unit under test), give it all possible inputs (you may use a nested for loop for this), and compare the output with the known result, calculated using the vhdl math library, which you know is correct and uses your pc's processor for the computation, and if the output is ever different, use the report function (or write to file) to display in the console the inputs for which the test failed, so that you can later investigate the anomaly.

As a side note, full coverage is actually impossible for a real black box, so in reality you need to have an idea of the design. For example, you could create an adder that always gives you the correct answer for any given set of inputs, unless the previous additions follow a specific pattern (welcome to the world of hardware backdoors), so you'd need to test for an arbitrarily large number of input sequences, unless you know the maximum amount of internal memory elements, etc. But I digress.