Redundant Radix Representations of Rings.
AbstractThis paper presents an analysis of radix representations of elements from general rings; in particular, we study the questions of redundancy and completeness in such representations. Mappings into radix representations, as well as conversions between such, are discussed, in particular where the target system is redundant. Results are shown valid for normed rings containing only a finite number of elements with a bounded distance from zero, essentially assuring that the ring is discrete. With only brief references to the more usual representations of integers, the emphasis is on various complex number systems, including the classical complex number systems for the Gaussian integers, as well as the Eisenstein integers, concluding with a summary on properties of some low-radix representations of such systems.
Introduction
Number representations have for long been a central
research topic in the field of computer arithmetic, since
choosing the wrong number system can have detrimental
effects on such aspects of computer design as storage effi-
ciency, accuracy and speed of operation. Designing a number
system amounts to choosing a representation suitable
for computer storage and transfer of elements of a set of
numbers, such that arithmetic operations can be performed
with relative ease on these, by merely manipulating their
representation.
number system has achieved the kind of wide spread
acceptance and popularity that the radix representations
have. Radix polynomials represent the elements of a set
by a weighted sum of digits, where the weights are integer
powers of the base or radix. This representation has the
advantage that each digit can be drawn from a small finite
digit-set easily encoded into machine states, and that arithmetic
algorithms can be broken into atomic steps operating
on individual digits. An important issue in the design of
number systems is the notion of completeness, i.e.,
does a given base and digit-set combination have the desired
effect of being able to represent all the elements of
the set of numbers in question. Equivalently the notion
Asger Munk Nielsen is with MIPS Technologies, Copenhagen, email:
asgern@mips.dk, and Peter Kornerup is with the Dept. of Mathematics
and Computer Science, Odense University, Denmark, email: ko-
rnerup@imada.ou.dk. This work has been supported by grant no.
5.21.08.02 from the Danish Research Council.
Manuscript received January 6, 1998, revised May 25 and October 7, 1998.
of redundancy is of importance, e.g., the presence of alternative
polynomials representing the same element,
has had a profound influence on algorithms and speed of
arithmetic operations in modern microprocessors. Redundancy
may allows parallel, constant time addition, and is
thus paramount to fast implementation of multiplication,
division and other composite computations.
As microprocessors become increasingly more complex,
the problems that can be solved in hardware likewise increase
in complexity. As an example we are at the point
where signal processing problems demanding fast and frequent
execution of arithmetic operations on complex numbers
can be solved by dedicated hardware [2]. It seems logical
to investigate alternative number representations for
these problems, addressing such issues as redundancy and
storage efficiency. Unfortunately assessing important questions
as completeness and redundancy, are no longer quite
as trivial tasks when we turn our attention to sets like complex
numbers. Answering these questions requires a fundamental
understanding of the underlying mathematical
foundation of radix polynomials. The goal of this paper is
to clarify some of these issues, while providing usable tools
for designing and evaluating number systems.
We will do this by using such well founded and widely
understood mathematical notions as rings, residue classes
and norms. This paper extends the work done by Matula
in [11; 12] to the general notion of commutative rings, and
gives an analysis of some previously discussed representations
of complex numbers, e.g. [9; 16; 4], but here emphasizing
redundant digit-sets for these representations. There
are a number of results on non-redundant representations,
also on the representation of complex numbers, e.g. [7; 5;
6; 1], but the question of redundancy beyond the usual
integer-based systems (e.g., as treated in [10]) has had little
treatment in the past. It is unavoidable that many of the
results included for completeness may seem well known, as
they are straightforward generalizations or formalizations
of known properties, possibly from the "folklore".
Section 2 introduces the notation and definitions of completeness
and redundancy of a digit-set, together with results
on these properties, as generalizations of results from
[11; 12]. Section 3 then discusses the determination of radix
representations, non-redundant as well as redundant, together
with an algorithm for determining whether a digit-
set is complete, i.e., capable of representing all elements
of the ring. Termination of these algorithms requires the
ring to be "discrete", in the sense that given a norm on the
ring, only a finite number of elements has norm less that
any given constant. This is likely to be satisfied for any
rings of practical interest, since most such rings have some
kind of lattice structure.
Section 4 then discusses mappings between radix representations
of different systems, in particular digit-set con-
versions. It is here shown that conversions are possible
with a finite carry-set under the same condition for termination
as above. For conversion into a redundant digit-set,
and thus addition as a special case, it is generally assumed
possible to do so in parallel and with limited carry propa-
gation, if only the digit-set is redundant and complete. It
is demonstrated that this is not the case in general, further
conditions on the regularity of the digit-set are needed.
In Section 5 some of the systems presented in the past for
representing complex numbers are then discussed, extending
these also into redundant representations. Section 6
then concludes with a summary of some of the properties
of practical concern for implementations of complex arithmetic

II. On the Representation of Numbers
This paper is devoted to the study of radix representations
of commutative rings. As a foundation for this study,
we will rely on the algebraic structure of sets of polynomi-
als. If R is a ring, then the entity denoted by R[x] is the
set of polynomials over the ring R. Each of these polynomials
is a formal expression in the indeterminate x of the
each coefficient is an element of R. The
set of Laurent polynomials over the ring R , denoted by
R   [x], is the set of polynomials of the form
that we will
here require that l and m are finite, so that any of the
above polynomials only has a finite number of terms.
When an element of a ring (a "number") is represented
in positional notation, each digit has a weight equal to
some power of the radix. The radix is in itself an element
of the ring and the digits are elements of a finite subset of
the ring, this subset is termed the digit-set. An element
of the ring may be represented by an algebraic structure
termed a radix polynomial. These polynomials are similar
to the polynomials over a ring, and may be thought of
as the algebraic objects expressible by a number system
characterized by a fixed base or radix fi 2 R and a digit-set
\Sigma. In this paper we will assume that the zero element of
the ring is always a member of the digit-set, and that the
base is not equal to the zero element, neither is it a unit of
the ring. For instance if the ring of integers,
then we will assume 0 2 \Sigma and jfij ? 1.
Definition 2.1 Radix Polynomials over \Sigma
with
In analogy with the definition of Laurent polynomials, assuming
exists in some extension of R, we define:
Definition 2.2 Extended Radix Polynomials over \Sigma
with
The extended radix polynomials may be thought of as algebraic
objects representing elements (numbers) with fractional
digits. If we replace [fi] by fi in a radix polynomial,
we evaluate the polynomial in the point
determine the element of the ring that the polynomial rep-
resents. This procedure may be formalized by the following
function defined as the evaluation mapping
The radix polynomials map into the ring R, and the extended
radix polynomials map into the set of elements defined
as the fi \Gamma ary elements:
Example: For the ring
the binary numbers, A 8 the octal numbers, and A 10 the
decimal numbers. 2
Observe that i in (4) may be negative, so the fi \Gamma ary
elements may contain fractional parts, but note that then
e.g., A 2 since i is finite.
Since the evaluation mapping k \Delta k is a homomorphism
from P[fi; R] into A fi , arithmetic in the ring A fi can be performed
in the ring of (extended-) radix polynomials, while
preserving a correct representation of the elements in A fi .
But the evaluation mapping is not an isomorphism, since
it is not necessarily one-to-one, for instance if one element
can be represented by more than one radix polynomial.
The goal of our study is to determine criteria for which
radix polynomials written over a digit-set sufficiently represents
a ring. By sufficiently we will understand that the
number system is capable of representing all the elements
of the ring, in the sense that for each element of the ring
there should exist at least one radix polynomial that represents
this element.
Definition 2.3 Completeness
A digit-set \Sigma is complete base fi for the ring R if and only
if
8r
The definition of completeness has deliberately been defined
based on the radix polynomials and not on the extended
radix polynomials, since in the latter case this would
lead to some obscure digit-sets being complete, i.e., digit-
sets where fractional digits are needed to represent the non-
fractional elements of A fi . An example being
fractional digits are needed
to express the odd integers. On the other hand, if a digit-
set \Sigma is complete base fi for the ring R, it is also complete
for the ary elements, in the following sense:
Let hzi denote the ideal I = fkzjk 2 Rg, generated by
z in the ring R, then the set r + I is termed a co-set.
Furthermore let R=I denote the set of distinct co-sets, and
jR=Ij the number of distinct co-sets. We will say that two
elements are congruent modulo I if r
and adopt the notation r 1 j r 2 mod I. If a set S has
exactly one element from each distinct co-set in R=I then
S is a complete residue system modulo I.
Example: For the ring of integers, the ideal generated by
i.e., all the elements divisible by fi. An example of a co-set
:g. The
set is a complete residue system modulo
fi, thus
Lemma 2.4 If \Sigma is complete base fi for the ring R, then
\Sigma contains a complete residue system modulo fi, and consequently
Proof: Let e 2 R. Since \Sigma is complete there exists a
polynomial of the form
with thus the element
e is represented by the residue class d 0
Consequently \Sigma contains a complete residue system
modulo fi. 2
The converse statement does not hold, e.g., the digit-set
1g is not complete base for the integers,
nor is although both are complete residue
systems modulo
turns out to be complete for
As previously noted, some digit-sets allow a single ring
element to be represented by numerous radix-polynomials,
these digit-sets are termed redundant.
Definition 2.5 Redundancy
A digit-set \Sigma is redundant base fi for the ring R if and
only if
and is non-redundant base fi if and only if
Redundancy can complicate the determination of the
sign or the range of a number, but the presence of redundancy
can also be desirable. By exploiting the redundancy,
arithmetic operations can be performed more efficiently,
e.g., addition and subtraction may then be performed with
limited carry propagation and hence in constant time.
The following lemma provides a condition for the presence
of redundancy.
Lemma 2.6 If \Sigma is complete base fi for the ring R, and
j\Sigmaj ? jR=hfiij, then \Sigma is redundant base fi.
that d 1 j d 2 (mod fi) thus 9k
Since \Sigma is complete base fi, there exists a polynomial P 2
I
with we conclude that \Sigma is redundant
base fi. 2
The difference between two congruent digits is a multiple
of the radix, if the factor is in the digit-set or is representable
then the digit-set is redundant. Thus redundancy
can also occur in non-complete digit-sets. For instance if
expressing the same element of the ring Z, thus \Sigma is re-
dundant. On the other hand \Sigma is not complete since no
negative integer can be expressed.
Lemma 2.7 If j\Sigmaj ? and the number of
elements from R that can be represented with radix polynomials
of degree at most n is bounded by \Phi n  C \Delta k n
then \Sigma is redundant base fi.
Proof: Let ng be the
set of radix polynomials of degree at most n. The number
of such polynomials is jQn . The
ratio:
has a limit value of zero as n tends towards infinity, thus
there will be more polynomials than elements to represent,
e.g., \Sigma is redundant base fi. 2
Theorem 2.8 For the ring of integers (i.e.,
j\Sigmaj ? jZ=hfiij then \Sigma is redundant base fi.
Proof: Consider the ring of integers
we have
the largest numerical value that can be represented by a
radix polynomial of degree at most n is given by
thus the number of integers that can be represented is
bounded by
As demonstrated the condition of Lemma 2.7 is satisfied,
thus j\Sigmaj ? jZ=hfiij implies that \Sigma is redundant base fi. 2
A similar result can be proven for the ring of Gaussian
integers (see Lemma 5.1), in fact we have been unable to
find rings where j\Sigmaj ? jR=hfiij does not imply that \Sigma is re-
dundant, thus it seems likely that the following conjecture
holds.
Conjecture 2.9 If j\Sigmaj ? jR=hfiij, then \Sigma is redundant
base fi.
Lemma 2.10 If there exists no digits
belonging to the same residue class modulo fi (i.e., j\Sigmaj
then \Sigma is non-redundant base fi for the ring R.
Proof: Assume that
l
the smallest index such that p k 6= q k then
and consequently p k j q k (mod fi), a contradiction. 2
As stated above, the amount of redundancy is closely
related to the size of the digit-set, so we define the redundancy
index of a digit-set \Sigma, as
From Lemma 2.4 we note that a negative redundancy
index implies that \Sigma cannot be complete, and for rings
satisfying Conjecture 2.9, that a positive index implies that
the digit-set is redundant, and finally from Lemma 2.10
that an index less than or equal to zero implies that the
digit-set is non-redundant.
If R is an integral domain, R is said to be ordered if and
only if R contains a non-empty subset R + such that
1.
2. Each element of R belongs to exactly one of the sets
g.
The set R + is termed the positive elements of R. As an
example one easily checks that the integers are ordered,
since they can be divided into three sets, namely Z
0g.
Definition 2.11 If R is ordered, a digit-set \Sigma is termed
semi-complete base fi for the ring R, if and only if \Sigma is
complete base fi for the positive elements in the sense
that
8r
If a digit-set is semi-complete for a ring R, then by definition
all the positive elements of the ring can be represented,
thus if an element of R is represented by its magnitude (i.e.,
a positive element), along with a sign indicating whether
the element belongs to R
of the ring can be represented. Historically these representations
are referred to as sign-magnitude representations.
III. Determining a Radix Representation
This section covers the problem of determining a radix
representation of a ring element, given a base and a finite
digit-set. It will generally be assumed that the ring R is an
integral domain, and that the ring is normed, in the sense
that there exists a norm N We will assume
that the norm satisfies 8a; b 2 R:
1.
2.
3.
Furthermore we will assume that given a real number k 2
exists only a finite number of elements in R that
has at most norm k, i.e.,
This assumption is needed for the termination of algo-
rithms, essentially assuring that the ring is "discrete", not
having condensation points.
If \Sigma is a complete residue system modulo fi, for any element
r 2 R the following algorithm terminates after a
finite number of steps. The correctness follows from arguments
similar to those of the proof below of Theorem
3.2.
Algorithm 3.1 DGT-Algorithm
Stimulus: A base fi, a digit-set \Sigma that is a complete
residue system modulo fi, and an element r 2
R.
Response:
with
or
while r l 6= 0 and OK do
h find d l
r l+1 / (r l \Gamma d l )=fi
l
Example: Consider the ring of Gaussian integers
\Gamma1, and the number system
1g. Using the DGT-algorithm we will
determine a radix polynomial representing the Gaussian
integer
thus d
fi , and the DGT-algorithm
proceeds as indicated in the following table, and as depicted
in

Figure

1.
l
r l 3
Thus the radix polynomial
is a representation of
r 4
r 6
Fig. 1. DGT-algorithm example: Conversion of 3
polynomial from P I 1g]. The black dots represents the
ideal
The following theorem is based on the DGT-algorithm,
and provides a test for the completeness of a digit-set,
showing that it is sufficient to check the representability
of a small set of ring elements.
Theorem 3.2 Let R be a ring, and N
Let \Sigma be a digit-set containing a complete residue system
modulo fi, then \Sigma is complete base fi for the ring R if and
only if
8r
\Sigma 0 is a complete residue system modulo fi.
Proof: If \Sigma is complete then by definition 8r
I thus assume (6) holds. Choose any
r 2 R, and in analogy with the DGT-algorithm choose a
sequence of digits d :, from the remainders
(this is possible since \Sigma 0 contains a complete residue system
modulo fi). Form the subsequent remainders as:
Notice that fi divides r
From the properties of the norm N we deduce:
thus
Since there exists only a finite number of elements of
norm at most N (r 0 ), after a finite number of steps we arrive
at some remainder r k , such that
By assumption there exists a polynomial P 2 P I [fi; \Sigma] with
and by the recurrence (7) we have
thus the polynomial P
with value kP r is a representation of r, and \Sigma is
complete base fi. 2
Corollary 3.3 Let R be an ordered ring, with positive elements
be a digit-set
containing a complete residue system modulo fi, then \Sigma is
semi-complete if and only if
8r
contains
a complete residue system modulo fi.
Theorem 3.2 together with the DGT-algorithm can be
used to establish the completeness of a digit-set.
Example: In Section II it was claimed that the digit-
set
proper subset is complete. By Theorem 3.2 it is sufficient
to check the representability of the members of the
set can be chosen, using
the absolute value as the norm. Here it turns out that 2
is most difficult to represent, needing the digit \Gamma13 as well
as \Gamma19 in its string representation 1 0 0 19 19 13, whereas
there is no finite representation if only one of these digits
is available. 2
As an example, employing the absolute value as a norm
on the integer ring, Theorem 3.2 can be used to check when
a traditional, contiguous digit-set for the integers is com-
plete, e.g., it can be used in the proof of the following
lemma.
Lemma 3.4 The digit-set
complete for the ring of integers Zif
(rs
and non-complete otherwise.
Whenever \Sigma is complete for base fi, by definition any
a 2 R has a radix polynomial representation, but Algorithm
3.1 (DGT) can only be applied when \Sigma is non-redundant
(\Sigma is a complete residue system modulo fi).
Theorem 3.2 provides a clue to a modified algorithm which
can be applied also for redundant digit-sets. The problem
here is that there may be infinitely many radix polynomial
representations of a given a 2 R, and to assure termination
a finite representation must be enforced. But for any
a satisfying (6) we can choose a finite, shortest, canonical
representation R a 2 P[fi; D], kR a a, and these representations
can then be tabulated. We may thus formulate
a modified DGT-algorithm as follows:
Algorithm 3.5 DGT-Algorithm for complete digit-sets
Stimulus: A base fi, a digit-set \Sigma that is complete for
[fi], and an element r 2 R.
Response: A radix polynomial
with
while r l 6= 0 do
if N (r l )
then
h choose d l as the least significant digit
of the canonical representation of r l i
else
choose some d l 2 \Sigma such that
r l+1 / (r l \Gamma d l )=fi
l
The algorithm thus needs a table containing for each r
with N (r)
, the value of the least significant
digit of the canonical polynomial of value r. If there is
more than one polynomial of the lowest possible degree
representing r, any one can be chosen as the canonical
representation, except when the degree is zero where the
canonical representation has to be chosen as a digit in the
digit-set to assure termination.
IV. Conversion between Radix Systems
In practice, the most likely situation is that an element of
a ring is given in some radix representation (the source sys-
tem), but a conversion is needed into some other radix system
(the target system) over the same ring. Algorithm 3.5
is sequential, and hence does not exploit the possibilities
of parallelism available if the digit-set of the target system
is redundant.
In general a conversion may be needed between systems
with different radices (a base conversion), which can be
performed by evaluating the source polynomial, and then
applying one of the above DGT algorithms mapping the
element into the target system.
However in some cases it is possible two use a parallel
procedure. In general this is the case if some power of the
source base equals some power of the target base.
Definition 4.1 The radices fi S and fi T both elements of
the same ring, are termed compatible if there exists integers
1g such that
For instance are compatible bases, since
are compatible
since 8. Note that if fi S and fi T are compatible bases,
then A fi suggesting that if \Sigma T is complete base fi T ,
then for all there exists at least one radix
polynomial
To convert a polynomial P 2 into a polynomial
in a representation using a compatible base fi T , we
might proceed as follows (assuming fi p
1. Convert from (fi S ; \Sigma S ) into (ffifi p
2. Convert from (fi q
The first step of the conversion amounts to grouping digits
and evaluating these groups as digits in an intermediate
digit-set
The second step is a bit more complicated, since this step
involves splitting digits from the set \Sigma 0 into groups of q digits
from a final digit-set \Sigma 00 . The final digit-set \Sigma 00 should
be chosen such that for each digit d 0 2 \Sigma 0 , there should
exist a q-digit radix polynomial in P I [fi representing
this digit. The existence of such a digit-set is shown in the
following lemma [14].
Lemma 4.2 If fi 2 R, \Sigma 0 ae R and q ? 0 then there exists
a digit-set \Sigma 00 ae R such that
furthermore if \Sigma 0 is redundant base fi q , then \Sigma 00 is necessarily
redundant base fi.
Example: Let the source system be defined by fi
and and the target base be fi
i. The bases are compatible since fi 2
The intermediate digit-set is calculated from (13) as
This digit-set is redundant base ffi fi p
\Gamma4, thus from
Lemma 4.2 the final digit-set \Sigma 00 must also be redundant. It
is easily shown that the redundant digit-set \Sigma
satisfies (14).
A table of q-digit polynomials from P I [fi representing
the digits in \Sigma 0 can now be constructed. When
changing the base of a polynomial P 2
of digits are used to generate intermediate digits
from \Sigma 0 . From each of these digits groups of
from \Sigma 00 are generated.
As an example, let us convert the
from the source system into a polynomial from the target
system, using these steps.
-z
z -
z -
z -
Thus the polynomial
is a representation
of kPk in the target system
When converting a polynomial from the set P[fi; \Sigma S ] to
a polynomial in the P[fi; \Sigma T ] we will assume, that the two
systems are related in such a way, that there exists a p  1
and a carry set C ' R, such that for all c 2 C and d 2 \Sigma S
there exists c 0 2 C and e 0 2 \Sigma T such that
It is useful in certain contexts with p ? 1, e.g., when \Sigma S
and \Sigma T are subsets of some subring S of R, and there
exists a p such that fi p 2 S so that also C ae S. E.g., when
2i so
We may then define a conversion mapping
that for \Sigma T non-redundant ff p is unique, while for \Sigma T redundant
there are several possible mappings ff p . Also observe
that the computation of carries in a conversion can
take place as p parallel processes, each process taking care
of one "carry-chain".
Provided that the carry-set C is finite, a table of the
conversion mapping may be constructed. Each entry of
the table contains a pair c; e where c 2 C; e 2 \Sigma T . Let C
initially contain the zero element of R, and let d 2 \Sigma S be
a digit from the source system. Since the target system is
complete there exists
that kP 0 is to
be included in C. Repeat this for all d in \Sigma S , this takes
care of the zero element in C. Now repeat this process for
any c 2 C, mapping c+d into a pair c 0 ; e 0 such that
possibly adding new elements to
C and thus the need for new rows in the table. In this way
the complete carry set is deduced while constructing the
conversion mapping. Under the same conditions on R and
its norm as for the DGT-Algorithms (3.1 and 3.5) we can
now show termination of the construction:
Theorem 4.3 For any P[fi; \Sigma S ] and P[fi; \Sigma T ] in a normed
ring R with \Sigma T complete for fi, there exist a conversion
mapping,
carry-set C ae R.
Proof: Let C g.
Relating to the algorithm described above, define C
then easy to show that
hence N (c 0 S) must remain bounded, so for some
and the algorithm can terminate with a finite carry-
set
Example: Consider conversion from the source digit-set
into the target digit-set \Sigma
the base 1. Note that \Sigma S is redundant
base fi, whereas \Sigma T is non-redundant. The following table
shows the conversion mapping deduced while constructing
the complete carry-set.
1Employing the conversion mapping, it is possible to convert
in linear time, starting at the least significant posi-
tion, forwarding carries in the usual way. But using parallelism
it is possible to convert faster. For simplicity of
notation in the following, we shall now assume that
the generalization is trivial. Given a conversion mapping
define a set of carry-transfer
functions ffl d g d2\Sigma S ,
and another set of functions f d g d2\Sigma S ,
digit-mapping functions:
Note that fl d (c) is a function describing the mapping of an
incoming carry value (c) into its outgoing carry value
when "passing through" a particular digit value (d) being
converted. We can now immediately generalize carry-
transfer functions to strings of digits:
or
where ffi denotes functional composition. The function fl dk
thus describes the carry transfer through the digit
string d k d functional composition is asso-
ciative, the carries into all positions can be computed in
logarithmic time using parallel prefix computation.
This is optimal when \Sigma T is non-redundant, but with \Sigma T
redundant we expect to be able to perform the conversion
in parallel and in constant time. The idea in the multi-level
conversion is to perform it through (possibly several) con-
versions, each rewriting digits in parallel and moving carries
one position forward, where the carries are absorbed.
Note that the rewriting of a digit in each of these conversions
is independent of the rewriting of its neighbors. Thus
there is only a limited carry propagation, corresponding to
the fixed number of levels. This is the well-known technique
used in redundant addition, which is a special case
of conversion, converting from the digit-set consisting of
digits formed as sums of two digits, back into the original
digit-set. This type of addition can be performed in two or
possibly three levels of conversions for standard digit-sets.
Each conversion converts a digit d into some digit e and
a carry c so that adds an incoming
carry c 0 to e generating a digit e e. Introducing the
following notation for set operations in R
each conversion maps a digit-set \Sigma S ' \Sigma into the
digit-set employing some intermediate digit-
set \Sigma and carry-set C 6= f0g. The set \Sigma must be a complete
residue set, but as the target digit-set \Sigma T is redundant
there may be several choices for \Sigma where \Sigma ae \Sigma T .
Observation 4.4 Redundancy and completeness of the target
digit-set are necessary but not sufficient conditions for
the multi-level parallel, constant time conversion or addi-
tion. The target digit-set has to be of the form \Sigma
where the set \Sigma must contain a complete residue system
modulo fi and C 6= f0g.
This condition is trivially satisfied for the ordinary digit-
sets consisting of a contiguous set of integers, e.g., for
base 2 with \Sigma it is possible to choose either
time conversion is
possible from any subset of f\Gamma1; 0g+2f0;
respectively 1g. But the
redundant and complete digit-set f\Gamma1; 0; 1; 4g for base 3
does not allow such a splitting \Sigma
time conversion into it is not possible, e.g., the number
into itself or various digit strings
where 11 is substituted by 04. However, adding an extra
digit 5 makes constant time conversion possible from
any subset of the digit-set f\Gamma3; \Gamma2; 0;
3f\Gamma1; 0g, since f\Gamma1; 0;
agation. Observe that there is also an alternative splitting
of the digit-set f\Gamma1; 0; allowing
parallel conversion from subsets of f\Gamma1; 0; 2; 3; 4; 7g.
Obviously, in the ring Zthere are no particular reasons
not to use contiguous digit-sets of the form
rs easily seen to satisfy the
above conditions. Constant-time conversions into such redundant
digit-sets were shown possible in [10]. But the
conditions on the structure of digit-sets as expressed by
Observation 4.4 are of interest when investigating digit-
sets from more general rings, e.g., in the complex domain,
and in particular when the ring does not have a lattice
structure.
V. Representing Complex Numbers
Using the formal framework developed in Sections II and
III, we shall investigate possible radix representations of
the complex numbers. We will attempt to do this using
two different approaches, the first being by examining the
Gaussian integers, the second by examining a similar ring
that we will refer to as Eisenstein integers.
A. Representing the Gaussian Integers
The Gaussian integers is a lattice on the field of complex
numbers, defined as the set:
\Gamma1. It is a natural extension of the ring of
integers, and as such the number systems for the two rings
exhibit many common characteristics. Designing a number
system for complex numbers, involves facing a larger number
of decisions, than when designing a number system for
the integers, e.g., there is the possibility of choosing complex
or integer valued digit-sets and a complex or integer
base.
Initially we will examine a more general ring of algebraic
integers defined as:
with d 2 Z;d  1. Note that if ring is
the ring of Gaussian integers. Furthermore observe that
the function N : Z[
defined as N (a
is a norm on Z[
\Gammad], and that the set
is a complete residue system modulo fi,
\Gammad and d  2 if the cardinality of C satisfies
Lemma 5.1 For the ring
\Gammad], d 2 Z;d  1, if
\Gammad]=hfii
then \Sigma is redundant base
\Gammadfl.
Proof: The number of distinct residue classes is given by
\Gammadfl]
as can be derived
from classical results in algebraic number theory [18, pages
62 and 121]. Let and Qn be the
set of radix polynomials in P I [fi; \Sigma] with degree at most n.
The polynomials in Qn represent elements of Z[
\Gammad] that
have norms bounded by:
Since the norm of the base is N
the number
of elements that can be represented by radix polynomials
of degree at most n, is bounded by:
Thus by Lemma 2.7 the lemma is proven. 2
B. Complex Number Systems with an Integer Radix
The straightforward approach for representing the elements
of Z[i], is to choose an integer base and a complex
digit-set, e.g., fi 2 Zand
g. It is evident that if \Sigma r and \Sigma i are complete
digit-sets base fi for the integers, then
complete base fi for the Gaussian integers, furthermore if
\Sigma r or \Sigma i is a redundant digit-set base fi for the integers,
then \Sigma is redundant base fi for the Gaussian integers.
Example: The following base, digit-set combinations are
examples of the large number of possible number systems
that can be constructed combining two integer digit-sets.
1. Binary. 1g. Non-redundant
and non-complete.
2. Borrow-save. 1g.
Redundant and complete.
3. Carry-Borrow-save. 1g.
Redundant and non-complete but semi-complete. 2
These number systems are constructed such that the real
and imaginary parts of a number are written using respectively
the real and imaginary parts of the digit-set. This
has some obvious advantages since arithmetic can be based
on the conventional integer arithmetic algorithms [19]. Furthermore
converting from a conventional representation to
a complex representation and computing the complex conjugate
are fairly simple tasks.
C. Imaginary Radix Number systems
Instead of using an integer radix, we could alternatively
use a purely imaginary radix.
Lemma 5.2 The digit-set
complete base
\Gammad, d 2 Z;d ? 1 for the ring Z[
\Gammad]
if and only if \Sigma is complete base \Gammad for the integers.
If we allow a single extra digit immediately to the right
of the radix point in the definition of completeness, it is
in some cases possible to define number systems that are
not only complete for the ring Z[
\Gammad] but also for the
Gaussian integers.
Define the set of radix polynomials with one fractional
digit as
Definition 5.3 A digit-set \Sigma is fraction-complete base fi
for the ring R if and only if
8r
Lemma 5.4 If
\Gammad, d 2 Z;d ? 1 and
base fi for
\Gammad] then \Sigma is fraction-complete base fi for the Gaussian
integers if and only if
d is of the form
for some k 2 Z; jkj ? 1).
Proof: Assume that contains
a complete residue system modulo k 2 , there exists a
set
such that \Sigma 0 ae \Sigma and the set \Sigma is a complete
residue system modulo k.
Thus for any z 2 Zthere exists b 2 Z;d
such that z
Since \Sigma is complete base fi for Z[
\Gammak 2 ], for any a+
there exists a radix polynomial
that
Forming the polynomial P
value
conclude that \Sigma is fraction complete.
Assume
d is an irrational number. In
order to represent
\Gammad=
d we will implicitly have to
d using an extended radix polynomial with a
finite number of digits from P[\Gammad; \Sigma], this is obviously not
possible since 1=
d is an irrational number. 2
Classifying a number of different digit-sets, from Lemmas
3.4, 5.2 and 5.4 we derive the properties displayed in

Table

1.
Example: Imaginary Radix, Complex Number Representations

1. Binary.
\Gamma2].
Standard digit-set, non-redundant and complete.
2. Quarter-Imaginary.
3g.
Standard digit-set, non-redundant, complete and frac-
tion-complete (this number system was proposed by
Knuth in [9]).
3. Borrow-Save (Quarter-Imaginary).
3g. Maximally redundant digit-set, complete,
fraction-complete (addition in Redundant number systems
of this form has been examined in [13]). 2
D. Complex Radix Number Systems
As suggested in [16], we could use a fully complex base,
e.g., We will only here examine
number systems for which the digit-set contains exclusively
integer digits. Observe that the set
complete residue system modulo
and
Lemma 5.5 The digit-set
s  A 2 and
for the Gaussian integers.
Proof: The proof is a slight generalization of the one
given in [8]. 2
Lemma 5.6 The symmetric digit-set
and for the Gaussian integers.
Proof: If we have that \Sigma
is complete base fi, thus for any a + ib 2 Z[i] there exists
a radix polynomial
such that
If conversely by forming the polynomial:
with value kP we conclude that \Sigma is also
complete base
The case analogous to the above. 2
The set of elements that can be represented using the
standard digit set \Sigma is a somewhat non-symmetric
set, whereas the set of elements that can be
represented using a symmetric redundant digit-set has a
higher degree of symmetry (see Figure 2).
(a) (b) (c)
Fig. 2. The Gaussian integers representable with radix polynomials
of degree 7, using the number systems (a):
in (c) the elements representable
using polynomials of degree 5 with the redundant number system
1g. The elements that lie within the circles all
have norms less than
1), thus from
Theorem 3.2 we immediately conclude that the number systems (a)
and (c) are complete.
Example: The following base, digit-set combinations are
examples of complete number systems.
1. Binary. 1g. Standard digit-set,
non-redundant and complete.
2. Borrow-save. 1g. Minimally
and maximally redundant digit-set, complete.
Digit-set r, s j\Sigmaj Redundant j
Extended
Balanced
Min. Red. \Gammad  r  0  s  d d
Max. Red.

Table

1. Classification of digit-sets for Z[ p \Gammad].
Representing Eisenstein Integers
This section is devoted to the study of the ring
2 (i.e., the third
complex root of unity). This ring is a lattice on the complex
field (

Figure

3), it is similar to the Gaussian integers, but
as will be shown it exhibits some interesting properties.
r
1+r
Fig. 3. The ring Z[ae] and the digit-set
Note that both Z[i] and Z[ae] are algebraic integers, since
i and ae are roots of the polynomials i 2 respectively
rational coefficients. Furthermore,
observe that the set
1g is a complete residue system modulo fi with fi 2 Zand
jfij ? 1.
Lemma 5.7 For the ring Z[ae], if j\Sigmaj ? jZ[ae]=hfiij then \Sigma
is redundant base fi 2 Z, jfij ? 1.
Proof: Analogous to the one given for Lemma 5.1. 2
From Lemma 5.7, we conclude that, if a digit-set has more
than digits, then the digit-set is redundant. It is easy
to see that the ring
is isomorphic to the ring Z[ae]. Thus we conclude
that since Z[ae] and W are essentially equivalent, we may
instead study W as a valid representation of the elements in
Z[ae]. For convenience we introduce the following notation:
Theorem 5.8 The digit-set
base Zfor the ring Z[ae] if fi ! \Gamma1.
Proof: Take any r = a 0 +a 1 ae 2 Z[ae]. In Section III it was
shown that the digit-set \Sigma
for the integers. Thus there exist polynomials P
I [fi; \Sigma z ] representing the (possibly negative) integers a 0
respectively a 1 . Forming the polynomial P
I [fi; \Sigma] with value kP we conclude that \Sigma is
As shown in [4] it can be beneficial to represent the ring
Z[ae] using the redundant set
N[f0gg. It was also shown that addition in H
is possible, using the following theorem, here reformulated
in our terminology:
Theorem 5.9 If a satisfies 2
a is
complete base fi 2 Zwith fi ? 1 for the set W, and
The proof in [4] is based on geometrical considerations of
set coverings. By similar arguments it is possible to show
the following additional set inclusion under the same conditions
on a and fi:
and complete for radix fi we expect to be able to perform
addition and conversion into this digit-set in parallel and
constant time. In particular the binary digit-set H
is complete and redundant base
2. The digits of this number system were depicted in

Figure

3, and addition in this digit-set was shown possible
in [4] by grouping three base 2 digits into digits of base 8.
As an illustration of the use of Observation 4.4 we shall
extend that result on addition in radix 2. The analysis
in [4] was not sufficient to assure addition for fi  6, but
using the set inclusion (21) and Observation 4.4 we shall
now show that conversion into, and addition in, H fi\Gamma1 is
possible for
Observation 4.4 cannot be applied here for
by Theorem 5.9 then the only possible value for a is 1, and
not a proper subset of H fi\Gamma1 .
For choosing
4.4 can be applied, and constant
time conversion from H 1
possible. But neither of the inclusions (20) and (21) are
really applicable here, in fact the largest set H t satisfying
However, for fi  4 it is possible to chose a 2. By
Observation 4.4 it is possible to convert from
base digit-set ring compl. redund. closed fal bpd eff
\Gamma2 f0; 1g Z[
\Gamma2] true false true
\Gamma2 f\Gamma1; 0; 1g Z[
\Gamma2] true true true
Table

2. Properties of low-radix systems for representing complex numbers
into
using also (21). But since a another conversion
can be converted into H fi\Gamma2
. Thus we have proved the following:
Lemma 5.10 For fi  4 conversion from the digit-set
into the digit-
set \Sigma can be performed in
constant time, with carries propagating at most two posi-
tions. In particular, addition in the set W can be realized
in constant time using the digit-set \Sigma T for
conversion into radix 4.
Since the ary numbers written over Z[i], respectively
W, are not identical, conversion between elements from the
two extended rings cannot be exact. This is due to the fact
that since ae = 1+i
2 and
2 is an irrational number, there
does not exist a finite extended radix polynomial in P[fi; \Sigma]
with fi 2 Zand \Sigma ae Z, that represents
.
VI. Conclusion
A summary of some properties of various low radix number
systems for representing complex numbers has been
compiled in the form of Table 2.
The last two columns of the table deal with the efficiency
of representation, bpd is the number of bits needed
to encode the digits, and eff is a measure of efficiency of
the combined representation and digit encoding, defined as
follows:
Thus eff is the asymptotic ratio between the number of bits
needed to encode the values representable by radix polyno-
mials, and the number of bits needed to represent the digits
of the polynomial, using a minimal binary encoding of the
digits. Note that the actual encoding of digits can only
influence the implementation logic of the primitives, and
thus only change the area and timing by constant factors.
In order to evaluate the relative merits of these number
systems, we will now turn our attention to arithmetic operations
performed in these systems. As for storage, and if
digit serial arithmetic is an application, an encoding using
few bits per digit (bpd ) will be desirable, since this will minimize
module size and inter module wiring. If fast addition
is needed the system should be redundant, and need as few
levels of logic as possible (fal is the number of full-adder
levels needed for parallel, constant time addition). Furthermore
if a digit-set is closed under multiplication (i.e., the
product of two arbitrary digits is again a digit), performing
division and multiplication on radix polynomials written
over the digit-set is simpler than if the digit-set is not
closed under multiplication. In the latter case, when forming
the product of a single digit and a number, the individual
digit by digit products will introduce a carry effect into
the neighboring positions. As an example the binary integer
system, e.g., closed group
under multiplication. For the Gaussian integers, the number
system does not share
this property, since for instance (1
thus \Sigma is not closed under multiplication. But the systems
seems very
promising.
However performing digit by register multiplication, as
required in various multiplication and division algorithms,
might also be relatively easy if the partial products can
be generated by a shifting process possibly combined with
negation. This is the reason why modified Booth recoding,
e.g., conversion from the non redundant system (4; f0;
into the redundant system (4; f\Gamma2; is popular in
multiplier design. It can be shown that with proper encod-
ing, partial products can be formed trivially in the system
using a simple shifting rule.



--R

"Automatic Maps in Exotic Number Systems"
"Real/Complex Reconfigurable Arithmetic Using Redundant Complex Number Systems"
"Signed-Digit Number Representations for Fast Parallel Arithmetic"
"New Representation of Complex Numbers and Vectors"
"Radix Representations of Quadratic Fields"
"Number Systems in Imaginary Quadratic Fields"
"Canonical Number Systems in Imaginary Quadratic Fields"
"Canonical Number Systems for Complex Integers"
"An Imaginary Number System"
"Digit-Set Conversions: Generalizations and Applications"
"Radix Arithmetic: Digital Algorithms for Computer Architecture"
"Basic Digit Sets for Radix Repre- sentation"
"Borrow-Save Adders for Real and Complex Number Systems"
"Generalized Base and Digit-Set Conversion"
"On Radix Representation of Rings"
"A 'Binary' System for Complex Num- bers"
"On the Implementation of Arithmetic Support Functions for Generalized Signed Digit Number Systems"
"Algebraic Number The- ory"
"A Complex-Number Multiplier using Radix-4 Digits"
--TR

--CTR
Dhananjeuy S. Phatak , Tom Goff , Israe Koren, Constant-Time Addition and Simultaneous Format Conversion Based on Redundant Binary Representations, IEEE Transactions on Computers, v.50 n.11, p.1267-1278, November 2001
Marc Daumas , David W. Matula, Further Reducing the Redundancy of a Notation Over a Minimally Redundant Digit Set, Journal of VLSI Signal Processing Systems, v.33 n.1, p.7-12, January-February
number system conversion;radix representation of rings;redundancy;computer arithmetic;integer and computer radix number systems