0
\$\begingroup\$

How to multiply by 3 a natural number in n-bit binary representation?

Adding x to 2x(x shifted one bit position to the higher significance positions) reads simple enough.
For a ripple carry adder, this requires 2 half adders and n-2 full adders.

But shouldn't knowing one summand is twice the other allow improvements?
Simplifications, even speed-up?

Simple/cheap and fast depend on the cost and timing model, including the set of primitives to build from.
Other metrics include power-delay product.

Programmable logic basic building blocks ever changing, I'm most comfortable with # of transistors in static CMOS, say, no more than 7 channels in series (between any output and either power rail).
This would make the basic gate the And-Or-Invert gate starting from two transistors per input; I suggest to include odd and even parity up to 5 inputs (implementation options including pass transistors/gates).

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

In Efficient Multiply-by-3 and Divide-by-3 Algorithms and Their Fast Hardware Implementation,
Chin-Long WEY, Ping-Chang JUI, and Gang-Neng SUNG present a Unit Cell for Addition: UCA that has a simpler carry chain.
Comparing apples to apples (full adders alternating between inverted carry out and inverted carry in), it is the same speed as a full adder. (I take the paper's timing analysis with a measure of salt as well as their assumptions about building a ripple carry adder from FAs.)
The sum outputs being from "parity gates" in both alternatives, the cost difference is nine transistors per UCA vs. twelve per FA (the availability of one more inverted bit per pair possibly making the 3-input parity implementation simpler, for a smaller difference, still).

Carry chain link pair: full adder
Carry chain double link: full adder Carry chain link pair: UCA
enter image description here

\$\endgroup\$
1

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.