In Uwe Meyer-Baese's Book "Digital Signal
Processing with Field
Programmable Gate Arrays", I saw quite a lot of references to the (at
least for me) obscure Residue Number System. I'm wondering how
relevant the RNS is in practice. I've never seen it mentioned anywhere
except in scientific publications. Is anyone using RNS in a real FPGA
project?
Cheers, Guy.

On Feb 14, 3:10 pm, Guy Eschemann
<guy.eschem...@gmail.com> wrote:
> In Uwe Meyer-Baese's Book "Digital Signal Processing with Field
> Programmable Gate Arrays", I saw quite a lot of references to the (at
> least for me) obscure Residue Number System. I'm wondering how
> relevant the RNS is in practice. I've never seen it mentioned anywhere
> except in scientific publications. Is anyone using RNS in a real FPGA
> project?
> Cheers, Guy.

I'm not sure I've even heard of it.  It vaguely rings a bell, but I
may be thinking of something with a similar name that is otherwise
unrelated.  Nope, now that I've read a bit about it I can say I've
never heard of it.

I like the Wikipedia page on RNS.  Under Practical Applications they
actually say, "...it's particularly popular in hardware
implementations"!  This shows one of the shortcomings of Wikipedia...
unsubstantiated statements as if they were fact.  I didn't see a
reference for that one.

Rick

On Sun, 14 Feb 2010 12:10:21 -0800 (PST), Guy
Eschemann
<g...@gmail.com> wrote:

>In Uwe Meyer-Baese's Book "Digital Signal Processing with Field
>Programmable Gate Arrays", I saw quite a lot of references to the (at
>least for me) obscure Residue Number System. I'm wondering how
>relevant the RNS is in practice. I've never seen it mentioned anywhere
>except in scientific publications. Is anyone using RNS in a real FPGA
>project?
>Cheers, Guy.

I remember it appearing in signal processing conferences around 1990, (try ISSCC
the year it came to Glasgow) as a cute way to perform very fast multiplication
because of very short carry chains, but at a huge cost overhead transcoding the
inputs and outputs from normal binary to RNS and back again. 

Potential applications were where the number of multiplications was large enough
to make that overhead look small. (Usual suspects: radar signal processing and
cryptography).

Probably not at all useful in FPGA because the hard wired multipliers and carry
chains are so fast compared to random logic in LUTs.

Actually I think it was mainly a madcap scheme to win bragging rights on the
earliest date in the list of references - one paper had a (possibly bogus)
reference in the 2000BC timeframe on the Chinese Remainder Theorem...

- Brian

On Feb 14, 3:10 pm, Guy Eschemann
<guy.eschem...@gmail.com> wrote:
> In Uwe Meyer-Baese's Book "Digital Signal Processing with Field
> Programmable Gate Arrays", I saw quite a lot of references to the (at
> least for me) obscure Residue Number System. I'm wondering how
> relevant the RNS is in practice. I've never seen it mentioned anywhere
> except in scientific publications. Is anyone using RNS in a real FPGA
> project?

Back in the 70's I was designing digital video processing gear.
Typically each system we designed had multiple, large FIR filters.
This was before the TRW MPY8HJ appeared, so most of the
filters had one time programmable taps, each tap (pair) being based on
three 1024 x 4 proms, appropriately programmed. We gor four
multipliers on a board, so 23-tap filter would take up three boards.
Throw in a dozen such filters, and soon you were using a lot
of resources.

The mathematician associated with the group started thinking
about using Peled-Liu or the Chinese Remainder Theorem to
change the architecture of some of our filters, and perhaps save
some hardware. He concluded that there were no substantial
savings to be had for the sorts of filters we were using.

I can't remember much detail of his work, but the main hope was
to get rid of expensive multipliers. Now that multipliers in FPGAs are
dirt cheap, it seems that P-L and CRT would be even less attractive.

Pete

On Sun, 14 Feb 2010 12:10:21 -0800 (PST), Guy
Eschemann
<g...@gmail.com> wrote:

>In Uwe Meyer-Baese's Book "Digital Signal Processing with Field
>Programmable Gate Arrays", I saw quite a lot of references to the (at
>least for me) obscure Residue Number System. I'm wondering how
>relevant the RNS is in practice. I've never seen it mentioned anywhere
>except in scientific publications. Is anyone using RNS in a real FPGA
>project?
>Cheers, Guy.

RNS is one of the methods which allow you to add without carries. The
problem with them is two fold both of which have the same slow
solution. One you can't compare them, two there are no RNS peripherals
so while things are fast while you're in the RNS domain you have
convert IO to a 'normal' number system and also to compare two numbers
you have to convert to NNS. The conversion is quite slow as you have
to account for the carries during the conversion. These days with all
the embedded arithmetic blocks in FPGAs (or high speed/density of
logic processes in ASICs) there is no more need for them anymore. If
one manages to formulate an adaptive filter solely in RNS domain then
there may be renewed interest in their use.
-- 
Muzaffer Kal

DSPIA INC.
ASIC/FPGA Design Services

http://www.dspia.com