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     

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.     

RNS-to-Binary Converters for Two Four-Moduli Sets {2n−1,2n,2n+1,2n+1−1} and {2n−1,2n,2n+1,2n+1+1}

In this paper, reverse converters for two recently proposed four-moduli sets {2ⁿ - 1,2ⁿ,2ⁿ + 1,2ⁿ+1 - 1} and {2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2ⁿ+1 + 1} are described. The reverse conversion in the three-moduli set {2ⁿ - 1,2ⁿ,2ⁿ + 1} has been optimized in literature. Hence, the proposed converters are based on two new moduli sets {(2ⁿ(2²ⁿ-1)),2ⁿ⁺¹-1} and {(2ⁿ(2²ⁿ-1)), 2ⁿ⁺¹+1} and use mixed radix conversion. The resulting designs do not require any ROM. Both are similar in their architecture except that the converter for the moduli set {2ⁿ - 1, 2ⁿ, 2ⁿ + 1, 2ⁿ+1 + 1} is slightly complicated due to the difficulty in performing reduction modulo (2ⁿ⁺¹+1) as compared with modulo (2ⁿ⁺¹-1). The proposed conversion techniques are compared with earlier realizations described in literature with regard to conversion time as well as area requirements.     

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.     

Fast conversion between binary and residue numbers

New, efficient hardware implementations are considered which perform code conversions between the three moduli (2ⁿ-1, 2 ⁿ, 2ⁿ+1) residue number systems and their binary representations. Significant hardware saving together with high-speed throughput is achieved by using only n and (n+1)-bit binary adders     

Generalized Kasami Sequences: The Large Set

In this correspondence, new binary sequence families F^k of period 2ⁿ-1 are constructed for even n and any k with gcd(k,n)=2 if n/2 is odd or gcd(k,n)=1 if n/2 is even. The distribution of their correlation values is completely determined. These families have maximum correlation 2^n/2+1 and family size 2^3n/2 + 2^n/2 for odd n/2 or 2^3n/2+2^n/2-1 for even n/2. The proposed families include the large set of Kasami sequences, where the k is taken as k=n/2+1.     

A New Family of Ternary Almost Perfect Nonlinear Mappings

A mapping f(x) from GF(pⁿ) to GF(pⁿ) is differentially k-uniform if k is the maximum number of solutions x isin GF(pⁿ) of f(x+a) - f(x) = b, where a, b isin GF(pⁿ) and a ne 0. A 2-uniform mapping is called almost perfect nonlinear (APN). This correspondence describes new families of ternary APN mappings over GF(3ⁿ), n>3 odd, of the form f(x) = ux^d + x^{d 2} where d₁ = (3^n-1)/2 - 1 and d₂ = 3ⁿ - 2.     

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.

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.     

2n modified prime codes for use in fibre optic CDMAnetworks

2ⁿ modified prime codes are designed for all-optical code-division multiple access (CDMA) networks using very simple encoders and decoders. The proposed code is obtained from an original 2ⁿ prime code of prime number P. By padding P-1 zeros in each `subsequence' of codewords in the corresponding 2ⁿ prime code. The cross-correlation constraint of the resulting 2ⁿ modified prime code is equal to one, as opposed to two for a 2ⁿ prime code. For a given bit error rate (BER), the proposed code can thus be used to support a larger number of active users in the fibre optic CDMA network than a 2ⁿ prime code. Moreover, using the former can also reduce code length and weight compared with employing the latter to achieve the same BER     

Adder based residue to binary number converters for(2n-1, 2n, 2n+1)

Based on an algorithm derived from the new Chinese remainder theorem I, we present three new residue-to-binary converters for the residue number system (2ⁿ-1, 2ⁿ, 2ⁿ+1) designed using 2n-bit or n-bit adders with improvements on speed, area, or dynamic range compared with various previous converters. The 2n-bit adder based converter is faster and requires about half the hardware required by previous methods. For n-bit adder-based implementations, one new converter is twice as fast as the previous method using a similar amount of hardware, whereas another new converter achieves improvement in either speed, area, or dynamic range compared with previous converters     

Fast Bit Parallel-Shifted Polynomial Basis Multipliers in GF(2n)

A new nonpipelined bit-parallel-shifted polynomial basis multiplier for GF(2ⁿ) is presented. For some irreducible trinomials, the space complexity of the multiplier matches the best results available in the literature, and its gate delay is equal to T _A+lceillog₂nrceilT_X, where T_A and T_X are the delay of one two-input and and xor gates, respectively. To the best of our knowledge, this is the first time that the gate delay bound T_A+lceillog₂nrceilT_X is reached. For some irreducible pentanomials, its gate delay is equal to T_A +(1+lceillog₂nrceil)T_X. NIST has recommended five binary fields for the elliptic curve digital signature algorithm applications: GF(2¹⁶³), GF(2²³³), GF(2 ²⁸³), GF(2⁴⁰⁹), and GF(2⁵⁷¹), but no irreducible trinomials exist for three degrees, viz., 163, 283 and 571. For the three corresponding binary fields, we show that the gate delay of the proposed multiplier is T_A+(1+lceillog₂nrceil)T_X. This result outperforms the previously known results     

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.     

Groups of algebraic integers used for coding QAM signals

Linear block codes over Gaussian integers and Eisenstein integers were used for coding over two-dimensional signal space. A group of Gaussian integers with 2²ⁿ elements was constructed to code quadrature amplitude modulation (QAM) signals such that a differentially coherent method can be applied to demodulate the QAM signals. This paper shows that one subgroup of the multiplicative group of units in the algebraic integer ring of any quadratic number field with unique factorization, modulo the ideal (Pⁿ), can be used to obtain a QAM signal space of 2p^2n-2 points, where p is any given odd prime number. Furthermore, one subgroup of the multiplicative group of units in the quotient ring Z[ω]/(pⁿ) can be used to obtain a QAM signal space of 6p^2n-2 points; one subgroup of the multiplicative group of units in the quotient ring Z[i](pⁿ) can be used to obtain a QAM signal space of 4p^2n-2 points which is symmetrical over the quadrants of the complex plane and useful for differentially coherent detection of QAM signals; the multiplicative group of units in the quotient ring Z[ω]/(2ⁿ) can be used to obtain a QAM signal space of 3·2^2n-2 points, where i=√-1, ω=(-1+√-3)/2=(-1+i√3)/2, p is any given odd prime number, Z[i] and Z[ω] are, respectively, the Gaussian integer ring and the Eisenstein integer ring. These multiplicative groups can also be used to construct block codes over Gaussian integers or Eisenstein integers which are able to correct some error patterns     

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

Radix-2 FFT-pipeline architecture with reduced noise-to-signalratio

A radix-2 FFT-pipeline architecture has been developed which exhibits a two- to three-bit increase in accuracy for transform lengths N greater than 2¹⁰ if fixed-point arithmetic is utilised. The algorithm in use is a unification of the Cooley-Tukey radix-4 and radix-4+2 decompositions     

New algorithm for r-dimensional DCT-II

The paper shows that the type-II r-dimensional discrete cosine transform (rD-DCT-II) of size q^l1×q^l2x...xq ^l1, where r>1 and q is an odd prime number, can be converted into a series of one-dimensional reduced DCT-IIs by using the polynomial transform. The number of multiplications for computing an rD-DCT-II is significantly reduced compared to that needed by the row-column method. The total number of arithmetic operations (additions plus multiplications) needed by the proposed algorithm is also reduced substantially. In addition to the capability of dealing with different dimensional sizes, the proposed algorithm also has a simple computational structure because it requires only the 1D-DCT-II and the polynomial transform     

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.