Reconstruction of Spectrum from Nonuniformly Sampled Signals using FFT

Reconstruction of Spectrum from Nonuniformly Sampled Signals using FFT

Sung-Won Park,

Senior Member, IEEE Texas A&M University-Kingsville,

Kingsville, TX

Abstract In this paper, reconstruction of a spectrum from recurrent nonuniformly sampled signal using FFT for known nonuniform sampling ratios is described. Recurrent nonuniform sampling occurs in a very high-speed waveform digitizing system with interleaved A/D converters. We developed a reconstruction algorithm using FFT by deriving the relationship between the DTFT of a uniformly sampled signal and the DTFT of a nonuniformly sampled signal. A spectrum was reconstructed using the proposed algorithm and the result

each delay is exactly T seconds. However, due to the imperfection of the delays, the actual delay at the n-th converter is given by (n+rn)T where rn are termed the nonuniform sampling ratios and should be zero for uniform sampling. Recurrent nonuniform sampling of a continuous- time signal is shown in Fig. 2 when 3 A/D converters are used.

was compared to one existing algorithm that uses an alternative DTFT. The proposed method performed equally at lower computational complexity.

x(t)

: Uniform sampling : Recurrent nonuniform sampling

Index Terms Recurrent Nonuniform Sampling, Spectrum Reconstruction, FFT.

1. INTRODUCTION

   N this paper, reconstruction of a spectrum from recurrent

   T

   r0T (1+r1)T

   2T

   (2+r2)T

   4T 5T

   3T

   (3+r0)T (4+r1)T (5+r2)T

   t

   6T

   (6+r0)T t

   nonuniform sampling using FFT for known nonuniform sampling ratios is described. Recurrent nonuniform sampling occurs in a very high-speed waveform digitizing system with interleaved A/D converters [1][4].

   A/D
   A/D
   A/D
   A/D

   x(tr0T)

   Fig. 2. Recurrent nonuniform sampling. T is the sampling interval for uniform sampling, rn are the nonuniform sampling ratios.

   There is a periodic nonuniform sampling pattern. In this

   case the period N is 3.

   A continuous-time signal x(t) is nonuniformly sampled at

   delay 1

   (kN n)T rnT (kN n rn )T

   (1)

   delay 2

   x(t(1+r1)T)

   x(t(2+r2)T)

   delay N1

   x(t(N1+rN1)T)

   fs = 1/(NT)

   where k in general goes from to , n ranges from 0 to

   N1, and T is the average sampling interval.

   Memory

   Recurrent nonuniform sampling is described in the literature [1][7]. In particular, an algorithm to reconstruct a spectrum from a nonuniformly sampled signal for known nonuniform sampling ratios is proposed in [4] where an alternative transform is used. The method to estimate nonuniform sampling ratio or sampling time offset is presented in [8]. In this paper, we derived a relationship between the discrete-time Fourier Transform (DTFT) of a uniformly sampled signal and the DTFT of a nonuniformly sampled signal. Our derivation closely followed the one presented in [4]. Using the relationship an algorithm for reconstruction of spectrum using FFT is proposed. The development of the algorithm also followed the one described in [4]. The experiment verified that the proposed method

   Fig. 1. Very high-speed waveform ADC system.

   As shown in Fig. 1, to increase the sampling frequency N A/D converters are used. Sampling frequency of each A/D converter is 1/NT [Hz] and the resulting sampling frequency of the high-speed waveform digitizer is 1/T [Hz]. Ideally

   showed the identical performance at much lower computational complexity compared to the result described in [4].

   The paper is organized as follows. In section 2, a relationship between the DTFT of a uniformly sampled signal and the DTFT of a nonuniformly sampled signal is derived

   )e

   and the new algorithm that can take advantage of FFT is described. In section 3, experimental comparison between the proposed method and the existing one is made in terms of

   By replacing t in equation (8) with () and plugging it into equation (6) one obtains

   performance and computational complexity. Finally, a conclusion is made in section 4.

   X () N 1 1 X () 2

   ( k 2

   j ()ne jrn d (9)

2. RECONSTRUCTION METHOD USING FFT

   The discrete-time Fourier transform (DTFT) of a uniformly sampled discrete-time signal or sequence, x[kN+n] = x(kNT+nT), is

   n0 2 N k N

   Let us assume that a particular frequency 0 is inside the interval [0, 2/N). Using the sifting property equation (9) becomes when N is even

   N 1

   2 2

   N 1

   1 N 1 2

   2

   jk n j 0 k N rn

   X () X (e j ) x[kN n]e j(kN n)

   (2)

   X (0 ) X 0 k e

   N e

   k n0

   N n0

   N 1

   k N

   2

   N

   2 2

   where (= T) is termed the digital frequency (or normalized

   2 1 N 1

   j 0 k N rn

   j kn

   2

   frequency) in radians. Most literature use X(ej) rather than

   =

   e e N

   X 0 k

   (10)

   X() to denote the DTFT. However, we would like to use X() for convenience. The DTFT of the nonuniformly sampled sequence is

   k N N n0 N

   2

   When N is odd, equation (9) becomes

   N 1

   • j(kN n)

   N 1

   X () x[kN n]e

   (3)

   2 N 1

   j k 2 r j 2 kn

   1 0 N n

   2

   k n0

   X (0 )

   e e N

   X 0 k (11)

   where the nonuniformly sampled sequence is expressed as

   k N 1 N n0

   2

   N

   x[kN n] x(kNT nT rnT ) . (4) Using the inverse DTFT formula the DTFT of the

   We would like to continue with the case when N is even. Let us consider the frequency 0 + 2/N. With this frequency equation (9) becomes by the same way as in (10)

   nonuniformly sampled sequence becomes

   N 2

   2 2 2

   2 2

   1 N 1

   j 0 N k N rn

   j kn

   2 2

   X (0

   )

   e e N

   X 0 k

   N 1 1

   j(kN nr )

   j(kN n)

   N N

   2

   N n0

   N N

   X ()

   k n0 2

   X ()e

   n d e

   (5)

   N 2

   k

   1

   2 2

   2 1 N 1

   j 0 (k 1) N rn

   j kn

   2

   =

   e e N

   X 0 (k 1)

   where X() is the DTFT of the uniformly sampled sequence

   k N 1 N n0

   N

   2

   as in (2) except that is replaced by [rad]. By changing the

   N 1

   2

   N 1

   j k 2 r j 2 (k 1)n

   order of the summations and manipulating exponents,

   = 1 e 0 N n e

   X k 2

   (12)

   N

   N N

   0 N

   X () N 1 1

   X ()

   e j ()kN

   j()nr d

   k

   2

   n0

   e

   n (6)

   n0 2 k

   In general, for m = 0 to N1,

   2 2

   A train of unit impulse functions of t with the period P can be

   2

   2 1 N 1

   j 0 k N rn j

   (k m)n

   2

   X ( 0 m

   )

   e e N

   X 0 k

   expressed in terms of its own Fourier series so that

   N k N N n0 2

   N

   (t kP) 1

   jk 2 t

   e P

   (7)

   (13)

   k

   P k

   Equation (13) can be rewritten as

   where (t) is the unit impulse function, and the right hand side of the equation is the expression of the Fourier series.

   N 1

   2 2

   N 1 1

   2

   j k r 2

   0 N n j

   (mk )n

   2

   X (0 m

   )

   e e N

   X 0 k

   By substituting P with 2/N, one obtains

   N k N n0 N

   2

   N

   2

   (t k 2)

   e jtkN

   (14)

   N

   N

   k

   (8)

   k

   Let us define the following.

   N 1

   j k 2 r

   • j 2 mn

   An algorithm to reconstruct the spectrum from the

   1 0 N n

   B(k, m)

   N

   n0

   e e N

   (15)

   nonuniformly sampled signal is as follows.

   1. Compute the DFT, X (k) , of the nonuniformly sampled

      In other words, B(k, m) for m = 0, 1, , N1 is the DFT of the sequence given by

      signal using FFT by padding appropriate number of zeros as necessary. Now the number of the DFT coefficients is LN.

      0 N 0

      1 j k 2 r

      { e ,

      1 j k 2 r

      0 N 1

      e , ,

      1 j k 2 r

      0 N N 1

      e } (16)

   2. Do the following for l = 0, 1, 2, , L1.

      LN

      1. Let 0 = l 2 and compute B(k, m) using DFT as in

         N N N

         where k = N/2, (N/21), , 0, 1, , N/22, N/21.

         Now equation (14) becomes

         N 1

         equation (15).

      2. Form matrix A(l) using equations (19) and (20).

      3. Solve the following for reconstruction of the DFT,

         X , using Gaussian elimination.

         2

         X ( m 2)

         0

         B k, (m k) mod N X k 2

         (17)

         X (l)

         X (l)

         N N 0 N

         k

         X (L l)

         X (L l)

         2

         A(l) X (2L l) X (2L l)

         (21)

         Equation (17) can be rewritten as

         X (N 1)L l

         2 N 1

         2

         X (N 1)L l

         X (0 m N ) An, (m n) mod N X 0 n N

         (18)

   3. The resulting DFT sequence,

   where

   n0

   B(n, m) for 0 n N 1

   2

   A(n, m) 2

   (19)

   X (0), X (1), , X (N 1), X (N), , X (LN 1) is the reconstruction of the spectrum.

3. EXPERIMENTAL RESULT

   B(n N, m) for

   In matrix form, equation (18) becomes

   N n N 1

   In [4], an alternative discrete-time Fourier transform,

   X d () , is defined as follows and the procedure similar to one

   X X (20)

   described in the previous section is used for reconstruction of the spectrum.

   where

   N 1

   X 0

   X 0

   X () x(kNT nT r T )e j(kN nrn )

   d n

   k n0

   (22)

   N

   X 0 2

   X ,

   X 0 (N 2) 2

   X 0 2

   N

   X , and

   X 0 (N 2) 2

   In [4] instead of constructing a new N by N matrix equation for each l as in (21), only one N by N inverse matrix is used in all l. However, FFT cannot be used to compute the alternative DFT and that results in heavy computational

   N N

   N 0 N

   X 0 (N 1) 2 X (N 1) 2

   complexity.

   The following continuous-time signal as in [4] was used for

   A(0, 0)

   A(0,1)

   A(1, N 1)

   A(1, 0)

   A(N 2, 2)

   A(N 2, 3)

   A(N 1,1)

   A(N 1, 2)

   our experiment.

   A

   x(t) sin(2t)

   (23)

   A(0, N 2) A(1, N 3) A(N 2, 0) A(N 1, N 1)

   The average sampling interval T = 0.11 [sec], the number of

   A(0, N 1)

   A(1, N 2)

   A(N 2,1)

   A(N 1, 0)

   A/D converters N = 8, and the number of samples LN = 512

   The reconstruction of X,

   X , can be obtained by

   X 1 X . (21)

   (L = 64) in this experiment. The rn are chosen as follows.

   rn = {0.1, 0.26, 0.12, 0.14, 0.15, 0.22, 0.11, 0.13} (24)

   In practice, instead of finding the inverse matrix and multiplying it to the vector, equation (20) is solved using Gaussian elimination for X.

4. CONCLUSION

0

-10

-20

dB

-30

-40

-50

-60

-70

nonuniform

true spectrum

reconstruction

In this paper, we derived a relationship between the DTFT of a uniformly sampled signal and the DTFT of a nonuniformly sampled signal. Using the relationship an algorithm for reconstruction of a spectrum from the nonuniformly sampled signal using FFT is developed. The experiment verified that the proposed method showed identical performance at much lower computational complexity compared to an existing method.

REFERENCES

-300 -200 -100 0 100 200 300

Fig. 3. Plots of reconstructed, nonuniform, and true spectra.

The plots of reconstructed, nonuniform, and true spectra are shown in Fig. 3 which is identical to the result obtained using the algorithm described in [4]. TABLE 1 shows the number of complex multiplications required for reconstruction.

TABLE 1. Required number of complex multiplications

When L = 64, N = 8 and the number of samples LN = 512, the proposed method needs 21,440 complex multiplications If we use FFT to build N×N matrices while the method of [4] needs 266,768 multiplications. The complexity ratio is about 12.4. The ratio will increase as the number of samples increases (or L increases).

1. Y. C. Jenq, Digital spectra of nonuniformly sampled signals: Fundamental and high-speed waveform digitizers, IEEE Trans. Instrum. Meas., vol. 37, pp. 245-251, June 1988.

2. Y. C. Jenq, Digital Signal Processing with Interleaved ADC systems, Journal of VLSI Signal Processing 39, pp. 267-271, 2005.

3. D. Wei, Q. Ran, and Y. Li, Reconstruction of band-limited signals from multichannel and periodic nonuniform samples in the linear canonical transform domain, Opt. Commu., vol. 284, no.19, pp. 4307-4315, September 2011.

4. Y. C. Jenq, Perfect reconstruction of digital spectrum from nonuniformly sampled signals, IEEE Trans. Instrum. Meas., vol. 46, pp. 649-652, June 1997.

5. J. L. Yen, On nonuniform sampling of bandwidth-limited signals, IRE Trans. Circuit Theory, vol. 3, pp. 251257, December 1956.

6. P. Vandewalle, L. Sbaiz, J. Wandewalle, and M. Vetterli, Super-resolution from unregistered and totally aliased signals using subspace methods, IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3687-3702, July 2007.

7. Y. C. Jenq and L. Cheng, Digital spectrum o a nonuniformly sampled two-dimensional signal and its reconstruction, IEEE Trans. Instrum. Meas., vol. 54, no. 3, pp. 1180-1187, June 2005.

8. Y. C. Jenq, Digital Spectra of Nonuniformly Sampled Signals: A Robust Sampling Time Offset Estimation Algorithm for Ultra High-Speed Waveform Digitizers Using Interleaving, IEEE Trans. Instrum. Meas., vol. 39, no. 1, pp. 71-75, February 1990.