1st Edition

Multiple-Base Number System Theory and Applications

    294 Pages 11 Color & 110 B/W Illustrations
    by CRC Press

    302 Pages 11 Color & 110 B/W Illustrations
    by CRC Press

    294 Pages 11 Color & 110 B/W Illustrations
    by CRC Press

    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.

    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

    Biography

    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.