The Signed Digit Redundant Number System

Time for a new post on an arithmetical topic.

We all love the good old binary number system and some of us even consider round numbers to be 32, 64, 128, 256, …
Here is another important number system – the signed digit tri-nary number system, which is also a redundant number system. This means that we could have several representations for the very same number.
In the signed digit system we use -1,0,1 instead of just 0,1 for each digit.

It is best explained by an example; The picture below shows three different representations of the number 9 in tri-nary signed digit.

So why do we need to know another number system, and what is it useful for in digital design of ASICs and (especially) FPGAs?

Turns out that using the signed digit number system, one can add without needing to propagate the carry – i.e. in constant time!!!
Hold on your horses, it is not all bright and sunny. The result still needs to be converted back into the good old binary representation and that is not done in constant time, but dependent on the width of the number (although there are various techniques that help optimize the process).

If you are doing DSP applications, especially in FPGAs, where digital filter design is involved – using the signed digit number system can come in handy…

Arithmetic Tips and Tricks #2 – Another Look at a Slow Adder

Do you remember the old serial adder circuit below? A stream of bits comes in (LSB first) on the FA inputs, the present carry-out bit is registered and fed in the next cycle as a carry in. The sum comes in serially on the output (LSB first).

True, it is rather slow – it takes n cycles to add n bits. But hold on, check out the logic depth – one full adder only!! This means the clock can run a lot faster than your typical n-bit adder.
Moreover, it is by far the smallest, cheapest and consumes the least power of all adders known to mankind.

Of course you gotta have this high speed clock available in the system already, and you still gotta know when to stop adding and to sample your result.
Taking all this into consideration, I am sure this old nugget can still be useful somewhere. If you already used it before, or have an idea, place a comment.

Hands-on Arithmetic Operators

Here is a cool site that a colleague sent me – link here.
Scroll down and browse through the chapters. You can interactively play with different arithmetic operators and their implementations using the applets in the site. I found the special purpose adders to be especially interesting.

Arithmetic Tips & Tricks #1

Every single one of us had sometime or another to design a block utilizing some arithmetic operations. Usually we use the necessary operator and forget about it, but since we are “hardware men” (should be said with pride and a full chest) we know there is much more going under the hood. I intend to have a series of posts dealing specifically with arithmetic implementation tips and tricks. There are plenty of them, I don’t know all, probably not even half. So if you got some interesting ones please send them to me and I will post them with credits.

Let’s start. This post will explain 2 of the most obvious and simple ones.

Multiplying by a constant

Multipliers are extremely area hungry and thus when possible should be eliminated. One of the classic examples is when multiplying by a constant.
Assume you need to multiply the result of register A by a factor, say 5. Instead of instantiating a multiplier, you could “shift and add”. 5 in binary is 101, just add A to A00 (2 trailing zeros, have the effect of multiplying by 4) and you have the equivalent of multiplying by 5, since what you basically did was 4A+A = 5A.
This is of course very simplistic, but when you write your code, make sure the constant is not passed on as an argument to a function. It might be that the synthesis tool knows how to handle it, but why take the risk.

Adding a bounded value

Sometimes (or even often), we need to add two values where one is much smaller than the other and bounded. For example adding a 3 bit value to a 32 bit register. The idea here is not to be neat and pad the 3 bit value by leading zeros and create by force a 32 bit register from it. Why? adding two 32 bit values instantiates full adder logic on all the 32 bits, while adding 3 bits to 32 will infer a full adder logic on the 3 LSBs and an increment logic (which is much faster and cheaper) on the rest of the bits. I am quite positive that today’s synthesis tools know how to handle this, but again, it is good practice to always check the synthesis result and see what came up. If you didn’t get what you wanted it is easy enough to force it by coding it in such a way.