Improved memoryless RNS forward converter based on the periodicity of residues

The residue number system (RNS) is suitable for DSP architectures because of its ability to perform fast carry-free arithmetic. However, this advantage is over-shadowed by the complexity involved in the conversion of numbers between binary and RNS representations. Although the reverse conversion (RNS to binary) is more complex, the forward transformation is not simple either. Most forward converters make use of look-up tables (memory). Recently, a memoryless forward converter architecture for arbitrary moduli sets was proposed by Premkumar in 2002. In this paper, we present an extension to that architecture which results in 44% less hardware for parallel conversion and achieves 43% improvement in speed for serial conversions. It makes use of the periodicity properties of residues obtained using modular exponentiation.     

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.     

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.     

RNS to Binary Conversion Using Diagonal Function and Pirlo and Impedovo Monotonic Function

In this short paper, we present two techniques to perform residue number system (RNS) to binary conversion using diagonal function and show the relationship between the techniques for RNS to binary conversion using Chinese remainder theorem and diagonal function. We also consider RNS to binary conversion using another monotonic function due to Pirlo and Impedovo.     

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 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.     

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.     

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.     

New power-of-2 RNS scaling scheme for cell-based IC design

Previous scaling schemes are based on the conversion of the unpositional residue number system (RNS) digits into a positional number system via Chinese remainder theorem (CRT) or mixed-radix-conversion (MRC) and the back conversion into RNS with an associated size and speed penalty in cell-based integrated circuit (CBIC) designs. This paper presents a new scaling approach, which allows faster and more efficient schemes, because the scaling uses only RNS operations within the small word length channels.     

An RNS Implementation of an $F_{p}$ Elliptic Curve Point Multiplier

Elliptic curve point multiplication is considered to be the most significant operation in all elliptic curve cryptography systems, as it forms the basis of the elliptic curve discrete logarithm problem. Designs for elliptic curve cryptography point multiplication are area demanding and time consuming. Thus, the efficient realization of point multiplication is of fundamental importance for the performance of an elliptic curve system. In this paper, a hardware architecture of an elliptic curve point multiplier is proposed that exploits the intrinsic parallelism of the residue number system (RNS), in order to speed up the elliptic curve point calculations and minimize the area complexity of the elliptic curve point multiplier. The architecture proves to be the fastest among all known design approaches, while complexity is less than half of that of previous efforts. This architecture also supports the required input (binary-to-RNS) and output (RNS-to-binary) conversions. Through a graph-oriented approach, the area of the elliptic curve point multiplier is minimized, by optimizing the point addition and doubling algorithms. Also, through this approach, the number of execution steps for point addition is matched to the number of execution steps for point doubling. Additionally, the impact of various RNS bases, in terms of number of moduli and their bit lengths, on the area and speed of the proposed implementation is analyzed, in an effort to define the potential for using RNS in elliptic curve cryptography.      

神经网络余数制系统与余数制神经网络模型

余数制和神经网络各有其独特优点，将其有机结合这些优点得以充分发挥。将神经网络结构和方法引人余数制信号处理系统，构造出完成余数约化运算和余／十转换运算以及余数加法运算的新结构，开辟了高速实时信号处理的新途径．将余数制引入神经网络，即神经网络中的数据、权值均按余数制表示和运算，构造出一种新的感知机模型—余数制神经网络，由于余数制运算具有一种独特的非线性特点，使这种模型比常规神经网络具有更强的功能。     

An RNS Architecture for Quasi-Chaotic Oscillators

Wideband chaotic carrier is a promising solution for wideband communication, since it overcomes the disadvantages of both narrowband and spread-spectrum communication. It is particularly suited to realize information encryption for secure communication. Chaotic signals can be generated by using discrete-time non-linear dynamical circuits, since they can exhibit a quasi-chaotic (QC) behavior. A particular implementation of QC digital filters can be based on finite precision arithmetic and, in particular, on residue number system (RNS) circuits, which possess very attractive features with regard to their VLSI implementation. In the present paper, we propose an RNS architecture that can be used in connection with secure communication. Each RNS channel consists of a QC oscillator, having its coefficients belonging to a Galois field defined by a prime modulus. In particular, the QC behavior is ensured by well-known properties of primitive polynomials in this field, which generate the characteristic feedback of the oscillator. We demonstrate in the paper that the proposed RNS architecture yields a cost-effective VLSI implementation, which favorably compares with respect to other secure communication approaches proposed in the technical literature. We obtain encouraging results both in terms of confidentiality of the encrypted information and of throughput rate for real-time applications. Moreover, we propose an extended architecture suited to the protection of the secure communication system against transmission errors, by using the self-correcting ability of Redundant RNS (RRNS).     

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.     

余数系统在软件无线电中的应用

余数系统由于其良好的并行特性,在乘加密集型的数字信号处理系统中得到了广泛关注,而这正是构建软件无线电系统的关键所在.本文在介绍RNS基本理论的基础上,结合已有的研究成果.指出了基于RNS的数字信号处理系统关键单元及研究现状,并提出了一种基于RNS数值表征系统的DSP系统结构.结合冗余RNS的容错特性和并行性,介绍了一种基于RNS的多路并行正交通信系统,并指出了其在阵列SDR平台和航天级SDR平台设计中的应用.可以预见,在构建未来复杂SDR系统中,RNS将得到广泛应用.     

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.

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

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

Montgomery residue number systems

The Montgomery residue number system (MRNS) for long word-length arithmetic is introduced. MRNS, a modification of the residue number system (RNS), represents a long integer as a set of smaller Montgomery residues. Long integer addition, subtraction and multiplication can then be performed using hardware-efficient Montgomery operations applied independently to each of the residues. An MRNS hardware architecture suitable for incorporation on a microprocessor data path is also proposed     

RNS-based implementation of 8 /spl times/ 8 point 2D-DCT over field-programmable devices [image compression]

A new implementation of an 8 /spl times/ 8 two-dimensional discrete cosine transform (2D-DCT) processor based on the residue number system (RNS) is presented. This architecture makes use of a fast cosine transform algorithm. It is shown that the RNS implementation of the 2D-DCT over field-programmable logic devices leads to a 129% throughput improvement over the equivalent binary system.     

Enhanced architecture for residue number system-based CDMA for high-rate data transmission

This paper presents an advanced architecture for residue number system (RNS)-based code-division multiple-access (CDMA) system for high-rate data transmission by combining RNS representation, phase shift keying/quadrature amplitude modulation (PSK/QAM) and orthogonal modulation. The residues obtained from a fixed number of bits are again divided into spread code index and data symbol for modulation. The modulated data symbol is spread using the indexed orthogonal codes and transmitted through a communication channel. The proposed system uses a lower number of orthogonal codes than conventional RNS-based CDMA and the performance is comparable. The computational complexity of the proposed system is compared against alternative schemes such as M-ary CDMA and conventional RNS-based CDMA. The modified system is simulated extensively for different channel conditions and the results are discussed.     

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.