The Signed Digit Redundant Number System
September 5, 2008Time 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…
Adventures in ASIC Digital Design 
Hi Nir,
What do you mean by “especially in FPGAs”? Can you please be more explicit?
Thanks
José
Besides the conversion, there is an area overhead. It takes 2 bit to store a tri-nary digit. The issue is that 2 bit could store one out of 4 distinct values where a tri-nary digit only has one out of 3 different values. Thus, the utilization is only 3/4 of the binary representation.
It gets interesting because the unassigned pair can be used to reduce the amount of logic gates. (any operation with the undefined spare pair is in the DC-set)
Jose,
FPGA designs are normally slower than pure ASIC designs. Therefore sometimes using redundant number systems is very attractive – even at higher area cost.
Philip,
the points you brought up are VERY correct and should be heavily considered.
However, sometimes you don’t care much about the area overhead (especially when it is used only in one specific block).
as for the 3/4 utilization, it is very true that the 4th unused state can be used to reduce area, but it can also be use to indicate a “null” state required in some asynchronous designs (please see the post on Null convention logic). A few years back I toyed with the idea and developed it a bit, but it took too much of my time.
Nir,
First of all, you’re right, signed-digit numbers, similar to carry-save numbers, can be used to speed-up multi-operand adders or the sum of partial products as a result of — for instance — a multiply-and-accumulate operation (the basic operation of FIR filters). The usual implementation requiring rows of full-adders not connected in ripple.
On the other hand, some FPGAs have integrated carry-chains logic to speed up the carry computation of addition/subtraction. So, depending on the specification and the degree of pipeling redundant number systems may result in slower implementation.
Redundant binary numbers provide carry-free addition [no need for carry to propagate] that makes it useful in high speed applications. If you are adding a 2-bit numbers or a even 64-bit numbers, time taken to add the operands will be same, which is not the case in serial adders or carry look-ahead adders used for binary numbers.
Umair,
What you mentioned was mentioned in the post itself.
it also mentions the need to convert back to 2’s complement which IS a carry-like operation.