Multidimensional Logarithmic Number System:Multidimensional Representations

Introduction

The logarithmic number system (LNS) [1–3] is an alternative to the binary representation and it has been a subject of some investigation [4,5], particularly in the field of digital signal processing (DSP) [6,7], where the computation of inner (dot) products is a major computational step. In the LNS, multiplication and division are easy operations, whereas addition and subtraction are difficult operations, traditionally imple- mented by making use of large ROM arrays [8,9] or other techniques [10,11]. It has been recognized that LNS architectures are perfectly suited for low-power, low-precision DSP problems.

Inner products computed in DSP algorithms are often between a predetermined set of coefficients (e.g., Finite Impulse Response (FIR) filters or discrete transform basis functions) and integer data. For fixed-point binary implementations, the uniform quantization properties are perfectly matched to the mapping of most input data (the mapping of input data for nonlinear hearing instrument processing is a counterexample), but often the predetermined coefficients are better suited to a nonuniform quantization mapping. A study of a large number of filter designs reveals a histogram that benefits from the quantization associated with a logarithmic mapping [12].

A logarithmic-like representation, referred to as the index calculus double-base number system (IDBNS), that promises implementation improvements over the LNS while maintaining a logarithmic quantization distribution was previously introduced [13] and there have been several papers published on special results from this number representation [14–20].

In this chapter we will generalize the LNS number system and present several results that demonstrate the efficiencies in using this representation over the classical LNS for typical DSP computations. We will also detail the hardware used to perform mapping from binary to the multidimensional logarithmic number system (MDLNS) along with implementation examples that demonstrate the efficiencies of using the MDLNS.

Multidimensional Representations

The IDBNS is based on a single-digit representation of the form

We may therefore approximate, to arbitrary precision, every real number with the triple {s, a, b}. We may look at this representation as a two-dimensional generalization of the binary logarithmic number representation. The important advantage of this generalization in multiplication is that the binary and ternary indices are operated independently from each other, with an attendant reduction in complexity of the implementation hardware. As an example, a very large-scale integration (VLSI) architecture for inner product computation with the IDBNS, proposed in Refs. [14,15,20], has an area complexity dependent entirely on the dynamic range of the ternary exponents. Provided the range of the ternary exponent is smaller than the LNS dynamic range for equivalent precision, we have the potential for a large reduction in the IDBNS hardware compared to that required by the LNS. We can capitalize on this potential improvement by placing design constraints on the ternary exponent size. For example, if we want to represent digital filter coefficients in the IDBNS, then we can design the coefficients in such a way that the ternary exponent is minimized, an integer programming task [16,20]. Although this approach is sound, and can produce modest improvements, we can do better. In fact, the complexity of the architecture does not depend on the particular choice of the second base. Therefore, one may attempt to find a base, x , (or set of bases) such that the filter coefficients can be very well approximated of the form s2a x b, while keeping b (the nonbinary exponent) as small as possible.

We begin with a review of the necessary mathematical preliminaries, followed by a discussion of the nature of input data mapping by explaining both the error and nonerror-free representations using the MDLNS. We continue with information about the approximations to unity which play an important role in constraining the dynamic range of the exponents for calculations. Then, we discuss hardware complexity which includes an explanation of the single-digit computation unit (CU) followed by a generalization to an n-digit CU. We then demonstrate a filter design using MDLNS and provide an example where we can see which different bases (selected and optimal) can impact the physical imple- mentation complexity. Finally, we show some fabricated MDLNS DSP inner-product computational unit designs and summarize the main results.

Mathematical Preliminaries

There are some well-established results on s-integers that we can build upon. We start with two basic definitions [21].

Definition 84.1

An s-integer is a number whose largest prime factor does not exceed the sth prime number.

For example, nonnegative powers of 2 are 1-integers; numbers of the form 2a3b where a,b are nonne- gative integers, are 2-integers, and so on.

Modified 2-integers are numbers of the form 2apb where p is an odd integer.

Note that we do not impose restrictions on the signs of a and b in Definition 84.2.

The next definition offers the most general representation scheme we will consider in this chapter.

A representation of the real number x in the form are integers, is called a multidimensional n-digit logarithmic (MDLNS)

representation of x. b is the number of bases used (at least two, the first one, that is, p1, will always be assumed to be 2).

The next two definitions are special cases of Definition 84.3; the representation schemes defined by them will be used extensively in the chapter.

An approximation of a real number x as a signed modified 2-integer s2a pb is called a two-dimensional logarithmic representation of x.

An approximation of a real number x as a sum of signed modified 2-integers ån s 2ai

two-dimensional logarithmic representation of x. n = 2 will It is important to note that an extension of the classical LNS to a multidigit (or multicomponent) representation does not provide any inherent advantages in terms of complexity reduction. Arnold et al. [4] were the first to consider a similar representation scheme in the case of classical LNS (we shall call it a 2-component LNS). Although it leads to some reduction of the dynamic range of the exponents (correspondingly, a reduction of the ROM sizes), the number of bits required by the larger exponent to store the integer number, x , is approximately log(x). The storage reduction in the 2-component LNS (as opposed to the 1-component LNS) comes from the observation that in the 1-component LNS one needs approximately log2(x) + log2(log(x)) bits to encode x.

We will demonstrate that hardware complexity for the MDLNS is exponentially dependent on the size of the nonbinary-base(s) exponents; we clearly have a potential for quite a considerable hardware reduction provided that the dynamic range of the non-binary exponents is reduced as much as possible.