Re: Decimal carry-save adder using reversed biquinary notation

On Mon, 12 Jun 2006 20:05:53 +0200, Terje Mathisen
<terje.mathisen@xxxxxxxxxxxxx> wrote, in part:

I don't know exactly how current decimal units work, but from the
encoding standard (3 digits in 10 bits), I'd assumed that you might work
in modulo-1000 for a while, doing a final unpack/shift/pack at the end
to generate the final result.

After I posted my message, I added information about the 3 digits in 10
bits encoding that IBM has proposed as a standard to the page. (That's
an oversimplification; actually, IBM is proposing a related encoding
method, which I discuss on the page I've added a link to.)

From that description, it is clear - but you may not have seen my page
in its updated form - that the encoding is not to a form suitable for
mod-1000 arithmetic.

Even if you don't do this, and always work in mod-10, you still get the
benefit of a much shorter carry chain: maximum 14 digits vs 53 bits, right?

True, but *no* carry chain is better than a short carry chain. And no
carry chain is achievable by means of a carry-save adder.

Incidentally, though, my use of qui-binary, so that there are no carries
'inside' the digit, seems to be just what is needed to remove the need
for a decimal equivalent of Booth encoding. (IBM has a recent patent on
something like this that I could find at espacenet but not then in the
U.S. database, or it might be a patent application.)

Another fast approach for a long decimal multiplier would be to generate
all 8 possible (0 and 1 comes for free) multiples of the first input
value by a single digit value.

NORC did that. Actually, *this* is where Booth encoding comes in. The
problem is that some of those multiples are "hard multiples", meaning
that some carries are required in generating them. Just as in binary
multiplication, multiplying by *two* is OK, but multiplying by *three*
is a problem.

Booth encoding solves that by faking a multiplication by -1: the number
is one's complemented instead of being two's complemented, and one is
included in an *error term* that gets added in just before the end.

At the end, one *finally* takes the last two outputs of the last
carry-save adder to make one, and only one, addition which requires a
carry.

John Savard
http://www.quadibloc.com/index.html
_________________________________________
Usenet Zone Free Binaries Usenet Server
More than 140,000 groups
Unlimited download
http://www.usenetzone.com to open account
.

Relevant Pages

  • Re: Representing futuristic English
    ... >>If each pair of digits consistently represents a letter of the alphabet ... like the morning sun given even an almost casual frequency analysis. ... Here's an alphabet, here's some electronic text in that alphabet, ... encoding unknown. ...
    (rec.arts.sf.composition)
  • Re: IEEE Decimal Float on Itanium
    ... As it turns out, studying the IBM papers on this, they use an encoding ... techniques which gives them two additional digits of accuracy to 33, ...
    (comp.os.vms)
  • Re: ID vs. SETI was: Re: Learning about Scientific Theory of
    ... encoded the first ten digits of pi into our DNA, ... Or a sequence of prime numbers. ... Given that the "encoding" is unknown, it is HIGHLY likely that someone ... actually does enumerate the first 10 digits of Pi. ...
    (talk.origins)
  • Re: ID vs. SETI was: Re: Learning about Scientific Theory of
    ... encoded the first ten digits of pi into our DNA, ... Or a sequence of prime numbers. ... Given that the "encoding" is unknown, it is HIGHLY likely that someone ... actually does enumerate the first 10 digits of Pi. ...
    (talk.origins)
  • Re: Encoder 9 & DirectX Plugins
    ... parametric EQ plugin in the chain on encoding.. ... and also in the level indicators while encoding. ... BUT they do NADA when in the chain. ... I'm not a sound engineer, though a guy at work is - have you ...
    (microsoft.public.windowsmedia.encoder)
Loading