Multiple-Base Number System: Theory and Applications

Series:
Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
ISBN 9781439830468
Cat# K11497

$146.95

$117.56

SAVE 20%


eBook (VitalSource)
ISBN 9781439830475
Cat# KE11382

$146.95

$102.87

SAVE 30%


eBook Rentals

Other eBook Options:
 

Features

  • Explores everything from theory to practical applications of both DSP and cryptography
  • Offers flexible and easily applicable ideas for implementing a wide range of cryptographic protocols
  • Illustrates new and efficient hardware design concepts for DSP engineers, focusing on the new MBNS and associated theory and applications
  • Presents the latest research in very-high-performance DSP architectures and very efficient computations in cryptography
  • Provides a large number of challenging mathematical and algorithmic problems
  • Includes an introduction, summary, and references in each chapter

Summary

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.

Table of Contents

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

Author Bio(s)

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.