Dimitrov / Jullien / Muscedere Multiple-Base Number System

Theory and Applications
1. Auflage 2012
ISBN: 978-1-4398-3047-5
Verlag: CRC Press
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 294 Seiten

Reihe: Circuits and Electrical Engineering

Computer arithmetic has become so fundamentally embedded into digital design that many engineers are unaware of the many research advances in the area. As a result, they are losing out on emerging opportunities to optimize its use in targeted applications and technologies. In many cases, easily available standard arithmetic hardware might not necessarily be the most efficient implementation strategy.

Multiple-Base Number System: Theory and Applications stands apart from the usual books on computer arithmetic with its concentration on the uses and the mathematical operations associated with the recently introduced multiple-base number system (MBNS). The book identifies and explores several diverse and never-before-considered MBNS applications (and their implementation issues) to enhance computation efficiency, specifically in digital signal processing (DSP) and public key cryptography.
Despite the recent development and increasing popularity of MBNS as a specialized tool for high-performance calculations in electronic hardware and other fields, no single text has compiled all the crucial, cutting-edge information engineers need to optimize its use. The authors’ main goal was to disseminate the results of extensive design research—including much of their own—to help the widest possible audience of engineers, computer scientists, and mathematicians.

Dedicated to helping readers apply discoveries in advanced integrated circuit technologies, this single reference is packed with a wealth of vital content previously scattered throughout limited-circulation technical and mathematical journals and papers—resources generally accessible only to researchers and designers working in highly specialized fields. Leveling the informational playing field, this resource guides readers through an in-depth analysis of theory, architectural techniques, and the latest research on the subject, subsequently laying the groundwork users require to begin applying MBNS.

Zielgruppe

Professionals and students in digital signal processing hardware and computation, cryptography, computer arithmetic, mathematics, and computer science, circuits and systems, communications, control.

Autoren/Hrsg.

Dimitrov, Vassil

Jullien, Graham

Muscedere, Roberto

Fachgebiete

• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Kryptologie, Informationssicherheit
• Technische Wissenschaften Elektronik | Nachrichtentechnik Nachrichten- und Kommunikationstechnik
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Zeichen- und Zahlendarstellungen
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen

Inhaltsverzeichnis

Technology, Applications, and Computation
Ancient Roots
Analog or Digital?
Where Are We Now?
Arithmetic and DSP
Discrete Fourier Transform (DFT)
Arithmetic Considerations
Convolution Filtering with Exact Arithmetic

The Double-Base Number System (DBNS)
Motivation
The Double-Base Number System
The Greedy Algorithm
Reduction Rules in the DBNS
A Two-Dimensional Index Calculus

Implementing DBNS Arithmetic
Arithmetic Operations in the DBNS
Conversion between Binary and DBNS Using Symbolic Substitution
Analog Implementation Using Cellular Neural Networks

Multiplier Design Based on DBNS
Multiplication by a Constant Multiplier
Using the DBNS
DBNS Multiplication with Subquadratic Complexity
General Multiplier Structure
Results and Comparisons
Some Multiplier Designs
Example Applications

The Multidimensional Logarithmic Number System (MDLNS)
The Multidimensional Logarithmic Number System (MDLNS)
Arithmetic Implementation in the MDLNS
Multiple-Digit MDLNS
Half-Domain MDLNS Filter

Binary-to-Multidigit Multidimensional Logarithmic Number System Conversion
Single-Digit 2DLNS Conversion
Range-Addressable Lookup Table (RALUT)
Two-Digit 2DLNS-to-Binary Conversion
Binary-to-Two-Digit 2DLNS Conversion
Multidigit 2DLNS Representation (n > 2)
Extending to More Bases
Physical Implementation
Very Large-Bit Word Binary-to-DBNS Converter

Multidimensional Logarithmic Number System: Addition and Subtraction
MDLNS Representation
Simple Single-Digit MDLNS Addition and Subtraction
Classical Method
Single-Base Domain
Addition in the Single-Base Domain
Subtraction in the Single-Base Domain
Single-Digit MDLNS Addition/Subtraction
Two-Digit MDLNS Addition/Subtraction
MDLNS Addition/Subtraction with Quantization Error Recovery
Comparison to an LNS Case

Optimizing MDLNS Implementations
Background
Selecting an Optimal Base
One-Bit Sign Architecture
Example Finite Impulse Response Filter
Extending the Optimal Base to Three Bases

Integrated Circuit Implementations and RALUT Circuit Optimizations
A 15th-Order Single-Digit Hybrid DBNS Finite Impulse Response (FIR) Filter
A 53rd-Order Two-Digit DBNS FIR Filter
A 73rd-Order Low-Power Two-Digit MDLNS Eight-Channel Filterbank
Optimized 75th-Order Low-Power Two-Digit MDLNS Eight-Channel Filterbank
A RISC-Based CPU with 2DLNS Signal Processing Extensions
A Dynamic Address Decode Circuit for Implementing Range Addressable Look-Up Tables

Exponentiation Using Binary-Fermat Number Representations
Theoretical Background
Finding Suitable Exponents
Algorithm for Exponentiation with a Low Number of Regular Multiplications
Complexity Analysis Using Exponential Diophantine Equations
Experiments with Random Numbers
A Comparison Analysis
Final Comments

Über Autor(innen)

Vassil S. Dimitrov earned a Ph.D degree in applied mathematics from the Bulgarian Academy of Sciences in 1995. Since 1995, he has held postdoctoral positions at the University of Windsor, Ontario (1996–1998) and Helsinki University of Technology (1999–2000). From 1998 to 1999, he worked as a research scientist for Cigital, Dulles, Virginia (formerly known as Reliable Software Technology), where he conducted research on different cryptanalysis problems. Since 2001, he has been an associate professor in the Department of Electrical and Computer Engineering, Schulich School of Engineering, University of Calgary, Alberta. His main research areas include implementation of cryptographic protocols, number theoretic algorithms, computational complexity, image processing and compression, and related topics.

Graham Jullien recently retired as the iCORE chair in Advanced Technology Information Processing Systems, and the director of the ATIPS Laboratories, in the Department of Electrical and Computer Engineering, Schulich School of Engineering, at the University of Calgary. His long-term research interests are in the areas of integrated circuits (including SoC), VLSI signal processing, computer arithmetic, high-performance parallel architectures, and number theoretic techniques. Since taking up his chair position at Calgary, he expanded his research interests to include security systems, nanoelectronic technologies, and biomedical systems. He was also instrumental, along with his colleagues, in developing an integration laboratory cluster to explore next-generation integrated microsystems. Dr. Jullien is a fellow of the Royal Society of Canada, a life fellow of the IEEE, a fellow of the Engineering Institute of Canada, and until recently, was a member of the boards of directors of DALSA Corp., CMC Microsystems, and Micronet R&D. He has published more than 400 papers in refereed technical journals and conference proceedings, and has served on the organizing and program committees of many international conferences and workshops over the past 35 years. Most recently he was the general chair for the IEEE International Symposium on Computer Arithmetic in Montpellier in 2007, and was guest coeditor of the IEEE Proceedings special issue System-on-Chip: Integration and Packaging, June 2006.

Roberto Muscedere received his BASc degree in 1996, MASc degree in 1999, and Ph.D in 2003, all from the University of Windsor in electrical engineering. During this time he also managed the microelectronics computing environment at the Research Centre for Integrated Microsystems (formally the VLSI Research Group) at the University of Windsor. He is currently an associate professor in the Electrical and Computer Engineering Department at the University of Windsor. His research areas include the implementation of high-performance and low-power VLSI circuits, full and semicustom VLSI design, computer arithmetic, HDL synthesis, digital signal processing, and embedded systems. Dr. Muscedere has been a member of the IEEE since 1994.