Skip to main content
main-content

Über dieses Buch

There has been continuing interest in the improvement of the speed of Digital Signal processing. The use of Residue Number Systems for the design of DSP systems has been extensively researched in literature. Szabo and Tanaka have popularized this approach through their book published in 1967. Subsequently, Jenkins and Leon have rekindled the interest of researchers in this area in 1978, from which time there have been several efforts to use RNS in practical system implementation. An IEEE Press book has been published in 1986 which was a collection of Papers. It is very interesting to note that in the recent past since 1988, the research activity has received a new thrust with emphasis on VLSI design using non­ ROM based designs as well as ROM based designs as evidenced by the increased publications in this area. The main advantage in using RNS is that several small word-length Processors are used to perform operations such as addition, multiplication and accumulation, subtraction, thus needing less instruction execution time than that needed in conventional 16 bitl32 bit DSPs. However, the disadvantages of RNS have b. een the difficulty of detection of overflow, sign detection, comparison of two numbers, scaling, and division by arbitrary number, RNS to Binary conversion and Binary to RNS conversion. These operations, unfortunately, are computationally intensive and are time consuming.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
The origin of the topic RNS [Gar59] is credited to the Chinese scholar Sun Tzu of first Century AD and Greek Mathematician Nichomachus and Hsin-Tai-Wei of the Ming dynasty (1368AD–1643AD). Later, Euler presented a proof for the Chinese Remainder Theorem (CRT) in 1734. In the twentieth Century, Lehmer, Svoboda and Valach built hardware using RNS and much work was done at various laboratories during 1950’s and 1960’s. The text books by Szabo and Tanaka [Sza67] and Watson and Hastings [Wats67] in 1967 are the first documenting the results in this area. Subsequently, in 1977, resurgence of interest in this area was due to the pioneering work of Jenkins and Leon [Jenk77]. By 1980, interesting results were available in all areas of RNS such as residue Number scaling, RNS to Binary conversion, Binary to RNS conversion, scaling and error correction. These are largely due to the research of Soderstrand, Miller, Jullien, Jenkins, Leon among others. These early designs were mostly ROM based. The advent of VLSI technology has stimulated the work in the area of non-ROM based solutions. This led to work on special moduli sets. It is interesting to note that the computational speed has been increasing and excellent solutions have been evolving even as recently as December 2000.The work carried our till 1986 was compiled in an IEEE Press collection of papers [Sode86]. The reader is referred to an excellent historical introduction to this subject in this book.
P. V. Ananda Mohan

2. Forward and Reverse Converters for General Moduli Sets

Abstract
In this Chapter, the topic of RNS to binary conversion for the general moduli set is considered in detail. There are basically two techniques for RNS to Binary Conversion, one based on Mixed Radix Conversion and another based on Chinese Remainder Theorem (CRT). Several architectures using ROMs as well as not using ROMs have been described in literature. The choice of these techniques is decided by the RNS to Binary and Binary to RNS conversion speeds as well as the area needed for implementation. The discussion in this Chapter excludes specialized three moduli sets which will be discussed in the next Chapter in detail. The binary to RNS conversion also can be realized in several ways which are also considered in detail in this Chapter.
P. V. Ananda Mohan

3. Forward and Reverse Converters for The Moduli Set {2k-1, 2k, 2k+1}

Abstract
The particular three moduli set {2k-1, 2k, 2k+1} has received considerable attention in literature, since this moduli set offers considerable ease in forward and reverse conversion, scaling and other operations [Anan00b]. In this Chapter, VLSI architectures for forward and reverse conversion are discussed in detail. Related moduli sets {2k-1, 2k, 2k-1-1}, {2n, 2n+1, 2n-1} and {2n, 2n+1, 2n+2} also will be considered.
P. V. Ananda Mohan

4. Multipliers For RNS

Abstract
The design of RNS based signal processors needs invariably multipliers. Much attention has been paid to the topic of design of modulo multipliers as they have application in other areas such as Cryptography as well. The realization of multipliers could be using ROMs or could be without ROMs. Both these approaches will be studied in detail in this Chapter.
P. V. Ananda Mohan

5. Base Extension, Scaling and Division Techniques

Abstract
Division is an important operation in DSP applications such as filtering. Division by a constant is denoted as scaling. Scaling can usually be by one of the moduli or product of few moduli in a chosen RNS. Once scaling is done in the reduced moduli set, it is necessary to find the residues of the scaled value with respect to the scaling moduli. This operation is known as base extension. Thus, scaling and base extension need to be done together. Several techniques have been suggested in literature for this purpose which will be considered in detail in this Chapter. We first deal with base extension and then discuss scaling in the following sections.
P. V. Ananda Mohan

6. Error Detection and Correction in RNS

Abstract
Error detection and correction in RNS has received considerable attention in literature. This was considered to be necessary in ROM based designs where some faults may occur which may be corrected by reconfiguring or bypassing the faulty device using additional residues corresponding to additional moduli. These additional moduli are termed as redundant moduli. The errors evidently can occur in the residues or redundant residues. These redundant residues are mandatory for error detection and correction. Techniques for error detection and correction are considered in detail in this Chapter. The possibility of scaling and residue error correction in a single hardware also is considered.
P. V. Ananda Mohan

7. Quadratic Residue Number Systems

Abstract
Complex signal processing can be handled by RNS in a manner similar to standard complex number operations such as addition, subtraction, multiplication etc. However, under certain special cases of choice of moduli, the complete decoupling of computation of real and imaginary parts of the result is feasible. Nussbaumer [Nuss76] suggested that Fermat primes of the type 4k+l have this property. Later, this advantage has been extended to any primes of the type (4k+l) using the Quadratic Residue Number System (QRNS) [Jull87, Jenk87, Kris86a]. The QRNS also has been shown to be applicable for composite numbers which have (4k+l) as a factor and also to the case of composite numbers having (22n+l) as a prime factor. The primary disadvantage of the QRNS is the restriction on the type of moduli. Another technique which allows any modulus but with increase in number of multiplications has also been found known as Modified Quadratic Residue Number System (MQRNS) [Sode84b]. This will also be discussed in detail in this Chapter.
P. V. Ananda Mohan

8. Applications of Residue Number Systems

Abstract
In this Chapter, some applications of Residue Number System described in literature are reviewed so as to illustrate the various possibilities. Specifically, Digital to Analog Converters, FIR filters, IIR filters, Adaptive filters, 2-D FIR filters and Digital Frequency Synthesis are considered.
P. V. Ananda Mohan

9. References

Without Abstract
P. V. Ananda Mohan

Backmatter

Weitere Informationen