A methodology for incorporating Polynomial Residue Arithmetic (PRA) in the Montgomery multiplication algorithm for polynomials in GF(2n) is presented in this paper. The mathematical conditions that need to be satisfied, in order for this incorporation to be valid are examined and performance results are given in terms of the field characteristic n, the number of moduli elements L, and the moduli word-length w. The proposed architecture is highly parallelizable and flexible, as it supports Polynomial-to-PRA and PRA-to-Polynomial conversions, Chinese Remainder Theorem (CRT) for polynomials, Montgomery multiplication, and Montgomery exponentiation in the same hardware.

A novel approach for the reduction of the power dissipated in a signal processing application is introduced in this paper. By exploiting the properties of the Polynomial Residue Number System (PRNS) and of the arithmetic modulo (2n+1), the power dissipation of implementing cyclic convolution is reduced up to four times. Furthermore, the corresponding power x delay product is reduced up to 2.4 times, while a simultaneous reduction of area cost is achieved. The particular performance improvement becomes possible by introducing a way to minimize the forward and inverse conversion overhead associated with PRNS. The introduced minimization exploits the fact that for the conversions for particular lengths of data sequences and particular moduli, only multiplications with powers of two and additions are required, thus leading to low implementation complexity. In addition multiple supply voltages are utilized to further reduce power dissipation by more than 30% for particular cases. Formulas that return the applicable supply voltage values per PRNS channel are derived in this paper.

The Residue Number System (RNS) is an integer system appropriate far implementing fast digital signal processors since it can support parallel, carry-free, highspeed arithmetic. In this paper a new RNS system and an efficient implementation of its residue-to-weighted converter are presented. The new RNS is a balanced 5-moduli system appropriate for large dynamic ranges. The new residue-to-binary converter is very fast and hardware-efficient and is based on a 1's complement multioperand adder adding operands of size only 80% of the size of the system's dynamic range.

New algorithms for computing convolutions and other multiplicative intensive signal processing functions are presented. These algorithms use squaring operations and additions but not two-operand multiplications. The squared law algorithms presented are extensions of the quarter squared and the one-over eight squared algorithms, and they are more powerful and more hardware efficient than them. They are appropriate for modular and residue arithmetic and rely on ROM lookup tables for computing the squaring operations. Since the ROM performing the squaring operation is at the heart of the new techniques, the author presents some memory compression schemes for minimizing the size of such lookup table ROMs.>

Techniques for computing the product of two N-bit integers modulo 2/sup N/-1 from their k-bit byte decompositions are presented. A modulus 2/sup N/-1 is chosen, as multiplication performed in this modulus can be reconstructed from the cyclic convolution between the sequences of the k-bit bytes of the decomposed numbers. It is shown that cyclic convolutions can be computed using only additions and squaring operations but not two-operand multiplications. Since the squaring operation is a one-operand operation, significant savings in ROM bits can be obtained if look-up tables are used.>

A method for complex multiplication that relies on encoding 2n-bit complex numbers as polynomials of degree 7 in the ring of polynomials modulo x/sup 8/-1 with n/4-bit coefficients is introduced. Complex multiplication can then be performed with an 8-point cyclic convolution plus some conversion overhead and, with care, this can be done without introducing any errors. The technique is suitable for designs using systolic arrays.>

Pipelined structures based on the residue number system (RNS) have been found suitable for high-speed arithmetic. The polynomial RNS (PRNS) can speed up digital signal processing (DSP)-related tasks like correlations and convolutions. The authors introduce pipelined arrays able to serve as mapping modules for PRNS-based functional units. Such mappings, involve polynomial evaluation coupled with modulo operations. The authors show how VLSI array processors can perform modulo operations in a parallel environment. A methodology is presented by which the reliability of such fast architectures can be ensured simply by probing into the mechanics of the computations involved. The proposed techniques provide a hardware base for PRNS implementations. At the same time, a reasonable degree of fault-tolerance can be guaranteed in the face of high system throughputs.>

The design of a high-speed complex signal processor is presented. It is based on a novel multiplier whose hardware implementation is shown to be characterized by simplicity, a high degree of parallelism, regularity, and modularity. The multiplier design is made possible by recent advances in the theory of performing polynomial multiplication in modular rings with reduced complexity. This latter development is based on the polynomial residue number system (PNRS). While traditional parallel complex multiplication requires four real multiplications, the proposed scheme is based on decomposing the process into eight smaller concurrent processes. If p is the performance of each of the four processors of the traditional technique and h is the investment in hardware required for its realization, the performance of each of the processors of the proposed method is 4p and its hardware investment is h/16.>

The authors discuss the mathematical basis and hardware implementations of large-word length multipliers (mod 2/sup n/+or-1). The focus is on a recently developed parallel arithmetic system named the polynomial residue-number system (see A. Skavantzos, 1987). The proposed multipliers allow a variety of implementation options and are shown to have much better performance than multipliers based on traditional techniques. The performance improvement is most obvious in multiplication-intensive environments.>

In the recent past, several papers have been published on the subject of performing complex arithmetic in the Residue Number System (RNS). These papers introduced the Quadratic Residue Number System (QRNS) which is, in fact, a Multidimensional RNS of order 2. These papers demonstrated that a complexity savings of more than 50% can be achieved for the operation of a complex multiply and that higher throughputs can result. Extensions of this concept are presented and are based on polynomial rings which reduce the number of multiplies to Winograd's lower bound. The conditions under which this can be achieved are theoretically developed and examples are given. The newly developed system which will be called Multidimensional Residue Number System is compared to the QRNS from the standpoint of speed and amount of hardware.

Recent advancements in residue arithmetic have given rise to a complex number system variant which better than halves RNS multiplication complexity. This advantage is applied to the problem of implementing a high-speed radix-4 RNS FFT. It is shown that a significant improvement in both complexity and speed can be achieved.