Exponential Precision in A/D Conversion with an Imperfect Quantizer ^{∗}

I. Daubechies, R. DeVore, C.S. Güntürk, and V. Vaishampayan

September 14, 2001

Abstract

We analyze mathematically the effect of quantization error in the circuit implementation of Analog to Digital (A/D) converters such as Pulse Code Modulation (PCM) and Sigma-Delta Modulation (ΣΔ). We show that ΣΔ modulation, which is based on oversampling the signal, has a self correction for quantization error that is not inherited by PCM. This result may partially explain the success of such converters. Motivated by this example, we investigate whether it is possible to use redundancy to construct other encoders, with the same self correction property, but with higher order accuracy relative to bit rate. We introduce a class of encoders which exhibit exponential bit rate accuracy (in contrast to the polynomial rate of ΣΔ) and still retain the self correction feature.

Keywords: A/D conversion, quantization, robustness, sigma-delta modulation, betaexpansions.

∗This work has been supported by the National Science Foundation Grants DMS-9872890, DMS-9706753 and DMS-9729992, by the Office of Naval Research Contract N0014-91-J1343, and by Air Force for Scientific Research Contract F 49620-98-1-0044.

1 Introduction

A one-bit quantizer is a mapping Q of the real numbers into the discrete set {−1, 1}, defined by

Q(z) := \{ \begin{matrix}−1, & z ≤ 0 \\ 1, & z > 0. \end{matrix}  (1.1)

The hardware circuit implementation of such a device is never perfect: transition often happens at some point different from 0. This results in an erroneous quantizer Q̃, which instead computes

Q̃(z) := \{ \begin{matrix}−1, & z ≤ ρ \\ 1, & z > ρ, \end{matrix}  (1.2)

for a possibly unknown (small) value of ρ. One may further assume ρ to vary at each implementation of Q̃. We are interested in methods for converting an analog signal x(t) defined on the real line IR into a digital bitstream using such an imprecise one-bit quantizer.

Another essential ingredient of the methods we will be considering is the sampling operation, which maps a given signal x(t) to a sequence of numbers (x(nτ))_{n∈ZZ}, where τ is the sampling interval. We assume that this operation is carried out precisely.

We shall work with bandlimited functions, i.e., functions whose Fourier transforms are compactly supported. Any bandlimited function can be recovered perfectly from its samples on a sufficiently close-spaced grid; this is known as the “sampling theorem”. Let S(Ω) denote the class of functions x ∈ L^{2}(IR) whose Fourier transforms are supported on [−Ω, Ω]. The Shannon-Whittaker formula gives a way to reconstruct a function x ∈ S(π) from its samples (x(n))_{n∈ZZ} taken on the integer grid:

x(t) = ∑_{n∈ZZ} x(n)S(t − n),  (1.3)

where S is the sinc function

S(t) := \frac{sin πt}{πt}.  (1.4)

The functions S(· − n), n ∈ ZZ, form a complete orthonormal system for S(π). Clearly, the formula above can be extended through dilation to functions in S(Ω) for arbitrary Ω.

In practice, one observes a function only on a finite portion I = [a, b] of the real line IR. In addition, we shall consider functions of limited maximum amplitude; in other words, we consider the class S(Ω, M, I) of all signals x ∈ S(Ω) that take values in (−M, M) when t ∈ I:

|x(t)| < M, t ∈ I.  (1.5)

It will be sufficient in all of what follows to consider the case where Ω = π and M = 1. We denote S(π, 1, I) simply by S.

Pulse Code Modulation (PCM) is maybe the simplest method for analog to digital conversion of functions in S. Each sample x(n) ∈ (−1, 1) in the expression (1.3) is simply replaced by a truncated version x̃(n) of its binary expansion. (There is, however, a slight glitch to overcome due to the instability of the basis functions S(· − n), n ∈ ZZ, which is reflected by the fact that

∑_{n∈ZZ} |S(t − n)| = ∞  (1.6)

whenever t is not an integer. This can be easily fixed by oversampling, as we shall see in Section 2.)

Let the real number y ∈ (−1, 1) have the binary expansion

y = b_{0} ∑_{i=1}^{∞} b_{i}2^{−i},  (1.7)

with b_{0} = b_{0}(y) ∈ {−1, 1} and b_{i} = b_{i}(y) ∈ {0, 1} for all i ≥ 1. The sign bit b_{0} is given by b_{0}(y) = Q(y). The other bits can be computed using the one-bit quantizer described in (1.1) in the following algorithm known as Successive Approximation (SA). For each real number z, let Q_{1}(z) := (Q(z − 1) + 1)/2, i.e.,

Q_{1}(z) := \{ \begin{matrix}0, & z ≤ 1 \\ 1, & z > 1. \end{matrix}  (1.8)

Let u_{1} := 2b_{0}y = 2|y|; the first bit b_{1} is given by b_{1} := Q_{1}(u_{1}). Then the remaining bits are computed recursively as follows: if u_{n} and b_{n} have been defined, we let

u_{i+1} := 2(u_{i} − b_{i})  (1.9)

and

b_{i+1} := Q_{1}(u_{i+1}).  (1.10)

Let us now consider what will happen if we make errors in the quantization. We suppose that at each quantization step, the circuit does not compute Q(z) but rather Q̃(z), given by (1.2). This also leads to the definition

Q̃_{1}(z) := \{ \begin{matrix}0, & z ≤ 1 + ρ \\ 1, & z > 1 + ρ, \end{matrix}  (1.11)

where ρ may vary at each implementation of Q̃_{1}. We assume that |ρ| ≤ δ where δ > 0 is fixed. The debilitating effect of the quantization error can already be seen in the sign bit. Assume for example that ρ > 0. If y ∈ (0, ρ], then the sign bit of y will be incorrect. No matter how the remaining bits are assigned the resulting error |y − ỹ| is at least as large as |y| which can be as large as δ. By taking a function x(t) = yS(t − k), with S the sinc function (1.4), this translates into the same possible error for PCM in its circuit implementation. Note that this is not just an anomaly of only the sign bit. For y ∈ (1/2, 1/2 + ρ/2), the sign bit b_{0}(y) will be correct, but the bit b_{1}(y) will be wrong and no matter how the other bits are assigned the resulting error |y − ỹ| will be at least as large as |y − 1/2| which could be as large as δ/2.

In this paper, we shall look at two other schemes which do not suffer from this effect. In these schemes, it will be possible to reconstruct the signals perfectly by taking more bits from their digital representations, even if the quantizer used to derive the digital representations is imperfect. The compensation will come, as we shall see, from the redundancy of the codewords produced by these algorithms. To give a more systematic treatment, we first give a short discussion of the information theoretical aspects of the problem in the next section.

2 Encoding-Decoding and Kolmogorov Entropy

Let S be the space of our signals, as defined in Section 1. By an encoder E for S we mean a mapping

E : S → B  (2.1)

where the elements in B are finite bitstreams. The result of the encoding is to take the analog signal x to the digital domain. We also have a decoder D which maps bitstreams to signals

D : B → S̃  (2.2)

where the class S̃ is not necessarily the same as S. Note that there may be many decoders D associated to a given E.

In general DEx ≠ x. We can measure the distortion in the encoding/decoding by

∥x − DEx∥  (2.3)

where ∥ · ∥ is a norm defined on the signals of interest. We shall restrict our attention to the norm

∥x∥_{C(I)} := sup_{t∈I} |x(t)|,  (2.4)

where C(I) denotes the class of continuous functions on I. A similar analysis can be carried out for other norms such as the L^{2}(I) norm.

One way of possibly assessing the performance of encoders is to measure the distortion of the encoding-decoding

d(S; E, D) := sup_{x∈S} ∥x − DEx∥_{C(I)}.  (2.5)

for the class S. In order to have a fair competition between various encoding-decoding schemes we can look at the performance as a function of the bit budget. Given a distortion ϵ > 0, we let E := E(S, ϵ) denote the class of encoder-decoder pairs (E, D) for which d(S; E, D) ≤ ϵ. A given encoder E corresponding to a pair in this class utilizes a bit budget

n(S, ϵ, E, I) := sup_{x∈S} #(Ex),  (2.6)

where #(Ex) is the number of bits in the bitstream Ex. The smallest number of bits that can realize the distortion ϵ for S on I is given by

n(S, ϵ, I) := min_{(E,D)∈E(S,ϵ)} n(S, ϵ, E, I).  (2.7)

It is well known that n(S, ϵ, I) is determined by the Kolmogorov entropy H_{ϵ}(S, C(I)) of the class S as a subset of C(I). Here H_{ϵ}(S, C(I)) := log_{2} N_{ϵ}(S) where N := N_{ϵ}(S) is the smallest number of functions f_{1}, …, f_{N} ∈ C(I) such that each f ∈ S satisfies ∥f − f_{i}∥_{C(I)} ≤ ϵ for some i = 1, 2, …, N. It is then easy to see that

n(S, ϵ, I) = ⌈H_{ϵ}(S, C(I))⌉

with ⌈y⌉ the smallest integer ≥ y.

In many applications in signal processing, the interval I on which we wish to recover the signals x(t) is varying and will be large relative to the Nyquist sample spacing. Consider, for example, audio signals where sampling at 44, 000 times per second corresponds to high quality audio and sampling at 4, 000 times per second corresponds to wireless voice applications. Recovering M minutes of such signals in these two cases means that the interval I corresponds to a number of 2, 640, 000M or 240, 000M consecutive samples, respectively. So, the interval I, while finite, is typically very large. In this case, the average bit rate

n̄(S, ϵ) := lim_{|I|→∞} \frac{n(S, ϵ, I)}{|I|}  (2.8)

is a relevant measure of the encoding efficiency. There is a corresponding concept of average entropy

H̄_{ϵ}(S) := lim_{|I|→∞} \frac{H_{ϵ}(S, C(I))}{|I|}  (2.9)

and we have

n̄(S, ϵ) = H̄_{ϵ}(S).

The average entropy of the class S can be derived from results of Kolmogorov and Tikhomirov [2] on the average entropy of classes of analytic functions. These results yield

n̄(S, ϵ) = (1 + o(1)) log_{2} \frac{1}{ϵ}, 0 < ϵ < 1.  (2.10)

One can derive this result through the practical encoding scheme PCM. We shall here give a formulation of the proof using methods that are similar to those used in [2], however, with more generality. The first issue to be taken care of is the instability of the expansion (1.3) as stated in (1.6). We can circumvent this problem easily in the following way. We choose a real number λ > 1 and sample x at the points n/λ, n ∈ ZZ, thereby obtaining the sequence x_{n} := x(n/λ), n ∈ ZZ. When we reconstruct x from these sample values, we have more flexibility since the sample values are redundant. If g := g_{λ} is any function whose Fourier transform ĝ is 1 on [−π, π], and vanishes outside of [−λπ, λπ], then we have the recovery formula (see [1])

x(t) = \frac{1}{λ} ∑_{n∈ZZ} x_{n}g(t − n/λ).  (2.11)

Let G_{λ}(n) := sup_{t∈[0,1/λ)} |g(t − n/λ)|. We shall only need to consider g for which

∑_{n∈ZZ} G_{λ}(n) < ∞,  (2.12)

which can easily be achieved by choosing ĝ to be sufficiently smooth.

Given an integer m > 0, we define the encoder E_{m} as follows. Given an interval I = [a, b] in which we want to recover the signal, let Ī:= [a − M, b + M] where M = M(m, λ) is chosen so that

∑_{|n|≥⌊λM⌋} G_{λ}(n) < 2^{−m}.  (2.13)

For x ∈ S, we define E_{m}(x) to be the bitstream consisting of the bits b_{i}(x_{n}), i = 0, …, m, x_{n} ∈ Ī. Thus x̄_{n} := b_{0}(x_{n}) ∑_{i=1}^{m} b_{i}(x_{n})2^{−i} satisfies

|x_{n} − x̄_{n}| ≤ 2^{−m}.  (2.14)

¿From this bitstream, we can decode using the recovery

x̄(t) := \frac{1}{λ} ∑_{n∈λĪ} x̄_{n}g(t − n/λ).  (2.15)

We can easily bound the distortion for this encoding/decoding. We have

x = S_{0} + S_{1}  (2.16)

where S_{0} := \frac{1}{λ} ∑_{n∈λĪ} x_{n}g(t − n/λ) and S_{1} := \frac{1}{λ} ∑_{n∉λĪ} x_{n}g(t − n/λ). Therefore,

|x(t) − x̄(t)| ≤ |S_{1}(t)| + |x̄(t) − S_{0}(t)|.  (2.17)

We have |g(t − n/λ)| ≤ G_{λ}(n − ⌊λt⌋), so that for t ∈ I,

|S_{1}(t)| ≤ ∑_{n∉λĪ}|g(t − n/λ)| ≤ ∑_{|k|≥⌊λM⌋} G_{λ}(k) ≤ 2^{−m}.  (2.18)

In view of (2.14)

|x̄(t) − S_{0}(t)| ≤ 2^{−m} ∑_{n∈λĪ}|g(t − n/λ)| ≤ C2^{−m},  (2.19)

where C := C_{λ} denotes the sum of the series given by (2.12). Putting these two estimates into (2.17), we obtain

|x(t) − x̄(t)| ≤ (1 + C)2^{−m}, t ∈ I.  (2.20)

The number of bits used in this encoding is bounded by

m|Ī|λ = m(2M + |I|)λ,  (2.21)

from which we derive

n̄(S, (1 + C)2^{−m}) ≤ lim_{|I|→∞} |I|^{−1}(2M + λ|I|)m ≤ λm.  (2.22)

In other words,

n̄(S, ϵ) ≤ λ(log_{2} \frac{1}{ϵ} + log_{2}(1 + C)).  (2.23)

Now, given any δ > 0, we choose λ > 1 so that λ − 1 ≤ δ/2. Then for ϵ > 0 sufficiently small, (2.23) gives

n̄(S, ϵ) ≤ (1 + δ) log_{2} \frac{1}{ϵ}  (2.24)

We therefore obtain a proof of the upper bound of n̄(S, ϵ) stated in (2.10).

3 The Error Correction of Sigma-Delta Modulation

We have seen that for sufficiently large intervals I and a sufficiently large number of bits m per Nyquist interval, the accuracy d(S; E, D) of PCM, when implemented using a precise quantizer, is of order O(2^{−m}). However, when the quantizer is imperfect as defined in Section 1, the accuracy has no asymptotic decay as m is increased, as shown by our earlier examples. In this section, we shall look at another class of encoders, given by Sigma-Delta (ΣΔ) Modulation, which behave differently when quantization error is present.

We describe here only the simplest case of first order ΣΔ modulation. We again choose λ > 1 (although now λ will be chosen to be large rather than close to one). We continue with the notation x_{n} := x(n/λ) as above. Given (x_{n}), the algorithm creates a bitstream (b_{n}), b_{n} ∈ {−1, 1}, whose running sums are trying to match those of x_{n}. There is an auxiliary sequence u_{n} which tracks the error between these two running sums. We take u_{n} = 0 for n < λa where I = [a, b], and define

u_{n+1} := u_{n} + x_{n} − b_{n}, n/λ ∈ I,  (3.1)

where

b_{n} := Q(u_{n})  (3.2)

and Q is the quantizer defined by (1.1). The ΣΔ encoder E_{λ} maps x to the bitstream (b_{n}). We see that E_{λ} appropriates one bit for each sample, which corresponds to λ bits per Nyquist interval, therefore resulting in |I|λ bits for the whole signal x.

To decode the ΣΔ bitstream, we can use the recovery formula (2.15) with g as before and with each x̄_{n} replaced by b_{n}. This gives

x̄(t) := D((b_{n}))(t) := \frac{1}{λ} ∑_{n∈λĪ}b_{n}g(t − n/λ).  (3.3)

One can easily show (see also [1]) that using appropriate g yields

|x(t) − x̄(t)| ≤ C_{0}λ^{−1}, t ∈ I,  (3.4)

with the constant C_{0} depending only on the choice of g. Examples show that for general x, this bound cannot be improved, i.e.,

c_{0}λ^{−1} ≤ d(S; E, D) ≤ C_{0}λ^{−1}.  (3.5)

Hence we see that when the average bit rate is λ, first order ΣΔ modulation results in O(λ^{−1}) accuracy, much worse than what would be achieved if PCM was used. However, the remarkable fact is that ΣΔ encoders are impervious to error in the circuit implementation of the quantization. Theorem 3.1, below, shows that given any δ > 0, then an error of at most δ in each implementation of quantization in the ΣΔ encoder will not affect the distortion bound (3.4) save for the constant C.

Let us see how this works. Suppose that in place of the quantizer Q of (1.1), we use the imprecise quantizer Q̃ of (1.2), where ρ can vary at each occurence. We assume the uniform bound |ρ| ≤ δ. Using these quantizers will result in a different bitstream than would be produced by using Q. In place of the auxiliary sequence u_{n} of (3.1) which would be the result of exact quantization, we obtain the sequence ũ_{n}, which satisfies ũ_{n} = 0 for n/λ < a and

ũ_{n+1} = ũ_{n} + x_{n} − b̃_{n}, n ∈ λI  (3.6)

where

b̃_{n} = Q̃(ũ_{n}).  (3.7)

We then have:

Theorem 3.1 Suppose that ΣΔ modulation is implemented by using, at each occurence, one of the quantizers Q̃, with |ρ| ≤ δ, in place of Q. If the sequence (b̃_{n}) is used in place of b_{n} in the decoder (3.3), the result is a function x̃ which satisifies

|x(t) − x̃(t)| ≤ Cλ^{−1}, t ∈ I,  (3.8)

with C = C_{0}(2 + δ) and C_{0} the constant in (3.4) .

Proof: This theorem was proved in [1]. We do not repeat its simple proof in detail. The main idea which is to establish the following bound:

|ũ_{n}| ≤ 2 + δ,  (3.9)

which can be proved by induction on n. It is clear for n < λa. Assume that (3.9) has been shown for n ≤ N. If ũ_{N} ≤ ρ, then b̃_{N} = −1 and from (3.6) we have

ũ_{N+1} = ũ_{N} + x_{N} − b̃_{N}.  (3.10)

Now, x_{N} − b̃_{N} ∈ [0, 2] and hence ũ_{N+1} ∈ [−2 − δ, 2 + δ]. A similar argument applies if ũ_{N} > ρ and therefore we have advanced the induction hypothesis and thus proved (3.9). The remainder of the proof uses summation by parts to obtain (3.8) (see [1]). □

The error correction capability in ΣΔ is related to the large amount of redundancy in the representation (2.11). The question arises whether one could utilize redundancy to build other encoders which have the best of both worlds: self correction for quantization error and exponential accuracy in terms of the bit rate. In the next section, we shall construct a class of encoders which have the flavor of PCM but rather than using the binary representation of a real number y (which is unique), they utilize representations with respect to a base β ∈ (1, 2). Such beta-representations are not unique, even when β is kept fixed, and this fact is exploited to achieve the above mentioned properties.

4 Beta-Encoders with Error Correction

We shall now show that it is possible to obtain exponential bit rate performance while retaining quantization error correction by using what we shall call beta-encoders. The essential idea is to replace the binary representation of a real number y by a redundant representation.

Let 1 < β < 2 and γ := 1/β. Then each y ∈ [0, 1] has a representation

y = ∑_{i=1}^{∞} b_{i}γ^{i}  (4.1)

with

b_{i} ∈ {0, 1}.  (4.2)

In fact there are many such representations. The main observation that we shall utilize below is that no matter what bits b_{i}, i = 1, …, m, have been assigned, then, as long as

y − \frac{γ^{m+1}}{1 − γ} ≤ ∑_{i=1}^{m} b_{i}γ^{i} ≤ y,  (4.3)

there is a bit assignment (b_{k})_{k>m}, which, when used with the previously assigned bits, will exactly recover y.

We shall use this observation in an analogous fashion to Successive Approximation to encode real numbers, with the added feature of quantization error correction. These encoders have a certain offset parameter μ whose purpose is to make sure that even when there is an imprecise implementation of the encoder, the bits assigned will satisfy (4.3); as shown below, introducing μ corresponds to carrying out the decision to set a bit to 1 only when the input is well past its minimum threshold. We let Q_{1} be the quantizer of (1.8).

The beta-encoder with offset μ. Let μ > 0 and 1 < β < 2. For y ∈ [0, 1], we define u_{1} := βy and b_{1} := Q_{1}(u_{1} − μ). In general, if u_{i} and b_{i} have been defined, we let

u_{i+1} := β(u_{i} − b_{i}), b_{i+1} := Q_{1}(u_{i+1} − μ).  (4.4)

It then follows that

y − ∑_{i=1}^{m} b_{i}γ^{i} = y − ∑_{i=1}^{m} γ^{i}(u_{i} − γu_{i+1}) = y − γu_{1} + γ^{m+1}u_{m+1} ≤ γ^{m+1}∥u∥_{l^{∞}},  (4.5)

showing that we have exponential precision in our reconstruction, provided the |u_{i}| are uniformly bounded. We shall see below that we do indeed have such a uniform bound. Let’s analyze the error correcting abilities of these encoders when the quantization is imprecise. Suppose that in place of the quantizer Q_{1}, we use at each iteration in the beta-encoder the imprecise quantizer Q̃_{1} defined by (1.11) where at each application the value of ρ may vary. We assume a uniform bound |ρ| ≤ δ for the quantizer errors. In place of the bits b_{i}(y), we shall obtain inaccurate bits b̃_{i}(y) which are defined recursively by ũ_{1} := βy, b̃_{1} := Q̃_{1}(ũ_{1} − μ) and more generally,

ũ_{i+1} := β(ũ_{i} − b̃_{i}), b̃_{i+1} := Q̃_{1}(ũ_{i+1} − μ).  (4.6)

Theorem 4.1 Let δ > 0 and y ∈ [0, 1). Suppose that in the beta-encoding of y, the quantizer Q̃_{1} is used in place of Q_{1} at each occurence, with the values of ρ possibly varying but always satisfying |ρ| ≤ δ. If μ ≥ δ and β satisfies

1 < β ≤ \frac{2 + μ + δ}{1 + μ + δ} ,  (4.7)

then for each m ≥ 1, ỹ_{m} := ∑_{k=1}^{m} b̃_{k}γ^{k} satisfies

|y − ỹ_{m}| ≤ Cγ^{m}, m = 1, 2, …,  (4.8)

with C = 1 + μ + δ.

Proof: We first claim that

0 ≤ ũ_{n} ≤ β(1 + μ + δ), n = 1, 2, ….  (4.9)

This is proved by induction on n. For n = 1 it is true because

ũ_{1} := βy ≤ β.

Assume that (4.9) has been proved for n = N. If b̃_{N} = 0, then ũ_{N} ≤ 1 + μ + δ and hence

0 ≤ ũ_{N+1} = βũ_{N} ≤ β(1 + μ + δ),  (4.10)

as desired. If b̃_{N} = 1, then ũ_{N} > 1 + ρ + μ ≥ 1 − δ + μ ≥ 1. Also, in this case,

0 ≤ ũ_{N+1} = β(ũ_{N} − 1) ≤ β[β(1 + μ + δ) − 1] ≤ β(2 + μ + δ − 1) = β(1 + μ + δ) (4.11)

where we have used (4.7). This advances the induction hypothesis and proves (4.9). On the other hand,

y − ỹ_{m} = y − ∑_{k=1}^{m} b̃_{k}γ^{k} = γũ_{1} − ∑_{k=1}^{m} γ^{k}(ũ_{k} − γũ_{k+1}) = γ^{m+1}ũ_{m+1},  (4.12)

which together with (4.9) gives (4.8). □ (Note that, in the special case δ = 0, the bound (4.9) shows that the |u_{n}| in (4.5) are uniformly bounded, as claimed above.)

For signal encoding, we utilize the beta encoder as in PCM. Namely, we take λ > 1 and let x_{n} := x(n/λ) as before. We would like to avoid keeping sign bits of the x_{n}. We can do this by replacing x_{n} by x′_{n} := (x_{n} + 1)/2. For each x′_{n} we keep the first m bits b_{1}(x′_{n}), …, b_{m}(x′_{n}) of the beta encoder applied to x′_{n}. To decode, we use the beta-encoder bits to approximately recover x′_{n} by

x̄′_{n} := ∑_{k=1}^{m} b_{k}(x_{n})γ^{k}  (4.13)

and then approximately recover x_{n} by

x̄_{n} := 2x̄′_{n} − 1  (4.14)

which satisfies

|x_{n} − x̄_{n}| ≤ Cγ^{m}, n ∈ ZZ,  (4.15)

Given a signal x, an integer m > 0, and the interval I, we define x̄ as in (2.15) except that we use the x̄_{n} of (4.14).

Theorem 4.2 For any x ∈ S, the beta-encoder/decoder with m bits per sample satisfies

|x(t) − x̄(t)| ≤ Cγ^{m}, t ∈ I,  (4.16)

with C depending only on the reconstruction filter g. Moreover, if in place of the exact quantizer Q_{1}, we use, at each iteration, a quantizer Q̃_{1} given by (1.11), with ρ satisfiying |ρ| ≤ δ, then we still obtain the error bound (4.16) with the constant C now depending also on δ.

Proof: If we define S_{0} as in (2.16), then Theorem 4.1 gives

|S_{0}(t) − x̄(t)| ≤ Cγ^{m}, t ∈ I.

If we couple this with (2.18), we arrive at (4.16). □

Acknowledgment. This work was the result of a collaboration started during the Summer of 1999. The non-AT&T authors would like to thank AT&T for its hospitality and partial support (RDV and CSG). We would also like to thank the many AT&T researchers, in particular Jont Allen, with whom we had extensive and enjoyable discussions.

References

[1] I. Daubechies and R. DeVore, Reconstructing a bandlimited function from very

coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order,

submitted.

[2] A. N. Kolmogorov and V. M. Tikhomirov, ϵ-entropy and ϵ-capacity of sets in function

spaces. Uspehi, 14(86):3-86, 1959 (also: AMS Translations, Series 2, Vol. 17, 1961,

pp. 277-364).

Ingrid Daubechies Department of Mathematics and Program in Applied and Computational Mathematics Princeton University Fine Hall, Washington Road Princeton, NJ 08544.

email: ingrid@math.princeton.edu

Ronald DeVore Department of Mathematics University of South Carolina Columbia, SC 29208.

email: devore@math.sc.edu

C. Sinan Güntürk School of Mathematics Institute for Advanced Study Einstein Dr. Princeton, NJ 08540.

email: gunturk@math.ias.edu

Vinay Vaishampayan Information Sciences Research AT&T Labs 180 Park Avenue Florham Park, NJ 07932.

email: vinay@research.att.com