recommended netscape fonts: 14-point New Century Schoolbook or Helvetica


printable versions:
postscript
PDF with links
PDF without links


2001 Conf. on Information Sciences and Systems
The Johns Hopkins University, Baltimore MD, USA, March 21-23, 2001

Fractions in the Canonical-Signed-Digit Number System ¹

Jeffrey O. Coleman Naval Research Laboratory Washington DC, USA jeffc@alum.mit.edu

Arda Yurdakul Kadir Has University istanbul, Türkiye a.yurdakul@ieee.org

Abstract:

Canonical-signed-digit (CSD) coefficient representations lead to efficient add/subtract networks for hardwired DSP multiplies of two's complement signals. CSD has always been considered a fixed-point system, and available conversion algorithms operate on integers. Using methods applicable to many simple number systems, we rederive CSD for fractional numbers, derive a simple floating-point recursion for converting fractions to CSD, and briefly examine the associated truncation error.

Introduction

In hardware DSP a signal can be scaled by a coefficient using hardwired shifts and adds, but arithmetic operations are fewer when subtractions are permitted also [1,2]. The standard approach uses coefficients in CSD, a radix-two number system with ternary coefficient set $\{-1,0,1\}$, denoted in CSD digit strings in this paper by {1,0,1}, and having the ``canonical'' property that 1 and 1 are always followed by 0 in CSD strings. CSD string 100.101, for example, represents 3.625, the dot product of ternary coefficient vector $(1,0,0,-1,0,1)$ with powers $(2^2,2^1,2^0,2^{-1},2^{-2},2^{-3})$. So a CSD coefficient specifies which input-signal shifts to add to the output, which to subtract from it, and which to ignore.

CSD is quite old, but we boldly create it anew, justified by the widespread assumption elsewhere that CSD is a shifted-integer system. CSD here is inherently fractional. We begin generally, in radix $r\in\mathbb{R}$ with $\vert r\vert>1$ and a bounded alphabet ${\cal A}\subset\mathbb{R}$ containing zero. Then using $a_k\in{\cal A}$,

$$\begin{array}{r@{.}l\vert r@{\mbox{}=\mbox{}}l@{\displaystyl... ..._2\,a_3\ldots& rx& a_1 +\mbox{} & a_{k+1} & r^{-k}. \end{array}$$

Let translated set $\alpha+{\cal F}_{\alpha}\subset\mathbb{R}$ contain all products $rx$ when $a_1=\alpha\in{\cal A}$ and the sequence is finite. Then

$$r{\cal F}_0 = \bigcup_{\alpha\in{\cal A}} \alpha + {\cal F}_{\alpha}.$$ (1)

Certain properties are desired in sets ${\cal F}_{\alpha}$. First, make them disjoint to make finite sequence representations unique. Second, keep sequence memory finite by structuring the sequence following any $\alpha$ into an initial $\alpha$-dependent component of some length $N_{\alpha}$ and an $\alpha$-independent tail sequence: ${\cal F}_{\alpha}={\cal I}_{\alpha}+r^{-N_{\alpha}}{\cal T}$. Third, require ${\cal I}_{\alpha}=0$ so that every CSD digit of value $\alpha$ is followed immediately by $N_{\alpha}$ (highly desirable) zero digits. Of course $N_0=0$ is essential, else sequences will get ``stuck at zero'' forever, so ${\cal F}_0={\cal T}$. For $\alpha\neq 0$ then,

$${\cal F}_{\alpha}=r^{-N_{\alpha}}{\cal F}_0$$ (2)

Fourth and finally, there should be no gaps among numbers representable to arbitrary precision, so require (topological) closure $\overline{{\cal F}_0}$, just ${\cal F}_0$ with limit points appended, to be a (nontrivial) closed interval. This governs design of such number systems, because, with $\mu$ the (nonzero) width of interval $\overline{{\cal F}_0}$, disjoint union (1) and constraint (2) now imply $r\mu = {\displaystyle\sum_{\alpha\in{\cal A}}} r^{-N_{\alpha}} \mu$, or

$$\sum_{\alpha\in{\cal A}} r^{-(N_{\alpha}+1)}=1.$$ (3)

The terms of this sum give the relative proportions of $\overline{{\cal F}_0}$ represented by sequences beginning with each $\alpha\in{\cal A}$.

CSD for Fractions

Define ${\cal F}=\overline{{\cal F}_0}$ for brevity. In a radix-two system the $\alpha=0$ term in (3) is $r^{-1}=\frac{1}{2}$. Each nonzero $\alpha$ of a ternary system is msd (most significant digit) to the same proportion of ${\cal F}$ if both such terms in (3) are set to $\frac{1}{4}$. If these $\alpha$ are set to $\pm 1$, then the closure of (1) after substituting (2) and dividing out radix $r=2$ really defines CSD:

$${\cal F}= {\color{cyan}\left( \frac{1}{4} {\cal F}- \frac{1... ...lor{magenta}\left( \frac{1}{4} {\cal F}+ \frac{1}{2} \right)}$$ (4)

Each number in ${\cal F}$ is decomposed into an msd value of ${\color{cyan}-\frac{1}{2}}$, ${\color{zcolor}0}$, or ${\color{magenta}\frac{1}{2}}$ and a remainder represented by the other digits. The union was disjoint before closure, so the three closed subintervals just touch and the only solution is ${\cal F}=\left[-\frac{2}{3},\frac{2}{3}\right]$, shown in Fig. 1 with its recursive decomposition according to (4), the full meaning of which is now apparent.

Figure 1: Partitioning the CSD interval recursively using the msb makes a simple ``CSD ruler.''

Figure: 3: (right) Two's complement arithmetic is modular and so renders intermediate overflows harmless.

Two representations are possible at endpoints common to two subintervals of interval ${\cal F}$, so we arbitrarily open it on (either end but) the right (is conventional) before deriving a conversion algorithm. Now (4) with ${\cal F}=\left[-\frac{2}{3},\frac{2}{3}\right)$ implies

$$\renewedcommand{arraystretch}{1.25}c= \left\{ \begin{array}{... ...}\left[-\frac{2}{3},-\frac{1}{3}\right)}$,} \end{array}\right.$$ (5)

for some $c_i\in{\cal F}$, and so the associated CSD digit string is

$$\renewedcommand{arraystretch}{1.25}D(c)= \left\{ \begin{arra... ...}\left[-\frac{2}{3},-\frac{1}{3}\right)}$.} \end{array}\right.$$ (6)

Substituting for the $c_i$ solved from (5) recursively relates any $c\in\left[-\frac{2}{3},\frac{2}{3}\right)$ to its CSD representation :²

$$\renewedcommand{arraystretch}{1.25}\displaystyle D(c)= \left... ...}\left[-\frac{2}{3},-\frac{1}{3}\right)}$.} \end{array}\right.$$ (7)

Recursion (7) and the ``CSD ruler'' in Fig. 1 made from it show that existing more-significant digits do not change as new less-significant digits are produced. Thus, transforming to an iterative form that stops after some desired number of digits yields a simple real-to-CSD conversion algorithm.

Figure 2: The asymptotic (in the number of digits kept) error pdf for CSD conversion of a uniform random variable.

Some important CSD properties are now apparent. Zeros abound, as (7) never places nonzeros consecutively. The CSD ruler shows that conversion of a random variable distributed uniformly on ${\cal F}$ yields nonzero-digit probability $\frac{1}{2}$ for the msd and then $\frac{1}{2},\frac{1}{4}\ldots\:$, oscillating about and converging to $\frac{1}{3}$. As the number $N$ of kept digits grows, the distribution of the normalized truncation error asymptotically approaches that of the Fig. 2 pdf. Truncation adds no bias, and the asymptotic standard error deviation is $\frac{1}{3}2^{-N}$, exceeding rounded binary's by 1.25 dB. But the range of representation is higher for CSD than two's complement by twice this, so CSD as presented has 1.25 dB more dynamic range (SNR).³

A Final Application Note

CSD should be used for coefficients but not signals, because of overflow. A large input in a typical FIR-filter stopband, for example, results in large intermediate sums internal to the filter, with stopband cancellation only effective at the filter output. Using two's complement for signal paths renders this intermediate overflow harmless, as Fig. 3 shows. CSD is for coefficients only and only at design time, when it guides the design of add/subtract/shift systems for signals.

REFERENCES

[1]

A. Avizienis, ``Signed-digit number representation for fast parallel arithmetic,'' IRE Trans. Electron. Comp., vol. EC-10, pp. 389-400, 1961.

[2]

H. L. Garner, ``Number systems and arithmetic,'' Advanced Computers, vol. 6, pp. 131-194, 1965.

[3]

R. Hashemian, ``A new method for conversion of a 2's complement to canonic signed digit number system and its representation,'' in Proc. 1997 Asilomar Conf. on Signals, Systems and Computers, pp. 904-907.

[4]

A. Yurdakul and G. Dündar, ``Multiplierless realization of linear DSP transforms by using common two-term expressions,'' J. VLSI Signal Processing 22, pp. 163-172, 1999.

Footnotes

... System¹

This work was supported by the AMRFC program (ONR 31) of the Office of Naval Research, Arlington VA, USA.

... :²

Or for unambiguous storage effeciency (adapting Hashemian [3]), use trailing sign bits and replace 10, 0, and 10 here with binary 10, 0, and 11.

... (SNR).³

Conventional integer-to-CSD conversion has 1.25 dB less error, but only at the cost of giving up the stability of existing digits as more digits are converted, a property useful in common-subexpression optimization[4].