High Speed VLSI Architecture for 2 Scaling of Signed Integer in RNS
Residue Number System (RNS) is a non weighted robust number system that is capable of mapping large numbers to smaller residues. This allows arithmetic operations of long integers to be carried out without any need for carry propagation. Scaling of signedintegers in RNS is a problematic and relatively difficult operation which leads to performance bottleneck while implementing signal processing algorithms. But when scaling of an integer is performed by one of its moduli, the complexity of intermodulo operation can be greatly reduced. This paper proposes an efficient architecture signed integer RNS scaler for the moduli set {21,2,2+1} The architecture is implemented by employing the number theoretic properties of the moduli set {2 1, 2, 2+1} The proposed RNS scaler possesses zero scaling error because of the additional merged sign detection and correction circuit which eliminates the ambiguities present in scaling the signed integers and is also faster compared to the existing works. Index Terms Chinese Remainder Theorem,residue number system,scaling, moduli set, signed integar. 1. INTRODUCTION Sophisticated real time application specific digital signal processing(DSP) algorithms are widely used in modern electronic gadgets such as digital cameras, smart phones, camcorders etc. Residue number system (RNS) plays a very crucial role in this domain for mapping complex signal processing algorithms into application specific hardware accelerators. This is due to the fact that RNS is capable of decomposing any long integer arithmetic operations such as addition, subtraction, and multiplication into smaller carry free modulo operations for parallel processing [1] Thus RNS proves to be a promising alternative for the conventional two's complement number system for computation and data representation purposes. Since RNS has greater advantages compared to two's complement system and other conventional full adder implementations, RNS has been extensively used to implement the filter components in DSP and Very Large Scale Integration(VLSI) systems [2] and for solving precise systems using a low resolution multimoduli system[3] Though RNS has many advantages such as modularity, parallelism, and localized carry propagation arithmetic operations, it has some drawbacks such asRNS to binary conversion, magnitude scaling, overflow detection, sign detection, and parity detection [3] The most erroneous ambiguities occur during reverse conversion of an integer from its residue number representation, and while performing scaling of an integerby a known constant [3] [5] This paper presents an architecture that can perform scaling for signed integers. This design performs error correction of residues for negative numbers and when simulated in the Xilinx environment, the results show that the proposed architecture is faster and occupies less area compared to the existing works. 2. BACKGROUND MATERIAL 2.1 Residue Number System(RNS) Residue Number System (RNS) has its origination in the ancient Chinese mathematical book "Sun Zi Suan Jing" As mentioned earlier, RNS decomposes any long integers into a set of small residues, thereby reducing the carry chain length of adders and the size of multipliers. A residue number is characterized by k tuple of integer setP {p1,p2,p3, pk Each of this pi is called modulus and P is called moduli set. Let M be product of all elements of set P. A number X in decimal number system can be represented as {x1,x2,x3, xk where xi=X mod pi. This unique representation is applicable if X<M and if all elements of P are relatively prime to each other [7] Residue arithmetic operation of two numbers X1 and X2 is defined by: (Y1,Y2, Yn)(X11, X12, X1n)(X21, X22, X2n) (1) Suppose X1 and X2 are two different numbers with the same moduli set P. Then, X1 |p1 X 2| p2and so X 1 X 2|pi 0. Hence, X1 and X2 are the least common multiple (LCM) of pi. But if the elements of set P are relatively prime, then their LCM is M, and it must be that X1 and X2 is a multiple of M. So it cannot be that X1< M and X2< M. Therefore, the set |X|mi: 1< i<=N} is unique and can be a mathematical representation of X. In RNS, arithmetic operations such as addition, subtraction, and multiplication are inherently carry free[4] [5] Since each digit of the result is a function of only one digit of each operand, the computational complexity is reduced to a greater extent and the desired operation is performed in minimal time.Whenever the input integar X is a positive number, its range is [0, M 1] On the other hand, when the integer X is a non positive number, its dynamic range is M/2,M/2 1] International Journal of Advent Research in Computer and Electronics (IJARCE) Vol. 2, No. 8, August 2015 E ISSN: 2348 5523 7 2.2 Chinese Remainder Theorem Assume two positive numbers, x (the dividend) and y (the divisor) Now x modulo y (abbreviated as x (mod n) can be thought of as the remainder, on division of x by y. suppose we have the system of equations: X x1 mod m1 X x2 mod m2 X xnmod mn, where M={m1, m2, m3..mk} (2) This can be constructed from the formula: (3) Where, Mi= for 1 i n and |Mi| represents the inverse of Mi modulo mi The dynamic range of the chosen moduli set {m1, m2, m3. mn is given by the following relation: M= mi i (4) CRT states: If each pair of moduli mi and mj are relatively prime, where{i, j N,i j} then the equations have a solution and any two solutions are congruent i.e. the solution is unique when mi and mj are co prime and their greatest common divisor (GCD) is 1[2] Thus according to CRT, the integer X is related to its residues by the following relation: X= Mi i |Mi 1|mixi|M (5) where Mi .The Chinese Remainder Theorem (CRT) may be stated as one of the most important fundamental results in the theory of RNS as it solves the residue to binary conversion problem[5] 3. CHOICE OF MODULI SET There are many moduli sets such as {2 1, 2, 2+1} {2 1, 2, 2+1, 2+1}{2 1, 2, 2+1, 2+1} etc. The proposed system uses (2 1, 2, 2+1) as the desired moduli set.The moduli set {2 1,2,2+1} is superior to other moduli sets because it offers simple reverse conversion method from residues to binary number representation, thereby reducing the hardware complexity at the latter stages of the scaler[11] Another important feature of the moduli set {2 1, 2, 2+1} is that the delay is determined only by the modulo 2+1 channel because of the operand length of these moduli.In other words, if we reduce the time required for 2+1 addition, we can easily cut down the overall delay of the RNS system[16].The moduli set{2 1, 2, 2+1} allows easy conversion because of the presence of very efficient combinational converters from/to the binary system. Modulo 2+1 channel handles n+1 bit input because of the Diminished One modulo arithmetic representation of the input, whereas modulo 2 1 and 2channels handle only n bit input operands[7] [10] The complexity faced in implementing modulo 2+1 channel is reduced using Diminished One modulo arithmetic which can be implemented by either Circular Carry Selection scheme or the Parallel Prefix scheme. 4. UNSIGNED AND SIGNED INTEGARS An RNS is defined by a set of N pairwise relatively prime integers{m1,m2,,mN ,where mi is called a modulus. An unsigned integer X within the range of [0, M 1] can be uniquely represented by an N tuple {x1,x2,,xN} The residue xi is the least positive remainder of the division of X by mi and is usually represented as X mod mi or |X|mi .Let be a signed integer in the range M/2,M/2 1] if M is even, or in the range (M 1)/2,(M 1)/2] if M is odd. X' can also be uniquely represented by an N tuple in signed RNS representation. The relationship between the residue representations of X in unsigned RNS and in signed RNS under the same moduli set is =X if 0and X M if <0 (6) When =0, the residue representation of X can be mapped to that of in the range [0, M/2 1] if M is even, or in the range [0, (M 1)/2] if M is odd. When 0, the residue representation of X can be mapped to that of in the range [M/2, M 1] if M is even, or in the range (M 1)/2, M 1] if M is odd.After further research into the mathematical background of RNS, the valid RNS scaler was designed by utilizing the moduli set {2 1, 2, 2+1} and the scaling factor used was 2. 5. PROPOSED SIGNED INTEGAR SCALING ALGORITHM 5.1 Scaling of Signed Integars