# Incrementer optimization mentioned in lecture?

4 messages
Open this post in threaded view
|

## Incrementer optimization mentioned in lecture?

 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?
Open this post in threaded view
|

## Re: Incrementer optimization mentioned in lecture?

 Administrator 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.