On MultiModuli residue number systems with moduli of forms r/sup a/, r/sup b/-1, r/sup c/+1

The residue number system (RNS) is an integer system appropriate for implementing fast digital signal processors since it can support parallel, carry-free, high-speed arithmetic. One of the most important considerations when designing RNS systems is the choice of the moduli set. This is due to the fact that the system's speed, its dynamic range, as well as its hardware complexity depend on both the forms and the number of the chosen moduli. When performing high radix-r(r>2) arithmetic, moduli of forms r/sup a/, r/sup b/-1 and r/sup c/+1 imply simple RNS arithmetic and efficient weighted (radix-r)-to-RNS and RNS-to-weighted (radix-r) conversions. In this paper, new multimoduli high radix-r RNS systems based on moduli of forms r/sup a/, r/sup b/-1 and r/sup c/+1 are presented. These systems will be derived from some recently developed theory. Such systems including moduli of forms r/sup a/, r/sup b/-1 and r/sup c/+1 are appropriate for multiple-valued logic implementations or high radix (r>2) arithmetic using binary logic. The new RNS systems are balanced, achieve fast and simple RNS computations and conversions and implement large dynamic ranges. The specific case of the binary (radix r=2) domain is also presented.     

4模剩余数系统FIR数字滤波器设计

基于四模余数系统的FIR滤波器将一个滤波系统分为4个彼此独立,互不影响,并行运算的子滤波通道,消除了各个子运算通道之间的进位链,加快了计算的速度,提高了滤波精度。所有模都具有2n 和2n±1的形式,电路完全基于组合逻辑电路来实现。结果表明,无论在功耗,速度,实现复杂度等方面,采用余数系统构建的FIR滤波器都优于于传统二进制FIR滤波器。     

On the binary quadratic residue system with noncoprime moduli

The residue number system (RNS) appropriate for implementing fast digital signal processors since it can support parallel, carry-free, high-speed arithmetic. A development in residue arithmetic is the quadratic residue number system (QRNS), which can perform complex multiplications with only two integer multiplications instead of four. An RNS/QRNS is defined by a set of relatively prime integers, called the moduli set, where the choice of this set is one of the most important design considerations for RNS/QRNS systems. In order to maintain simple QRNS arithmetic, moduli sets with numbers of forms 2ⁿ+1 (n is even) have been considered. An efficient such set is the three-moduli set (2^2k-2+1.2^2k+1.2^2k+2+1) for odd k. However, if large dynamic ranges are desirable, QRNS systems with more than three relatively prime moduli must be considered. It is shown that if a QRNS set consists of more than four relatively prime moduli of forms 2ⁿ+1, the moduli selection process becomes inflexible and the arithmetic gets very unbalanced. The above problem can be solved if nonrelatively prime moduli are used. New multimoduli QRNS systems are presented that are based on nonrelatively prime moduli of forms 2ⁿ +1 (n even). The new systems allow flexible moduli selection process, very balanced arithmetic, and are appropriate for large dynamic ranges. For a given dynamic range, these new systems exhibit better speed performance than that of the three-moduli QRNS system     

A New Euclidean Division Algorithm for Residue Number Systems

We propose a new algorithm and architecture for performing divisions in residue number systems (RNS). Our algorithm is suitable for RNS with large moduli, with the aim of manipulating very large integers on a parallel computer or a special-purpose architecture. The two basic features of our algorithm are the use of a high-radix division method, and the use of a floating-point arithmetic that should run in parallel with the modular arithmetic.     

Forward and Reverse Converters and Moduli Set Selection in Signed-Digit?Residue?Number?Systems

This paper presents an investigation into using a combination of two alternative digital number representations; the residue number system (RNS) and the signed-digit (SD) number representation in digital arithmetic circuits. The combined number system is called RNS/SD for short. Since the performance of RNS/SD arithmetic circuits depends on the choice of the moduli set (a set of pairwise prime numbers), the purpose of this work is to compare RNS/SD number systems based on different sets. Five specific moduli sets of different lengths are selected. Moduli-set-specific forward and reverse RNS/SD converters are introduced for each of these sets. A generic conversion technique for moduli sets consisting of any number of elements is also presented. Finite impulse response (FIR) filters are used as reference designs in order to evaluate the performance of RNS/SD processing. The designs are evaluated with respect to delay and circuit area in a commercial 0.13 μm CMOS process. For the case of FIR filters it is shown that generic moduli sets with five or six moduli results in designs with the best area × delay products.

RNS Digital Filtering Structures for Wafer-Scale Integration

Wafer-scale integration (WSI) compresses a large amount of microelectronics representing a complete digital system onto a single intact wafer. This approach is desirable for applications requiring extensive computational capabilities but only limited input and output connections. Its primary advantage is an improvement in total system density. However, such designs must have built-in fault tolerance. Parallel architectures are ideal for WSI. Thus, digital filtering implemented via the residue number system (RNS) is an application that naturally fits the requirements and advantages of WSI. A finite impulse response (FIR) filter readily lends itself to RNS implementation, and a system architecture employing both RNS and WSI is proposed. Means of introducing inherent fault tolerance using the RNS are briefly covered. After a tutorial introduction to the residue number system, methods of performing addition and multiplication operations in the RNS are explored on the basis of reducing area for a custom VLSI design. Modulo addition implemented with two conventional binary adders provides a compact design that may be externally programmed for the modulus that it operates in. Realization of mod multiplication via index addition is shown to be more effective than implementing the mod multiplication truth table directly. Conversions from binary to the RNS representation and vice versa are major bottlenecks in RNS design. Techniques for conversion into the RNS and out of the RNS based on a sequential division algorithm and the mixed-radix system expansion, respectively, are presented.     

Improved RNS FIR filter architectures

A new architecture for implementing finite-impulse response (FIR) filters using the residue number system (RNS) is detailed. The design is based on using a restricted modulus set, with moduli of the form 2/sup n/,2/sup n/-1, and 2/sup n/+1. This does not restrict the modulus set to the common 3 modulus set {2/sup n/-1,2/sup n/,2/sup n/+1}, but any number of pairwise relatively prime moduli of this form, for example, {5,7,17,31,32,33}. Based on a comparison with a 2's complement design, the new RNS design can offer a significant speed improvement. The gain is obtained by using a set of small moduli, selected so as to minimize critical path delay and area. An algorithmic approach is used to obtain full adder based architectures that are optimized for area and delay. The modulus set is optimum based on cost parameters for each modulus. This new architecture presents a practical approach to implementing a fast RNS FIR filter.     

基于FPGA乘法器架构的RNS与有符号二进制量转换

RNS(余数数制系统)是一种整数运算系统,在粒度精确性,能源损耗和响应速度上有很大的优势.从RNS到二进制数的输入输出转换是基于余数算法的专用架构实现的关键.本文提出了一个基于N类模的RNS与有符号二进制量的通用转换算法在FPGAs的乘法器上的实现过程.该算法能更有效地进行有符号数与RNS的转换.基于该算法类型乘法器在同类型乘法器中显示出了速度优势.文章中该架构被映射到Altera的10K系列的FPGA上.     

An Efficient Scalable RNS Architecture for Large Dynamic Ranges

This paper proposes an efficient scalable Residue Number System (RNS) architecture supporting moduli sets with an arbitrary number of channels, allowing to achieve larger dynamic range and a higher level of parallelism. The proposed architecture allows the forward and reverse RNS conversion, by reusing the arithmetic channel units. The arithmetic operations supported at the channel level include addition, subtraction, and multiplication with accumulation capability. For the reverse conversion two algorithms are considered, one based on the Chinese Remainder Theorem and the other one on Mixed-Radix-Conversion, leading to implementations optimized for delay and required circuit area. With the proposed architecture a complete and compact RNS platform is achieved . Experimental results suggest gains of 17 % in the delay in the arithmetic operations, with an area reduction of 23 % regarding the RNS state of the art. When compared with a binary system the proposed architecture allows to perform the same computation 20 times faster alongside with only 10 % of the circuit area resources.     

Implementation of RNS-Based Distributed Arithmetic Discrete Wavelet Transform Architectures Using Field-Programmable Logic

Currently there are design barriers inhibiting the implementation of high-precision digital signal processing (DSP) objects with field programmable logic (FPL) devices. This paper explores overcoming these barriers by fusing together the popular distributed arithmetic (DA) method with the residue number system (RNS) for use in FPL-centric designs. The new design paradigm is studied in the context of a high-performance filter bank and a discrete wavelet transform (DWT). The proposed design paradigm is facilitated by a new RNS accumulator structure based on a carry save adder (CSA). The reported methodology also introduces a polyphase filter structure that results in a reduced look-up table (LUT) budget. The 2C-DA and RNS-DA are compared, in the context of a FPL implementation strategy, using a discrete wavelet transform (DWT) filter bank as a common design theme. The results show that the RNS-DA, compared to a traditional 2C-DA design, enjoys a performance advantage that increases with precision (wordlength).     

Optimized Implementation of RNS FIR Filters Based on FPGAs

In this paper optimized Residue Number System (RNS) arithmetic blocks to better exploit some of the architectural characteristics of the last generation FPGAs are presented. The implementation of modulo m adders, modulo m constant and general multipliers, input and output converters are presented. These architectures are based on moduli sets chosen in order to optimally use the 6-input Look-Up Tables (LUTs) available in the Complex Logic Blocks (CLBs) of the new generation FPGAs. Experiments based on the implementation of Finite Impulse Response (FIR) filters characterized by different number of taps and wordlengths shows that the use of RNS together with suitable moduli sets optimally fits the 6-input LUTs in the last generation FPGAs architectures.     

A Residue-to-Binary Converter for a New Five-Moduli Set

The efficiency of the residue number system (RNS) depends not only on the residue-to-binary converters but also the operand sizes and the modulus in each residue channel. Due to their special number theoretic properties, RNS with a moduli set consisting of moduli in the form of 2 ⁿplusmn1 is more attractive than those with other forms of moduli. In this paper, a new five-moduli set RNS {2ⁿ-1,2ⁿ,2ⁿ+1,2ⁿ+1-1,2 ^n-1-1} for even n is proposed. The new moduli set has a dynamic range of (5n-1) bits. It incorporates two additional moduli to the celebrated three-moduli set, {2ⁿ-1,2ⁿ,2ⁿ +1} with VLSI efficient implementations for both the binary-to-residue conversion and the residue arithmetic units. This extension increases the parallelism and reduces the size of each residue channel for a given dynamic range. The proposed residue-to-binary converter relies on the properties of an efficient residue-to-binary conversion algorithm for {2ⁿ-1,2ⁿ,2ⁿ+1,2ⁿ+1-1} and the mixed-radix conversion (MRC) technique for the two-moduli set RNS. The hardware implementation of the proposed residue-to-binary converter employs adders as the primitive operators. Besides, it can be easily pipelined to attain a high throughput rate     

A novel Sigma–Delta based parallel analogue-to-residue converter

An important step in the residue number system (RNS) based signal processing is the conversion of signal into residue domain. Many implementations of this conversion have been proposed for various goals, and one of the implementations is by a direct conversion from an analogue input. A novel approach for analogue-to-residue conversion is proposed in this research using the most popular Sigma–Delta analogue-to-digital converter (SD-ADC). In this approach, the front end is the same as in traditional SD-ADC that uses Sigma–Delta (ΣΔ) modulator with appropriate dynamic range, but the filtering is done by a filter implemented using RNS arithmetic. Hence, the natural output of the filter is an RNS representation of the input signal. The resolution, conversion speed, hardware complexity and cost of implementation of the proposed ΣΔ based analogue-to-residue converter are compared with the existing analogue-to-residue converters based on Nyquist rate ADCs.     

Design,evaluation and fault-tolerance analysis of stochastic FIR filters

Stochastic computing utilizes compact arithmetic circuits that can potentially lower the implementation cost in silicon area. In addition, stochastic computing provides inherent fault tolerance at the cost of a less efficient signal encoding. Finite impulse response (FIR) filters are key elements in digital signal processing (DSP) due to their linear phase-frequency response. In this article, we consider the problem of implementing FIR filters using the stochastic approach. Novel stochastic FIR filter designs based on multiplexers are proposed and compared to conventional binary designs implemented using Synopsys tools with a 28-nm cell library. Silicon area, power and maximum clock frequency are obtained to evaluate the throughput per area (TPA) and the energy per operation (EPO). For equivalent filtering performance, the stochastic FIR filters underperform in terms of TPA and EPO compared to the conventional binary design, although the stochastic design shows more graceful degradation in performance with a significant reduction in energy consumption. A detailed analysis is performed to evaluate the accuracy of stochastic FIR filters and to determine the required stochastic sequence length. The fault-tolerance of the stochastic design is compared with that of the binary circuit enhanced with triple modular redundancy (TMR). The stochastic designs are more reliable than the conventional binary design and its TMR implementation with unreliable voters, but they are less reliable than the binary TMR implementation when the voters are fault-free.     

A Generalization of a Fast RNS Conversion for a New 4-Modulus Base

A generalization of a new generic 4-modulus base for residue number systems (RNS) is presented in this paper. An efficient RNS to binary conversion algorithm and a hierarchical architecture for these bases are also described. The key features of our conversion architecture compared to previous published architectures of the same output range are a larger moduli set selection and savings on the critical delay, area and power. The FPGA implementation and the detailed proof supporting it are also discussed.      

An efficient VLSI design for a residue to binary converter for general balance moduli (2/sup n/-3,2/sup n/+1,2/sup n/-1,2/sup n/+3)

In this paper, we present a new four-moduli set (2/sup n/-3,2/sup n/+1,2/sup n/-1,2/sup n/+3) and an efficient residue to binary (R/B) converter design. The merits of the proposed four-moduli set include 1) larger dynamic range; 2) higher degree of parallelism for conversion; 3) balanced bit-width for internal RNS arithmetic operations; and 4) flexible moduli set selection. According to the relation between the proposed moduli, the divide-and-conquer technique is used to design a two-level converter architecture which has lower hardware cost and shorter critical delay. For the R/B converter designed with 12-b (n=3), our architecture has about 47% saving in hardware cost and 40% saving in critical delay compared to the last work.     

Novel Power-Delay-Area-Efficient Approach to Generic Modular Addition

Modular adders are fundamental arithmetic components typically employed in residue number system (RNS)-based digital signal processing (DSP) systems. They are widely used in modular multipliers and residue-to-binary converters and in implementing other residue arithmetic operations such as scaling. In this paper, a methodology for designing power-delay-area-efficient modular adders based on carry propagate addition is presented. The binary representational characteristics of the modulus are exploited to allow the sharing of hardware in a fast modular adder topology. VLSI implementation results using 0.13- standard-cell technology, together with a theoretical analysis, show that this approach produces adders that offer efficient tradeoffs when compared with the fastest through to the smallest generic modular adders in the literature.     

A high-speed low-cost modulo Pimultiplier with RNS arithmetic applications

Modulo Pimultipliers are implemented by look-up tables when Piis small (5 bits or less) and by index calculus if Piis larger (6 bits or more). However, index calculus only works for prime moduli Pi. In this letter, we introduce a new square-law multiplier that is useful for modulo Pimultiplication where Piis any modulus. It is expected that this will have important applications in RNS arithmetic computing hardware.