Sigma-Delta Quantization and Sturmian Words by ULAŞ AYAZ B.Sc., Boğaziçi University, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) October 2009 c© ULAŞ AYAZ 2009 Abstract In this thesis, our main focus is Sigma-Delta quantization schemes. These are commonly used in state-of-art Analog-to-digital conversion technology. Their main advantage is the ease of implementation and more importantly their insensitivity to certain circuit imperfections. When we compare sigma- delta scheme with pulse-code modulation (PCM), sigma-delta is inferior in terms of rate distortion because an N -bit kth order sigma-delta quantizer produces an approximation with the error of order O(N−k) whereas the cor- responding N -bit PCM scheme has accuracy of O(2−N ). However, this is a raw estimate of the actual rate-distortion characteristic of sigma-delta as one can further compress the bitstreams obtained via sigma-delta quantiza- tion. Even though this observation was made earlier in [10] under certain assumptions, to our knowledge, it was not investigated fully. In this thesis, such an investigation is made for first-order sigma-delta quantizers by us- ing some results from symbolic dynamics literature on “Sturmian words”. Surprisingly, it turns out that the approximation error is a function of the “actual bit-rate”, i.e., the bit-rate after compressing an N -bit first-order sigma-delta encoding. In addition, in this thesis, we will introduce a new setup for sampling a bandlimited function and then quantizing these samples via first-order sigma-delta scheme. This simple but surprisingly efficient technique will allow us to get a better bound for the approximation rate of sigma-delta schemes and it will allow us to apply the derived results for compression of the bitstreams. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Encoding and Robustness . . . . . . . . . . . . . . . . . . . . 4 2.1 A/D conversion setting . . . . . . . . . . . . . . . . . . . . . 4 2.2 PCM encoders . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Another family of encoders: Σ∆ schemes . . . . . . . . . . . 7 2.3.1 First-order Σ∆ quantizers . . . . . . . . . . . . . . . 8 3 Σ∆ Quantization and Sturmian Words . . . . . . . . . . . . 13 3.1 Sturmian words . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Possible codewords of Σ∆ quantization . . . . . . . . . . . . 17 3.3 An alternative comparison between PCM and Σ∆ . . . . . . 19 4 Error Analysis of Σ∆ Quantization . . . . . . . . . . . . . . . 21 4.1 Constant offset error . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Number of codewords with fixed initial value and offset error 23 4.3 Varying offset error . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.1 Non-recursive formulation . . . . . . . . . . . . . . . 27 4.3.2 Threshold regions . . . . . . . . . . . . . . . . . . . . 28 iii Table of Contents 4.4 Some conditions on initial value and δmax . . . . . . . . . . . 39 5 Implications for Bandlimited Functions . . . . . . . . . . . . 44 5.1 Basic error estimates for PCM and Σ∆ schemes . . . . . . . 45 5.2 A new Σ∆ quantization setup for bandlimited functions . . . 47 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 iv List of Figures 4.1 Quantization threshold regions, with levels depending on n . 34 4.2 (a) Linear relation between initial value û0 and δmax and (b) order of δmax (1/δmax) with respect to û0. N is fixed to 7 for this example. Marked points on the x axis are 6-Farey points. 42 4.3 Graph of function ∆N (û0) for N = 7. Dashed line shows the level of 1 2N2−2 . Marked points on the x axis are 6-Farey points. 43 v Acknowledgements I would like to thank my advisor Özgür Yılmaz for his help and support during my two years at UBC. He has been very patient and understanding with me as well as a very good mentor for a young mathematician at the beginning of his path. I also thank him for sharing his ideas generously with me and advising me during the whole period of writing this thesis. vi Chapter 1 Introduction In signal processing, one of the main issues is encoding an analog object with finitely many number of bits in an efficient and robust way. Typically, signals of interests, i.e., audio, video signals and natural images, take their values in the continuum. These signals need to be represented by discrete- valued finite sequences in order to digitally process and transmit this data for further applications. This is called as Analog-to-digital (A/D) conversion (see [3], [4], [5], [6]). A/D conversion process consists of two main steps: sampling and quantization. Sampling is mainly collecting real-valued sample values of a function x on a sufficiently dense grid in the domain of x, i.e., the analog signal which we want to digitally process. In the A/D conversion setting, typically, x belongs to a linear space X and enjoys a decomposition x = ∑ j∈Λ xjψj where {ψj}j∈Λ is a basis or a frame for X – sampling can be seen as obtaining the values of xj in this decomposition. The goal in quantization is to replace the coefficients xj , which are in general real numbers, with some qj ∈ A, where A is a a fixed finite set, such that ‖x −∑ qjψj‖ is small for some approximation norm of interest. To make our discussion more concrete, we now consider a common ex- ample: Let X = BΩ where BΩ is the space of bandlimited functions, i.e., BΩ = {x ∈ L2 : supp x̂ ⊆ [−Ω,Ω]}. Here, x̂ denotes the Fourier transform of x. In this case, if x ∈ BΩ is sampled on a regular grid that is sufficiently dense, then x can be perfectly reconstructed from its sample values. In par- ticular, x is completely characterized by it samples {x(n/2λΩ) : n ∈ Z} for any λ ≥ 1. This is known as the classical sampling theorem. The quantity 1 Chapter 1. Introduction T = 1/2λΩ is called the sampling rate and λ is called the oversampling ratio. When λ = 1, the corresponding sampling rate is called the Nyquist sampling rate. We will visit bandlimited functions setting in Chapter 5 again. In this thesis, our main emphasis is on quantizing real numbers (this can be thought of obtaining alternative “binary” representations for real numbers). In particular, we will fix X = [0, 1] and investigate various rep- resentations of x ∈ [0, 1] by bitstreams of finite length, say N . The two important criteria in evaluation of different representations are: i) approx- imation rate and ii) robustness of the representation. The approximation rate refers to the rate with which the associated approximation error decays as N increases. On the other hand, we say that a representation is robust if we can obtain it with imperfect arithmetic and still get a decent approxima- tion error that goes to 0 as N goes to infinity. (See Section 2.1 for a more specific definition of robustness). We will start with pulse-code-modulation (PCM) methods which are based on computing truncated binary expansions of x. These are the most intuitive quantizers and in fact they provide optimally accurate approxima- tions, see [4]. On the other hand, it is well known that these schemes are not robust. This is the main motivation for considering alternative represen- tations, and in particular Sigma-Delta (Σ∆) schemes. These schemes were first devised in 1960s, [14]. There has been active research on these schemes since then and they have been popular in A/D conversion of bandlimited functions. Σ∆ schemes produce approximations the accuracy of which be- haves like an inverse polynomial in the number of bits used, and so they are significantly inferior when compared with PCM. However, Σ∆ schemes are robust with respect implementation imperfections, [3, 4, 6, 9, 19]. In this thesis, we investigate the extent to which representations of real numbers on [0, 1] via first-order Σ∆ schemes can be compressed. In partic- ular, it is known that not all 2N distinct N -bit words can be produced by running a first-order Σ∆ scheme with some input x ∈ [0, 1]. In fact, it is shown in [10] and in [12] that for every fixed initial condition in [0, 1] the number of distinct bit-streams of length N produced by Σ∆ is O(N2). Using some results from the literature on Sturmian words, e.g. [16] and 2 Chapter 1. Introduction [1], we will show that the standard first-order Σ∆ scheme (implemented per- fectly) produces only O(N3) different N -bit words with any input x and any initial condition. Furthermore, we show that the set of all codewords (which has cardinality O(N3) remains unchanged if the scheme is implemented with some unknown (but fixed) quantization offset error. Consequently, the N - bit words obtained by such a scheme can be represented using R = 3 log2N bits. It follows that after compression, the approximation rate of a first- order Σ∆ scheme becomes O(2− R 3 ). Note that in this approach we see compression as a “post-processing” stage that is performed in the digital domain. In other words, such a compression stage does not compromise robustness properties of the first-order Σ∆ schemes. On the other hand, the above reasoning is based on counting all codewords that can be obtained using a first-order Σ∆ scheme. This number, unfortunately, is affected if the scheme is implemented with “random” offset errors. In Section 4.4, we provide sufficient conditions under which the scheme, even when it is im- plemented with random offset errors, generates the same O(N3) codewords. Consequently, if these conditions are satisfied, the approximation rate of an imperfectly-implemented first-order Σ∆ scheme remains to be O(2− R 3 ). The organization of this thesis is as follows. We devote Chapter 2 to the introduction of basic notions and setup for the general A/D conversion prob- lem. Some important results regarding PCM schemes (e.g., they achieve the Kolmogorov -entropy (see [18]) when encoding restrictions of bandlimited functions to intervals, [3], [4]), important drawbacks of PCM, and basic def- initions of first and higher-order Σ∆ schemes are also given in this chapter. Chapter 3 is on Sturmian words. In particular, we highlight some results in this theory and investigate their implications for counting codewords asso- ciated with a first-order Σ∆ quantizer. In Chapter 4, we analyze the affects of various offset error types on the number of distinct codewords that can be generated by a first-order Σ∆ quantizer. We state the main theorems of this thesis in this chapter. Finally, Chapter 5 investigates the implications of our earlier results in the bandlimited settings. 3 Chapter 2 Encoding and Robustness 2.1 A/D conversion setting We start with setting the notation and describing the problem (see also [5]). Suppose that X is a compact metric space equipped with the metric induced by some norm ‖ · ‖. Our goal is to represent x ∈ X by finitely many bits. Equivalently, we wish to find a map ψ : X → {0, 1}N that is invertible. Given such a map, we define the associated N -bit encoder as: EN : x→ (ψ(x)1, ψ(x)2, . . . , ψ(x)N ) A map DN is called a decoder if it maps the range of EN to a subset of X. It can be observed that if X is a infinite set, EN can never be one-to-one which means that A/D conversion has to be lossy. We define the reconstruction error, α for a given encoder, EN , as follows: α(EN ) = inf DN sup x∈X ‖x−DN (EN (x))‖ Clearly, if ψ is invertible, α(EN ) → 0 as N → ∞. One of the important qualities of an encoder is the rate at which α(EN )→ 0 as N →∞. This is called approximation rate. The limit of this rate is determined by the space X, more precisely by the Kolmogorov -entropy of X. This is defined to be the base-2 logarithm of the smallest number k such that there exists an -net for X of cardinality k (see [18]). Another important criterion for an A/D conversion scheme is its ro- bustness. Due to imperfections of the circuits that implement the encoding algorithm, while passing from an analog value to a discrete range, some 4 2.2. PCM encoders small perturbations are introduced. In other words, the quantization for- mula of the encoder is not fully known. This motivates the following formal definition of robustness. Definition 2.1.1. (Robustness) Suppose that we have an encoder {EδN} where δ is some parameter (e.g., quantizer threshold values). We say that {EδN} is robust with respect to δ if there exists a decoder DN for Eδ0N and > 0 such that ‖x − DN (EδN (x))‖ → 0 as N → ∞ whenever d(δ, δ0) ≤ (here d is an appropriate metric on the parameter space). 2.2 PCM encoders We fix X = [0, 1). Suppose that we want to encode x ∈ X with N bits. A natural way to do that is finding the binary expansion of x and using the N -bit truncated approximation. Consider the dynamical system defined by T : u→ 〈2u〉 where 〈2u〉 denotes the fractional part of 2u, i.e., 〈2u〉 = 2u − b2uc. Next, put bi := { 1 if T i(x) ∈ [0, 12) 0 if T i(x) ∈ [12 , 1) , i = 1, 2, . . . (2.1) The PCM encoder EPCMN and an associated decoder D PCM N can be defined as EPCMN (x) = (b1, b2, . . . , bN ) and DPCMN ({bi}Ni=1) = N∑ i=1 bi2−i + 2−N−1. It can then be proved that for all x ∈ [0, 1) |x−DPCMN (EPCMN (x))| ≤ 2−N−1 5 2.2. PCM encoders and consequently, α(EPCMN ) = O(2 −N ). (2.2) PCM achieves Kolmogorov -entropy: Given a bit budget of N , the approximation rate (2.2) is the fastest rate that can be achieved by an encoder, i.e., PCM encoders achieve the Kolmogorov -entropy for X = [0, 1]. The notion of Kolmogorov entropy [18] can be explained roughly by asking the following question: Given N bits, what is the smallest value such that we can have an -net for X = [0, 1] of cardinality 2N? Here 2N is the number of points we can distribute in this interval with N bits. If we distribute these points with equal spaces in the [0, 1] interval, then the distance between them, i.e., value needed, will be order of 2−N which is the approximation rate achieved by the PCM encoders (for a discussion in a more general setting see [4]). Robustness of PCM: PCM is optimal in approximation rate and re- mains the standard encoding scheme for audio signals but it is not that as popular as its optimality might suggest. This is mainly because PCM suf- fers from various implementation difficulties and imperfections. Note that x is an analog quantity, so T i(x) must be implemented on analog hardware. Realization of a binary expansion on a circuit, i.e., dividing the interval [0, 1] into 2N equal bins, is challenging. Particularly, it can be very costly to implement a device which generates bi sequence of the PCM encoder, especially in the high-accuracy setting, i.e., when N is large. (See [3–6, 9] for further discussion). Next we will see why PCM behaves poorly under certain circuit imperfections. Proposition 2.2.1. Define {EPCM,δN } by replacing T in (2.1) with T δ : u→ 2u−b2u+δc and note that {EPCM,0N } coincides with the classical PCM encoder. Then sup x∈[0,1) |x−DPCMN (EPCM,δN (x))| ≥ δ/2. Consequently, EPCM,δN is not robust with respect to δ. 6 2.3. Another family of encoders: Σ∆ schemes Proof. Suppose: T δ : u→ 2u− b2u+ δc. Then, x = 1 2 − δ 2 ⇒ b1 = 1, b2 = 0, . . . . So, |x−∑Ni=1 bi2−i| = δ2 for all N. Thus, we cannot correct the error by choosing N larger. 2.3 Another family of encoders: Σ∆ schemes Despite the superior performance of PCM quantizers in terms of approxi- mation rate, their lack of robustness is a reason for investigation of different, more robust quantization methods. Σ∆ quantizers have been introduced in the 60s and found wide use in electrical engineering (see [13], [15] and [17] for a further reading). To quantize x ∈ X, one first finds an expansion of x in the form of x = ∑ xnen where {en} is a basis or a frame for X. Then, Σ∆ quantizers take the coefficients xn as input and generate their output recursively. For example, one-bit Σ∆ quantizers replace each coefficient xn with either -1 or 1. Although multi-bit Σ∆ quantizers are getting popular in applications, in this thesis, we will restrict our attention to one-bit quan- tizers (see [2], [7] and [14] for a general idea of one-bit quantizers). Let us start by giving the most general setup for a kth order Σ∆ quantizer. Define ∆kn(u) := k∑ i=0 (−1)l ( k l ) un−1. Note that ∆0n(u) = un and ∆ 1 n(u) = un−un−1. A kth order Σ∆ quantization scheme is defined by the following system of difference equations: ∆kn = xn − qn qn = sign(F (∆0n(u), . . . ,∆ k−1 n (u), xn)) (2.3) where F is an arbitrary function on Rk+1 chosen so that un stays bounded. It is well known that the approximation rate for a stable kth-order Σ∆ quan- 7 2.3. Another family of encoders: Σ∆ schemes tizer is order of O(N−k), where N is the bit budget allocated for the quanti- zation. This estimate falls short in comparison with PCM which achieves an exponential decay. There is a vast research area on deriving better bounds on reconstruction error, i.e., decaying faster with respect to N ([3], [9]). One other challenge with Σ∆ quantizers of order k > 1, is stability. A Σ∆ quantizer which has uniform bounds for state variables un is called to be stable and choosing an appropriate F is required to obtain a stable scheme. In [3] and [9], families of stable high-order Σ∆ quantizers are introduced. 2.3.1 First-order Σ∆ quantizers Throughout this paper we will consider and analyze only first-order Σ∆ quantizers with constant input. An ideal first-order quantizer is defined via the recursion u0 ∈ [0, 1) (initial condition); qn = Q(un−1 + x) (2.4) un = un−1 + x− qn = 〈un−1 + x〉, n = 1, 2, . . . where the quantizing map Q is given by Q(u) = { 0 u < 1 1 u ≥ 1 (2.5) In (2.4), the input x is in [0, 1), and 〈r〉 denotes the fractional part of r. Since un−1 + x remains in [0, 2) for all n, we replaced map Q by floor function in (2.4). Stability and robustness: It is not difficult to observe that un ∈ [0, 1) for all n, so ensuring stability for an ideal first-order Σ∆ quantizer is not as challenging as it is for higher order schemes. In addition, a first-order Σ∆ quantizer is known to be robust with respect to circuit imperfections. In comparison to PCM, there are several reasons why Σ∆ schemes are more reliable when quantizer imperfections are considered. In the PCM case, bi- 8 2.3. Another family of encoders: Σ∆ schemes nary expansions real numbers are essentially unique. So if any of the bits in the representation is erroneous, this error cannot be fixed by modifying the rest of the binary word. In contrast, in the case of Σ∆ quantization, every real number can produce many different codewords with similar ap- proximation properties (mainly depending on the initial state of the circuit, i.e., u0, as well as the quantizing map that is used -note that any map Q can be used in (2.4) as long as the resulting un are guaranteed to remain bounded). Because of this multitude of “good” codewords, errors that are introduced due to circuit imperfections can be implicitly corrected later in the quantization process. In Σ∆ literature, it is common to work with schemes where the quantizer alphabet is {±1} rather than {0, 1}, e.g., [19, Equation (10)]: v0 ∈ [−1, 1) (initial condition) vn = vn−1 + x− hn (2.6) hn = sign(un−1 + x) which is a special case of the higher order scheme given in (2.3). Here hn’s are quantization outputs and v is an internal state variable with v0 ∈ [−1, 1) and it can be shown that if x ∈ [−1, 1), then vn ∈ [−1, 1) for all n. For the sake of completeness, we now show that the former system (2.4) is indeed equivalent to the latter one, (2.6). Proposition 2.3.1. Let x ∈ [−1, 1). Suppose that hn are obtained via (2.6) with input x and initial condition v0 ∈ [−1, 1), and qn are obtained by running (2.4) with input x+12 and initial condition u0 = v0+1 2 . Then qn = 1 whenever hn = 1 and qn = 0 whenever hn = −1. Proof. We can re-write (2.4) as: vn + 1 = vn−1 + 1 + x+ 1− (hn + 1) (2.7) Define vn := vn + 1, x := x+ 1 and hn := hn + 1. Then vn, x ∈ [0, 2). Then 9 2.3. Another family of encoders: Σ∆ schemes we have: vn = vn−1 + x− hn hn = sign(vn − 1 + x− 1) + 1 = 2b1 2 (vn−1 + x)c (2.8) and x, vn ∈ [0, 2). Now define un := vn2 , x̃ := x 2 and qn := hn 2 . So arranging (2.8) again, we have: un = un−1 + x̃− qn qn = bun−1 + x̃c (2.9) where x̃, un ∈ [0, 1) and qn = hn + 12 . As one can observe the scheme given by (2.9) is identical to the original scheme (2.4). And there is a bijective mapping X :[−1, 1)→ [0, 1) x→ x+ 1 2 = x̃ for the inputs of two systems. So the proof is complete. Approximation rate with a simple decoder: In order to find the ap- proximation rate we assume that the data is constructed by following de- coder: DΣ∆N ({qi}Ni=1) := 1 N N∑ i=1 qi 10 2.3. Another family of encoders: Σ∆ schemes then, u1 − u0 = x− q1 u2 − u1 = x− q2 ... uN − uN−1 = x− qN uN − u0 = Nx− N∑ i=1 qi (2.10) ⇒ x− 1 N N∑ i=1 qi = 1 N (uN − u0) Note that uN ∈ [0, 1) and u0 ∈ [0, 1) ⇒ − 1 < uN − u0 < 1.∣∣∣∣∣x− 1N N∑ i=1 qi ∣∣∣∣∣ ≤ 1N (2.11) Improved approximation rates: One can improve the error bound (2.11) by using arguments from the theory of uniform distribution (along with a slightly more sophisticated reconstruction kernel). Güntürk in [8] uses the notion of discrepancy and some results on exponential sums to prove the following bound for a first-order Σ∆ quantizer:∣∣∣∣∣x− N∑ i=1 hiqi ∣∣∣∣∣ ≤ CxN−2 log2+N where {hi}Ni=1 is the triangular filter with ∑N i=1 hi = 1 and > 0 is arbitrary. Comparison of PCM and Σ∆: So far we have two main results, (2.2) and (2.11) for the reconstruction error corresponding to PCM and first-order Σ∆ respectively. Clearly, the exponential accuracy obtained via PCM is sig- nificantly superior to the inverse polynomial accuracy of Σ∆. In Chapter 3, we will derive some very useful results from the symbolic dynamics litera- ture which will bound the actual number of codewords that can be generated by a first-order Σ∆ quantizer. This will allow us to further compress bit- streams coming out of a Σ∆ quantizer and at the end of the chapter we will give an alternative comparison of the approximation rates of PCM and Σ∆ 11 2.3. Another family of encoders: Σ∆ schemes schemes after allowing a “post-compression” stage in the case of Σ∆. This alternative angle illustrates that Σ∆ schemes have “exponential accuracy” after such a compression. 12 Chapter 3 Σ∆ Quantization and Sturmian Words Recall that the recursion given in (2.4) describes an ideal first-order Σ∆ quantizer. As explained before, in order to make a fair comparison between Σ∆ quantization and PCM, we need to count the number of distinct code- words that can be generated by Σ∆ quantizer after N steps. In this chapter, we will show that using results on Sturmian words, we can achieve this task. 3.1 Sturmian words Here we will rely heavily on results on Sturmian words by Mignosi [16]. Below, we will adopt the notation of [16] whenever possible. Definition 3.1.1. [16, p.71] Let x and u0 be two real numbers with x ∈ [0, 1). Consider the sequence 〈(n − 1)x + u0〉, n ∈ N, n > 0, and define the infinite word fx,u0 = b1(x, u0)b2(x, u0)b3(x, u0) . . . by the rule: bn(x, u0) = { 0 if 〈(n− 1)x+ u0〉 ∈ [0, 1− x), 1 if 〈(n− 1)x+ u0〉 ∈ [1− x, 1), (3.1) where for any real number r, 〈r〉 is the fractional part of r. We will write bn instead of bn(x, u0) whenever there is no possibility of confusion. Proposition 3.1.2. The first N elements generated by the equation (3.1) with input x and inital value u0, say {bi}Ni=1, is identical to the ones gener- ated by the first-order Σ∆ quantizer in (2.4) with the same input and initial value, say {qi}Ni=1. 13 3.1. Sturmian words Proof. Fix k ≤ N . We first find a non-recursive formula for qk. By (2.4) q1 = bx + u0c and u1 = 〈x + u0〉. In turn, q2 = bx + 〈x + u0〉c and u2 = 〈x+ 〈x+ u0〉〉. Repeating this argument, one can observe that qk = x+ 〈x+ 〈 . . . 〈x︸ ︷︷ ︸ (k−1)times +u0〉〉 . . . 〉 . Now, observing that 〈x+ 〈 . . . 〈x︸ ︷︷ ︸ (k−1)times +u0〉〉 . . . 〉 = 〈(k− 1)x+ u0〉, we can write qk = bx+ 〈(k − 1)x+ u0〉c. So, in other words: qk = { 0 if 〈(k − 1)x+ u0〉 ∈ [0, 1− x), 1 if 〈(k − 1)x+ u0〉 ∈ [1− x, 1), Since k is arbitrary {qi}Ni=1 is identical to {bi}Ni=1 as claimed. If x = p/q with p, q coprime natural numbers, then it is easy to see that fx,u0 is periodic with minimal period q. If x is irrational then fx,u0 is not ultimately periodic and it is called Sturmian. Definition 3.1.3. [16, p.74] For every word f over an alphabet S and for any natural number N > 0, gf (N) is defined to be card(F ∩{0, 1}N ), where F is the set of subwords of f . In this thesis, the alphabet we will consider is S = {0, 1}. Then the Sturmian words are exactly the non-ultimately periodic words f such that gf (N) = N + 1. For the following definition, we will stick to the notation used in Mignosi’s paper, [16]. Definition 3.1.4. [16, p.73] (Farey points) For any natural number N > 0, a point x ∈ [0, 1] is an N-Farey point if it is of the form x = p/q with p and q coprime natural numbers, p ≥ 0, 1 ≤ q ≤ N . We notice that, 0 and 1 are two Farey points for any natural number. Here are some early results derived in [16]. 14 3.1. Sturmian words Proposition 3.1.5. Let x ∈ [0, 1) and fx,u0 , Fx,u0 and gf be defined as above. Then the followings hold. (i) [16, Corollary 3, p.73] The set Fx,u0 of subwords of fx,u0 depends only on the sequence {−ix}, i ∈ N, i > 0, and consequently, depends only on x and does not depend on u0. So we can assume u0 = 0 and use fx and Fx from now on. (ii) [16, Corollary 4, p.73] For any natural number N > 0, and for any x ∈ (0, 1), gfx(N) ≤ N + 1; if x = p/q with p and q coprime natural numbers, then gfx(N) ≤ q. (iii) [16, Theorem 6, p.74] For each natural number N > 0, if x ∈ (0, 1) is not an N -Farey point then gfx(N) = N + 1; if x ∈ (0, 1) is such that x = p/q with p and q coprime natural numbers g ≤ N , then gfx(N) = q. Below, fx denotes fx,0, and Fx denotes Fx,u0 (because the set Fx,u0 does not depend on u0, we drop the subscript u0). In [16], Mignosi uses these results to determine the number of distinct length-N subwords of all possible infinite words that could be generated by the scheme given in (3.1). In other words, [16] calculates the cardinality of the set AN := ⋃ x∈[0,1) Fx ∩ {0, 1}N . In order to achieve this, Mignosi establishes the following important facts. Proposition 3.1.6. Let N ∈ N be given. Then the followings hold. (i) [16, Corollaries 9-10 and Theorem 11] Let t and u be two consecutive N -Farey points. Then for any x, y ∈ (t, u) with x < y, we have Fx ∩ {0, 1}N = Fy ∩ {0, 1}N . Moreover, Fx∩{0, 1}N ⊃ Fu∩{0, 1}N and Fx∩{0, 1}N ⊃ Ft∩{0, 1}N . (Note that from Proposition 3.1.5, we also know that gfx = gfy = card(Fx ∩ {0, 1}N ) = N + 1.) 15 3.1. Sturmian words (ii) [16, Corollary 15] If t < x < u = p/q < y < v where t, u, v are three consecutive N -Farey points with p and q coprime natural numbers then Fx ∩ Fy ∩ {0, 1}N = Fu ∩ {0, 1}N and so card((Fy ∩ {0, 1}N ) − Fx) = N − q + 1. (iii) [16, Theorem 16] If 0 < x < u = p/q < y < v where u, v are two consecutive N -Farey points with p and q coprime natural numbers then ((Fy ∩ {0, 1}N )− Fu) ∩ Fx = ∅. Proposition 3.1.6 is enough to determine the cardinality of AN . If there are a total of K N -Farey points, including 0 and 1, then there are K − 1 mutually exclusive subintervals between them. Let us order these N -Farey points and call the subinterval between ith and (i+ 1)st N -Farey points as T (i). Proposition 3.1.6-(i) basically says that all points in set T (i) has the same length-N subword set, which can be denoted as: GNi := Fx ∩ {0, 1}N , x ∈ T (i) whose cardinality is N + 1. In addition, by Proposition 3.1.6-(ii) the inter- section of GNi−1 and G N i is the length-N subword set of ith N -Farey point, which can be denoted as: FNi := Fy ∩ {0, 1}N = GNi−1 ∩GNi where y is the ith N -Farey point. If the ith N -Farey point can be written as p/q, p, q coprime, then card(FNi ) = q. So we can observe that AN =⋃ i<K G N i . Finally Proposition 3.1.6-(iii) says that given an interval T (i) (one of the K− 1 intervals explained above), the length-N subwords introduced by this interval, in addition to the ones produced by previous intervals, have the cardinality of card(GNi \GNi−1). In other words, given i: card(GNi \ ⋃ j<i GNj ) = card(G N i \GNi−1) = N − q + 1 where ith N -Farey point can be written as p/q, p, q coprime. 16 3.2. Possible codewords of Σ∆ quantization Cardinality of AN : Combining all results and arguments above, we can calculate that: card(AN ) = N + 1 + N∑ j=2 (N − j + 1)× card({p/j ∈ (0, 1) : p, j coprime}) (3.2) It is a fact that card({p/j ∈ (0, 1) : p, j coprime}) = ϕ(j) where ϕ is the Euler function. Using results from [11, p.268], the desired result follows. Theorem 3.1.7. card(AN ) is asymptotically equivalent to N 3 pi2 . 3.2 Possible codewords of Σ∆ quantization Now we want to count all possible codewords of length N that can be gen- erated by a single bit ideal first-order Σ∆ quantizer where x and u0 are in [0, 1). To this end, we will use the main results from the previous sec- tion. Recall that given x ∈ [0, 1), the set of all length-N subwords of the infinite word generated by x via (3.1) does not depend on the initial value u0. In the case of Σ∆ quantization, by Proposition 3.1.2, our codewords are the first N bits of these infinite sequences. So given x, different choices of u0 may give different codewords. Next we will show that the two slightly different formulations, i.e., “fixing u0 and considering all possible length-N subwords” and “varying u0 and considering only the first N bits”, are in fact equivalent. First we introduce some notation. Definition 3.2.1. Consider fx,u0 and corresponding bn(x, u0), n ≥ 0 defined in (3.1). Now given u0 ∈ [0, 1), define Au0(N) := {{bi(x, u0)}Ni=1 : x ∈ [0, 1)} to be the all possible outcomes of a single bit ideal Σ∆ quantizer with fixed initial value, u0, and for all x ∈ [0, 1). This should not be confused with AN which was defined in the previous section. AN was the set of all possible length-N subwords of infinite words 17 3.2. Possible codewords of Σ∆ quantization generated by the first-order Σ∆ quantizer (equivalently by (3.1)) for all x, u0 ∈ [0, 1), whereas Au0(N) is the set of length-N words that consist of the first N bits generated by the Σ∆ quantizer with fixed u0 but for all x ∈ [0, 1). We are interested in determining card(⋃u0∈[0,1)Au0(N)). Proposition 3.2.2. Given N ∈ N, ⋃ u0∈[0,1) Au0(N) = AN Proof. For simplicity, call Y := ⋃ u0∈[0,1)Au0(N). It is obvious that each element of Y also belongs to AN . Now fix x ∈ [0, 1). Remember that initial value is not important for AN . We need to prove that each subword of the infinite word fx,0, indeed belongs to Y . Say, fx,0 = b1(x, 0)b2(x, 0) . . . as defined in (3.1). Fix an arbitrary natural number m > 0 and let {bm, . . . , bm+N−1} be our arbitrary subword. By (3.1), bm = bx+〈(m−1)x〉c. Now choose u0 = 〈(m− 1)x〉 and consider the word fx,u0 = a1(x, u0)a2(x, u0) . . .. Since u0 ∈ [0, 1), {ai}Ni=1 clearly belongs to Y . So it is enough to show that {ai(x, u0)}Ni=1 = {bi}i=m+N−1i=m By (3.1) a1(x, u0) = bx+ 〈(m− 1)x〉c which is equal to bm. Fix 1 < k ≤ N : ak = bx+ 〈(k − 1)x+ 〈(m− 1)x〉〉c = bx+ 〈(k +m− 2)x〉c on the other hand: bm+k−1 = bx+ 〈(m+ k − 1− 1)x〉c = bx+ 〈(m+ k − 2)x〉c ⇒ ak(x, u0) = bm+k−1(x, 0) Since k is arbitrary, our claim becomes true which completes the proof. So, we proved the following important fact about first-order Σ∆ schemes 18 3.3. An alternative comparison between PCM and Σ∆ with constant input. Theorem 3.2.3. The total number of length-N codewords that can be pro- duced using the first-order Σ∆ scheme in (2.4), regardless of the initial con- dition u0 ∈ [0, 1) and the input x ∈ [0, 1) is asymptotically equivalent to N3/pi2. Remark: A weaker version of this result was known in the Σ∆ literature. In particular, in [10] and [12] it is shown that if the initial value of the quantizer is fixed and input x ∈ [0, 1), the number of different codewords is O(N2). This result will be derived in Section 4.2 of this thesis. 3.3 An alternative comparison between PCM and Σ∆ In this chapter we have shown one of the main observations of this thesis: Number of different codewords that can be generated by an ideal Σ∆ quan- tizer is only order of O(N3), more precisely, asymptotically equivalent to N3 pi2 while there are 2N binary words of length N . Accuracy of first-order Σ∆ schemes: The observation above means that {qi}Ni=1, the “raw” codewords obtained by the first-order Σ∆ scheme via (2.4) can be compressed substantially. In particular, since there are a total of N3/pi2 codewords, we only need N3 distinct labels (we omit 1/pi2 in the rest of the discussion), thus R = 3 log2N bits to encode all these codewords in a lossless fashion. In other words, there is a bijection ψN,R : AN 7→ {1, 2, . . . , 2R} with R = 3 log2N . Consequently, we can calculate the “actual accuracy” of the first-order Σ∆ schemes in terms of this new bit rate. In particular, set ẼΣ∆R := ψN,R ◦ E Σ∆ N , D̃ Σ∆ R := D Σ∆ N ◦ ψ −1 N,R. Then we have the following. 19 3.3. An alternative comparison between PCM and Σ∆ Theorem 3.3.1. In the setting described above, we have sup x∈[0,1) |x− D̃Σ∆R (ẼΣ∆R (x))| ≤ 2−R/3, regardless of the initial condition u0. Proof. Because ψN,R is a bijection, we clearly have D̃Σ∆R (Ẽ Σ∆ R (x)) = D Σ∆ N (E Σ∆ N (x)) for all x ∈ [0, 1). We also know that sup x∈[0,1) |x−DΣ∆N (EΣ∆N (x))| < 1/N. Substituting R = 3 log2N above yields the desired result. Since ψN,R(AN ) can be encoded using R bits, Theorem 3.3.1 shows that, after a post-compression stage (which is lossless), we get the approximation error corresponding to the first-order Σ∆ scheme to be O(2− R 3 ), comparable to O(2−N ), which is the optimal rate and is achieved by the PCM quantizer (see (2.2)). Note that for the Σ∆ case, after quantization step we will need to com- press the output codewords. This can be done adaptively by using tech- niques from adaptive coding and data compression. One of the main reasons Σ∆ schemes are preferred in practice over PCM is their superior robustness properties. It is important to note that a post- compression stage will be performed once the analog input is converted to a digital bitstream. Since the operations in the digital domain can be typically done with perfect accuracy, this compression stage does not influence the robustness properties of the underlying Σ∆ scheme. On the other hand, the total number of possible codewords depend (sensitively) on the actual parameters that are used when implementing the scheme, and may increase if the ideal scheme given in (2.4) is replaced with some non-ideal version. This issue will be discussed in Chapter 4 in detail. 20 Chapter 4 Error Analysis of Σ∆ Quantization In this chapter, we first formalize certain types of imperfections that may be considered while designing an encoder. For such imperfections, it is well known that Σ∆ schemes are robust in the sense of Definition 2.1, e.g., [3]. However, in this thesis, our main emphasis is the total number of length-N codewords produced by a Σ∆ scheme, and as alluded to above, this number may depend on the actual parameters that are used in the implementation. In this chapter, we investigate this dependence. In the previous chapter, we counted all possible codewords that can be generated by an ideal Σ∆ quantizer. Our counting technique took the advantage of considering all possible inputs, x, and initial values, u0, from the interval [0, 1). But it has to be noted that given a constant input x, the outcome of the quantizer contains information on the initial value u0. This is because, unlike the case when considering all subwords of the infinite word generated by x, in Σ∆ quantization we deal with the first, say, N bits of the sequence. So in further analysis, we will talk about the effect of u0 often. 4.1 Constant offset error First, we consider the “imperfect” first-order Σ∆ quantizer with a constant offset error δ ∈ (−δmax, δmax), where δmax > 0 is some fixed margin. A non-ideal quantizer with offset error will have a quantizer threshold of 1− δ. 21 4.1. Constant offset error More precisely, this new quantizer is described by: qδn = Q(ũn−1 + x+ δ) ũn = ũn−1 + x− qδn (4.1) n = 1, 2, . . . Here the quantizing map Q is as in (2.5), and {qδi }Ni=1 is the output vector of the system. It is well known that such an imperfect quantizer still generates approximations to x with approximation error of the order O(N−1), i.e., the first-order Σ∆ scheme is robust with respect to constant offset errors. Next, we investigate the set of possible codewords that can be obtained using the scheme described in (4.1). The following lemma is essentially identical to [10, Lemma 2.1]. Since the underlying Σ∆ scheme in [10] is slightly different than the ones given in this thesis, we will give a somewhat different proof here. Lemma 4.1.1. Let x ∈ [0, 1) and δ ∈ (−δmax, δmax) be fixed. Suppose {qδn}Nn=1 is obtained by running (4.1) with some initial condition ũ0. Then {qδn}Nn=1 is identical to the output sequence {qn}Nn=1 that is obtained using the ideal Σ∆ quantizer, given in (2.4) quantizer with the initial condition u0 := ũ0 + δ. Proof. We will prove this by induction. Our claim is that for all n ∈ N, qn = qδn and un = ũn + δ. First set n = 1 and note that ũ1 = u0 + x−Q(u0 + x+ δ)︸ ︷︷ ︸ qδ1 +(δ − δ) u1 = (u0 + δ) + x−Q(u0 + x+ δ)︸ ︷︷ ︸ q1 . Consequently, our claim is true for n = 1. Now assume that the claim is 22 4.2. Number of codewords with fixed initial value and offset error true for n. Then ũn+1 = ũn + x+−Q(ũn + x+ δ)︸ ︷︷ ︸ qδn+1 +(δ − δ) (4.2) un+1 = un + x−Q(un + x)︸ ︷︷ ︸ qn+1 By our hypothesis, ũn + δ = un. It follows that Q(ũn + x+ δ) = Q(un + x), and thus qδn = qn. In addition, we can write (4.2) again as: ũn+1 = un + x−Q(un + x)− δ which proves ũn+1 = un+1 − δ. This shows that first-order Σ∆ schemes are insensitive to fixed (but unknown to the both the encoder and the decoder) offset error. To ensure that the number of distinct codewords remain O(N3), the initial condition u0 of the ideal scheme should remain in [0, 1). This can be guaranteed by choosing ũ0, the initial condition of the non-ideal scheme, in [δmax, 1−δmax). Another issue here is stability of this new scheme: we need to ensure that |ũn| remain bounded. We can show that if δmax < 1/2 and ũ0 ∈ [δmax, 1−δmax), we have −δmax ≤ ũn < 1 + δmax, ∀n > 0. 4.2 Number of codewords with fixed initial value and offset error In Chapter 3, we showed that the number of all codewords that can be generated by a first-order Σ∆ quantizer is of order O(N3). In this section, we consider the case of arbitrary but fixed initial value and fixed offset error, and review some results in the literature that provide upper bounds on the number of distinct codewords in this setting. As discussed in the previous section, studying a Σ∆ quantizer with a fixed initial value u0 and fixed offset error δ reduces to the case of studying the ideal quantizer with initial 23 4.2. Number of codewords with fixed initial value and offset error value u0 + δ, i.e., Σ∆ quantizer is insensitive against fixed and bounded offset errors. So we will only consider nonideal quantizers. Let us assume that an arbitrary initial value u0 ∈ [0, 1) is given. It is obvious that the number of all possible codewords that can be generated in this setup with a constant input from [0, 1) is order of O(N3), since this is the total number of codewords over all possible initial values. In fact, it has been well known that the number of length-N codewords for a first-order Σ∆ quantizer with a fixed arbitrary initial value is O(N2), e.g. [12]. For the special case of u0 = 0, number of distinct codewords of length-N becomes closely related to number of N -Farey points which is asymptotically equivalent to 3N 2 pi2 . For this result we stick to the notation in [10] and give a proof for the sake of completenes. Below, [N ] denotes the set {1, 2, . . . , N}. Proposition 4.2.1. [10, Lemma 2.2] Fix u0 ∈ [0, 1) and define the sequence {sj}Jj=1 by ordering every distinct element of the set SN (u0) := {(z − u0)/n : z ∈ [n], n ∈ [N ]} ∪ {0, 1} so that 0 ≤ s1 < s2 < . . . sJ ≤ 1. Then all x ∈ [sj , sj+1), when used as the input of the first-order Σ∆ scheme in (2.4) with the initial condition u0, result in the same codeword (q1, q2, . . . .qn). The points sj are called the associated quantization threshold crossings. Proof. Let x, u0 ∈ [0, 1), suppose we run the scheme in (2.4) to obtain un and qn. Then since x + un remains in [0, 2) for all n (this follows from the stability of the first-order Σ∆ scheme) and since for u ∈ [0, 2), Q(u) = buc, we can rewrite (2.4) (with the given initial condition u0) as qn = bun−1 + xc un = 〈un−1 + x〉 Then by a series of recursive substitution as in (2.10), we have un = u0 + nx− n∑ i=1 qi (4.3) 24 4.2. Number of codewords with fixed initial value and offset error On the other hand, using un = 〈un−1 + x〉, we can check that u1 = 〈u0 + x〉 u2 = 〈u1 + x〉 = 〈〈u0 + x〉+ x〉 = 〈u0 + 2x〉 ... un = 〈u0 + nx〉 (4.4) Combining the two formulas (4.3) and (4.4), we get: Zn := n∑ i=1 qi = bu0 + nxc (4.5) It can be shown that the sequence {qi}ni=1 is uniquely determined by the sequence {Zi}ni=1, and vice versa (see [10, Appendix A]). Since Zn changes value at the points {x = (j − u0)/n : j ∈ [n]} (at x = 0, Zn = 0 for all n and at x = 1, Zn = n for all n). So distinct intervals [sj , sj+1) given by the (ordered) threshold points in SN correspond to distinct N - tuples {Zi}Ni=1 and thus to distinct length-N codeword {qi}Ni=1. So, the cardinality of distinct codewords generated by this quantizer will be equal to the cardinality of the set SN . It can be observed that cardinality of SN (u0) can be at most N(N+1) 2 + 1 which is of order O(N2). For the special case of u0 = 0, some of the values are repeated, so SN (0) becomes the set of N -Farey points, i.e., {j/n ∈ [0, 1] : gcd(j, n) = 1} and its cardinality is asymptotically equivalent to 3N2 pi2 ≈ 0.304N2 as N → ∞. It can be also proven that if u0 is irrational, every distinct (j, n) pair produces a distinct point in SN , and consequently the number of distinct codewords attains its maximum. It is important to note that for each distinct value of u0, the corresponding set of O(N2) output codewords may be different (depending on u0). Besides, we know that total number of all possible codewords with u0 ∈ [0, 1) is order of O(N3) (in fact asymptotically equivalent to N3/pi2). It is interesting to observe that an uncountable union of sets, each with O(N2) elements has a cardinality that 25 4.3. Varying offset error is only of order O(N3). 4.3 Varying offset error Another imprecision type we will consider is a nonideal quantizer with offset error changing with n independently, i.e., put δn in place of δ in (4.1) where the only information we have on δn is that |δn| < δmax for all n where δmax is an appropriate margin. For now, we will assume that δmax < 1/4. Clearly, this is a harder case to analyze since we can no longer compensate the effect of offset error by changing the initial value. Instead, we need to do a finer analysis. We first give the recursion that describes this new “imprecise” first-order Σ∆ scheme: q̂n = Q(ûn−1 + x+ δn) ûn = ûn−1 + x− q̂n, (4.6) n = 1, 2, . . . where the quantizing map Q is as in (2.5) and δn ∈ (−δmax, δmax) are arbitrary. Our goal again is to count the number of codewords that can be generated by this quantizer. It is non-trivial to relate this question to the results given in Chapter 3 where we considered all possible initial values and constant inputs from [0, 1) with the ideal scheme. Our results in Section 4.2, where we counted distinct codewords when u0 is fixed and when we had a constant offset error, do not generalize to the varying offset error case. Here, we will again fix û0, arbitrarily chosen from some interval, and we seek the total number of possible output codewords over all admissible input values. In this case (i.e., when û0 is fixed and the offset error is varying), the value of û0 and δmax have a significant effect on the upper bounds for the number of codewords. 26 4.3. Varying offset error 4.3.1 Non-recursive formulation The scheme given in (4.6) is a recursive formula, and therefore it is difficult to analyze. In order to determine the quantization thresholds, we first obtain a non-recursive formulation as we have in the proof of Proposition 4.2.1. It is easy to see that ûn = û0 + nx− n∑ i=1 q̂i (4.7) Note that this is essentially identical to (4.3). In order to get a relation similar to (4.4), we will assume that quantizing map Q behaves as a floor function. For that assumption to be true, ûn−1 + x + δn should remain in the interval [0, 2). Then we can do the following induction: û1 = û0 + x− bû0 + x+ δ1c+ (δ1 − δ1) = 〈û0 + x+ δ1〉 − δ1 û2 = û1 + x− bû1 + x+ δ2c+ (δ2 − δ2) = 〈û1 + x+ δ2〉 − δ2 = 〈〈û0 + x+ δ1〉 − δ1 + x+ δ2〉 − δ2 = 〈û0 + 2x+ δ2〉 − δ2 ... ⇒ ûn = 〈û0 + nx+ δn〉 − δn (4.8) Combining (4.7) and (4.8), we get: 〈û0 + nx+ δn〉 − δn = û0 + nx− n∑ i=1 q̂i + (δn − δn) ⇒ Ẑn := n∑ i=1 q̂i = bû0 + nx+ δnc (4.9) As it can be observed in (4.9), Ẑi is only affected by the offset error that occurs at the ith step, i.e., δi. Also, an argument as in the proof of Proposi- tion 4.2.1 shows that the sequence {Ẑi}ni=1 uniquely determines the output 27 4.3. Varying offset error codeword {q̂i}ni=1. For further analysis, we will take advantage of (4.9), but first we state the conditions on the ranges of û0 and x in order to have a stable system and thus to be able to use the argument above. Lemma 4.3.1. Consider the Σ∆ scheme in (4.6). Let |δn| < δmax for all n ≥ 1 and δmax < 1/4. If x ∈ (2δmax, 1 − 2δmax) and û0 ∈ [0, 1), then ûn + x + δn+1 ∈ [0, 2) for all n ≥ 1 and ûn remains bounded with ûn ∈ [−δmax, 1 + δmax) for all n > 0. Proof. It is trivial that ûn + x + δn+1 ∈ [0, 2) holds for n = 0. By using the relation ûn+1 = ûn + x − Q(ûn + x + δn+1) for n = 0, we can see that û1 ∈ [−δmax, 1 + δmax) and û1 + x + δ2 ∈ [0, 2). Since the claim holds for n = 0 and n = 1, by the nature of recursive algorithm of the scheme, it will hold for all n > 0. 4.3.2 Threshold regions To find quantization thresholds of the scheme given in (4.6), we use the equation (4.9) as we used (4.5) in the ideal quantizer case. It can be observed that when û0+nx+δn is a natural number, Ẑn changes value, which uniquely corresponds to a change in q̂n. Since we have an independent offset errors δn, in this setting instead exact threshold points, we have threshold regions. Definition 4.3.2. Consider the nonideal N -bit Σ∆ quantizer with varying offset error δ := {δ1, . . . , δN} where δn ∈ (−δmax, δmax) for n ≥ 1 and constant input x ∈ (2δmax, 1 − 2δmax). Let û0 ∈ [0, 1) be fixed. Define the map tû0(z, n, δ) and interval Iû0(z, n) for z ∈ [n], n ∈ [N ], as follows: tû0 : (z, n, δ)→ z − û0 − δn n (4.10) Iû0(z, n) := ( z − û0 − δmax n , z − û0 + δmax n ) (4.11) Then we can define the set of threshold regions and points as follows: RN (û0) := {Iû0(z, n) : Iû0(z, n) ∩ (2δmax, 1− 2δmax) 6= ∅, z ∈ [n], n ∈ [N ]} TN (û0, δ) := {tû0(z, n, δ) : Iû0(z, n) ∈ RN (û0), z ∈ [n], n ∈ [N ]} 28 4.3. Varying offset error RN (û0) is a set of intervals Iû0(z, n), each of which has at least one quantization threshold point, tû0(z, n, δ). Observe that RN (û0) does not depend on the sequence {δn}Nn=1 whereas TN (û0, δ), i.e., the exact locations of the threshold points, depends on {δn}Nn=1. All points belonging to the interval between two consecutive quantization threshold points, generate one and the same codeword. Since the domain of input is not [0, 1) but [2δmax, 1 − 2δmax) anymore, before considering the affect of varying input, in the following lemma, we will derive the number of distinct codewords if the threshold point tû0(z, n, δ) was in the middle of the interval Iû0(z, n), i.e., if δn = 0 for all n. Definition 4.3.3. Consider the nonideal N -bit Σ∆ quantizer with offset threshold δmax and initial value û0. (i) The interval (2δmax, 1 − 2δmax) is called the admissable region and a pair (z, n) is called as admissable pair if Iû0(z, n) ∈ RN (û0). (ii) We define the set of original quantization thresholds as follows: ŜN (û0) := {(z − û0) n : (z, n) is admissable pair} Notation: Observe that ŜN (û0) = TN (û0, 0), where δ = 0 means δn = 0 for all n > 0. Similarly |δ| < δmax means |δn| < δmax for all n. In the rest of discussion, we omit û0 in the notation when there is no chance of confusion. Lemma 4.3.4. Consider the ideal N -bit Σ∆ quantizer with constant input x ∈ (2δmax, 1−2δmax). Let û0 ∈ [0, 1) and δmax < 1/4. Then card(ŜN (û0)) N2. Proof. First observe that card(ŜN (û0)) < card(SN (û0)) ≤ N(N+1)2 + 1 since admissable region is smaller than [0, 1). It is enough to count the integer values bû0 + nxc can take. Fix 1 ≤ n0 ≤ N . The range is: 2n0δmax < û0+n0x < n0+1−2n0δmax. If δmax < 1/4, then n0+1−2n0δmax > 2n0δmax. Number of integer values in this range depends on δmax and can be calculated 29 4.3. Varying offset error to be n0 − 2b2n0δmaxc. Now consider the sequence { b k2δmax c }2Nδmax k=0 . We can observe that if b k2δmax c < n0 < b k+12δmax c, then: n0 − 2b2n0δmaxc = n0 − 2k So we can write the following equalities: card(ŜN (û0)) = 1 + 2Nδmax−1∑ k=0 b k+1 2δmax c∑ i=b k 2δmax c+1 (i− 2k) = 1 + 2Nδmax−1∑ k=0 b k+1 2δmax c∑ i=b k 2δmax c+1 i− 2 2Nδmax−1∑ k=0 b k+1 2δmax c∑ i=b k 2δmax c+1 k = 1 + N∑ i=1 i− 2 2Nδmax−1∑ k=0 k b k+1 2δmax c∑ i=b k 2δmax c+1 1 Observe that: 1 2δmax − 2 < b k+1 2δmax c∑ i=b k 2δmax c+1 1 < 1 2δmax Using the right inequality, it follows: card(ŜN (û0)) > 1 + N∑ i=1 i− 2 1 2δmax ( 2Nδmax−1∑ k=0 k ) From here, it can be calculated that card(ŜN (û0)) & N2(0.5 − 2δmax) as N →∞. This shows that O(N2) is also a lower bound for card(ŜN (û0)). But if the orientation of threshold points with respect to themselves change due to a different error sequence, intervals between them will produce different codewords. We can formulate the set that we want to count with a similar notation to Definition 3.2.1, as follows: Definition 4.3.5. Consider the nonideal N -bit Σ∆ quantizer with initial 30 4.3. Varying offset error value û0 ∈ [0, 1) be fixed. Let Âδmaxû0 (N) denote the set of all possible N -bit output codewords, {q̂i}Ni=1, that can be generated by the scheme (4.6) for all possible inputs x ∈ (2δmax, 1− 2δmax) and {δn}Nn=1 sequences within the bounds |δn| < δmax. The cardinality of Âδmaxû0 (N) depends on δmax and û0. If every threshold point was in the middle of corresponding threshold region, i.e., if δn = 0 for all n, then we would have the number of codewords to be order of O(N2). Next, we will investigate the affect of varying offset error on the number of codewords. Definition 4.3.6. Consider the quantization thresholds and regions given in Definition 4.3.2 for a fixed û0 ∈ [0, 1). Assume that there is a subset D of RN (û0) with k elements, say D = {Ijû0}kj=1, which has the following properties: ⋂ 1≤j≤k Ijû0 6= ∅ ⋂ 1≤j≤k Ijû0 ∩ Iû0 = ∅ for all Iû0 ∈ (RN (û0) \ D) Such a set D will be referred to as a k-degree intersection. Definition 4.3.7. Assume that û0 ∈ [0, 1), N is fixed, and we have a se- quence of errors δ = {δn}Nn=1. Let us label the original quantization thresh- olds in the increasing order as: t1 ≤ t2 ≤ . . . tl−1 ≤ tl such that TN (û0, 0) = {t1, . . . , tl} where l = card(TN (û0, 0)). Note that ti = t(z, n, 0) for some (z, n) pair and i ∈ [l]. For a given input x ∈ (2δmax, 1 − 2δmax) we define the binary word bx,δ(i) by: bx,δ(i) := { 0 if x < tû0(z, n, δ) and ti = tû0(z, n, 0) 1 if x ≥ tû0(z, n, δ) and ti = tû0(z, n, 0) i = 1, 2, . . . , l 31 4.3. Varying offset error Remark: The original threshold points ti may change their orientation with respect to each other when an offset error is introduced. But we keep labelling them with respect to their initial order in the original case. When x and δ are fixed, the word bx,δ actually tells the location of x with respect to perturbed threshold points. Observe that the word bx,δ remains fixed if x varies in the interval between two consecutive threshold points. Proposition 4.3.8. Assume that N and û0 ∈ [0, 1) are fixed. Consider the set of all possible binary words bx,δ for all x ∈ (2δmax, 1 − 2δmax) and |δ| < δmax: Bδmaxû0 := ⋃ x,δ bx,δ Then there is a bijection between Bδmaxû0 and Â δmax û0 (N). Proof. Suppose for some x, δ, we have bx,δ = b. Then define L(x) := {t(z, n, δ) ≤ x : (z, n) is admissable pair} which consists of all quantization threshold points that remain to the left of x (when δ is given). Note that L(x) is completely and uniquely determined by b (i.e., different b gives differ- ent L(x)). On the other hand, the set L(x) uniquely determines the sequence {Ẑn}Nn=1 which was defined to be the partial sum of a codeword, i.e., Ẑn =∑n i=1 q̂i. Indeed, fix n ∈ [N ], and define z0 := max{z : t(z, n, δ) ∈ L(x)}. If {z : t(z, n, δ) ∈ L(x)} = ∅, set z0 = 0. Then, t(z0, n, δ) ≤ x < t(z0 + 1, n, δ), and this implies Ẑn = z0. To see this, recall that Ẑn = bû0+nx+δnc and the points where Ẑn changes value are actually the quantization threshold points given in (4.10). Since n is arbitrary, given the set L(x) the sequence {Ẑn}Nn=1 can be determined. In addition, a different L(x) would produce a different {Ẑn}Nn=1 sequence since any change in the orientation of a given point x with respect to quantization points (being on the left or right of them) affects the digits of Ẑn. Finally, as there is a one-to-one correspondence between {Ẑn}Nn=1 and {q̂n}Nn=1 sequences, we conclude that whenever word b is given, a codeword {q̂n}Nn=1 is uniquely determined, i.e., different b corresponds to different {q̂n}Nn=1. This implies that card(Bδmaxû0 ) ≤ card(Âδmaxû0 (N)). A similar argument can be used in order to show the opposite of this re- sult. In other words, given a codeword {q̂n}Nn=1 for some x, δ, there is a 32 4.3. Varying offset error unique binary word b that corresponds to this codeword. Changing the codeword would result in getting a different binary word. This implies that card(Bδmaxû0 ) ≥ card(Âδmaxû0 (N)). So we conclude that cardinalities of two finite sets Bδmaxû0 and Â δmax û0 (N) are equal which completes the proof. Theorem 4.3.9. Let û0 ∈ [0, 1), N and δmax be fixed in the scheme (4.6). If there exists a k-degree intersection set D, then card(Âδmaxû0 (N)) is at least 2k. Proof. Let us say that original threshold points are {tj}lj=1 in the increasing order and we know that l is order of O(N2). Now assume that for some index set Λ with cardinality k, D = {Ij}j∈Λ where Ij is the threshold region that has the center at tj . By definition of k-degree intersection we know that, points with indices in Λ can change order with respect to themselves in every way possible. This implies that the restriction bx,δ |Λ can have every possible combination of binary sequences with length k, for some x value and δ sequence. Since there are 2k such binary sequences, and at least 2k different bx,δ sequences, we conclude that there are as many different codewords, {qn}Nn=1 that belong to Âδmaxû0 (N). This completes the proof. Theorem 4.3.9 gives an exponential order for the number of codewords that can be generated by a single k-degree intersection. For a given k ≤ N , existence and the number of k-degree intersections depend on the initial value û0 and δmax. Because the former determines the location of the quan- tization threshold regions and the latter determines the size of them. For instance if û0 = 0 or û0 = 0.5, then N/2 quantization threshold regions are centered at 0.5 due to points {z/n : n = 2z, n ≤ N}. Then no matter δmax is, we have at least one N2 -degree intersection. This is not desired since we would need too many bits to represent output codewords of order O(2N/2). In the ideal case, we took advantage of relatively small number of distinct words that could be generated, so we could make a reasonable comparison between approximation rates of Σ∆ quantization and PCM method. But in the case of varying offset error, this comparison can easily fail for certain u0 and δmax values. So we need to derive some conditions on these values in 33 4.3. Varying offset error 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 !0.4 !0.2 0 0.2 0.4 0.6 0.8 1 1.2 1.4 N=15 offset=0.05 u0=0.13 x y Figure 4.1: Quantization threshold regions, with levels depending on n order not to have any (k-degree) intersections. Definition 4.3.10. Let û0 ∈ [0, 1), N ∈ N and δmax < 1/4 be given. Assume that n0 and n1 are given with n0 + m = n1 ≤ N , m > 0. If there exist z0 ≤ n0 and z1 ≤ n1 such that Iû0(z0, n0)∩Iû0(z1, n1) 6= ∅, then we say that there is an m-level intersection. If Iû0(z0, n0) and Iû0(z1, n1) belong to RN (û0) then we say that intersection is in the admissable region. For an easier visualization of intersections defined above, see Figure 4.1. Each quantization threshold region Iû0(z, n0) is drawn at the level y = n0/N and at each level there are n0 intervals. Center of the interval Iû0(z, n) is located at ( z−û0n ) and its size is 2δmax n . Vertical lines on the left and right are the boundaries for admissable region, with equations x = 2δmax and x = 1− 2δmax. Definition 4.3.11. Let us be given two intervals I and J . We say that I is on the left of J if for all x ∈ I, y ∈ J , we have x < y. Denote it as I < J . If I is on the left of J , then J is on the right of I, i.e., J > I. 34 4.3. Varying offset error Remark: If n = n0 is fixed: z − û0 + δmax n0 < z + 1− û0 − δmax n0 ⇔ δmax < 1/2 that is, there is no intersection of threshold regions on the level n0, i.e., Iû0(n0, z) < Iû0(n0, z + 1) for all z ∈ [n0 − 1] and δmax < 1/4. Even though we assume that exact locations of threshold points are independent from each other, actually for a fixed n = n0, threshold points tû0(z, n0, δ) all depend on the same δn0 value, see (4.10). Since we just showed that threshold regions on the same level n0 do not intersect, for the purposes of counting all possible intersections of threshold regions, we can assume that they are independent. Lemma 4.3.12. Consider the N -bit nonideal Σ∆ scheme with û0 ∈ [0, 1) and δmax < 1/4. Let m,n be given such that 1 ≤ m < n ≤ N . Then: ∀z ∈[n] : Iû0(z, n) ∈ RN (û0) ⇒ Iû0(z, n) < Iû0(z, n−m) Similarly: ∀z ∈[n−m] : Iû0(z +m,n) ∈ RN (û0) ⇒ Iû0(z, n−m) < Iû0(z +m,n) Proof. For the first claim, assume that Iû0(z, n) ∈ RN (û0) for a given z ∈ [n]. This implies that the right end of the interval Iû0(z, n) should be greater than 2δmax, i.e., z − û0 + δmax n > 2δmax ⇔ z > (2n− 1)δmax + û0 (4.12) 35 4.3. Varying offset error Simple algebra shows that (4.12) implies: z > (2n− 1)δmax + û0 ⇒ z > δmax ( 2n m − 1 ) + û0 ⇔ z − û0 − δmax n−m > z − û0 + δmax n (4.13) (4.13) means that the right end of Iû0(z, n) is smaller than the left end of Iû0(z, n−m), i.e., Iû0(z, n) < Iû0(z, n−m). Then first claim becomes true for all z ∈ [n]. Similarly for the second claim, assume that Iû0(z + m,n) ∈ RN (û0) for a given z ∈ [n−m]. Then the left end of the interval Iû0(z +m,n) should be smaller than 1− 2δmax, i.e., z +m− û0 − δmax n < 1− 2δmax ⇔ z < n+ û0 −m− (2n− 1)δmax (4.14) By simple algebra, (4.14) implies: z < n+ û0 −m− (2n− 1)δmax ⇒ z < n+ û0 −m− δmax ( 2n m − 1 ) ⇔ z − û0 + δmax n−m < z +m− û0 − δmax n (4.15) (4.15) means that the right end of Iû0(z, n−m) is smaller than the left end of Iû0(z + m,n), i.e., Iû0(z, n −m) < Iû0(z + m,n). Then second claim is also true for all z ∈ [n−m]. This completes the proof. In fact, this lemma says that, in order to have an (m-level) intersection in the admissable region, two threshold intervals have to have z values, say z0, z1, with property 1 ≤ |z0 − z1| ≤ m− 1. Corollary 4.3.13. Consider the N -bit nonideal Σ∆ scheme with û0 and δmax. Then there is no 1-level intersection in the admissable region. 36 4.3. Varying offset error Proof. If we choose m = 1 in the Lemma 4.3.12, then it is straightforward. In the following lemma, we will give a condition in order not to have any (m-level) intersection in the admissable region. Lemma 4.3.14. Consider the N -bit nonideal Σ∆ scheme with 0 ≤ û0 < 1 and δmax. Let 1 < m < N be given. If there is no integer value in the interval[ j m + û0 − δmax ( 2N m − 1 ) , j m + û0 + δmax ( 2N m − 1 )] (4.16) for all j ∈ N such that 0 ≤ j ≤ m, then there is no m-level intersection in the admissable region. Proof. Fix n > m. Then most generally consider two threshold intervals Iû0(z+j, n) and Iû0(z, n−m) that may possibly have an m-level intersection, where 1 ≤ j ≤ m − 1 and 1 ≤ z ≤ n − m. These bounds for j and z are implied by Lemma 4.3.12. The condition for these two intervals not to have an m-level intersection is either Iû0(z + j, n) < Iû0(z, n − m) or Iû0(z + j, n) > Iû0(z, n−m). If we write these conditions explicitly: z + j − û0 + δmax n < z − û0 − δmax n−m or z + j − û0 − δmax n > z − û0 + δmax n−m If we simplify these inequalities, we have the condition: z 6∈ [ jn m − j + û0 − δmax ( 2n m − 1 ) , jn m − j + û0 + δmax ( 2n m − 1 )] (4.17) Note that it is sufficient to have: z 6∈ [ jn m − j + û0 − δmax ( 2N m − 1 ) , jn m − j + û0 + δmax ( 2N m − 1 )] (4.18) 37 4.3. Varying offset error as these new sets include the sets given in (4.17) for every n and j. Recall that z is a positive integer. So, if there is no integer value in the interval in (4.18) for all m < n ≤ N and 1 ≤ j ≤ m − 1, then there is no m-level intersection for the whole set RN (û0). Since we can write the equivalent intervals in “mod 1”, it is equal to say that there is no integer value in the interval:[〈 jn m 〉 − j + û0 − δmax ( 2N m − 1 ) , 〈 jn m 〉 − j + û0 + δmax ( 2N m − 1 )] Since j is an integer, we can omit it. So we have the interval:[〈 jn m 〉 + û0 − δmax ( 2N m − 1 ) , 〈 jn m 〉 + û0 + δmax ( 2N m − 1 )] Lastly, we claim that for a fixed m,{〈 jn m 〉 : 1 ≤ j ≤ m− 1,m < n ≤ N } ⊆ { j m : 0 ≤ j ≤ m− 1 } Say jn = am+ b where b < m and a, b ∈ N. It follows that: jn m = a+ b m ⇒ 〈 jn m 〉 = b m So for every 1 ≤ j < m, there is 0 ≤ b < m that satisfies 〈 jn m 〉 = bm . Note that b = 0 is also possible for the remainder if n is a multiple of m. If we choose n = m + 1, then jnm = j m , which proves our claim. It is sufficient to consider: [ j m + û0 − δmax ( 2N m − 1 ) , j m + û0 + δmax ( 2N m − 1 )] where 0 ≤ j ≤ m− 1 and 1 < m < n ≤ N . We can include the case j = m since it is identical to the case j = 0 as long as we are interested in the integer values in the interval. This completes the proof. 38 4.4. Some conditions on initial value and δmax 4.4 Some conditions on initial value and δmax In order to do post-processing compression for a Σ∆ quantizer, number of possible codewords should be bounded reasonably. For instance having a bound with exponential order will not help much for our practical purposes in comparison to other quantization schemes. As we saw earlier, an k- degree intersection is enough to make number of codewords at least order of O(2k). Deriving conditions on δmax and û0 in order not to have any k-degree intersection does not seem easy. Instead, we will use the Lemma 4.3.14 to derive conditions for δmax in order not to have any m-level intersection for 1 < m < N . Theorem 4.4.1. Consider the N -bit nonideal Σ∆ quantizer scheme given in (4.6) with initial value û0 ∈ [0, 1). If δmax < 12N2−2 , then there exists some values for û0 that guarantee there is no m-level intersection for all m such that 1 < m < N , so Âδmaxû0 (N) = Â 0 û0 (N) and has cardinality order of O(N2) as the ideal case. Proof. We can generalize the result of Lemma 4.3.14 in order to have a sufficient condition for not having any m-level intersection for 1 < m < N . z 6∈ [ j m + û0 − δmax ( 2N m − 1 ) , j m + û0 + δmax ( 2N m − 1 )] (4.19) ∀z ∈ Z, 1 < m < N, 0 ≤ j ≤ m. So we again came across Farey series with this condition. We have some intervals around û0-shifted (N−1)-Farey points. We can write these shifted points as: FN−1(û0) := { j m + û0 : gcd(j,m) = 1, 1 < m < N, 0 ≤ j ≤ m} Now, it can be observed that only three natural numbers that can be con- tained by intervals around FN−1(û0), are 0, 1 and 2 for small δmax. Fur- thermore, if we choose δmax small enough so that the intervals around any two consecutive points in Fm(û0) do not intersect, then for some û0, (4.19) should be satisfied. Note that, if ca and d b are two consecutive (N −1)-Farey 39 4.4. Some conditions on initial value and δmax points, then their difference is 1ab . We can write the condition on δmax as: δmax ( 2N a − 1 ) + δmax ( 2N b − 1 ) < 1 ab ⇔ δmax[2N(a+ b)− 2ab] < 1 (4.20) for all a, b ≤ m < N and n ≤ N . It can be showed that max(2N(a+b)−2ab) is attained at a = b = N − 1. Then we have the following upper bound for δmax which guarantees no m-level intersection: δmax < 1 2N2 − 2 which is order of O(N−2) bound. We can find the appropriate û0 by the following formulas: û0 + c a + δmax ( 2N a − 1 ) < 1 û0 + d b − δmax ( 2N b − 1 ) > 1 ⇒ 1− d b + δmax ( 2N b − 1 ) < û0 < 1− c a − δmax ( 2N a − 1 ) (4.21) for any two consecutive (N − 1)-Farey points, ca and db . If we substitute δmax by the worst case bound of 12N2−2 in (4.21), we will have a nonempty interval to choose for û0. Lemma 4.4.1 says if δmax is small enough, for some discrete values of û0, possible codewords of a nonideal Σ∆ quantizer remain same as the ideal case. Yet, one may seek for a continuous relation between δmax and û0 in order to have a sufficient condition for keeping the same output codewords set, i.e., Âδmaxû0 (N) = Â 0 û0 (N). Let us assume that for a particular value of û0, 1 falls between two consecutive points of set FN−1(û0), say ca + û0 and d b + û0. Here 0 and 1 belong to (N − 1)-Farey points and it will be enough to consider only 1 as the possible natural number z that can be included by some interval. This is because Farey points and intervals around them are 40 4.4. Some conditions on initial value and δmax symmetrical with respect 0.5 and shifting by û0 is always to the right. So there is a circular relation when we consider the possible natural numbers 0,1 and 2 for z. Then, let us have the particular constraint: 1− d b ≤ û0 < 1− c a If û0 is under the above constraint, then in order not to have intersection of two intervals around the chosen points ca + û0 and d b + û0, we need following conditions: 1− û0 − c a > δmax ( 2N a − 1 ) ⇒ a(1− û0)− c 2N − a > δmax û0 + d b − 1 > δmax ( 2N b − 1 ) ⇒ b(û0 − 1) + d 2N − b > δmax (4.22) We also need to guarantee that any consecutive two interval will not intersect by setting δmax < 12N2−2 . Then we have the final relation: δmax < min { a(1− û0)− c 2N − a , b(û0 − 1) + d 2N − b , 1 2N2 − 2 } whenever 1 − db ≤ û0 < 1 − ca . Observe that the relation between û0 and δmax is linear between two consecutive (N − 1)-Farey points and δmax will have an optimum value in that region. As we saw earlier, we expect this optimum value to be order of O(N−2). (See Figure 4.2) Remark: In Figure 4.2-(a) we have triangles with bases located between two consecutive (N − 1)-Farey points. The linearity of the relation between û0 and corresponding δmax comes from the formulas given in (4.22). Peak points of the triangles are where these two formulas become equal. We can observe that δmax values that correspond to these peak points cannot be smaller than 1 2N2−2 since this value guarantees that there is no mutual intersection of all intervals given in (4.19), whereas the bounds for δmax in (4.22) guarantees only that there is no intersection of intervals that are around two consecutive û0-shifted-Farey points. This observation will be 41 4.4. Some conditions on initial value and δmax 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 N=7 û0 δ m a x 1/(2N 2 − 2) (a) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 100 200 300 400 500 600 700 800 900 1000 N=7 û0 1 / δ m a x (2N 2 − 2) (b) Figure 4.2: (a) Linear relation between initial value û0 and δmax and (b) order of δmax (1/δmax) with respect to û0. N is fixed to 7 for this example. Marked points on the x axis are 6-Farey points. important for a further discussion in Section 5.2. Finally, given N , let us write the function ∆N that gives the formula between û0 and δmax in order not to have any m-level intersections for m ≤ N : ∆N (û0) = { min { a(1− û0)− c 2N − a , b(û0 − 1) + d 2N − b , 1 2N2 − 2 } : c a , d b are two consecutive (N − 1)-Farey points and 1− d b ≤ û0 < 1− c a } Now for a given δmax value, define the set VN (δmax) := {û0 : ∆N (û0) < δmax}. It is important to observe that for all û0 ∈ VN (δmax), the non- ideal Σ∆ quantizer (4.1) gives the same codeword of length N as the ideal quantizer in (2.4) would give. We can formulate this as follows: Given δmax⋃ û0∈VN (δmax) Aδmaxû0 (N) ⊂ AN 42 4.4. Some conditions on initial value and δmax 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.002 0.004 0.006 0.008 0.01 0.012 ∆N ( û0) , N = 7 û0 δ m a x 1/(2N 2 − 2) Figure 4.3: Graph of function ∆N (û0) for N = 7. Dashed line shows the level of 1 2N2−2 . Marked points on the x axis are 6-Farey points. and AN has the cardinality of order O(N3). In Figure 4.3, it can be seen that ∆N (û0) consists of truncated triangles at level 12N2−2 . 43 Chapter 5 Implications for Bandlimited Functions In Chapter 1, we mentioned about two basic steps of A/D conversion pro- cess, one of which was sampling of functions. Sampling is the reduction of a continuous function to a discrete set of values. The question of how to sample a function in order to make it possible to reconstruct the original function completely was answered for bandlimited functions by Classical (Nyquist- Shannon) Sampling Theorem. This theorem states that an Ω-bandlimited function f , i.e., suppf̂ ⊆ [−Ω,Ω], where f̂ is the Fourier transform of f , is completely characterized by sampling it at the Nyquist frequency Ωpi , [3]. f(t) = ∑ n∈Z f (npi Ω ) sinc ( t− npi Ω ) (5.1) where sinc(x) = x−1 sinx. In particular, at any fixed t0, f(t) is an infinite weighted average of the sample values f ( npi Ω ) . For computational purposes, we would want that only a few of these “weights”, i.e., sinc ( t− npiΩ ) , to be “large”. However except at integer cases (i.e., when npiΩ − t0 is integer for all n), these weights decay only like 1n . In addition, if the samples are not know exactly and we have f ( npi Ω ) + εn with all |εn| < ε, then the corresponding approximation f̃n may differ appreciably from f(t). Thus the reconstruction is not local. For a more detailed argument of this we refer to [3], [6] and [4]. However, we can solve this problem by oversampling the function at rate higher than Nyquist, say at rate λΩpi , λ > 1. Our more closely spaced samples are {f (nλ)}n∈Z. Then sinc kernel in (5.1) can be replaced by another kernel ϕ where ϕ̂(ξ) = 1 for |ξ| ≤ Ω and ϕ̂(ξ) = 0 for |ξ| ≥ λΩ. If we choose ϕ 44 5.1. Basic error estimates for PCM and Σ∆ schemes such that ϕ̂ is smooth, we will have the desired fast decay properties. Then we have the formula: f(t) = ∑ n∈Z 1 λ f (npi λΩ ) ϕ ( t− npi λΩ ) (5.2) For simplicity we can choose Ω = pi in the following arguments which makes sampling rate equal to λ. 5.1 Basic error estimates for PCM and Σ∆ schemes By oversampling, we bought the freedom of choosing our reconstruction kernel and having a little number of “significantly contributing” samples. While this process turns a continuous time signal to a discrete time signal, samples are still real numbers. We need to quantize this numbers with a given bit budget. In general, if we replace f(nλ ) by f̃( n λ ) + εn in (5.2) with |εn| < ε, then [3] gives the approximation error as: |f(t)− f̃(t)| ≤ ε 1 λ ∑ n∈Z ∣∣∣ϕ(t− n λ )∣∣∣ ≤ εCϕ (5.3) where Cϕ := λ−1‖ϕ′‖L1 + ‖ϕ‖L1 . PCM schemes: If we have a bit budget of N for each sample, the simplest way to do this is finding the truncated binary expansion of the sample. We can assume that |f(t)| ≤ 1 for all t. Then each sample f(t) is reconstructed with error 2−N , i.e., ε . 2−N . This leads to |f(t)− f̃(t)| ≤ C2−N where C is independent of N and f . This type of quantization is used in representing audio signals, but they have implementation drawbacks which we discussed in Chapter 2 in details. Mainly, designing a circuit which implements bi- nary expansion of a real valued sample is not very robust with respect to imperfections. In practice, Σ∆ schemes has been preferred widely with their robustness properties compared to PCM schemes. 45 5.1. Basic error estimates for PCM and Σ∆ schemes Σ∆ schemes: The oversampling ratio λ indicates the number of samples we have in a Nyquist interval. In Σ∆ schemes, instead of using N -bit per sample, we use them to quantize all λ samples in a Nyquist interval. Here we actually set N = λ and choose λ 1. Then we have the corresponding formula for Σ∆ scheme as: un = un−1 + f (n λ ) − qλn qλn = Q ( un−1 + f (n λ )) (5.4) with an initial condition u0 ∈ [0, 1) and Q as defined in (2.5). In circuit implementation, the range of n in (5.4) is n ≥ 1. [3] shows that un and qλn can be written directly in terms of un+1 and fn+1 when n < 0. But in the rest of the discussion about Σ∆ schemes, we will assume that n ≥ 1. Next, if we use the following reconstruction formula: f̃(t) = 1 λ ∑ n qλnϕ ( t− n λ ) then [3] derives the following approximation error estimate: |f(t)− f̃(t)| ≤ 1 λ ‖ϕ′‖L1 (5.5) We discussed before that this polynomial decay 1λ is rather poor with respect to PCM schemes but main advantage of Σ∆ schemes was their robustness, i.e., keeping this approximation rate same even when implemented with imprecise (nonideal) quantizers. If we replace the quantization formula in (5.4) with imprecise version: qλn = Q ( un−1 + f (n λ ) + δn ) where |δn| < δ, then [4] derives an error estimate for imprecise Σ∆ scheme as follows: |f(t)− f̃(t)| ≤ Cδ,ϕ(1 + δ) λ 46 5.2. A new Σ∆ quantization setup for bandlimited functions This shows that Σ∆ scheme is robust since it keeps the same approximation rate, 1λ in the imperfect case. If the first-order Σ∆ scheme is generalized to higher-order schemes, one can get better bounds for approximation error. [3] derives the approximation rate to be order of 1 λk for a general kth order Σ∆ scheme. But this is still poor in comparison to PCM scheme. 5.2 A new Σ∆ quantization setup for bandlimited functions We saw that the approximation rate of a Σ∆ quantizer is not affected by possible imperfections. While we have this robustness, we want to be able to do post-processing compression owing to the fact that number of distinct codewords of length N produced by a first-order Σ∆ quantizer is much lesser than 2N . In Chapter 3, we showed that number of distinct codewords for an ideal quantizer is order of O(N3) which leads to an approximation rate order of O(2− N 3 ) (see Section 3.3). This result is valid for a constant input quantizer and this fact gives a motivation to us to come up with following simple but somewhat interesting sampling technique for a first-order Σ∆ quantizer. A new setup: Assume that we oversample our continuous function f with an oversampling rate λ. But instead of feeding our Σ∆ quantizer with values f(nλ ), we repeat each value N times before skipping to the next one. So the input sequence becomes: {. . . , f (n λ ) , . . . , f (n λ ) ︸ ︷︷ ︸ N−times , f ( n+ 1 λ ) , . . . , f ( n+ 1 λ ) ︸ ︷︷ ︸ N−times , . . .} 47 5.2. A new Σ∆ quantization setup for bandlimited functions Then we can write the following recovering formula: f(t) = 1 λ ∑ n f (n λ ) ϕλ ( t− n λ ) = 1 λ 1 N N∑ j=1 ∑ n f (n λ ) ϕλ ( t− n λ ) for λ > 1. If we define gn := f ( dn/Ne λ ) and φλ ( t− nλ ) := ϕλ ( t− dn/Neλ ) , we have the following formula: f(t) = 1 Nλ ∑ n gnφλ ( t− n λ ) Observe that φ has desired smoothness properties as ϕ. So in our new setup, we can assume that we use the input sequence {gn}n≥1 for the ideal quantizer in (5.4) with an initial condition u0 ∈ [0, 1). Then we can bound the approximation error with 1Nλ by using a similar argument as in [3]. If the produced bit sequence is {qλn}n≥1, set f̃(t) = 1Nλ ∑ n q λ nφλ ( t− nλ ) and observe that gn − qλn = un − un−1. Then it follows as: |f(t)− f̃(t)| = 1 Nλ ∣∣∣∣∣∑ n (un − un−1)φλ ( t− n λ )∣∣∣∣∣ = 1 Nλ ∣∣∣∣∣∑ n un ( φλ ( t− n λ ) − φλ ( t− n+ 1 λ ))∣∣∣∣∣ ≤ 1 Nλ ∑ n ∣∣∣∣φλ (t− nλ)− φλ ( t− n+ 1 λ )∣∣∣∣ ≤ 1 Nλ ∑ n ∫ t−n λ t−n+1 λ |φ′(y)|dy = 1 Nλ ‖φ′‖L1 A similar result can be derived for the nonideal case in order to show ro- bustness. Remark: One interesting result of this setup is, by only repeating sample values N times, we have a better approximation rate of 1Nλ . The sampling 48 5.2. A new Σ∆ quantization setup for bandlimited functions rate is kept same. Another result is: This setup allows us to further compress the bit stream qλn. Assuming that n ≥ 1, N -bit sequence {qλ1 , qλ2 , . . . , qλn} can be seen as the output of the Σ∆ scheme given in (2.4) with constant input g1 and initial value u0, then the N -bit sequence {qλN+1, qλN+2, . . . , qλ2N} can be seen as the output of (2.4) with constant input g2 and initial value uN , and so on. We know that for an ideal quantizer all these N -bit codewords belong to the set of AN with cardinality of order O(N3) regardless of the initial value, so we can follow the argument of further compression made in Section 3.3. Nonideal quantizer in the new setup: In the case of a nonideal quan- tizer with a varying offset error |δn| < δmax, the eligible initial values depend on the δmax value with function ∆N (û0) introduced in Section 4.4. More specifically assume that δmax is fixed; if the initial value of the nonideal quantizer is in the set VN (δmax) then the N -bit codeword will be in the set of original codewords generated by the ideal quantizer with cardinality of order O(N3). In our setup, the input sequence {gn}n≥1 changes value at n = kN + 1, k ∈ N. So we can think as we have a constant input quan- tizer that generates codewords length-N with the initial value sequence of {ukN}k∈N. We know from [8, Section 3.1] that ukN has uniform distribu- tion in [0, 1) for all k independently from each other. Since the initial value ukN determines whether N -bit codeword generated with input g(kN+1) is in the set of order O(N3), it is possible to calculate the probability for having reasonably bounded number of codewords after quantization. Lemma 5.2.1. Let δmax be given. For a random u0 ∈ [0, 1), P(u0 ∈ VN (δmax)) > τ − δmax τ where τ = 1 2N2−2 . Proof. Let µ be the Lebesgue measure. It is easy to see that P(u0 ∈ VN (δmax)) = µ({u0 : ∆N (u0) < δmax}). At the end of the Section 4.4, we remarked that the peak points of the triangles formed by function ∆N (u0) 49 5.2. A new Σ∆ quantization setup for bandlimited functions are not smaller than τ . If we assume that we have such triangles with their peaks exactly at the level τ , and if the corresponding function was ∆̃N (u0), then from triangle similarity, we would have µ({u0 : ∆̃N (u0) < δmax}) = τ−δmax τ . Since our original triangles are taller than these ones, we have µ({u0 : ∆N (u0) < δmax}) > µ({u0 : ∆̃N (u0) < δmax}). This proves the lemma. Theorem 5.2.2. Let δmax and an arbitrary bandlimited function f with Nyquist rate 1 be given. Assume that we will oversample function f at rate λ 1 with the Σ∆ quantizer explained above (it produces N -bit codewords per sample). If an L-unit portion of the function is processed via quantizer with L 1, then the probability of having at least k codewords in the set AN is: ≥ ( Lλ k ) pk(1− p)Lλ−k where p = τ−δmaxτ and τ = 1 2N2−2 . Proof. In the L-unit interval of f , there are Lλ samples. Each sample is fed into quantizer as a constant input and generates a length-N codeword. Lemma 5.2.1 says that probability of each of these codewords to be in the set AN is at least τ−δmaxτ and we know that these probabilities are independent. By a simple combinatorics argument we can get the desired result. Remark: Theorem 5.2.2 gives us freedom of choosing k such that we can bound the total number of distinct codewords with any order. For instance, if we choose k = Lλ−N3, then it is certain that k many codewords will be in the set AN which is of order O(N3). On the other hand, if we assume that all other Lλ− k = N3 codewords are out of this set, which is the worst case, we will have total number of O(N3) +N3 distinct codewords. This is still order of O(N3). Lastly we can talk about the post-processing compression in this setup. For a bandlimited function, number of bits used to represent all samples in a Nyquist interval is important. If we oversample with rate λ and use N bits per sample, so it makes λN bits per Nyquist interval. Approximation rate 50 5.2. A new Σ∆ quantization setup for bandlimited functions was 1λN for this Σ∆ quantizer. As a further argument, if we know that there are only order of O(N3) distinct codewords that may be generated, then we can spend only R = 3 log2N bits to represents all codewords, and this leads to an approximation rate of 1λN = 1 λ2 R 3 = 2 −R3 λ . This new setup for Σ∆ quantizers allows us to repeat the argument given in Section 3.3 for bandlimited functions and make a much better comparison between PCM and Σ∆ schemes in terms of approximation rates. 51 Bibliography [1] Jean Berstel. Recent results on sturmian words. In Developments in Language Theory, pages 13–24, 1995. [2] J.C. Candy. A use of double integration in sigma delta modulation. IEEE Trans. Commun., COM-33:249–258, Mar. 1985. [3] Ingrid Daubechies and Ronald A. DeVore. Reconstructing a bandlim- ited function from very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order. Annals of Mathematics, 158(2):679–710, 2003. [4] Ingrid Daubechies, Ronald A. DeVore, C. Sinan Güntürk, and Vinay A. Vaishampayan. A/d conversion with imperfect quantizers. IEEE Trans- actions on Information Theory, 52(3):874–885, 2006. [5] Ingrid Daubechies, C. Sinan Güntürk, Y. Wang, and Özgür Yılmaz. The golden ratio encoder. CoRR, abs/0809.1257, 2008. [6] Ingrid Daubechies and Özgür Yılmaz. Robust and practical analog-to- digital conversion with exponential precision. IEEE Transactions on Information Theory, 52(8):3533–3545, 2006. [7] R.M. Gray. Oversampled sigma-delta modulation. IEEE Trans. Com- mun., COM-35:481–489, May 1987. [8] C. Sinan Güntürk. Harmonic analysis of two problems in signal quan- tization and compression. PhD thesis, Princeton Univ., Princeton, NJ, 2000. 52 Bibliography [9] C. Sinan Güntürk. One-bit sigma-delta quantization with exponential accuracy. Comm. Pure. Appl. Math., 56(511):1608–1630, 2003. [10] C. Sinan Güntürk, J. C. Lagarias, and Vinay A. Vaishampayan. On the robustness of single-loop sigma-delta modulation. IEEE Transactions on Information Theory, 47(5):1735–1744, 2001. [11] G.H. Hardy and E.M. Wright. An Introduction to the Theory of Num- bers. Oxford University Press, 5th edition, 1983. [12] S. Hein, K. Ibraham, and A. Zakhor. New properties of sigma-delta modulators with dc inputs. Communications, IEEE Transactions on, 40(8):1375–1387, Aug 1992. [13] S. Hein, K. Ibraham, and A. Zakhor. Sigma Delta modulators: nonlin- ear decoding algorithms and stability analysis. Dordrecht, The Nether- lands:Kluwer, 1993. [14] H. Inose and Y. Yasuda. A unity bit coding method by negative feed- back. Proc. IEEE, 51:1524–1535, Nov. 1963. [15] D.F. Hoschele Jr. Analog-to-Digital and Digital-to-Analog Conversion Techniques. New York:Wiley, 1994. [16] Filippo Mignosi. On the number of factors of sturmian words. Theor. Comput. Sci., 82(1):71–84, 1991. [17] R. Schrier S.R. Norsworthy and Eds G.C. Temes. Delta-Sigma data con- verters: theory, design, and simulation. Piscataway, NJ: IEEE Press, 1996. [18] V.M. Tikhomirov and A.N. Kolmogorov. ε-entropy and ε-capacity of sets in function spaces. Amer. Math. Soc. Transl., 17(2):277–364, 1961. [19] Özgür Yılmaz. Stability analysis for several sigma-delta methods of coarse quantization of bandlimited functions. Constructive Approxima- tion, 18(4):599–623, 2002. 53
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Sigma-delta quantization and Sturmian words
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Sigma-delta quantization and Sturmian words Ayaz, Ulaş 2009
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Sigma-delta quantization and Sturmian words |
Creator |
Ayaz, Ulaş |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | In this thesis, our main focus is Sigma-Delta quantization schemes. These are commonly used in state-of-art Analog-to-digital conversion technology. Their main advantage is the ease of implementation and more importantly their insensitivity to certain circuit imperfections. When we compare sigma-delta scheme with pulse-code modulation (PCM), sigma-delta is inferior in terms of rate distortion because an N-bit kth order sigma-delta quantizer produces an approximation with the error of order O(N-k) whereas the corresponding N-bit PCM scheme has accuracy of O(2−N)). However, this is a raw estimate of the actual rate-distortion characteristic of sigma-delta as one can further compress the bitstreams obtained via sigma-delta quantization. Even though this observation was made earlier in [10] under certain assumptions, to our knowledge, it was not investigated fully. In this thesis, such an investigation is made for first-order sigma-delta quantizers by using some results from symbolic dynamics literature on “Sturmian words”. Surprisingly, it turns out that the approximation error is a function of the “actual bit-rate”, i.e., the bit-rate after compressing an N-bit first-order sigma-delta encoding. In addition, in this thesis, we will introduce a new setup for sampling a bandlimited function and then quantizing these samples via first-order sigma-delta scheme. This simple but surprisingly efficient technique will allow us to get a better bound for the approximation rate of sigma-delta schemes and it will allow us to apply the derived results for compression of the bitstreams. |
Extent | 552245 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-10-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0067841 |
URI | http://hdl.handle.net/2429/14203 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_fall_ayaz_ulas.pdf [ 539.3kB ]
- Metadata
- JSON: 24-1.0067841.json
- JSON-LD: 24-1.0067841-ld.json
- RDF/XML (Pretty): 24-1.0067841-rdf.xml
- RDF/JSON: 24-1.0067841-rdf.json
- Turtle: 24-1.0067841-turtle.txt
- N-Triples: 24-1.0067841-rdf-ntriples.txt
- Original Record: 24-1.0067841-source.json
- Full Text
- 24-1.0067841-fulltext.txt
- Citation
- 24-1.0067841.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0067841/manifest