2008 July « ASIC Digital Arithmetic

Archive for July, 2008

Negabinary addition (addition in base -2)

July 14, 2008 at 3:19 pm · Filed under Addition ·Tagged binary addition, negative base, negative radix

The negative radix-2 number system (base -2) is also called negabinary number system. The algebraic value of a n-bit number $A$ represented in this system is given by

$A = \sum_{k=0}^{n-1} a_k\cdot (-2)^k$ with $a_i \in \{0,1\}$ ,

$A = a_0 - a_1\cdot 2+a_2\cdot 2^2 - a_3\cdot 2^3 + \dots$ .

It is apparent that bits in odd positions are negative whereas bits in even positions are positive.

Addition in this number system is trivial if one makes use of generalized full- and half-adders (GFAs and GHAs; see a previous post). The next figure represents addition of two 6-bit numbers, $A+B$ , with $A=\{a_5,a_4,a_3,a_2,a_1,a_0\}$ and $B=\{b_5,b_4,b_3,b_2,b_1,b_0\}$ .

Note that the result of the first row of GFAs must be inverted to keep the sign negative only in odd positions. Thus, we use a row of GHAs in order to obtain the required value represented in negabinary.

It would be interesting to know if such a system has been ever used in practice (at most, I’ve found a US patent 6832235). This structure does not show any advantage compared to a two’s complement one. Anyway, this is just an example where generalized FA and HAs come handy.

On the other hand, why do we have two carry-chains? Can we do better? Obviously, this number system is not redundant, so we need at least one carry-chain or, in other words, a carry-propagate adder (CPA). But, why two? The answer may lie in the backyard of “Digit-Set Conversion” theory.

Just a comment: Amanzingly enough, I didn’t realize one can present a binary adder without explicitly describing any Boolean formula!

Permalink Leave a Comment

Generalized Half Adders

July 9, 2008 at 5:49 pm · Filed under General ·Tagged half-adder

In this post it is shown what I meant by generalized half-adders (GFA), just for completeness. Note the difference between (b) and (c): in (b) the negative sign is propagated to the sum bit, whereas in (c) the negative sign is propagated to the carry bit.

Permalink Leave a Comment

Publish first, review later!

July 9, 2008 at 5:57 am · Filed under opinion ·Tagged opinion, reflections

Robert W. Lucky is the author of the column titled “Technical Publications and the Internet”, you find in the IEEE Spectrum, January, 2008. We are lucky and have access to it, http://www.spectrum.ieee.org/jan08/5825. Please take 2 minutes and have a look. If you have faced the long procedure that it takes to publish a paper you will be convinced of the idea “publish first, review later”. I am also conviced that the future goes in the direction of open peer reviewing. And, in all, is it not true that the most important thing for an author when publishing is to get a critical and constructive response?

Permalink Leave a Comment

Generalized Full-Adders and Half-Adders

July 8, 2008 at 5:28 pm · Filed under General ·Tagged full-adder, half-adder

A signed bit is a bit that takes the value 0, 1 or -1. It is well known that signed bits or, in general, signed digits, appear very often in arithmetic (for example, in two’s complement numbers). In these cases I find very useful the use of generalized Full-Adders (GFAs) and Half-Adders (GHAs).

Figure (a) represents a conventional FA (also known as a (3,2) counter) with a, b and d as inputs and, c (carry) and s (sum) as outputs. Note that the sign of the bits is given. In this case (a), all inputs and ouputs are positive (+). On the other hand, figure (b) represents a GFA where input d has a negative sign. Since the outputs must represent a number in $\{-1,0,+1,+2\}$ the sum takes a negative sign. Further, the idea can be extended to figure (c) where two inputs are negative, and straightforwardly to any combination. It is also shown that the implementation of a GFA is that of a conventional FA with additional inverters (represented as circles).

Generalized HAs follow easily. In a next post I will show how one can make use of these GFAs and GHAs.

Permalink Leave a Comment

The Critical Path is all about transitions!

July 1, 2008 at 5:23 am · Filed under General ·Tagged carry-skip, critical path

Many of you will find the title of this post trivial. Well, I will show you that this is not yet well understood.

One finds very often in the literature carry-skip adder blocks with OR-gates such as the one represented in the following figure,

comprised of a carry-propagating adder (CPA; usually a carry-ripple adder), and an OR- and an AND-gate. The structure is based on the boolean expression,

$c_{i+1} = c'_{i+1} + P_{i:k}\cdot c_k$

where $c_k$ is the incoming carry bit, $P_{i:k} = p_i\cdot p_{i-1}\cdot \dots \cdot p_k$ with $p_i=a_i\cdot b_i$ is the block propagate signal, $c_{i+1}$ is the carry bit at position i+1 which goes to next block and, $c'_{i+1}$ is the output carry bit from the CPA.