Multidimensional Logarithmic Number System:FIR Digital Filter and A Case Study

FIR Digital Filter: A Case Study

Choice of the Nonbinary Base

A closer look at the architecture of Figure 84.1 shows the following feature. Assume that we are working

with 2DLNS. In this case, we simply store the input data into the form input sample is stored as a combination of six integers (s1, a1, b1, s2, a2, b2). The multiplication between the input data and the filter coefficients is replaced by addition of the corresponding exponents with the result transformed to a binary representation by making use of a ROM table which stores an FP-like representation of the powers of the second base D. The area complexity depends almost entirely on the size of the nonbinary exponents, b1 and b2; therefore, our main goal in approximating the digital filter coefficients is to minimize as much as possible the size of the largest nonbinary exponents used while maintaining the design constraints. The actual value of D can be selected to optimize the imple- mentation without changing the overall complexity of the architecture; in fact, as we shall see, such an optimization offers a great potential for further reductions of the hardware complexity. It is also important to point out that D does not have to be an integer! While the expansion of the idea to noninteger bases leads to large theoretical hurdles (in terms of rigorous justification of the results obtained), it is equally clear that with this extension in hand one can vastly increase the chance to obtain an extremely good representation of the filter coefficients with very small exponents and only single-digit representations.

Limiting the Nonbinary Base

We can limit the potential range of what could be considered to be an optimal value by analyzing the unsigned single-digit representation as shown in the following equation:

This shows that we can multiply or divide the unknown base by the first base and not change the computational result; however, the exponent of the first base will change. This simple relationship implies a restriction on the range of values of an optimal base. For example, if our search were to begin at D = 3, then it would be pointless to go outside of the range 3–6 as the results of the representation would simply repeat.

The relationship in Eq. (84.23) also shows that as the value of D is reduced by a multiple of 2, the exponent of the first base will increase when b is positive, but decrease when b is negative. A similar conclusion can be made for the case when D is multiplied by 2. Therefore, some representations may have large values for the first base exponent, and some may have small values. For a VLSI implementation, the bit width of the first base exponent should be minimized while maintaining the selected representation space. We can determine the bit width for the first base exponent by limiting our representation with the following equation:

Since the range of b is known, the value of a can be found for all valid values of b, and so the integer range of a can be found from the maximum and minimum values of b. The binary word length of the usable 2DLNS range is added to the maximum integer range of a to find the total range of a. For example, if D = 3 and b ranges from -4 to 3 (4 bits), then the range for the first base exponent will be between -4 and 7. If we wish to represent a 9-bit integer, then we will require a range of [-4, (7 + 9 =16)] for the first base exponent or 6 bits.

We can also potentially reduce the number of bits required to represent a. From Eq. (84.26), the range of a is a function of the factor ln(D)/ ln(2) , therefore ln(D) is our target for minimization. Since the factor has a denominator of ln(2), any integer multiple, k of 2kD will produce the same double-base number system (DBNS) results. The function ln(D) will be minimized when D is the closest to 1. The optimal range optimal range for D that will provide a minimal bit width to represent the first base exponent, a.

If we rework our previous example using D = 0.75 and letting the range of b equal [-4, 3] (4 bits), then the range for the first base exponent will be between -1 and 2. To represent a maximum of a 9-bit integer, we will require a range of [-1, (2 + 9 = 11)] for the first base exponent or 5 bits. This is a saving of 1 bit from the previous example, using D = 3, but with no change in the representation.

Finding the optimal value of the second base for a given digital filter specification is a challenging optimization problem even for a single-digit 2DLNS representation. It can be posed as follows:

Input: (1) Digital filter coefficients (h0, h1, …, hk--1) designed to satisfy specific digital filter constraints and (2) the number of bits, R, of the nonbinary exponents.

Output: A real number D and triples of integers (si, ai, bi), i  satisfy the constraints provided.

There are many methods for designing digital filters, each of which prioritize different output characteristics. To further reduce the complexity of this problem we will first generate the filter coefficients by using classical design techniques. In this case, we will minimize the pass band ripple, maximize the stop- band attenuation, and maintain linear phase. We then optimize the mapping of the real coefficients into a 2DLNS representation. This approach can be used with many more filter design techniques or even for applications other than the filter design.

Note that we do not impose restrictions on the size of the binary exponents, since they have very little contribution to the overall complexity of the architecture proposed. We require, however, to know what their range will be.

To demonstrate how important it is to choose the optimum base D, we provide the following example of a 53-tap FIR filter described by the coefficients (coefficients 28–53 are a mirror of 1–26 to guarantee linear phase) shown in Table 84.10:

For the signal samples we will need to use two or more digits. In Ref. [12] the typical distribution of the coefficients of many different filters was found to be a Gaussian-like function centered on zero. Such a coefficient distribution is better represented by a logarithmic-like number system such as the MDLNS rather than a linear number representation (such as binary). Therefore we should be able to obtain very good single-digit approximations in the 2DLNS by making use of a carefully calculated second base. This allows us to reduce the number of computational channels by a factor of two. We shall also consider a two-digit 2DLNS representation.

The frequency response of the above filter is shown below in Figure 84.11 along with an implementation of a 1-digit and 2-digit DBNS filter responses, each using almost the same number of bits and 3 as the second base.

The size of the second base exponent plays an important role in the size of the hardware owing to the required LUTs; a 1-bit increase to the nonbinary exponent doubles the LUT size. An increase in the binary exponent adds minimal hardware. Any change to the second base, including to real numbers has no impact on the structure of the hardware. Therefore, hardware designed for a ternary base is easily converted into the optimal base.

Finding the Optimal Base

To determine the optimal base a program was created that performs a thorough search of real bases. We have already seen that the most efficient bases for hardware implementation lie in the range [1/ 2 , 2 ].

This limitation offers a practical start and endpoint for a range-type search. The program uses a dynamic step size which is applied by analyzing the change in the optimization score and controlling the test points for the base, from the start to the endpoint, to reduce the overall search time. The step size increases so long as the resulting scores are monotonically improving. The program retraces and decreases the step

size when the scores change in a nonmonotonic fashion. Each time a better result or score is found, it is added to a running list of “best scores.” Once the entire range has been processed, each element in this list is finely adjusted by progressively smaller values. This optimization algorithm drastically improves search times by initially performing a coarse search followed by a finer search near the optimum point.

As the dynamic range of the nonbinary exponent is increased, we increase the efficiency of the coefficient mapping therefore increasing the performance of the implemented filter.

Results

By using a single-digit 2DLNS representation with an optimal base of 0.7278946656213228 the filter was able to achieve a stop-band attenuation of over 80 dB, and a two-digit 2DLNS representation with an optimal base of 0.7352545180621994 was able to achieve a stop-band attenuation of over 81.5 dB (see Figure 84.12). Using these optimum second bases we see a considerable performance improvement compared to filters designed using a second base of 3 (see Figure 84.11) that have a stop-band attenuation of 66 dB for single-digit and 69 dB for two-digit representation.

Table 84.11 shows the filter coefficients and the approximations for the optimal base. A closer look at the table shows the advantages of the proposed number system in terms of the dynamic range of the computations. For a one-digit 2DLNS we have used only 9 bits for the nonbinary exponents and, correspondingly, we have to use only a 512-word ROM (two for a parallel implementation). For a two- digit 2DLNS we need only 3 bits to represent the nonbinary exponents requiring only an 8-word ROM (four for a parallel implementation). The same accuracy can be achieved in the case of classical binary arithmetic if one uses a 16-bit dynamic range for the filter coefficients. It is also very important to note that the entire architecture is multiplier-free; it consists of only small adders and very small ROM arrays, several orders of magnitude smaller than the equivalent classical LNS design.