Incrementer optimization mentioned in lecture?

[rrauenza]

In the lecture, Professor Nisan says this about the the incrementer:

But this is a special case, so it may be worthwhile to actually note what happens, how do we add a sin, 1 to a number. Well, if you look what happens if you just do addition, well, you start adding 1, if the left, rightmost bit is 0, you just turn 0 to 1 and you've got your new number. If it's 1, you turn the 1 to a 0 because you add 1 plus 1, and then you have a carry. And you move to the next bit from the right. And again, if it's 0, you turn it to 1. If it's 1 you turn it to 0, but you need to keep on going because you have another carry. So in general basically, in general what you do for the special case of adding 1 to a given number, you start from the rightmost bit. You keep on flipping bits until you reach a 0 that you flip to 1. And at that point you stop. And that's the very simple hardware to manipulate, you don't, to actually build. You don't need to write the completely general addition circuitry although you may.


Is this just the "carry select adder" with a hard coded input of 1?

[WBahn]

No. Two very different things.

With a carry-select adder, you are increasing the speed while retaining the ability to add two arbitrary numbers with a substantial increase in complexity -- on the order of three times the number of gates.

With an optimized incrementer you are increasing the speed and drastically reducing the number of gates by forfeiting the ability to add two arbitrary numbers.

[rrauenza]

Is there a reference for this optimized incrementer I could read more about?

I'm trying to wrap my head about how to flip all the bits until I find a 0 in combinatorial logic.  

[WBahn]

There are several ways to do it.

The simplest (not necessarily the most efficient) is to look at each bit position in isolation. You want a circuit that takes the input from that bit position and another single input that, if 1, tells you if ALL of the bits to the right of that bit position are a 1 and, if so, the output is the opposite of the input bit otherwise it is simply the input bit.

Can you make a circuit that does that? Two inputs, one output.

Next, can you make a circuit that has N input and whose output is a 1 only when all of the inputs are 1?