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.     

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.     

VLSI implementation of new arithmetic residue to binary decoders

This paper introduces two arithmetic decoders that decode the residue number system into its binary equivalent. The first one deals with the moduli set: (2/sup n/,2/sup n/-1,2/sup n/+1,2/sup n/-2/sup (n+1/2)/+1,2/sup n/+2/sup (n+1/2)/+1), while the other deals with the moduli set: (2/sup n+1/,2/sup n/-1,2/sup n/+1,2/sup n/-2/sup (n+1/2)/+1,2/sup n/+2/sup (n+1/2)/+1), where n is odd. Compact forms for the multiplicative inverse of each modulus is introduced, which facilitates the implementation of these arithmetic decoders. The proposed hardware realizations for these decoders are based on using six carry save adders and one carry propagate adder. The hardware and time requirements of these decoders are much better than other similar decoders found in literature. A sub-micron silicon implementation for the decoder has been performed and reported.     

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

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

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     

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     

RNS-To-Binary Converter for a New Three-Moduli Set {2n+1−1,2n,2n−1}

In this brief, the design of residue number system (RNS) to binary converters for a new powers-of-two related three-moduli set {2ⁿ⁺¹ - 1, 2ⁿ, 2ⁿ - 1} is considered. This moduli set uses moduli of uniform word length (n to n + 1 bits). It is derived from a previously investigated four-moduli set {2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2^{n +1} - 1}. Three RNS-to-binary converters are proposed for this moduli set: one using mixed radix conversion and the other two using Chinese remainder theorem. Detailed architectures of the three converters as well as comparison with some earlier proposed converters for three-moduli sets with uniform word length and the four-moduli set {2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2ⁿ⁺¹ - 1} are presented.     

Power-delay-area efficient modulo 2/sup n/+1 adder architecture for RNS

A new modulo 2/sup n/+1 adder architecture based on the ELM addition algorithm is introduced. A simplification to an existing modulo 2/sup n/+1 addition algorithm is also presented. VLSI implementations using 130 nm CMOS technology demonstrate the superiority of the proposed adder over existing designs in the literature.     

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.     

A universal architecture for designing efficient modulo 2/sup n/+1 multipliers

This paper proposes a simple and universal architecture for designing efficient modified Booth multipliers modulo (2/sup n/+1). The proposed architecture is comprehensive, providing modulo (2/sup n/+1) multipliers with similar performance and cost both for the ordinary and for the diminished-1 number representations. The performance and the efficiency of the proposed multipliers are evaluated and compared with the earlier fastest modulo (2/sup n/+1) multipliers, based on a simple gate-count and gate-delay model and on experimental results obtained from CMOS implementations. These results show that the proposed approach leads on average to approximately 10% faster multipliers than the fastest known structures for the diminished-1 representation based on the modified Booth recoding. Moreover, they also show that the proposed architecture is the only one taking advantage of this recoding to obtain faster multipliers with a significant reduction in hardware. With the used figures of merit, the proposed diminished-1 multipliers are on average 10% and 25% more efficient than the known most efficient modulo (2/sup n/+1) multipliers for Booth recoded and nonrecoded multipliers, respectively.     

Reverse Converters for a New Moduli Set {2<Superscript>2n</Superscript> − 1, 2<Superscript>n</Superscript>, 2<Superscript>2n</Superscript> + 1}

A new moduli set derived from a recently proposed four moduli set is considered, in this paper. The problem of reverse conversion has been considered, and it is shown that the proposed moduli set needs less reverse conversion time and area requirements than the converter for the four moduli set from which it is derived. The proposed moduli set is also compared with two other well-known three moduli sets and for realizing the same dynamic range regarding the area and conversion times of the residue number system (RNS)-to-binary converters.     

Novel digital filter implementations using hybrid RNS-binary arithmetic

The implementation of a FIR filter using a new hybrid RNS-binary arithmetic is presented for the first time. In the new arithmetic, the data samples are represented using RNS, and hence the carry free advantage of RNS computations is retained. However, the computation performed for each modulo is implemented using conventional binary arithmetic elements which overcome the drawback of ROM-based RNS arithmetic elements that become inefficient for large moduli. The conventional binary arithmetic elements are also faster and require less area than existing memoryless RNS arithmetic elements. It is shown that the filter structures based on the new arithmetic have better performance than those based on either the conventional binary or conventional RNS arithmetic for large moduli.     

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.      

Cryptographic applications of Brahmagupta-Bha/spl tilde/skara equation

The Brahmagupta-Bha/spl tilde/skara (BB) equation is a quadratic Diophantine equation of the form NX/sup 2/+k=Y/sup 2/, where k is an integer (positive or negative) and N is a positive integer such that /spl radic/N is irrational. A particular case of the BB equation with k=1 is also known as Pell equation in literature. This equation in the Galois Field GF(p), where p is an odd prime has some practically useful properties. Application of these properties in two different fields of cryptography, namely, digital encryption and user authentication are discussed in this paper. For those applications, where software computation of the roots of the BB equation is unacceptable for being too slow, a hardware architecture for using the BB equation in GF(p) is given that is useful for implementation in VLSI form.     

Shifter circuits for {2n+1, 2n, 2n−1} RNS

Shifter circuits are introduced for residue number systems (RNS) with bases composed of the moduli set Shifter circuits for {2n+1, 2n, 2n−1} RNS . The proposed circuits are straightforward to design and their implementation has very small area and delay, making shift operations in RNS inexpensive.     

Random properties of the highest level sequences of primitive sequences over Z(2/sup e/)

Using the estimates of the exponential sums over Galois rings, we discuss the random properties of the highest level sequences /spl alpha//sub e-1/ of primitive sequences generated by a primitive polynomial of degree n over Z(2/sup e/). First we obtain an estimate of 0, 1 distribution in one period of /spl alpha//sub e-1/. On the other hand, we give an estimate of the absolute value of the autocorrelation function |C/sub N/(h)| of /spl alpha//sub e-1/, which is less than 2/sup e-1/(2/sup e-1/-1)/spl radic/3(2/sup 2e/-1)2/sup n/2/+2/sup e-1/ for h/spl ne/0. Both results show that the larger n is, the more random /spl alpha//sub e-1/ will be.     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

RNS与Delta-Sigma编码的位数据流的数值转换算法及硬件实现

利用RNS(余数数制系统)可以执行并行的数据处理以及实现快速无进位算法,在VLSI(超大规模集成电路)设计中表现出低功耗、占用面积小和时延少等优良特性.根据中国剩余定理,基于(2n-1)2n(2n+1)模组,利用Verilog语言设计了RNS到位数据流的数值转换接口电路.以使传统的多位数(Bit)的复杂运算转化为多个并行的较少位数的简单运算,从而降低单次运算的复杂度、时延和功耗.该转换电路面向"Σ-Δ"编码的数据流,不同于传统的二进制数据转换,可以方便地与基于DSD(Direct Stream Digital)的Delta-Sigma系统进行无缝连接.