Multiple-Base Number System

Theory and Applications

Vassil Dimitrov, Graham Jullien, Roberto Muscedere

• Publisher: CRC Press
• Year: 2017
• Print ISBN: 9781439830468
• eBook ISBN: 9781351833660
• Edition: 1
• Topic: Computer Science
• Subtopic: Cryptography
• Index: Computer Science

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.

1

Technology, Applications, and Computation

1.1 Introduction

The field of computer arithmetic is a fascinating subject, and not at all the drudgery that most of us experienced with our first exposure to the third r of the three r’s at school. The first two r’s are related as requirements of the processes required to become literate. The third r relates to numeracy, the understanding and implementation of computation which is a basic requirement for “technical literacy,” as important a skill in today’s world as was traditional literacy in the past. In this introductory chapter, we provide a brief history and introduction to number systems and machine calculation; we emphasize special applications that drive the search for efficient machine arithmetic given the requirements of the applications and the available technology.

1.2 Ancient Roots

Ancient numbering systems abound, but the most striking is the system developed by the Babylonians starting around 5,000 years ago. It is striking in that it is a form of weighted positional system, which we use today. However, the Babylonians did not have a symbol for zero (instead they used a space) and the weighting was based on the number 60 rather than the number 10, which we use today for representing decimal numbers. (Vestiges of the weight 60 can still be found in the way we measure time and angles.) It also appears that the binary number system, which we naturally think of as being introduced with the advent of electronic computers built with logic gates, was used at least 4,000 years ago for determining weights using a simple balance and carefully weighed stones [1].

1.2.1 An Ancient Binary A/D Converter

We can imagine a trader from 4,000 years ago by the side of a river, setting up a balance and then searching for a handful of river-washed pebbles that had specific weight characteristics. These characteristics were determined from the simple operation of producing a balance between sets of stones. The technology used here was based only on the force of gravity using a balance bar and fulcrum. The operation is demonstrated in Figure 1.1 for an equivalent 4-bit representation (1–15 times the smallest stone weight). The accuracy of the number system is determined by the accuracy with which the stones were selected and correctly balanced (including positioning the stones so that their accumulated center of gravity was always in the same position on the opposite sides of the balance). The relative weights of the stones in the full measurement set are shown in Figure 1.1 as {1, 1, 2, 4, 8}. Designers of binary-weighted digital/analog converters (D/As) know this sequence well! Such a D/A converter can be used to implement a successive approximations A/D converter. The two 1’s are redundant in terms of a 4-bit measurement system, only being required to generate the full measurement set. In a sense, the traders of 4,000 years ago had also built an A/D converter in which an analog commodity weight was converted into a subset of stones from the full measurement set.

FIGURE 1.1
(See color insert)
Four-thousand-year-old binary number system.

1.2.2 Ancient Computational Aids

Computational aids and calculators also have ancient roots. Counting boards (a precursor of the “more modern” abacus using beads) have been used for several thousand years [2], with some evidence that they were initially developed by the Romans. Of some surprise, an astronomical prediction machine, circa 200 BC, was recovered from an ancient shipwreck off the Greek island of Antikythera in 1901. This mechanism was truly advanced based on the fact that mechanical calculators of similar complexity did not appear again (or, at least, have not been found) for at least another 1,500 years. Based on an analysis of CT scans of the components [3], the calculator used a variety of sophisticated precision gears, each with up to several hundred teeth, along with epicyclic gearing. The mechanism was able to compute addition, subtraction, and multiplication with precise fractions and, for example, could predict the position of the moon based on models available at the time.

1.3 Analog or Digital?

Over the past five centuries the interest in computational aids and calculating machines has steadily increased, with an explosive growth over the past 100 years, driven by mechanical devices, electromechanical devices, and electronics.

Mechanical and electromechanical devices were based on decimal arithmetic because of the need to interact with human operators. Some of the early electronic computers also used the decimal-based number systems for the same reason, even though the two-state property (0, 1) of signal propagation into and out of computer logic circuits provides a perfect match with pure binary number representations. Until the latter part of the 20th century, analog devices were also heavily used for advanced mathematical computations, such as finding solutions of nonlinear differential equations, where a physical quantity (e.g., voltage in electronic circuits or rotation in mechanical systems) is observed as the solution to a problem. In this case there is no implied number system, only that of the operator in interpreting the analog results. Analog systems have a relatively large computational error (several percent) compared to the much higher precision capable of digital machines, but there were application areas found for both analog and digital machines. We will discuss an analog method of computing with a double-base system in Chapter 3.

Examples of applications that took advantage of the disparity in complexity and error between analog and digital mechanisms are ideally portrayed in comparing Lord Kelvin’s analog tide prediction machine [4] to Babbage’s digital difference engine [5]; they were proposed within a few decades of each other in the 19th century.

1.3.1 An Analog Computer Fourier Analysis Tide Predictor

The tide predictor computed the heig...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• About the Authors
• 1. Technology, Applications, and Computation
• 2. The Double-Base Number System (DBNS)
• 3. Implementing DBNS Arithmetic
• 4. Multiplier Design Based on DBNS
• 5. The Multidimensional Logarithmic Number System (MDLNS)
• 6. Binary-to-Multidigit Multidimensional Logarithmic Number System Conversion
• 7. Multidimensional Logarithmic Number System Addition and Subtraction
• 8. Optimizing MDLNS Implementations
• 9. Integrated Circuit Implementations and RALUT Circuit Optimizations
• 10. Exponentiation Using Binary-Fermat Number Representations
• Index