Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!seismo!ll-xn!cit-vax!polecat!fritz
From: fritz@polecat.UUCP
Newsgroups: comp.arch
Subject: Re: Other advantages of ternaries (was number bases)
Message-ID: <3053@cit-vax.Caltech.Edu>
Date: Fri, 19-Jun-87 00:54:54 EDT
Article-I.D.: cit-vax.3053
Posted: Fri Jun 19 00:54:54 1987
Date-Received: Sat, 20-Jun-87 02:14:47 EDT
References: <35@b.gp.cs.cmu.edu> <163@edm.UUCP>
Sender: news@cit-vax.Caltech.Edu
Reply-To: fritz@polecat.Caltech.EDU (Fritz Nordby)
Organization: California Institute of Technology
Lines: 32
Keywords: redundant binary adders, parallel multipliers, Booth encoding
Summary: works in binary, not in ternary

In article <163@edm.UUCP> rroot@edm.UUCP (uucp) writes:
>In article <35@b.gp.cs.cmu.edu>, jsp@b.gp.cs.cmu.edu (John Pieper) writes:
>> 
>> One distinct advantage of a (+1, 0, -1) number representation is that no
>> carry-propagation is required for adders. Since the minor cycle of a machine
>
>You will still have carry propogation in many instances, even if you always
>do manage to normalize a number. Granted you may not have to carry as OFTEN
>(on the random case), but carry will still be necessary from time to time.

Addition in minimal balanced signed-digit ternary does indeed still require
carry propagation, since it is an irredundant number system.  Signed-digit
binary addition, however, requires no carry propagation (or, more accurately,
has an absolutely bounded maximum carry length) using the same digit set.
(Reference: Kai Hwang, ``Computer Arithmetic: Principles, Architecture, and
Design,'' John Wiley & Sons, New York, 1979, pp.107-112.  This only covers
the case of r>=3, for which carry length is limited to 1; for r=2, carry
length is limited to 2, and a slightly more complex addition algorithm is
needed for the general case, but ``totally parallel'' addition and subtraction
are still possible.)

In other words: using (+1,0,-1) for representing numbers in ternary doesn't
eliminate carry propagation in addition; using the same digit set for binary
numbers allows absolutely bounded carry propagation during addition.

I've actually designed a multiplier chip using a restricted form of this type
of arithmetic.  In terms of circuitry, the adders are quite similar to carry-
save full adders; the advantage over a standard carry-save array multiplier
comes in sign handling (it's much easier to get the design right when the
number system takes care of the sign rather than making you worry about it).

		Fritz Nordby.	fritz@vlsi.caltech.edu	cit-vax!fritz