Multidimensional Logarithmic Number System:Error-Free Integer Representations

Error-Free Integer Representations

As stated in the introduction, more often in DSP applications the input data has to be converted from analog to a fixed-point binary value with a uniform quantization error bound. Mapping to integers has a quantization error bounded by ±0.5 for all converted values. For a classical LNS representation (and also a one-digit MDLNS representation) we do not have this uniform quantization accuracy so we have to choose a sufficient number of bits so that we will be able to maintain this conversion accuracy for the larger data values. In the multidigit MDLNS we can mitigate this quantization problem; in fact, we can find certain MDLNS representations that are completely error-free.

Consider the case of the two odd prime bases, (3, 5).

A representation of a real number into forms given in Definitions 84.3–84.5 is called error-free if the approximation error is zero. The next three theorems and one conjecture provide new and interesting results about the error-free two-dimensional logarithmic representation of numbers.

Theorem 84.2

Every real number x may have at most 14 different error-free two-digit two-dimensional logarithmic representations.

Proof

Let us assume that x is represented in the form of Definition 84.5:

apply the following result (recently proved by Bennett [23]): If a, b, and c are integers, a, b ³ 2, then the equation ax – by = c may have at most two different solutions in integers (x , y). Therefore, Eq. (84.9) may have at most four different solutions if the signs are different. If the signs are identical (say, positive, which corresponds to positive M), then we can do the following. Represent the exponents e and f with respect to modulo 3: e = 3e1 + e2 and f = 3f1 + f2, e2, f2 Î {0, 1, 2}. For the nine possible combinations of residues (e2, f2) we have nine Diophantine equations of the form

where c1 and c2 are constants. Delone–Fadeev’s theorem [24] about the cubic Diophantine equations states that Eq. (84.11) may have at most one solution in integers. Since we have nine Diophantine equations of this type, we may have at most nine different solutions of Eq. (84.10).

Therefore, the total number of different error-free representations is bounded from above by 4 (the maximal number of solutions of Eq. (84.9)) + 9 (the maximal number of solutions of Eq. (84.10) plus one (the maximal number of solutions of Eq. (84.8)), that is, 14.

In some important special cases, this bound can be considerably improved.

Theorem 84.3

Every real number x may have at most seven different error-free two-digit two-dimensional loga- rithmic representations if the nonbinary base is 3.

Proof

Assume that x is represented in the form

Let x = 3.25; then x can be represented with no error in a two-digit 2DLNS with odd base 3 as follows:

The point of the theorem is to establish an effectively computable upper bound that could be a starting point for improvements. The example given shows that the lower bound for the maximal number of error-free representation is five.

Theorem 84.4

The smallest positive integer with no error-free two-digit 2DLNS representation in the case of odd base three is 103.

Proof

The proof is based on the following result proved by Ellison [26]: let x > 11, x ¹ 13,14,16,19,27; then for all x, y E N the following inequality holds: |2x - 3y | > ex(ln 2-0.1).

Up to 102 we can give proper examples found by computational experiments. A simple check shows that 103 is not a sum of integers of the form 2a3b . 103 is not divisible by 2 and 3, therefore, it must be a difference of a power of 2 and a power of 3 (or vice versa). Applying Ellison’s theorem we have

Therefore, x should be smaller than 8, and there are only 13 possible values for x, namely, x = 1,2,3,4,5,6,7,11,13,14,16,19,27. We now calculate, and in none of the cases do we find that the corresponding y is integer, therefore, 103 cannot be represented in an error-free manner in two- digit 2DLNS with bases 2 and 3.

Theorem 84.5

The smallest positive integer with no error-free two-digit two-dimensional logarithmic representa- tion, in the case of nonbinary base 5, is 43.

Proof

The proof is based on a theorem, proved by Tijdeman [27], which has a much more general result than Ellison’s result used in Theorem 84.4. Tijdeman states that if x and y are two consecutive s-integers, s > 1, then |x - y| > y /(log y)c, where c is an effectively computable constant. In the case of 2-integers c is estimated to be less than 64, based on recent results in transcendental number theory [28]. We apply this theorem to numbers of the form 2a5b.

Again, up to 42 inclusively, we can find appropriate error-free representations; 43 is not a sum of two numbers of this form, therefore it could only be a difference, so we may apply Tijdeman’s theorem and obtain an upper bound for the possible solutions. Namely, if 43 = |x-y |, x and y being of the form 2a5b, then the theorem implies that 43(log y)64 > y, therefore, y < 2575. There are 296,371 numbers of the form 2a5b less than 2575, that is 296,371 potential values of x to be checked out; in none of these cases is the corresponding value for x = y + 43 a number of the form 2a5b. This shows that 43 is indeed the smallest positive integer without an error-free two-dimensional two-digit LNS representation for the case of nonbinary base 5.

We note that Tijdeman’s theorem can be used for the proof of Theorem 84.3. We have, however, provided this new proof based on a result concerning the set of bases two and three to point out the difficulties that may arise if one applies general theorems from transcendental number theory.

The following conjecture is based on extensive numerical calculations.

Conjecture 84.1

The smallest positive integer with no error-free 3-digit two-dimensional logarithmic representation in the case of odd base 3 is 4985. Or, in the language of the exponential Diophantine equations, it can be posed as follows—the equations ± 2a3b ± 2c3d ± 2e3f = 4985 do not have solutions in integers.

It is important to note that such results will be available (and different) for every particular set of bases that we choose. In this case (i.e., a 3-digit two-dimensional logarithmic representation with odd base 3) we see that a 12-bit error-free mapping that is a useful dynamic range for many DSP applications is available. It should also be noted that the size of all of the exponents used (a, b, c, d, e, f ) only require 3-bit unsigned integers for their representation.