# Patent

## Title
Nonlinearity robust successive requantizer

## Abstract

A successive requantizer, which serves as a replacement for a ΔΣ modulator in a fractional-N PLL or a DAC, and avoids spurious tone problems, thereby circumventing the tradeoffs that result from reliance on the common approach of making highly linear analog circuitry to avoid spurious tones. A successive requantizer fractional-N PLL of the invention has the potential to reduce power consumption and the cost of commercial communication devices. The successive requantizer performs digital quantization one bit at a time in such a way that the quantization noise can he engineered to have desirable properties such as non-linearity robustness. The successive requantizer is applicable to most high-performance digital communication systems, such as cellular telephone handsets and wireless local and metropolitan area network transceivers.

## Background
PRIORITY CLAIM AND REFERENCE TO RELATED APPLICATION
The application claims priority under 35 U.S.C. §119 from prior provisional application Ser. No. 61/105,635, which was filed on Oct. 15, 2008.


STATEMENT OF GOVERNMENT INTEREST
This invention was made with government support under Contract No. CCF0515286 awarded by National Science Foundation. The government has certain rights in the invention.


FIELD
A field of the invention is wireless communications. Another field of the invention is digital to analog converters. Example applications of the invention include high-performance digital communication systems such as cellular telephone handsets and wireless local and metropolitan area network transceivers.
BACKGROUND
Virtually all wireless communication systems require local oscillators for up-conversion and down-conversion of their transmitted and received signals. Most commonly, the local oscillators are implemented as fractional-N PLLs (phase locked loops). Fractional-N PLLs can generate a high quality, high frequency signal from a digital input stream and a lower frequency reference waveform.
The spectral purity of the local oscillator in a transceiver is a critical factor in overall transceiver performance. Communication standards therefore explicitly or implicitly stipulate stringent phase noise requirements on the local oscillators. Most standards dictate the maximum acceptable phase noise power in various frequency bands. Additionally, most standards require that spurious tones in the local oscillator's phase noise be highly attenuated, particularly in critical frequency bands. DACs also have stringent spurious tone requirements in wireless applications, digital audio applications and instrumentation applications. Digital audio and instrumentation spurious tone requirements are particularly critical in many consumer products.
Modern digital-to-analog converters (DACs) and fractional-N phase-locked loops (PLLs) rely upon a digital delta-sigma modulator (ΔΣ modulator) to coarsely quantize a constant or slowly varying digital sequence. The quantized sequence can be viewed as the sum of the original sequence plus spectrally shaped quantization noise that has most of its power outside of a given low-frequency signal band. Ultimately, the quantized sequence is converted to an analog signal and further processed by analog circuitry including a low-pass filter to suppress quantization noise outside of the signal band.
FIG. 1 is a block diagram of a conventional ΔΣ fractional-N PLL. The purpose of the system is to generate an output signal of frequency (N+α)fref where N is a positive integer, a is a constant fractional value between 0 and 1, and fref is the frequency of a reference oscillator. The system consists of a phase-frequency detector (PFD) and a charge pump 100, a loop filter 102, a voltage controlled oscillator (VCO) 104, a multi-modulus divider 106, and a digital ΔΣ modulator 108. The divider output, vdlv(t), is a two-level signal in which the nth and (n+1)th rising edges are separated by N+y[n] periods of the VCO output, for n=1, 2, 3, . . . , where y[n] is a sequence of integers generated by the ΔΣ modulator 108. As indicated in FIG. 1B for the case where the PLL is locked, if the nth rising edge of the reference signal, vref(t), occurs before that of vdlv(t), the charge pump 100 generates a positive current pulse of magnitude lCP with a duration equal to the time difference between the two edges. This increases the VCO control voltage; vctrl(t), thereby increasing the VCO output frequency. Alternatively, if the nth rising edge of vref(t), occurs after that of vdlv,(t), the situation is similar except the polarity of the current pulse is negative, which decreases the VCO frequency. This causes the output frequency to settle to fref times the sum of N and the average of y[n].
If y[n] could be set directly to the desired fractional value, a, directly then the output frequency of the PLL would settle to (N+α)fref, thereby achieving the goal of the fractional-N PLL. Unfortunately, y[n] is restricted to integer values because the divider 106 is only able to count integer VCO cycles whereas a is a fractional value. To circumvent this problem y[n] is designed to be a sequence of integers that average to α. The input to the ΔΣ modulator 108 is α plus pseudo-random least significant bit (LSB) dither, so its output has the form y[n]=α+s[n], where s[n] is a zero-mean sequence consisting of spectrally shaped ΔΣ quantization noise and LSB dither. The dither prevents s[n] from containing spurious tones that would otherwise show up as spurious tones in the PLL's output. Hence, the output frequency settles to an average (N+α)fref, as desired, although s[n] introduces phase noise.
For most wireless applications spurious tones can be sufficiently suppressed only with design tradeoffs that significantly degrade other aspects of performance. This is particularly problematic in fractional-N PLLs wherein the input to the modulator usually is a constant and the output sequence from the modulator is converted to analog form and subjected to various nonlinear operations because of nonideal circuit behavior. The common approach to address spurious tones is to make the analog circuitry very linear so that the spurious tones have sufficiently low power for the given application. This limits design options and results in higher analog circuit power consumption than would be required if fewer linear analog circuits could be tolerated.
The tradeoffs tend to increase power consumption and circuit area, limit the choice of reference frequencies, and dictate low PLL bandwidths which preclude on-chip loop filters. They also become less effective in system-on-chip designs as CMOS circuit technology is scaled into the sub-100 nanometer regime. Therefore, the spurious tone problem negatively affects power consumption, cost, and manufacturability of wireless transceivers, and the problem gets worse as CMOS circuit technology scales with Moore's Law.
To address the quantization noise, researchers have described methods of implementing noise-shaped quantizers. See, e.g., A. J. Magrath and M. B. Sandler, “Efficient Dithering of Sigma-delta Modulators with Adaptive bit Flipping,” Electron. Lett, vol. 31, no. 11, pp. 846-847, May 1995; S. H. Yu, “Noise-Shaping Coding through Bounding the Frequency Weighted Reconstruction Error,” IEEE Trans. Circuits Syst. II: Expr. Briefs, vol. 53, no. 1, pp. 67-71, January 2006; D. E. Quevedo and G. C. Goodwin, “Multistep Optimal Analog-to-Digital Conversion,” IEEE Trans. Circuits and Systems I: Regular Papers, vol. 52,no. 3, pp. 503-515, March 2005; I. Daubechies and R. DeVore, “Approximating a Bandlimited Function Using Very Coarsely Quantized Data: A Family of Stable Sigma Delta Modulators of Arbitrary Order,” Ann. Math., vol. 158, no. 2, pp. 679-710, 2003.
Generally, known phase noise cancelling fractional-N PLLs are effective to cancel phase noises that result from mismatches between positive and negative current sources in the charge pump. However, these methods specifically focus on stabilizing noise-shaped coders and do not address the effect of nonlinearities on the quantization error.
SUMMARY OF THE INVENTION
An embodiment of the invention is a successive requantizer, which serves as a replacement for a ΔΣ modulator in a fractional-N PLL or DAC, and avoids the above-mentioned spurious tone problem, thereby circumventing the tradeoffs that result from reliance on common approach of making highly linear analog circuitry to avoid spurious tones. A successive requantizer fractional-N PLL of the invention has the potential to reduce power consumption and the cost of commercial communication devices. A successive requantizer of the invention performs digital quantization one bit at a time in such a way that the quantization noise can be engineered to have desirable properties such as non-linearity robustness. The invention is applicable to most high-performance digital communication systems, such as cellular telephone handsets and wireless local and metropolitan area network transceivers.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1A (prior art) is a block diagram of a fractional-N PLL; FIG. 1B illustrates waveforms in the PLL of FIG. 1A;
FIG. 2A is a block diagram of a preferred embodiment successive requantizer for a fractional-N PLL or DAC;
FIG. 2B illustrates the general form of a preferred embodiment quantization block in the successive requantizer of FIG. 2A in which all variables are integer-valued two's complement numbers;
FIGS. 2C-2E illustrates detail on the sequence generation of the successive requantizer of FIGS. 2A-2B;
FIG. 3A is a block diagram that shows the register transfer level details of the dth quantization block of FIG. 2A, and FIG. 3B illustrates the combinatorial logic truth table of an example implementation of sequence generation logic; and
FIG. 4 is a block diagram of a preferred embodiment prototype fractional-N PLL or DAC.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
It is critical spurious tones in the noise introduced by DACs and fractional-N PLLs have very low power. Unfortunately, spurious tones are inevitable in the phase noise of fractional-N PLLs. In principle, dither applied to a modulator can prevent the quantization noise from containing any spurious tones whatsoever. In practice, digital delta sigma modulators are major sources of spurious tones in oversampling DACs and fractional-N PLLs and are believed by the present inventors to give rise to spurious tones whenever their quantization noise is subjected to nonlinear distortion.
The present invention identifies and addresses a surprising fundamental source of spurious tones in fractional-N PLLs, namely, the digital ΔΣ modulator. The fractional-N PLL is identified as the fundamental source of spurious tones in the PLL's phase noise. This is true even when dither is used to prevent spurious tones in the ΔΣ modulator's quantization noise. Regardless of how dither is applied, spurious tones are induced when the ΔΣ modulator's quantization noise is subjected to non-linear distortion. In a typical ΔΣ modulator used in a fractional-N PLL, the interaction of the constant input and the modulator's first accumulator gives rise to hidden periodicities. Dither provides sufficient randomness to avoid spurious tones in y[n], but not to avoid spurious tones when s[n] is subjected to nonlinear distortion.
This is particularly problematic in fractional-N PLLs wherein the output sequence from the ΔΣ modulator is converted to analog form and subjected to various non-linear operations because of non-ideal circuit behavior. In embodiments of the invention, a successive requantizer replaces the ΔΣ modulator and avoids the spurious tone problems. The successive requantizer can also serve as a replacement for a ΔΣ modulator in digital analog converter, and example embodiment DACs take the same form as a fractional-N PLL.
An embodiment of the invention is a successive requantizer, which serves as a replacement for a ΔΣ modulator in a fractional-N PLL, and avoids the above-mentioned spurious tone problem, thereby circumventing the tradeoffs that result from reliance on common approach of making highly linear analog circuitry to avoid spurious tones. A successive requantizer fractional-N PLL or DAC of the invention has the potential to reduce power consumption and the cost of commercial communication devices. A successive requantizer of the invention to performs digital quantization one bit at a time in such a way that the quantization noise can be engineered to have desirable properties such as non-linearity robustness. The invention is applicable to most high-performance digital communication systems, such as cellular telephone handsets and wireless local and metropolitan area network transceivers.
Preferred embodiments of the invention will now be discussed with respect to the drawings. The drawings may include schematic representations, which will be understood by artisans in view of the general knowledge in the art and the description that follows. Features may be exaggerated in the drawings for emphasis, and features may not be to scale.
Fractional-N PLLs used in communications applications and DACs using ΔΣ modulators ultimately generate analog waveforms. Each such waveform contains components corresponding to digitally generated quantization noise, s[n], and, in the case of fractional-N PLLs, its running sum,




  
    
      
        
          t
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            ∑
            
              k
              =
              0
            
            n
          
          ⁢
          
            
              s
              ⁡
              
                [
                k
                ]
              
            
            .
          
        
      
    
    
      
        (
        1
        )
      
    
  




Inevitable non-ideal analog circuit behavior causes non-linear distortion. The distortion can be any non-linear function, but for almost all practical applications can be represented by a memory-less, truncated power series. This gives rise to components in the output waveform corresponding to sp[n] for p=1, 2, 3, . . . , hs, and tp[n] for p=1, 2, 3, . . . , ht, where hs, and ht are the highest significant orders of distortion for the given application applied on s[n] and t[n] respectively.
Most communication system standards specify required performance in terms of quantities that can be measured using spectrum analyzers, so the properties of the waveforms typically are quantified in the laboratory using spectrum analyzers. Although the waveforms themselves are considered to be random processes in most cases, spectrum analyzers can only average over time, not over ensemble. Therefore, in such applications the properties of the periodograms of sp[n] and tp[n] given by




  
    
      
        
          
            
              I
              
                
                  s
                  p
                
                ,
                L
              
            
            ⁡
            
              (
              ω
              )
            
          
          =
          
            
              1
              L
            
            ⁢
            
              
                
                
                  
                    ∑
                    
                      n
                      =
                      0
                    
                    
                      L
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      
                        s
                        p
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    ⁢
                    
                      e
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        ω
                        ⁢
                        
                          
                        
                        ⁢
                        n
                      
                    
                  
                
                
              
              2
            
          
        
        ⁢
        
          

        
        ⁢
        and
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          
            I
            
              
                t
                p
              
              ,
              L
            
          
          ⁡
          
            (
            ω
            )
          
        
        =
        
          
            1
            L
          
          ⁢
          
            
              
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    L
                    -
                    1
                  
                
                ⁢
                
                  
                    
                      t
                      p
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ⁢
                  
                    e
                    
                      
                        -
                        j
                      
                      ⁢
                      
                        
                      
                      ⁢
                      ω
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                  
                
              
              
            
            2
          
        
      
    
    
      
        (
        3
        )
      
    
  




are of particular interest, rather than traditional power spectral density (PSD) functions. It is well known that in certain cases the expected values of the periodograms converge to the true PSD functions in the limit as L→∞, but in the applications mentioned above this is not a requirement, or even relevant to the measured performance. The successive requantization of the invention can be understood with respect to the properties of the periodograms given by (2) and (3).
Preferred Embodiment Successive Requantizer and PLL
FIG. 2A illustrates a preferred embodiment successive requantizer that can replace a ΔΣ modulator, such as the ΔΣ modulator 108 in the FIG. 1A fractional-N PLL. The fractional-N PLL of FIG. 1A as modified by the successive requantizer of FIG. 2A is a type of DAC, as it converts a digital sequence to an analog output. The successive requantizer of FIG. 2A readily serves as the replacement for any converter that uses a delta sigma modulator. The bit sequences illustrated are examples only, and the number of quantization blocks 2021-202d will depend upon the number of bits in the input bit sequences and the desired number of bits in the output sequence. The successive requantizer 200 illustrated in FIG. 2A quantizes a 19-bit input sequence received at its input 204 by 16 bits (using 16 quantization blocks 202) to generate a 3-bit output sequence at its output 206.
The input 204 and output 206 of the successive requantizer 200 are integer-valued. For the fractional-N PLL application, the goal is to quantize α, which is a fractional value between 0 and 1, and in this design a is taken to be a constant multiple of 2−16. Therefore, a is scaled by 216 prior to the successive requantizer to convert it into an integer. As explained below, the 3-bit integer-valued output of the successive requantizer is y[n]=α+s[n], where s[n] is quantization noise. While the example assumes that each quantization block quantizes its input sequence by one bit, the quantization blocks can quantize their inputs by more than one bit, as will be appreciated by artisans.
As shown in FIG. 2B each quantization stage/block 202d simultaneously halves its input and quantizes the result by one bit every sample period. The output of the dth quantization block 202d is xd+1[n]=(xd[n]+sd[n])/2, where sd[n] a sequence generated within the quantization block. At each time n, sd[n] is chosen such that xd[n]+sd[n] does not exceed the range of a (20−d)-bit (calculated by 4+N−d, where N is the number of quantization blocks) two's complement integer, and the parity of sd[n] is the same as that of xd[n]. The range can be generally stated as (K−d)-bit two's complement integer, where the parity of sd[n] is the same as that of xd[n], where K is determined by the number of quantization stages, the number of bits quantized per stage, and the logic which generates sd[n].
The parity restriction ensures that xd[n]+sd[n] is an even number so its LSB is zero. Discarding the LSB simultaneously halves the quantization block's input value and quantizes the result by one bit. The resulting quantization noise is sd[n]/2, so the successive requantizer's overall quantization noise is




  
    
      
        
          
            s
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                d
                =
                1
              
              16
            
            ⁢
            
              
                2
                
                  d
                  -
                  17
                
              
              ⁢
              
                
                  s
                  d
                
                ⁡
                
                  [
                  n
                  ]
                
              
            
          
        
        ,
      
    
    
      
        
          (
          4
          )
        
        ⁢
        
          (
          i
          )
        
      
    
  




which can be generalized to





  
    
      
        
          s
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            ∑
            
              d
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            
              2
              d
            
            ⁢
            
              
                
                  s
                  d
                
                ⁡
                
                  [
                  n
                  ]
                
              
              .
            
          
        
      
    
    
      
        
          (
          4
          )
        
        ⁢
        
          (
          ii
          )
        
      
    
  




Therefore, s[n] is a linear combination of the sd[n] sequences, so it inherits the properties of the sd[n] sequences.
The example presented in (4)(i) is for a specific number of input bits and quantization but can be generalized as in (4)(ii) for different numbers of input bits and different numbers of bit quantizations. Generalized for an input that is a sequence of B-bit numbers, x0[n], and an output that is a sequence of B-K-bit numbers, xK[n], where n=0, 1, 2, . . . , is the time index of the sequences. The generalization is shown in FIGS. 2C-2E. The successive requantizer then consists of K quantization blocks 202K, each of which quantizes its input by one bit, so the successive requantizer quantizes K bits overall. Each quantization block generates a quantization sequence, sd[n], with the property that xd[n]+sd[n] is an even number for each n, where xd[n] is the quantization block's input sequence. The quantization block adds sd[n] to xd[n] and discards the least significant bit (LSB) to implement the 1-bit quantization. Without loss of generality, numbers within the successive requantizer are taken to be integers with a two's-compliment binary number representation. Since xd[n]+sd[n] is an even number for each n, its LSB is zero, so discarding the LSB does not incur a truncation error. Hence, the quantization noise of the successive requantizer is a weighted sum of the sd[n] sequences.
The properties of the quantization noise s[n] can be engineered by appropriate design of the sd[n] sequences. So far, the only restriction on the sd[n] sequences is that xd[n]+sd[n] must be an even integer for each n and d. In the example successive requantizer 200 this restriction on the sd[n] sequences is that they must be chosen such that xd[n]+sd[n] is a (20−d)-bit two's complement even integer for each n and d. This leaves considerable flexibility in the design of the sd[n] sequences, which can be exploited to achieve the desired quantization noise properties.
The successive requantizer partially exploits this flexibility to ensure that the running sum of each sd[n] sequence, i.e.,




  
    
      
        
          
            
              t
              d
            
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                k
                =
                0
              
              n
            
            ⁢
            
              
                s
                d
              
              ⁡
              
                [
                k
                ]
              
            
          
        
        ,
      
    
    
      
        (
        5
        )
      
    
  




is bounded for all n, and each sd[n] has a smooth PSD (power spectral density) that increases monotonically with frequency. This implies that s[n] is highpass shaped quantization noise that is free of spurious tones and the PSD of s[n] is zero at ω=0.
This still leaves flexibility in the design of the sd[n] sequences which can exploited as described below to ensure that the sequences
(s[n])p for p=1, 2, 3, 4, 5, and (t[n])p for p=1, 2, 3,
are free of spurious tones, where t[n] is the running sum of s[n] given by:




  
    t
    ⁡
    
      [
      n
      ]
    
  
  =
  
    
      ∑
      
        k
        =
        0
      
      n
    
    ⁢
    
      s
      ⁡
      
        [
        k
        ]
      
    
  




The objective is to ensure that the successive requantizer's quantization noise does not introduce significant spurious tones when subjected to the degree of nonlinear distortion expected from the analog circuits within the PLL. Circuit simulations can be used during PLL design to verify that preventing spurious tones from occurring in the (s[n])p and (t[n])p sequences is sufficient to achieve this objective.
FIG. 3A is a block diagram that shows the register transfer level details of the dth quantization block, and FIG. 3B illustrates the combinatorial logic truth table. There are many choices of sequences which can yield non-linear robust properties. The truth table of FIG. 3B illustrates one particular example. Each value of sd[n] is calculated via the combinatorial logic 300 as a function the previous value of td[n] provided by D flip flop's 302, the parity of the current value of xd[n], and the current value of a 4 bit pseudo-random sequence (provided by pseudo random number generator 304), rd[n], where {rd[n], d=1, 2, . . . , 16, n=0, 1, 2, . . . } well-approximates independent identically distributed random variables. For this design the range of values taken on by sd[n] and td[n] are

sd[n]ε{−3, −2, −1, 0, 1, 2, 3}, and td[n]ε{−2, −1, 0, 1, 2},  (6)

It can be verified that td[n] is a discrete-valued Markov random sequence conditioned on the parity of xd[n]. Whenever xd[n] is odd the one-step state transition matrix for td[n] is given by

Ao=[P{td[n]=Tj|td[n−1]=Ti,od[n]=1}]5×5  (7)

and whenever xd[n] is even the one-step state transition matrix for td[n] is given by

Ae=[P{td[n]=Tj|[n−1]=Ti,od[n]=0}]5×5  (8)

where P{X|Y} denotes the conditional probability of event X given event Y, od[n] is the LSB of xd[n], and T1=−2, T2=−1, T3=0, T4=1, T5=2. The specific state transition matrices corresponding to the quantization block 202d




  
    
      
        
          
            A
            o
          
          =
          
            [
            
              
                
                  0
                
                
                  
                    3
                    /
                    4
                  
                
                
                  0
                
                
                  
                    1
                    /
                    4
                  
                
                
                  0
                
              
              
                
                  
                    3
                    /
                    16
                  
                
                
                  0
                
                
                  
                    3
                    /
                    4
                  
                
                
                  0
                
                
                  
                    1
                    /
                    16
                  
                
              
              
                
                  0
                
                
                  
                    1
                    /
                    2
                  
                
                
                  0
                
                
                  
                    1
                    /
                    2
                  
                
                
                  0
                
              
              
                
                  
                    1
                    /
                    16
                  
                
                
                  0
                
                
                  
                    3
                    /
                    4
                  
                
                
                  0
                
                
                  
                    3
                    /
                    16
                  
                
              
              
                
                  0
                
                
                  
                    1
                    /
                    4
                  
                
                
                  0
                
                
                  
                    3
                    /
                    4
                  
                
                
                  0
                
              
            
            ]
          
        
        ⁢
        
          

        
        ⁢
        and
        ⁢
        
          

        
        ⁢
        
          
            A
            e
          
          =
          
            
              [
              
                
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                
                
                  
                    
                      1
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      8
                    
                  
                
                
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        9
        )
      
    
  




Details on the derivation of these state transition matrices are provided below in the successive quantization detail section. These state transition matrices ensure that the (s[n])p and (t[n])p sequences are free of spurious tones because each is a random process whose autocorrelation function converges to a constant as its time spread increases. Furthermore, the PSD of sd[n] has a zero at ω=0 and increases at 6 dB per octave as ω increases from zero. In this respect, the quantization noise shaping of this version of the successive requantizer is comparable to that of a first-order ΔΣ modulator.
Successive requantizers with higher than first-order quantization noise shaping can also be designed. For example, second-order quantization noise shaping can be achieved by quantization blocks that calculate sd[n] as a function the running sum of td[n] in addition to td[n], a random sequence, and the parity of xd[n]. However, the fractional-N PLL in this work is a phase noise cancelling fractional-N PLL, so higher than first-order shaping is not necessary because most of the quantization noise is removed prior to the loop filter via a DAC.
The running sums of each td,i[n] sequence, i.e.,




  
    
      
        
          
            
              t
              
                d
                ,
                i
              
            
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                k
                =
                0
              
              n
            
            ⁢
            
              
                t
                
                  d
                  ,
                  
                    i
                    -
                    1
                  
                
              
              ⁡
              
                [
                k
                ]
              
            
          
        
        ,
        
          
            
              t
              
                d
                ,
                1
              
            
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                k
                =
                0
              
              n
            
            ⁢
            
              
                t
                d
              
              ⁡
              
                [
                n
                ]
              
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




can be bounded for all n, and each td,i[n] has a smooth power spectral density that increases monotonically with frequency.
A tradeoff related to the quantization block 202d in FIGS. 3A and 3B is that its reduced susceptibility to nonlinearity-induced spurious tones comes at the expense of increased quantization noise power. For example, if it is desired to have quantization noise with a first-order highpass spectral shape, but it is not necessary to prevent nonlinear distortion from inducing spurious tones in the quantization noise and its running sum, a quantization block that implements




  
    
      
        
          
            s
            d
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          {
          
            
              
                
                  0
                  ,
                
              
              
                
                  
                    
                      x
                      d
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  =
                  even
                
              
              
                
                  
                
              
            
            
              
                
                  
                    
                      r
                      d
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ,
                
              
              
                
                  
                    
                      
                        x
                        d
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    =
                    odd
                  
                  ,
                
              
              
                
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                  =
                  0
                
              
            
            
              
                
                  1
                  ,
                
              
              
                
                  
                    
                      
                        x
                        d
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    =
                    odd
                  
                  ,
                
              
              
                
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                  =
                  
                    -
                    1
                  
                
              
            
            
              
                
                  
                    -
                    1
                  
                  ,
                
              
              
                
                  
                    
                      
                        x
                        d
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    =
                    odd
                  
                  ,
                
              
              
                
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                  =
                  1
                
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




can be used, where rd[n] is an independent random sequence that takes on the values 1 and −1 with equal probability. In this case sd[n] takes on values of −1, 0, and 1, whereas the td[n] generated by the quantization block of FIG. 3A takes on values of −1, 0, 1. Consequently, the power of the quantization noise from a quantization block based on (11) is significantly lower than that from the quantization block of FIG. 3A.
This example suggests what is believed to be a fundamental design tradeoff: reduced susceptibility to nonlinearity-induced spurious tones comes at the expense of increased quantization noise power. Increased quantization noise is unlikely to be a significant problem in phase noise cancelling fractional-N PLLs, but it is likely to be an issue in fractional-N PLLs that lack phase noise cancellation. Any particular design will benefit from analytical quantification of the tradeoff and its effect on the performance of a particular fractional-N PLL, and especially in the case of a PLL that lacks phase noise cancellation. Preferred embodiments of the invention use a phase noise cancelling PLL design, such as the design that is described in commonly owned U.S. patent application Ser. No. 12/352,293 (“the '293 application”), filed Jan. 12, 2009, and entitled Adaptive Phase Noise Cancellation for Fractional-N Phase Locked Loop (which application is incorporated by reference herein).
FIG. 4 is a block diagram of an experimental prototype phase noise cancelling fractional-N PLL prototype in accordance with the invention. The prototpye's reference frequency was 12 MHz, and its output frequency range covered the 2.4 GHz ISM band. The phase noise cancellation enables a loop bandwidth of 975 kHz which is close to the fref/10 loop bandwidth upper limit for stability.
The FIG. 4 fractional-N PLL includes the successive requantizer 200 to that is shown in FIGS. 2A-3B and the remainder of the circuit preferably conducts adaptive phase noise cancellation as conducted by the preferred embodiments in the '293 application. The FIG. 4 fractional-N PLL includes a sampled loop filter 402 that drives a VCO 404, with preferred embodiments using a sampled loop filter having two separate loop filter halves that drive separate half-sized parallel varactors in the VCO 404 as in the '293 application. An amplifier 406 uses a 12 MHz crystal and supplies the reference clock voltage to a phase frequency detector/charge pump 408. The timing of pulses in the reference voltage and pulses received from the divider 410 determines whether the PFD/Charge pump will produce a positive or negative pulse of current to increase or decrease the VCO frequency. The successive requantizer 200 acts as discussed above to provide a sequence of values that average to a desired fractional value. A noise cancellation path including a filter 412, dithered quantizer 414, segmented DEM 416 encoder and DAC bank 418, discrete-time integrates the quantization noise to obtain a digital sequence and transform it via the DAC 202 into a current pulse of fixed duration and variable amplitude that equals the quantization noise portion of the charge in the corresponding charge pump pulse. A prototype integrated circuit in accordance with FIG. 4 also included alternate circuitry that could be enabled or disabled, including a ΔΣ modulator which could be optionally be used instead of the successive requantizer and an offset pulse generator 420 that can be enabled or disabled. In the IC prototype, the loop filter's sampling could be enabled or disabled, and when it was disabled, the loop filter reduces to a conventional loop filter.
The divider 410 is similar to the divider in the '293 application, except with minor changes to provide timing signals that control the offset current generator 418 and open the loop filter switch each reference period. As described in '293 application, the necessary timing signals are obtained by a chain of flip-flops clocked at half the VCO frequency. The timing signal used to close the loop filter switch each reference period could similarly have been derived within the divider block, but an RC one-shot circuit, timed from an output of the divider block, with a nominal duration of 25 ns was used in the prototype integrated circuit instead for simplicity because the length of time the switch is left open is not critical. Provided the switch is open when the loop filter's input current is non-zero, the PLL dynamics are relatively insensitive to the length of time it is open. Testing of the prototype with the successive requantizer, offset pulse generator, and sampled loop filter enabled and α chosen such that αfref=50 kHz revealed fractional spurs well inside the 975 kHz loop bandwidth, but all below −70 dBc in power. Four copies of the IC were tested. Table 1 shows the worst-case measurements taken from the four ICs. An IC wiring mistake disabled the DAC calibration circuitry, so the measurements described above were made after a one-time manual adjustment of the DAC gain. To confirm the diagnosis of the mistake, it was corrected in one copy of the IC by FIB microsurgery, but with the anticipated side effect of a coupling path that increased the measured in-band phase noise, 3 MHz phase noise, and largest in-band fractional spur by 10 dB, 3 dB, and 3 dB, respectively, above those shown in Table 1.












Design Details









Technology
0.18 um 1P6M CMOS



Package and Die area
32 pin TQFN,



2.2 mm × 2.2 mm










Vdd
1.8
V



Reference frequency
12
MHz


Output frequency
2.4-2.5
GHz


Measured loop bandwidth
975
kHz







Measured Current Consumption










VCO and Divider Buffer
5.9
mA
Core


Divider
7.3
mA
27.1 mA


Charge Pump, PFD, and Buffers
8.6
mA


Offset Current
0.6
mA


Digital
1.9
mA


DAC
2.8
mA


Bandgap Bias Generator
5.4
mA
 9.8 mA


Crystal Buffer
2.7
mA


External Buffer
1.7
mA







Measured Integer-N Performance










Phase Noise at 100 kHz
−103
dBc/Hz



Phase Noise at 3 MHz
−125
dBc/Hz


Reference spur without sampling
−58
dBc


enabled


Reference spur with sampling
−70
dBc


enabled







Measured Fractional-N Performance










Phase Noise at 100 kHz
−98
dBc/Hz



Phase Noise at 3 MHz
−121
dBc/Hz


Worst case in-band fractional spur
−45
dBc


with ΔΣ modulator


Worst case in-band fractional spur
−64
dBc


with SR


Reference spur without sampling
−40
dBc


enabled


Reference spur with sampling
−70
dBc


enabled









Successive Requantization Proof
The restriction to first-order highpass shaped quantization noise discussed above still leaves flexibility in the design of the sd[n] sequences. This flexibility is exploited to ensure that sp[n] for p=1, 2, . . . , h, and tp[n] for p=1, 2, . . . , ht are free of spurious tones, where hs and ht are positive integers. By definition, if sp[n] and tp[n] contain spurious tones at a frequency ωn, then Equations (2) and (3) above, respectively, are expected to be unbounded in probability at ω=ωn as L>∞. Therefore, to establish that there are no spurious tones in either sp[n] or tp[n], it is sufficient to show that Equations (2) and (3) are bounded in probability for all |ω|≦π as L→∞. A spurious tone at ω=0 is just a constant offset. Many practical systems are able to tolerate, or compensate for this offset so this case is excluded from consideration. Theorems 1 and 2 below present sufficient conditions on the sd[n] sequences for (2) and (3) to be bounded in probability for every L≧1 and 0<|ω|≦π, thereby ensuring the absence of spurious tones in sp[n] and tp[n]. First-order highpass quantization noise is achieved with quantization blocks that implement equation (11) above. Results imply that neither sd[n] nor td[n] contain spurious tones. Therefore, s[n] and t[n] inherit these properties provided the rd[n] sequences for d=0, . . . , K−1 are independent.
However, if the quantization noise or its running sum is subjected to non-linear distortion, spurious tones can be induced. The presence of spurious tones implies that subjecting t[n] to second-order distortion is sufficient to induce spurious tones even though t[n] is known to be free of spurious tones.
The spur generation mechanism can be understood by considering the first quantization block. Suppose the input to the successive requantizer is an odd-valued constant and t0[n−1]=0 for some value of n. Then (11) implies that (s0[n], s0[n+1]) is either (−1, 1) or (1, −1) depending on the polarity of P0[n]. It follows from (5) that (t0[n], t0[n+1]) is either (−1, 0) or (1, 0), and, by induction, t0[n] has the form { . . . , 0, ±1, 0, ±1, 0, ±1, 0, . . . }. Therefore, t02[n] has the form { . . . , 0, 1, 0, 1, 0, 1, 0, . . . } which is periodic. A similar, but more involved analysis can be used to show that the td2[n] sequences for d>0 also contain periodic components. These periodic components cause the spurious tones.
For the purpose of illustrating the principle of successive requantization for tone free quantization sequences, the remainder of the description assumes that the input to the quantizer, x0[n], is an integer-valued and deterministic sequence for n=0, 1, . . . , and that the successive requantizer is designed such that the following properties are satisfied:

    Property 1: xd+1[n]=(sd[n]+xd[n])/2 is integer-valued for n=0, 1, . . . , and d=0, 1, . . . , K−1.
    Property 2: there exists a positive constant B such that |td[n]|<B, for n=0, 1, 2, . . . .
    Property 3: td[0]=0, and

td[n]=f(td[n−1],rd[n],od[n])  (12)
    
        where rd[n], d=0, 1, . . . , K−1, n=1, 2, . . . } is a set of independent identically distributed (iid) random variables, and
    
    






  
    
      
        
          
            o
            d
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            
              
                x
                d
              
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              mod
              ⁢
              2
            
          
          =
          
            {
            
              
                
                  
                    1
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          d
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      is
                      ⁢
                      
                        
                      
                      ⁢
                      odd
                    
                    ,
                  
                
              
              
                
                  
                    0
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          d
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      is
                      ⁢
                      
                        
                      
                      ⁢
                      even
                    
                    ,
                  
                
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




    
    
        is called the parity sequence of the dth quantization block. Furthermore, f(x, y, z) is a deterministic function which does not depend on n.
    
    


Property 2 guarantees first-order spectral shaping of the quantization error by ensuring that td[n] takes on a finite number of values for all n. However it need not be an optimal bound on the quantization error of the successive requantizer. Relaxing this bound, and hence incurring more quantization error power, permits the removal of spurious tones under non-linearities.
Property 1 and the assumption that x0[n] is integer-valued imply that sd[n] is an even integer when xd[n] is even, and an odd integer otherwise. Therefore, (5) implies that td[n] is integer-valued, and Property 2 further implies that it is restricted to a finite set of values. Let T1, T2, . . . , TN denote these values. Therefore, the function, ƒ, in Property 3 takes on values restricted to the set {T1, T2, . . . , TN}.
It follows from Properties 1, 2, and 3 that xd+1[n], sd[n], and td[n], for d=0, 1, K−1,and n=1, 2, . . . , depend only on the set of iid random variables {rd[n], d=0, 1, . . . , K−1, n=0, 1, 2, . . . } and the deterministic successive requantizer input sequence, {x0[n], n=1, 2, . . . ,}. Therefore, the sample description space of the underlying probability space is the set of all possible values of the random variables {rd[n], d=0, 1, . . . , K−1, and n=0, 1, 2, . . . }.
Equation (5) implies that

sd[n]=td[n]−td[n−1].  (14)

Therefore, it follows from Property 1 that

xd[n]=td−1[n]−td−1[n−1]+xd−1[n])/2,  (15)

for 1≦d<K. Recursively substituting (15) into itself and applying (13) yields




  
    
      
        
          
            o
            d
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            
              1
              2
            
            ⁡
            
              [
              
                
                  
                    x
                    o
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                +
                
                  
                    ∑
                    
                      k
                      =
                      0
                    
                    
                      d
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      2
                      
                        -
                        k
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            t
                            k
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        -
                        
                          
                            t
                            k
                          
                          ⁡
                          
                            [
                            
                              n
                              -
                              1
                            
                            ]
                          
                        
                      
                      )
                    
                  
                
              
              ]
            
          
          ⁢
          mod
          ⁢
          
            
          
          ⁢
          2.
        
      
    
    
      
        (
        16
        )
      
    
  




Recursively substituting (12) into itself implies that for any integer n>0,

td[n]=gn(rd[n],rd[n−1], . . . , rd[1],od[n],od[n−1], . . . , od[1])  (17)

where gn is a deterministic, memoryless function. Similarly, for any pair of integers n2>n1>0, recursively substituting (12) into itself m=n2−n1−1 times implies that

td[n2]=hm(td[n1],rd[n1+1],rd[n1+2], . . . , rd[n2], od[n1+1], od[n1+2], . . . , od[n2])  (18)

where hm is a deterministic, memoryless function.
Repeatedly substituting (16) into (17) to eliminate the variables {od[n], . . . , od[1]} and then recursively substituting the result into itself to eliminate the variables {tk[m], k=0, . . . , d−1, m=1, . . . , n} shows that td[n] is a random variable that depends only on x0[n] (which is deterministic), and the random variables {rk[m], k=0, 1, . . . , d, m=1, 2, . . . , n}. This in conjunction with (16) implies that od[n] is a random variable that depends only on x0[n], and the random variables {rk[m], k=0, 1, d−1, m=1, 2, n}. In particular, since the random sequence {od[n], n=0, 1, 2, . . . } does not depend on the random sequence {rd[n], n=0, 1, 2, . . . } and since all the random variables {rk[m] d=0, 1, . . . , K−1, n=0, 1, 2, . . . } are statistically independent by Property 3, it follows that {od[n], n=0, 1, 2, . . . } and {rd[n], n=0, 1, 2, . . . } are statistically independent random sequences. By similar reasoning, the random variable td[n] is statistically independent of the random variables {rd[m], m=n+1, n+2, . . . }
Hence, (18) implies that td[n2] conditioned on the random variables td[n1], od[n1+1], od[n1+2], od[n2] is a function only of the statistically independent random variables rd[n1], rd[n1+1], . . . , rd[n2]. By definition, for i≠j the random variables {ri[n1], ri[n1+1], . . . , ri[n2]} are statistically independent of the random variables {rj[n1], rj[n1+1], . . . , rj[n2]}. Therefore, for i≠j the random variables ti[n2] and tj[n2] and conditioned on ti[n1], tj[n1], oi[n1+1], oi[n1+2], . . . , oi[n2], oj[n1+1], oj[n1+2], . . . , oj[n2] are statistically independent. Consequently, for any positive real numbers p0, . . . , pk−1,




  
    
      
        
          
            E
            ⁡
            
              [
              
                
                  
                    
                      ∏
                      
                        j
                        =
                        0
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        t
                        j
                        
                          p
                          j
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          2
                        
                        ]
                      
                    
                  
                  ❘
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                
                ,
                
                  
                    
                      o
                      d
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ;
                  
                    d
                    =
                    0
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  K
                  -
                  1
                
                ,
                
                  n
                  =
                  
                    
                      n
                      1
                    
                    +
                    1
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  n
                  2
                
              
              ]
            
          
          =
          
            
              
                ∏
                
                  j
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                E
                [
                
                  
                
                ⁢
                
                  
                    
                      
                        t
                        j
                        
                          p
                          j
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          2
                        
                        ]
                      
                    
                    ❘
                    
                      
                        t
                        d
                      
                      ⁡
                      
                        [
                        
                          n
                          1
                        
                        ]
                      
                    
                  
                  ,
                  
                    
                      
                        o
                        d
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    ;
                    
                      d
                      =
                      0
                    
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    K
                    -
                    1
                  
                  ,
                  
                    n
                    =
                    
                      
                        n
                        1
                      
                      +
                      1
                    
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    n
                    2
                  
                
                ]
              
            
            =
            
              
                ∏
                
                  j
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                E
                [
                
                  
                
                ⁢
                
                  
                    
                      
                        t
                        j
                        
                          p
                          j
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          2
                        
                        ]
                      
                    
                    ❘
                    
                      
                        t
                        j
                      
                      ⁡
                      
                        [
                        
                          n
                          1
                        
                        ]
                      
                    
                  
                  ,
                  
                    
                      
                        o
                        j
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    ;
                    
                      n
                      =
                      
                        
                          n
                          1
                        
                        +
                        1
                      
                    
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    n
                    2
                  
                
                ]
              
            
          
        
        ,
      
    
    
      
        (
        19
        )
      
    
  




where the second equality follows from (12) and the independence of the {rd[n], n=1, 2, . . . ,} sequences for d=0, K−1. This implies that the pmf of the random variable ti┌n2┐ conditioned on ti┌n1┐, oi┌n1+1┌, oi┌n1+2┐, . . . , oi┌n2┐ is independent of any additional conditioning by and tj[n1], oj[n1+1], oj[n11+2], . . . , oj[n2] for i≠j.
The statistical independence of od[n] and rd[n] together with (12) imply that {td[n], n=0, 1, . . . } is a discrete-valued Markov random sequence conditioned on the sequence {od[n], n=0, 1, . . . }. Whenever xd[n] is odd the one-step state transition matrix for td[n] is given by

Ao=[r{td[n]=Tj|td[n−1]=Ti,od[n]=1}]N×N.  (20)

Similarly, whenever xd[n] is even the one-step state transition matrix for td[n] is given by

Ae=[P{td[n]=Tj|td[n−1]=Ti,od[n]=0}]N×N.  (21)

The function ƒ in Property 3 is independent of n and d, so neither matrix is a function of n and d.
Equation (14) implies that each possible value of sd[n] is given by Tj−T1 for some pair of integers i and j, 1≦i, j≦N, so

P{sd[n]=Tj−Ti|td[n−1]=Ti,od[n]=1}=P{td[n]=Tj|td[n−1]=Ti,od[n]=1}.  (22)

Given that td[n] is restricted to N possible values, sd[n] is restricted to N′ possible values where N′≦N2. With identical reasoning to that used to proceed from (15) to (19), it follows that




  
    
      
        
          E
          ⁡
          
            [
            
              
                
                  
                    ∏
                    
                      j
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      s
                      j
                      
                        p
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        2
                      
                      ]
                    
                  
                
                ❘
                
                  
                    t
                    0
                  
                  ⁡
                  
                    [
                    
                      n
                      1
                    
                    ]
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  t
                  
                    K
                    -
                    1
                  
                
                ⁡
                
                  [
                  
                    n
                    1
                  
                  ]
                
              
              ,
              
                
                  
                    o
                    d
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                ;
                
                  d
                  =
                  0
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                K
                -
                1
              
              ,
              
                n
                =
                
                  
                    n
                    1
                  
                  +
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                n
                2
              
            
            ]
          
        
        =
        
          
            ∏
            
              j
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            
              E
              [
              
                
              
              ⁢
              
                
                  
                    
                      s
                      j
                      
                        p
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        2
                      
                      ]
                    
                  
                  ❘
                  
                    
                      t
                      j
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                
                ,
                
                  
                    
                      o
                      j
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ;
                  
                    n
                    =
                    
                      
                        n
                        1
                      
                      +
                      1
                    
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  n
                  2
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        23
        )
      
    
  




Given that {td[n], n=0, 1, . . . } is a discrete-valued Markov random sequence conditioned on the sequence {od[n], n=0, 1, . . . }, the conditional probability mass function (pmf) of td[n2] given td[n1] and od[n] is equal to the conditional pmf of td[n2] given td[n1], td[n1−1] and od[n]. Therefore, (14) implies that (23) is equivalent to




  
    
      
        
          E
          ⁡
          
            [
            
              
                
                  
                    ∏
                    
                      j
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      s
                      j
                      
                        p
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        2
                      
                      ]
                    
                  
                
                |
                
                  
                    s
                    0
                  
                  ⁡
                  
                    [
                    
                      n
                      1
                    
                    ]
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  s
                  
                    K
                    -
                    1
                  
                
                ⁡
                
                  [
                  
                    n
                    1
                  
                  ]
                
              
              ,
              
                
                  t
                  0
                
                ⁡
                
                  [
                  
                    n
                    1
                  
                  ]
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  t
                  
                    K
                    -
                    1
                  
                
                ⁡
                
                  [
                  
                    n
                    1
                  
                  ]
                
              
              ,
              
                
                  
                    o
                    d
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                ;
                
                  d
                  =
                  0
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                K
                -
                1
              
              ,
              
                n
                =
                
                  
                    n
                    1
                  
                  +
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                n
                2
              
            
            ]
          
        
        =
        
          
            ∏
            
              j
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            E
            ⁡
            
              [
              
                
                  
                    
                      s
                      j
                      
                        p
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        2
                      
                      ]
                    
                  
                  |
                  
                    
                      t
                      j
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                
                ,
                
                  
                    
                      o
                      j
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ;
                  
                    n
                    =
                    
                      
                        n
                        1
                      
                      +
                      1
                    
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  n
                  2
                
              
              ]
            
          
        
      
    
    
      
        (
        24
        )
      
    
  




The following definitions are used by the theorems presented below. In analogy to the matrices Ao and Ae, let

So=[P{sd[n]=Sj|td[n−1]=Ti,od[n]=1}]N×N′,  (25)

and

Se[P{sd[n]−Sj|td[n−1]=Ti,od[n]=0}]N×N′,  (26)

where {Si, 1≦i≦N′} is the set of all possible values of sd[n]. Property 3 ensures that neither matrix is a function of n and d. It follows from (22) that each non-zero element of So or Se is equal to an element in Ao or Ae, respectively. For example, if Sk=Tj−Ti, then the element in the ith row and kth column of So is equal to the element in the ith row and jth column of Ao. In this fashion, once Ao and Ae are known, So and Se can be deduced.

Let




  
    
      
        
          1
          ⁢
          
            =
            Δ
          
          ⁢
          
            [
            
              
                
                  1
                
              
              
                
                  ⋮
                
              
              
                
                  1
                
              
            
            ]
          
        
        ,
        
          
            t
            
              (
              p
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            [
            
              
                
                  
                    
                      (
                      
                        T
                        1
                      
                      )
                    
                    p
                  
                
              
              
                
                  ⋮
                
              
              
                
                  
                    
                      (
                      
                        T
                        N
                      
                      )
                    
                    p
                  
                
              
            
            ]
          
        
        ,
        
          
            and
            ⁢
            
              
            
            ⁢
            
              s
              
                (
                p
                )
              
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            [
            
              
                
                  
                    
                      (
                      
                        S
                        1
                      
                      )
                    
                    p
                  
                
              
              
                
                  ⋮
                
              
              
                
                  
                    
                      (
                      
                        S
                        
                          N
                          ′
                        
                      
                      )
                    
                    p
                  
                
              
            
            ]
          
        
      
    
    
      
        (
        27
        )
      
    
  




Suppose a sequence of vectors, b[n]=[b1[n], . . . , bN[n]]T converges to a constant vector, b1, as n→∞. Then the convergence is said to be exponential if there exist constants C≧0 and 0≦α<1 such that

|bi[n]−b|≦Cαn  (28)

for all 1≦i≦N and n≧0.
Theorem 1: Suppose that the state transition matrices Ae and Ao satisfy

AeAo=AoAe,  (29)

and there exists an integer ht≧1 such that for each positive integer p≦ht




  
    
      
        
          
            
              lim
              
                n
                →
                ∞
              
            
            ⁢
            
              
                A
                e
                n
              
              ⁢
              
                t
                
                  (
                  p
                  )
                
              
            
          
          =
          
            
              b
              p
            
            ⁢
            1
          
        
        ,
        
          
            and
            ⁢
            
              
            
            ⁢
            
              
                lim
                
                  n
                  →
                  ∞
                
              
              ⁢
              
                
                  A
                  o
                  n
                
                ⁢
                
                  t
                  
                    (
                    p
                    )
                  
                
              
            
          
          =
          
            
              b
              p
            
            ⁢
            1
          
        
      
    
    
      
        (
        30
        )
      
    
  




where bp is a constant and the convergence of both vectors is exponential. Then for every L≧1,

E[Itp,L(ω)]≦C(ω)<∞  (31)

for each 0<|ω|≦π. Moreover, the bound C(ω), which is independent of L, is uniform in ω for all 0<ε<|ω|≦π.
By Markov's Inequality, this immediately leads to:
Corollary 1: Under the assumptions of Theorem 1, Itp,L(∞) is bounded in probability for all L≧1 and for each ω satisfying 0<|ω|≦π.
Proof of Theorem 1: The expectation of Itp,L(ω) can be expressed as




   
  
    
      
        
          
            
              
                
                  E
                  ⁡
                  
                    [
                    
                      
                        I
                        
                          
                            t
                            ⁢
                            
                              
                            
                            ⁢
                            P
                          
                          ,
                          L
                        
                      
                      ⁡
                      
                        (
                        ω
                        )
                      
                    
                    ]
                  
                
                =
                
                ⁢
                
                  
                    1
                    L
                  
                  ⁢
                  
                    
                      ∑
                      
                        
                          n
                          1
                        
                        =
                        0
                      
                      
                        L
                        -
                        1
                      
                    
                    ⁢
                    
                      
                        ∑
                        
                          
                            n
                            2
                          
                          =
                          0
                        
                        
                          L
                          -
                          1
                        
                      
                      ⁢
                      
                        
                          E
                          ⁡
                          
                            [
                            
                              
                                
                                  t
                                  p
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    1
                                  
                                  ]
                                
                              
                              ⁢
                              
                                
                                  t
                                  p
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    2
                                  
                                  ]
                                
                              
                            
                            ]
                          
                        
                        ⁢
                        
                          e
                          
                            -
                            
                              jω
                              ⁡
                              
                                (
                                
                                  
                                    n
                                    1
                                  
                                  -
                                  
                                    n
                                    2
                                  
                                
                                )
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    
                      1
                      L
                    
                    ⁢
                    
                      
                        ∑
                        
                          
                            n
                            1
                          
                          =
                          0
                        
                        
                          L
                          -
                          1
                        
                      
                      ⁢
                      
                        E
                        ⁡
                        
                          [
                          
                            
                              t
                              
                                2
                                ⁢
                                p
                              
                            
                            ⁡
                            
                              [
                              n
                              ]
                            
                          
                          ]
                        
                      
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      1
                      L
                    
                    ⁢
                    
                      
                        ∑
                        
                          
                            
                              n
                              1
                            
                            =
                            0
                          
                          
                            
                              n
                              1
                            
                            ≠
                            
                              n
                              2
                            
                          
                        
                        
                          L
                          -
                          1
                        
                      
                      ⁢
                      
                        
                          ∑
                          
                            
                              n
                              2
                            
                            =
                            0
                          
                          
                            L
                            -
                            1
                          
                        
                        ⁢
                        
                          
                            E
                            ⁡
                            
                              [
                              
                                
                                  
                                    t
                                    p
                                  
                                  ⁡
                                  
                                    [
                                    
                                      n
                                      1
                                    
                                    ]
                                  
                                
                                ⁢
                                
                                  
                                    t
                                    p
                                  
                                  ⁡
                                  
                                    [
                                    
                                      n
                                      2
                                    
                                    ]
                                  
                                
                              
                              ]
                            
                          
                          ⁢
                          
                            e
                            
                              -
                              
                                jω
                                ⁡
                                
                                  (
                                  
                                    
                                      n
                                      1
                                    
                                    -
                                    
                                      n
                                      2
                                    
                                  
                                  )
                                
                              
                            
                          
                        
                      
                    
                  
                  ⁢
                  
                    =
                    Δ
                  
                  ⁢
                  
                    
                      J
                      1
                    
                    +
                    
                      
                        J
                        2
                      
                      .
                    
                  
                
              
            
          
        
      
      
        
          (
          32
          )
        
      
    
  




The notation above means that J1 and J2 are defined as the first and second terms, respectively, to the left of the  symbol. Property 2 states that |td[n]|≦B, so it follows from (6) that t[n]≦B1 for some finite constant B1. Therefore, J1≦B12p. The crux of the proof is showing that there exists a constant Ctp, positive constants D1, D2, and a constant 0<α<1 such that for n1≠n2 

|E[tp[n1]tp[n2]−Ctp]|≦D1α|n2−n1|+D2α11  (33)

The proof of (33) is outlined in Lemma 1 in the proof of Lemmas given below. Here (33) is used to complete the proof of the theorem. From (32), J2 can be expressed as




  
    
      
        
          J
          2
        
        =
        
          
            
              
                1
                L
              
              ⁢
              
                
                  ∑
                  
                    
                      
                        n
                        1
                      
                      =
                      0
                    
                    
                      
                        n
                        1
                      
                      ≠
                      
                        n
                        2
                      
                    
                  
                  
                    L
                    -
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      
                        n
                        2
                      
                      =
                      0
                    
                    
                      L
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      (
                      
                        E
                        ⁡
                        
                          [
                          
                            
                              
                                
                                  t
                                  p
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    1
                                  
                                  ]
                                
                              
                              ⁢
                              
                                
                                  t
                                  p
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    2
                                  
                                  ]
                                
                              
                            
                            -
                            
                              C
                              
                                t
                                p
                              
                            
                          
                          ]
                        
                      
                      )
                    
                    ⁢
                    
                      e
                      
                        -
                        
                          jω
                          ⁡
                          
                            (
                            
                              
                                n
                                1
                              
                              -
                              
                                n
                                2
                              
                            
                            )
                          
                        
                      
                    
                  
                
              
            
            +
            
              
                1
                L
              
              ⁢
              
                
                  ∑
                  
                    
                      
                        n
                        1
                      
                      =
                      0
                    
                    
                      
                        n
                        1
                      
                      ≠
                      
                        n
                        2
                      
                    
                  
                  
                    L
                    -
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      
                        n
                        2
                      
                      =
                      0
                    
                    
                      L
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      C
                      
                        t
                        p
                      
                    
                    ⁢
                    
                      e
                      
                        -
                        
                          jω
                          ⁡
                          
                            (
                            
                              
                                n
                                1
                              
                              -
                              
                                n
                                2
                              
                            
                            )
                          
                        
                      
                    
                  
                
              
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              J
              
                2
                ,
                1
              
            
            +
            
              
                J
                
                  2
                  ,
                  2
                
              
              .
            
          
        
      
    
    
      
        (
        34
        )
      
    
  




From (33) it is seen that




  
    
      
        
          
          
            J
            
              2
              ,
              1
            
          
          
        
        ≤
        
          
            1
            L
          
          ⁢
          
            
              ∑
              
                
                  
                    n
                    1
                  
                  =
                  0
                
                
                  
                    n
                    1
                  
                  ≠
                  
                    n
                    2
                  
                
              
              
                L
                -
                1
              
            
            ⁢
            
              
                ∑
                
                  
                    n
                    2
                  
                  =
                  0
                
                
                  L
                  -
                  1
                
              
              ⁢
              
                (
                
                  
                    
                      D
                      1
                    
                    ⁢
                    
                      α
                      
                        
                        
                          
                            n
                            1
                          
                          -
                          
                            n
                            2
                          
                        
                        
                      
                    
                  
                  +
                  
                    
                      D
                      2
                    
                    ⁢
                    
                      α
                      
                        n
                        1
                      
                    
                  
                
                )
              
            
          
        
        ≤
        
          
            
              
                D
                1
              
              L
            
            ⁢
            
              
                ∑
                
                  
                    n
                    1
                  
                  =
                  0
                
                
                  L
                  -
                  1
                
              
              ⁢
              
                
                  ∑
                  
                    
                      n
                      2
                    
                    =
                    0
                  
                  
                    L
                    -
                    1
                  
                
                ⁢
                
                  α
                  
                    
                    
                      
                        n
                        1
                      
                      -
                      
                        n
                        2
                      
                    
                    
                  
                
              
            
          
          +
          
            
              D
              2
            
            ⁢
            
              
                ∑
                
                  
                    n
                    1
                  
                  =
                  0
                
                
                  L
                  -
                  1
                
              
              ⁢
              
                α
                
                  n
                  1
                
              
            
          
        
        ≤
        
          2
          ⁢
          
            (
            
              
                D
                1
              
              +
              
                D
                2
              
            
            )
          
          ⁢
          
            
              1
              -
              
                α
                L
              
            
            
              1
              -
              α
            
          
        
        ≤
        
          2
          ⁢
          
            (
            
              
                D
                1
              
              +
              
                D
                2
              
            
            )
          
          ⁢
          
            
              1
              
                1
                -
                α
              
            
            .
          
        
      
    
    
      
        (
        35
        )
      
    
  




and the bound is independent of L. Similarly, J2,2 can be bounded by




  
    
      
        
          
            
            
              J
              
                2
                ,
                2
              
            
            
          
          ≤
          
            
              
                
                
                  C
                  
                    t
                    p
                  
                
                
              
              L
            
            ⁢
            
              
              
                
                  
                    
                    
                      
                        ∑
                        
                          n
                          =
                          0
                        
                        
                          L
                          -
                          1
                        
                      
                      ⁢
                      
                        e
                        
                          
                            -
                            jω
                          
                          ⁢
                          
                            
                          
                          ⁢
                          n
                        
                      
                    
                    
                  
                  2
                
                -
                L
              
              
            
          
          ≤
          
            
              
                
                
                  C
                  
                    t
                    p
                  
                
                
              
              L
            
            ⁢
            
              
              
                
                  
                    
                    
                      
                        1
                        -
                        
                          e
                          
                            
                              -
                              jω
                            
                            ⁢
                            
                              
                            
                            ⁢
                            L
                          
                        
                      
                      
                        1
                        -
                        
                          e
                          
                            
                              -
                              jω
                            
                            ⁢
                            
                              
                            
                          
                        
                      
                    
                    
                  
                  2
                
                -
                L
              
              
            
          
        
        =
        
          
            
              
                
                
                  C
                  
                    t
                    p
                  
                
                
              
              L
            
            ⁢
            
              
                
                
                  
                    
                      
                      
                        
                          sin
                          ⁡
                          
                            (
                            
                              ω
                              ⁢
                              
                                
                              
                              ⁢
                              
                                L
                                /
                                2
                              
                            
                            )
                          
                        
                        
                          sin
                          ⁡
                          
                            (
                            
                              ω
                              /
                              2
                            
                            )
                          
                        
                      
                      
                    
                    2
                  
                  -
                  L
                
                
              
              ·
            
          
          ≤
          
            
              
              
                C
                
                  t
                  p
                
              
              
            
            ⁢
            
              (
              
                1
                +
                
                  1
                  
                    
                      sin
                      2
                    
                    ⁡
                    
                      (
                      
                        ω
                        /
                        2
                      
                      )
                    
                  
                
              
              )
            
          
        
      
    
    
      
        (
        36
        )
      
    
  




which is finite, independent of L, for each ω satisfying 0<ω|≦π; the bound is uniform for all ω satisfying 0<ε<|ω|≦π since sin(ω/2)>sin(ε/2). The result of the theorem then follows from (32) through (36).

Theorem 2: Suppose that the state transition matrices Ae and Ao satisfy

AeAo=AoAe,  (37)

and there exists an integer hs≧1 such that for each positive integer p≦hs, the sequence transition matrices Se and So satisfy




   
  
    
      
        
          
            
              
                
                  
                    lim
                    
                      n
                      →
                      ∞
                    
                  
                  ⁢
                  
                    
                      A
                      e
                      n
                    
                    ⁢
                    
                      S
                      e
                    
                    ⁢
                    
                      s
                      
                        (
                        p
                        )
                      
                    
                  
                
                =
                
                ⁢
                
                  
                    lim
                    
                      n
                      →
                      ∞
                    
                  
                  ⁢
                  
                    
                      A
                      e
                      n
                    
                    ⁢
                    
                      S
                      o
                    
                    ⁢
                    
                      s
                      
                        (
                        p
                        )
                      
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    lim
                    
                      n
                      →
                      ∞
                    
                  
                  ⁢
                  
                    
                      A
                      o
                      n
                    
                    ⁢
                    
                      S
                      e
                    
                    ⁢
                    
                      s
                      
                        (
                        p
                        )
                      
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    lim
                    
                      n
                      →
                      ∞
                    
                  
                  ⁢
                  
                    
                      A
                      o
                      n
                    
                    ⁢
                    
                      S
                      o
                    
                    ⁢
                    
                      s
                      
                        (
                        p
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  =
                  
                  ⁢
                  
                    
                      c
                      p
                    
                    ⁢
                    1
                  
                
                ,
              
            
          
        
      
      
        
          (
          38
          )
        
      
    
  




where cp is a constant and the convergence of all vectors are exponential. Then for every L≧1,

E[Isp,L(ω)]≦D(ω)<∞  (39)

for each 0<<|ω|≦π. Moreover, the bound D(ω), which is independent of L, is uniform in ω for all 0<ε<|ω|<π.
By Markov's Inequality, this immediately leads to,
Corollary 2: Under the assumptions of Theorem 2, Isp,L(ω) is bounded in probability for all L≧1 and for each ω satisfying 0<|ω|≦π.
Proof of Theorem 2: The proof is identical to that of Theorem 1. Replacing tp[n1] and tp[n2] with sp[n1] and sp[n2] respectively, the crux of the proof is showing that there exists a constant Csp, positive constants E1, E2, and a constant 0<β<1 such that for n1≠n2 

|E[sp[n1]sp[n2]−Csp]|≦+Etβ|n2−n1|+E2βn1,  (40)

With (40) proven in Lemma 2 below, the remainder of the proof follows directly from Theorem 1.

Matrices Ae, Ao, Se, and So which can be used with the successive requantizer to generate quantized sequences and satisfy the conditions of Theorems 1 and 2 for ht=3 and hs=5 are presented are provided as an example.
For a state td[n] whose possible values are {−2, −1, 0, 1, 2}, define

t(p)=[(−2)p(−1)p 0 1p 2p]T  (41)

and the proposed state transition matrices as




  
    
      
        
          
            
              A
              o
            
            =
            
              [
              
                
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                
                
                  
                    
                      3
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      16
                    
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                
                
                  
                    
                      1
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      16
                    
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                
              
              ]
            
          
          ;
        
        ⁢
        
          

        
        ⁢
        and
        ⁢
        
          

        
        ⁢
        
          
            A
            e
          
          =
          
            
              [
              
                
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                
                
                  
                    
                      1
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      8
                    
                  
                
                
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        42
        )
      
    
  




From (14) all possible sd[n] values are {−4, −3, −2, −1, 0, 1, 2, 3, 4}, and further define

s(p)=[(−4)p (−3)p (−2)p (−1)p 0 1p 2p 3p 4p]T.  (43)

Applying (22) yields




  
    
      
        
          
            
              S
              o
            
            =
            
              [
              
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      16
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          and
        
        ⁢
        
          

        
        ⁢
        
          
            S
            e
          
          =
          
            
              [
              
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      5
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        44
        )
      
    
  




Multiplying the matrices in either order yields




  
    
      
        
          
            
              A
              e
            
            ⁢
            
              A
              o
            
          
          =
          
            
              
                A
                o
              
              ⁢
              
                A
                e
              
            
            =
            
              [
              
                
                  
                    0
                  
                  
                    
                      9
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      7
                      /
                      16
                    
                  
                  
                    0
                  
                
                
                  
                    
                      9
                      /
                      64
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      7
                      /
                      64
                    
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                
                
                  
                    
                      7
                      /
                      64
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      9
                      /
                      64
                    
                  
                
                
                  
                    0
                  
                  
                    
                      7
                      /
                      16
                    
                  
                  
                    0
                  
                  
                    
                      9
                      /
                      16
                    
                  
                  
                    0
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        45
        )
      
    
  




so the matrices commute. Direct computation reveals that the eigenvectors of both Ae and Ao are linearly independent, and therefore Ae and Ao are diagonalizable. Specifically, Aen=VeλenVe−1, where





  
    
      
        
          
            
              Λ
              e
              ′′
            
            =
            
              [
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      
                        4
                        ′′
                      
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      
                        4
                        ′′
                      
                    
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          
            
              V
              e
            
            =
            
              [
              
                
                  
                    1
                  
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    
                      -
                      1
                    
                  
                
                
                  
                    1
                  
                  
                    0
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      3
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                
                
                  
                    1
                  
                  
                    
                      -
                      1
                    
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
          and
        
        ⁢
        
          

        
        ⁢
        
          
            
              V
              e
              
                -
                1
              
            
            =
            
              [
              
                
                  
                    
                      1
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      8
                    
                  
                
                
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                
                
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      
                        -
                        3
                      
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                
                
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
        
      
    
    
      
        (
        46
        )
      
    
  




and Aon=VoλonVo−1, where




  
    
      
        
          
            
              Λ
              o
              n
            
            =
            
              [
              
                
                  
                    
                      
                        (
                        
                          -
                          1
                        
                        )
                      
                      n
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      
                        (
                        
                          
                            -
                            1
                          
                          /
                          4
                        
                        )
                      
                      n
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      
                        4
                        n
                      
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          
            
              V
              o
            
            =
            
              [
              
                
                  
                    1
                  
                  
                    1
                  
                  
                    1
                  
                  
                    
                      -
                      1
                    
                  
                  
                    1
                  
                
                
                  
                    
                      -
                      1
                    
                  
                  
                    1
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      3
                    
                  
                
                
                  
                    
                      -
                      1
                    
                  
                  
                    1
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    1
                  
                  
                    
                      -
                      1
                    
                  
                  
                    1
                  
                  
                    1
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          and
        
        ⁢
        
          

        
        ⁢
        
          
            V
            o
            
              -
              1
            
          
          =
          
            
              [
              
                
                  
                    
                      1
                      /
                      16
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      4
                    
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      4
                    
                  
                  
                    
                      1
                      /
                      16
                    
                  
                
                
                  
                    
                      1
                      /
                      16
                    
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    
                      1
                      /
                      16
                    
                  
                
                
                  
                    
                      1
                      /
                      4
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      4
                    
                  
                
                
                  
                    
                      
                        -
                        1
                      
                      /
                      4
                    
                  
                  
                    
                      
                        -
                        1
                      
                      /
                      2
                    
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      2
                    
                  
                  
                    
                      1
                      /
                      4
                    
                  
                
                
                  
                    
                      3
                      /
                      8
                    
                  
                  
                    0
                  
                  
                    
                      
                        -
                        3
                      
                      /
                      4
                    
                  
                  
                    0
                  
                  
                    
                      3
                      /
                      8
                    
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        47
        )
      
    
  




By inspection of (46), λen converges to




  
    
      
        
          
            Λ
            
              e
              ,
              1
            
          
          =
          
            [
            
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
            
            ]
          
        
        ,
      
    
    
      
        (
        48
        )
      
    
  




The vector given by Veλe,1Ve−1t(p) is equal to bp1, where bp=0, 1 and 0 for p=1, 2 and 3 respectively, which is of the form required by Theorem 1. To show exponential convergence, consider




  
    
      
        
          
            
            
              
                
                  A
                  e
                  n
                
                ⁢
                
                  t
                  
                    (
                    p
                    )
                  
                
              
              -
              
                
                  b
                  p
                
                ⁢
                1
              
            
            
          
          =
          
            
              
              
                
                  (
                  
                    
                      A
                      e
                      n
                    
                    -
                    
                      
                        V
                        e
                      
                      ⁢
                      
                        Λ
                        
                          e
                          ,
                          1
                        
                      
                      ⁢
                      
                        V
                        e
                        
                          -
                          1
                        
                      
                    
                  
                  )
                
                ⁢
                
                  t
                  
                    (
                    p
                    )
                  
                
              
              
            
            ≤
            
              
                
                
                  
                    A
                    e
                    n
                  
                  -
                  
                    
                      V
                      e
                    
                    ⁢
                    
                      Λ
                      
                        e
                        ,
                        1
                      
                    
                    ⁢
                    
                      V
                      e
                      
                        -
                        1
                      
                    
                  
                
                
              
              ⁢
              
                
                
                  t
                  
                    (
                    p
                    )
                  
                
                
              
            
          
        
        ,
      
    
    
      
        (
        49
        )
      
    
  




where ∥ ∥ is the l2 norm, and p=1, 2 or 3. Evaluating ∥t(p)∥ for p=3, and ∥Aen−Veλe,1Ve−1∥ yields √{square root over (130)} and √{square root over (2)}(1⁄4)n respectively therefore the right side of (49) is equal to

√{square root over (260)}(1⁄4)n  (50)

and therefore each element of the vector given by Aent(p)−bp1 converges exponentially to zero.
By inspection of (47), λon does not converge, however it is sufficient to show that the vector VoλoVo−1t(p) converges. Consider Aon=Voζo,1nVo−1+Voλo,2nVo−1 where




  
    
      
        
          
            
              Λ
              
                o
                ,
                1
              
              n
            
            =
            
              [
              
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    
                      
                        (
                        
                          
                            -
                            1
                          
                          /
                          4
                        
                        )
                      
                      n
                    
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      1
                      /
                      
                        4
                        n
                      
                    
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
          
            

          
          ⁢
          and
        
        ⁢
        
          

        
        ⁢
        
          
            
              Λ
              
                o
                ,
                2
              
              n
            
            =
            
              [
              
                
                  
                    
                      
                        (
                        
                          -
                          1
                        
                        )
                      
                      n
                    
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
              
              ]
            
          
          ,
        
      
    
    
      
        (
        51
        )
      
    
  




Multiplying Voλo,2nVo−1 by t(p) for p=1, 2 or 3 results in a vector with all zero elements for all n≧1. Therefore, for all n≧1 and p=1, 2 or 3, Aont(p)=Voλo,1nVo−1t(p). By inspection, ζo,1n converges to




  
    
      
        
          
            Λ
            
              o
              ,
              3
            
          
          =
          
            [
            
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
            
            ]
          
        
        ,
      
    
    
      
        (
        52
        )
      
    
  




The vector given by Voλo,3Vo−1t(p) is equal to bp1, where bp=0, 1 and 0 for p=1, 2 and 3 respectively. Replacing Aen,Ve, λe,1, and Ve−1 in (49) with Aon,Vo, λo,3, and Vo−1 respectively shows that ∥Aont(p)−bp1∥ converges exponentially to bp1. Therefore the state transition matrices given by (42) satisfy the conditions of Theorem 1 for ht=3.
Using the decomposition in (46) and (47) and the sequence transition matrices given by (44), it can be shown by direct computation that AonSes(p), AonSos(p), AenSes(p) and AenSos(p) converges to cp1, where cp=0, 1.5, 0, 6, and 0 for p=1, 2, 3, 4 and 5 respectively. Furthermore, the convergence of each vector at index n can be bounded using (49), replacing ∥t(p)∥ alternately with ∥Ses(p)∥ and ∥Sos(p)∥, which implies that the convergence of AonSes(p), AonSos(p), AenSes(p) and AenSos(p) are exponential. Therefore, the matrices A., Ao, Se, and So given in (42) and (44) also satisfy the conditions of Theorem 2 for hs=5.
Proof of Lemmas 1 and 2
Lemma 1: Suppose the conditions of Theorem 1 are satisfied. Then there exists a constant Ctp, positive constants D1, D2, and a constant 0<α<1 such that for n1≠n2 

|E[tp[n1]tp[n2]−Ctp]|≦Dtα|n2−n1|+D2αn1  (53)

Proof of Lemma 1: To establish (54), it suffices to assume that n2>n1. Using (5), E[tp[n2]tp[n1]] can be expressed as





  
    
      
        
          E
          ⁡
          
            [
            
              
                
                  t
                  p
                
                ⁡
                
                  [
                  
                    n
                    2
                  
                  ]
                
              
              ⁢
              
                
                  t
                  p
                
                ⁡
                
                  [
                  
                    n
                    1
                  
                  ]
                
              
            
            ]
          
        
        =
        
          
            ∑
            
              
                c
                1
              
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            ...
            ⁢
            
              
            
            ⁢
            
              
                ∑
                
                  
                    c
                    p
                  
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  ∑
                  
                    
                      d
                      1
                    
                    =
                    0
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  ...
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      ∑
                      
                        
                          d
                          p
                        
                        =
                        0
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        2
                        
                          
                            c
                            1
                          
                          +
                          ...
                          +
                          
                            c
                            p
                          
                          +
                          
                            d
                            1
                          
                          +
                          ...
                          +
                          
                            d
                            p
                          
                        
                      
                      ⁢
                      
                        
                          E
                          ⁡
                          
                            [
                            
                              
                                ∏
                                
                                  i
                                  =
                                  1
                                
                                p
                              
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  
                                    t
                                    
                                      c
                                      i
                                    
                                  
                                  ⁡
                                  
                                    [
                                    
                                      n
                                      2
                                    
                                    ]
                                  
                                
                                ⁢
                                
                                  
                                    ∏
                                    
                                      j
                                      =
                                      1
                                    
                                    p
                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    
                                      t
                                      
                                        d
                                        j
                                      
                                    
                                    ⁡
                                    
                                      [
                                      
                                        n
                                        1
                                      
                                      ]
                                    
                                  
                                
                              
                            
                            ]
                          
                        
                        .
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        54
        )
      
    
  




It is seen that the above expression is a finite sum of terms of the form




  
    
      
        
          
            Q
            ⁡
            
              (
              
                
                  n
                  1
                
                ,
                
                  n
                  2
                
              
              )
            
          
          =
          
            E
            ⁡
            
              [
              
                
                  ∏
                  
                    j
                    =
                    0
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    
                      
                        t
                        j
                        
                          p
                          j
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          2
                        
                        ]
                      
                    
                    ⁢
                    
                      
                        t
                        j
                        
                          q
                          j
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          1
                        
                        ]
                      
                    
                  
                  )
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        55
        )
      
    
  




where pj and qj are positive integers less than or equal to p. It thus suffices to establish a bound for Q(n1, n2) of the form

|Q(n1,n2)−C3|≦C1αn2 . . . n1+C2αn1.  (56)

The right side of (55) is computed by conditional expectation as follows




  
    
      
        
          Q
          ⁡
          
            (
            
              
                n
                1
              
              ,
              
                n
                2
              
            
            )
          
        
        =
        
          E
          ⁢
          
            
              {
              
                
                  ∏
                  
                    i
                    =
                    0
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                    
                      t
                      i
                      
                        p
                        i
                      
                    
                    ⁢
                    
                      
                    
                    [
                    
                      n
                      1
                    
                    ]
                  
                  ⁢
                  
                    E
                    (
                    
                      
                        
                          
                            ∏
                            
                              j
                              =
                              0
                            
                            
                              K
                              -
                              1
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              t
                              j
                              
                                q
                                j
                              
                            
                            ⁡
                            
                              [
                              
                                n
                                2
                              
                              ]
                            
                          
                        
                        ❘
                        
                          
                            t
                            d
                          
                          ⁡
                          
                            [
                            
                              n
                              1
                            
                            ]
                          
                        
                      
                      ,
                      
                        
                          o
                          d
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      ,
                      
                        d
                        =
                        0
                      
                      ,
                      1
                      ,
                      ...
                      ⁢
                      
                        
                      
                      ,
                      
                        K
                        -
                        1
                      
                      ,
                      
                        n
                        =
                        
                          
                            n
                            1
                          
                          +
                          1
                        
                      
                      ,
                      ...
                      ⁢
                      
                        
                      
                      ,
                      
                        n
                        2
                      
                    
                    )
                  
                
              
              }
            
            .
          
        
      
    
    
      
        (
        57
        )
      
    
  




Substituting (19) into the inner conditional expectation of (57) yields




  
    
      
        
          Q
          ⁡
          
            (
            
              
                n
                1
              
              ,
              
                n
                2
              
            
            )
          
        
        =
        
          E
          ⁢
          
            {
            
              
                ∏
                
                  j
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                (
                
                  
                    
                      t
                      j
                      
                        p
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                  ⁢
                  
                    E
                    ⁡
                    
                      [
                      
                        
                          
                            
                              t
                              j
                              
                                q
                                j
                              
                            
                            ⁡
                            
                              [
                              
                                n
                                2
                              
                              ]
                            
                          
                          ❘
                          
                            
                              t
                              j
                            
                            ⁡
                            
                              [
                              
                                n
                                1
                              
                              ]
                            
                          
                        
                        ,
                        
                          
                            o
                            j
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        ,
                        
                          n
                          =
                          
                            
                              n
                              1
                            
                            +
                            1
                          
                        
                        ,
                        ...
                        ⁢
                        
                          
                        
                        ,
                        
                          n
                          2
                        
                      
                      ]
                    
                  
                
                )
              
            
            }
          
        
      
    
    
      
        (
        58
        )
      
    
  




Since {td[n], n=0, 1, . . . } is a Markov process for any given parity sequence, {od[n]=od, n, n=0, 1, . . . } where od,nε{0,1}, it follows from (20) and (21) that the m-step state transition matrix corresponding to td[n] from time n to time n+m can be written as




  
    
      
        
          
            
              A
              d
            
            ⁡
            
              [
              
                n
                ,
                m
              
              ]
            
          
          =
          
            
              ∏
              
                k
                =
                
                  n
                  +
                  1
                
              
              
                n
                +
                m
              
            
            ⁢
            
              
            
            ⁢
            
              [
              
                
                  
                    A
                    o
                  
                  ⁢
                  
                    o
                    
                      d
                      ,
                      k
                    
                  
                
                +
                
                  
                    A
                    e
                  
                  ⁡
                  
                    (
                    
                      1
                      -
                      
                        o
                        
                          d
                          ,
                          k
                        
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        59
        )
      
    
  




where Ad[n, m] is an N×N matrix with elements of the form

P{td[n+m]=Ti|td[n]=Ti,od[n+1]=od,n+1, od[n+2]=od,n+2, . . . , od[n+m]=od,n+m}.  (60)

Since od,n is either 1 or 0 for each n, (29) can be used to write (59) as




  
    
      
        
          
            
              A
              d
            
            ⁡
            
              [
              
                n
                ,
                m
              
              ]
            
          
          =
          
            
              
                A
                e
                
                  y
                  m
                
              
              ⁢
              
                A
                o
                
                  m
                  -
                  
                    y
                    m
                  
                
              
            
            =
            
              
                A
                o
                
                  m
                  -
                  
                    y
                    m
                  
                
              
              ⁢
              
                A
                e
                
                  y
                  m
                
              
            
          
        
        ,
        
          

        
        ⁢
        
          
            where
            ⁢
            
              
            
            ⁢
            
              y
              m
            
          
          =
          
            
              ∑
              
                k
                =
                
                  n
                  +
                  1
                
              
              
                n
                +
                m
              
            
            ⁢
            
              
            
            ⁢
            
              
                o
                
                  d
                  ,
                  k
                
              
              .
            
          
        
      
    
    
      
        (
        61
        )
      
    
  




By definition, ym≧m/2 or m−ym≧m/2 depending on the given parity sequence. It follows from the exponential convergence of (30) that there exists positive numbers Cp,e and Cp,o positive numbers αp,e and αp,o and less than unity such that each element of

Aeymt(p)−bp1  (62)

is less than Cp,eαp,om/2 for ym≧m/2, and each element of

Aom−ymt(p)−bp1  (63)

is less than Cp,oαp,om/2 for m−ym≧m/2.
The matrices Aom−ym and Aeym are stochastic matrices, so Aom−ym1=1, Aeym1=1 and

Aom−ym(Aeymt(p)−bp1)=Aom−ymAeymt(p)−bp1,  (64)

Aeym(Aom−ymt(p)−bp1)=AeymAom−ymt(p)−bp1,  (65)

Since the elements of the vectors in (62) and (63) are exponentially bounded, the same must be true for the vectors in (64) and (65). From (61) it follows that the right side of either (64) or (65) is equal to

Ad[n,m]t(p)−bp1.  (66)

Therefore, in general each element of (66) has a magnitude less than Cαm/2 where C=max{Cp,e, Cp,o} and α=max {αp,e, αp,o}, which implies that

E[tdp[n+m]|td[n],od[n+j]=od,n+j, j=1, . . . , m]→bp  (67)

as m→∞ uniformly in n where the convergence is also exponential. This result is independent of the given deterministic sequence {od,n, n=0, 1, . . . }, so it implies that

E[tdp[n+m]|td[n],od[n+j], j−1, . . . , m]→bp  (68)

almost surely as m→∞ uniformly in n where the convergence is also exponential.
Thus, the inner conditional expectation in (58) converges exponentially to brj as n2−n1→∞ with probability one so that




  
    
      
        
          Q
          ⁡
          
            (
            
              
                n
                1
              
              ,
              
                n
                2
              
            
            )
          
        
        →
        
          
            ∏
            
              j
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            
              b
              
                q
                j
              
            
            ⁢
            E
            ⁢
            
              
                {
                
                  
                    ∏
                    
                      i
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      t
                      i
                      
                        p
                        i
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                
                }
              
              .
            
          
        
      
    
    
      
        (
        69
        )
      
    
  




More precisely, the exponential convergence of (69) implies that for every n2>n1 

|E[tjqj[n2]tj[n1],oj[n],n=n1+1, . . . , n2]bqj|≦C(qj)αn2−n1.  (70)

with probability one where C(qi) is a constant that depends on qj. For every n2>n1




  
    
      
        
          
            
            
              
                Q
                ⁡
                
                  (
                  
                    
                      n
                      1
                    
                    ,
                    
                      n
                      2
                    
                  
                  )
                
              
              -
              
                
                  ∏
                  
                    j
                    =
                    0
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    b
                    
                      q
                      j
                    
                  
                  ⁢
                  E
                  ⁢
                  
                    {
                    
                      
                        ∏
                        
                          i
                          =
                          0
                        
                        
                          K
                          -
                          1
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          t
                          i
                          
                            p
                            i
                          
                        
                        ⁡
                        
                          [
                          
                            n
                            1
                          
                          ]
                        
                      
                    
                    }
                  
                
              
            
            
          
          ≤
          
            E
            ⁢
            
              {
              
                
                  ∏
                  
                    j
                    =
                    0
                  
                  
                    K
                    -
                    1
                  
                
                ⁢
                
                  
                    
                      
                      
                        
                          t
                          j
                        
                        ⁡
                        
                          [
                          
                            n
                            1
                          
                          ]
                        
                      
                      
                    
                    
                      p
                      j
                    
                  
                  ⁢
                  
                    
                    
                      
                        E
                        ⁡
                        
                          [
                          
                            
                              
                                
                                  t
                                  j
                                  
                                    q
                                    j
                                  
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    2
                                  
                                  ]
                                
                              
                              ❘
                              
                                
                                  t
                                  j
                                
                                ⁡
                                
                                  [
                                  
                                    n
                                    1
                                  
                                  ]
                                
                              
                            
                            ,
                            
                              
                                o
                                j
                              
                              ⁡
                              
                                [
                                n
                                ]
                              
                            
                            ,
                            
                              n
                              =
                              
                                
                                  n
                                  1
                                
                                +
                                1
                              
                            
                            ,
                            ...
                            ⁢
                            
                              
                            
                            ,
                            
                              n
                              2
                            
                          
                          ]
                        
                      
                      -
                      
                        b
                        
                          q
                          j
                        
                      
                    
                    
                  
                
              
              }
            
          
          ≤
          
            
              ∏
              
                j
                =
                0
              
              
                K
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              
                C
                ⁡
                
                  (
                  
                    q
                    j
                  
                  )
                
              
              ⁢
              
                B
                
                  p
                  j
                
              
              ⁢
              
                α
                
                  
                    n
                    2
                  
                  -
                  
                    n
                    1
                  
                
              
            
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            C
            1
          
          ⁢
          
            α
            
              
                n
                2
              
              -
              
                n
                1
              
            
          
        
      
    
    
      
        (
        71
        )
      
    
  




where B is given from Property 2. By similar reasoning, it can be established that




  
    
      
        
          
          
            
              E
              ⁢
              
                {
                
                  
                    ∏
                    
                      j
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      t
                      j
                      
                        q
                        j
                      
                    
                    ⁡
                    
                      [
                      
                        n
                        1
                      
                      ]
                    
                  
                
                }
              
            
            -
            
              
                ∏
                
                  j
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                b
                
                  q
                  j
                
              
            
          
          
        
        ≤
        
          
            C
            2
          
          ⁢
          
            α
            
              n
              1
            
          
        
      
    
    
      
        (
        72
        )
      
    
  




Hence, the above two bounds imply there exist positive constants C1 and C2 such that for all n2>n1




  
    
      
        
          
          
            
              Q
              ⁡
              
                (
                
                  
                    n
                    1
                  
                  ,
                  
                    n
                    2
                  
                
                )
              
            
            -
            
              
                ∏
                
                  i
                  =
                  0
                
                
                  K
                  -
                  1
                
              
              ⁢
              
                
                  b
                  
                    p
                    i
                  
                
                ⁢
                
                  
                    ∏
                    
                      j
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    b
                    
                      q
                      j
                    
                  
                
              
            
          
          
        
        ≤
        
          
            
            
              
                Q
                ⁡
                
                  (
                  
                    
                      n
                      1
                    
                    ,
                    
                      n
                      2
                    
                  
                  )
                
              
              -
              
                E
                ⁢
                
                  {
                  
                    
                      ∏
                      
                        i
                        =
                        0
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        t
                        i
                        
                          p
                          i
                        
                      
                      ⁡
                      
                        [
                        
                          n
                          1
                        
                        ]
                      
                    
                  
                  }
                
                ⁢
                
                  
                    ∏
                    
                      j
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    b
                    
                      q
                      j
                    
                  
                
              
            
            
          
          +
          
            
              
              
                
                  E
                  ⁢
                  
                    {
                    
                      
                        ∏
                        
                          i
                          =
                          0
                        
                        
                          K
                          -
                          1
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          t
                          i
                          
                            p
                            i
                          
                        
                        ⁡
                        
                          [
                          
                            n
                            1
                          
                          ]
                        
                      
                    
                    }
                  
                  ⁢
                  
                    
                      ∏
                      
                        j
                        =
                        0
                      
                      
                        K
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      b
                      
                        
                          q
                          j
                        
                        ⁢
                        
                          
                        
                      
                    
                  
                
                -
                
                  
                    ∏
                    
                      i
                      =
                      0
                    
                    
                      K
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      b
                      
                        p
                        i
                      
                    
                    ⁢
                    
                      
                        ∏
                        
                          j
                          =
                          0
                        
                        
                          K
                          -
                          1
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        b
                        
                          q
                          j
                        
                      
                    
                  
                
              
              
            
            .
          
        
        ≤
        
          
            
              C
              1
            
            ⁢
            
              α
              
                
                  n
                  2
                
                -
                
                  n
                  1
                
              
            
          
          +
          
            
              C
              2
            
            ⁢
            
              
                α
                
                  n
                  1
                
              
              .
            
          
        
      
    
    
      
        (
        73
        )
      
    
  




Consequently, there exists a constant C3 such that

|Q(n1,n2)−C3|≦C1αn2−n1+C2αn1  (74)

which is of the required form.
Lemma 2: Suppose the conditions of Theorem 2 are satisfied. Then there exists a constant Csp, positive constants E1, E2, and a constant 0<β<1 such that for n1≠n2 

|E[sp[n1]sp[n2]−Csp]|≦E1β|n2−n1|+E2βn1  (75)

Proof of Lemma 2: The proof is similar to that of Lemma 1, so only the non-trivial differences with respect to the proof of Lemma 1 are presented.
Similarly to the proof of Lemma 1, it is necessary to show that

E[sdp[n+m]|td[n],od[n+j],j=1, . . . ,m]→cp  (76)

almost surely as m→∞ uniformly in n where the convergence is also exponential. With this result and sd[n], cp, and (24) playing the roles of td[n], bp, and (19) in the proof of Lemma 1, respectively, the proof of Lemma 2 is almost identical that of Lemma 1. Therefore, it is sufficient to prove (76).
Since the random variables td[n−1] and od[n] are statistically independent, for any given parity sequence, {od[n]=od,n, n=0, 1, . . . } where od,nε{0,1}, it follows from (25), (26), and (60) that

Sd[n,m+1]=Ad[n,m][Sood,n+m+1+Se(1−od,n+m+1)]  (77)

where Sd[n, m+1] is an N×N′ matrix with elements of the form

P{sd[n+m+1]=Sj|td[n]=Ti,od[n+1]=od,n+1, . . . , od[n+m+1]=od,n+m+1},  (78)

where i is the row index and j is the column index. By similar reasoning to that used in the proof of Lemma 1, (37) and (38) together imply that there exists a positive number D and a positive number β less than unity such that each element of the vector

Sd[n,m+1]s(p)−cp1,  (79)

has a magnitude less than D·βm/2. Thus, (79) implies that

E[sdp[n+m]|td[n],od[n+j]=od,n+j, j=1, . . . , m]→cp  (80)

as m→∞ uniformly in n where the convergence is also exponential. This result is independent of the given deterministic sequence {od,n, n=0, 1, . . . }, so it implies that (76) holds almost surely as m→∞ uniformly in n where the convergence is also exponential.
While specific embodiments of the present invention have been shown and described, it should be understood that other modifications, substitutions and alternatives are apparent to one of ordinary skill in the art. Such modifications, substitutions and alternatives can be made without departing from the spirit and scope of the invention, which should be determined from the appended claims.
Various features of the invention are set forth in the appended claims.

## Claims

1. A successive requantizer device comprising:
a plurality of quantization stages that each accept an input sequence and quantize the input sequence by a predetermined number of bits; wherein
each quantization stage generates a quantization sequence sd[n], with the property that xd[n]+sd[n] is an even number for each n, where xd[n] is the quantization stage's input sequence; and
each quantization stage adds sd[n] to xd[n].

2. The device of claim 1, wherein each quantization stage discards a predetermined number of least significant bits to implement the quantization.

3. The device of claim 1, wherein each quantization stage simultaneously divides its input by 2b and quantizes the result by b bits every sample period

4. The device of claim 3, wherein each quantization stage simultaneously halves its input and quantizes the result by one bit every sample period.

5. The device of claim 1, wherein numbers within the successive requantizer device are integers with a two's-compliment binary number representation at each time n, and at each quantization stage sd[n] is chosen such that xd[n]+sd[n] does not exceed the range of a (K−d)-bit two's complement integer, and the parity of sd[n] is the same as that of xd[n], where K is determined by the number of quantization stages, the number of bits quantized per stage, and the logic which generates sd[n].

6. The device of claim 1, wherein that the running sum of each sd[n] sequence, i.e.,




  
    
      
        t
        d
      
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        ∑
        
          k
          =
          0
        
        n
      
      ⁢
      
        
      
      ⁢
      
        
          s
          d
        
        ⁡
        
          [
          k
          ]
        
      
    
  
  ,



is bounded for all n, and each sd[n] has a smooth power spectral density that increases monotonically with frequency.

7. The device of claim 6, wherein td[n] is a discrete-valued Markov random sequence conditioned on the parity of xd[n].

8. The device of claim 6, wherein td[n] is a random process whose autocorrelation function converges to a constant as its time spread increases.

9. The device of claim 6, wherein each quantization stage calculates sd[n] as a function the running sum of td[n] in addition to td[n], an independent random sequence, and the parity of xd[n].

10. The device of claim 6, wherein each quantization stage calculates sd[n] as a function of the previous value of td[n], the parity of the current value of xd[n], and the current value of an independent random sequence.

11. The device of claim 1, wherein each quantization stage implements




  
    
      s
      d
    
    ⁡
    
      [
      n
      ]
    
  
  =
  
    {
    
      
        
          
            0
            ,
          
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              
                
                  x
                  d
                
                ⁡
                
                  [
                  n
                  ]
                
              
            
            =
            even
          
        
      
      
        
          
            
              
                p
                d
              
              ⁡
              
                [
                n
                ]
              
            
            ,
          
        
        
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                
                  
                    x
                    d
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
              
              =
              
                
                  odd
                  ⁢
                  
                    
                  
                  ⁢
                  and
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                
                =
                0
              
            
            ,
          
        
      
      
        
          
            1
            ,
          
        
        
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                
                  
                    x
                    d
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
              
              =
              
                
                  odd
                  ⁢
                  
                    
                  
                  ⁢
                  and
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                
                =
                
                  -
                  1
                
              
            
            ,
          
        
      
      
        
          
            
              -
              1
            
            ,
          
        
        
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                
                  
                    x
                    d
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
              
              =
              
                
                  odd
                  ⁢
                  
                    
                  
                  ⁢
                  and
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      t
                      d
                    
                    ⁡
                    
                      [
                      
                        n
                        -
                        1
                      
                      ]
                    
                  
                
                =
                1
              
            
            ,
          
        
      
    
  



can be used, where pd[n] is an independent random sequence that takes on the values 1 and −1 with equal probability.

12. The device of claim 1, wherein that the running sums of each td,i[n] sequence, i.e.,




  
    
      
        t
        
          d
          ,
          i
        
      
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        ∑
        
          k
          =
          0
        
        n
      
      ⁢
      
        
      
      ⁢
      
        
          t
          
            d
            ,
            
              i
              -
              1
            
          
        
        ⁡
        
          [
          k
          ]
        
      
    
  
  ,
  
    
      
        t
        
          d
          ,
          1
        
      
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        ∑
        
          k
          =
          0
        
        n
      
      ⁢
      
        
      
      ⁢
      
        
          t
          d
        
        ⁡
        
          [
          n
          ]
        
      
    
  



are bounded for all n, and each td,i[n] has a smooth power spectral density that increases monotonically with frequency.

13. A fractional-N PLL device, comprising:
a phase lock loop generating an output frequency from a voltage controlled oscillator based upon a low frequency reference voltage; and
a successive requantizer according to claim 1 for providing a sequence of integers to control a divider in the phase locked loop to settle to a desired fractional value.

14. The fractional-N PLL device of claim 12, further comprising an adaptive phase noise cancellation path.

15. A successive requantizer device comprising:
a plurality of quantization stages that each accept an input sequence and quantize the input sequence by a predetermined number of bits; wherein
each quantization stage adds a quantization sequence to the quantization stage's input sequence and the quantization sequence is a discrete-valued Markov random sequence conditioned on the parity of the input sequence.

16. A successive requantizer device comprising:
a plurality of quantization stages that each accept an input sequence and quantize the input sequence by a predetermined number of bits; wherein
each quantization stage adds a quantization sequence to the quantization stage's input sequence and the quantization sequence is random process whose autocorrelation function converges to a constant as its time spread increases.