关于余数数制RNS

timthorpe

余数数制 (Residue Number System,RNS )
      余数数制是一种我国古代代数系统，中国余数定理，
也称中国剩余定理，孙子剩余定理。RNS 是一个古老的数值
表征系统，“今有物不知其数 ，三三数之剩二 ，五五数之剩三 ，七七数之剩二 问物几何？”就是 RNS 的
最早命题， 记载于公元 1 世纪的孙子算经中，即中国剩余
定理 （chinese remainder theorem CRT） RNS。RNS是一种整数运算系统，其中定义了基本的加，减
和乘除运算。RNS 由一组称为余数基的互为质数的
数{ m1,m 2, ,ml }来定义的。  能表示 的动态范围
为 M= m1* m2..ml.对于有符号数而言，则X的整数什是约
束在【—M/2,M/2】.若 M>max {X } 则 称 RNS 为冗余余
数系统 (redundant residue number system RRNS).
   RNS算法是在同一个同构计算环内定义的：Zm约等于
Zm1*Zm2*..*Zml.其中Zm=Z/(M)，与整数模M的计算环相关，
后者称为余数类模 modM.整数 可以用其对该余数基的余数向量{ x1, x2, ,xl }来表征.（xi=X mod mi）。定义#
为代数运算的符号+.-或*，如果Z,X,Y属于Zm,则有：
          Z=X#Y mod M
RNS算法是对偶定义的。Z=X#Y mod M 的L个元素是在L个
短整形字长 mod(ml)信道中同时计算的，信道的字宽是
受wl=[log2(ml)]位限制的（通常是4位到8位）。在实际实
用中，大多数RNS运算系统中使用的是小型RAM或着ROM表来
实现模映射zl=xl#yl mod ml.
   RNS数制已经在定制的VLSI元器件。GaAs 和LSI中得到应用
，xilinx 和altera的部分器件中也提供了类似的表对提高速度
有显著作用。
   实现RNS到整数的解码.除法或着是绝对值缩放，首先必须将数
据从RNS转换成整数。通过所使用的转换理论被称为中国余数定理
（Chinese Remainder Theorem,CRT）和混和基数转换（Mixed-radix conversion,MRC）算法。实际不，MRC
是生成整数加权数制表达式的数位，而CRT直接给出了RNS的一个映射，
参考 ：数字信号处理的FPGA实现 Uwe Meyer-Baese
       余数系统在软件无线电中的应用
附件:
以_2_n_1_2_n_2_n_1_为基的余数系统2_n高性能缩放.rar
[时间:2011-3-22 08:29 - 下载次数:22]
余数系统在软件无线电中的应用.rar
[时间:2011-3-22 08:29 - 下载次数:23]
opt_rns.rar
[时间:2011-3-22 11:20 - 下载次数:16]