2
$\begingroup$

This circuit should be reasonably efficient in size and depth, but with priority on depth.

If depth was not a concern, then I guess I could make a specialized adder for the least significant bit and then modelled the rest of the circuit as a ripple adder with only that initial, possible carry. The carry has to ripple through the first sequence of consecutive bits set to 1. For example:

$inc(0111) = 1000$
$inc(0001) = 0010$
$inc(0100) = 0101$ (no ripple)

But this takes linear time, in the worst case (binary string is $1...1$). How do you optimize for depth? Does the optimal circuit have a $log_2(n)$ depth?

Is perhaps the best strategy to use a parallel prefix circuit? If so, I guess one would make a specialized adder for the least significant bit. Then you have the result of the least significant bit, which is 0 if a carry was generated, 1 otherwise. If a carry was generated, then you need to efficiently ripple it through all the adjacent, consecutive 1-bits. If one is to use a prefix sum, then you need an associative binary operator. It also needs to preserve the value of the bits that are not part of the initial, consecutive 1-bits (from right to left). This might mean that you pass in the carry bit that was (possibly) generated after the increment on the least significant bit, while the rest of the operators gets fed predefined bits which preserve the values of the relevant bits of the number (bit vector).

At this point, I'm stuck.

Improve this question
$\endgroup$
3
  • $\begingroup$ There's lots of literature on efficient adder circuits, with different tradeoffs between size and depth. Of course, as you noted, one can take any such adder circuit and hard-code one of its inputs to the integer $1$, thus giving us different tradeoffs between size and depth. Have you investigated what size and depth is attainable in this way? Have you investigated whether any of those constructions meet your needs? Is there any reason to expect that it will be possible to do better than the best achievable in that way? $\endgroup$ Commented May 1, 2014 at 22:00
  • $\begingroup$ @D.W. Yes, an efficient adder specialized to a constant input (1) is what I want. I know what I want; an adder with $log_2(n)$ depth that is specialized to just create a carry starting at the least significant bit. But I don't know how to make this parallel; how to efficiently propagate that initial carry. $\endgroup$ Commented May 1, 2014 at 22:09
  • $\begingroup$ Again, my suggestion is to start with standard constructions of adder circuits (there are many described in the literature), hardcode a constant $1$ input into each of them, see what size and depth this gives you in each case, and edit your question to include this research. $\endgroup$ Commented May 1, 2014 at 22:12

1 Answer 1

Reset to default
2
$\begingroup$

You are on the right track with a parallel-prefix circuit. You already have the key when you said

The carry has to ripple through the first sequence of consecutive bits set to 1.

Now suppose you are figuring out the output for, say, the 5th bit. What function of the first 4 bits tells you whether the 5th bit should ripple? That's the function you need to make a parallel-prefix circuit for.

Improve this answer
$\endgroup$
8
  • $\begingroup$ The function should be $AND$? I also need some extra machinery for flipping the initial consecutive 1's, and only them. Maybe the binary operator should take pairs of bits, $(a,b)$, where $a$ is the prefix sum of $AND$ on the string and $b$ is some bit that helps keep track of where we are in the bit vector. The operator needs to output the $AND$ prefix sum, but also output 0 for the bits where this prefix sum is 1. But then, is this operator 'symmetric' so that it can be associative? $\endgroup$ Commented May 1, 2014 at 22:43
  • $\begingroup$ You might be over-thinking. The parallel-prefix circuit for AND will take $N$ bits input and output $N$ bits. Concentrate on making a $\log$ depth circuit for that. When you are done with that, for each bit you will have the original input (either 0 or 1) and also the output of the parallel prefix circuit which tells you if all the preceding bits are 1. So write down the k-map for that 2-bit function. $\endgroup$ Commented May 1, 2014 at 22:52
  • $\begingroup$ How about this: first use the $AND$ prefix sum, then send the output of that into another circuit that outputs a bit vector of equal length, but with only one 1 set to to 1; the position of the last 1-bit in the consecutive bit vector. For example: $111000 → 001000$. Though even if that is fruitful, I don't know how to compute that. I have not read about Karnaugh map. $\endgroup$ Commented May 1, 2014 at 23:12
  • $\begingroup$ ^ The circuit could be computed by a prefix sum $\neg a AND \neg b$, given that the bit vector is padded with an initial 0 (so e.g $11100$ gets padded to $011100$). Then, the whole circuit might be like this: compute the $AND$ pref. sum, call it $and$, then the circuit given here on the input $and$, then compute $XOR$ on $and$ and the original input and call it $xor$, then finally $OR$ on $and$ and $xor$. If that even works, it feels a bit convoluted. But if the complexity is OK, then I guess it might be fine. Was that even in the ballpark of what you might have had in mind? $\endgroup$ Commented May 1, 2014 at 23:26
  • $\begingroup$ ^ The last step should be $OR$ on $xor$ and the output of the circuit that mapped the one 1-set bit (the one computation that I did not give a name). $\endgroup$ Commented May 1, 2014 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.