 Open Access
 Total Downloads : 203
 Authors : SungWon Park
 Paper ID : IJERTV4IS080209
 Volume & Issue : Volume 04, Issue 08 (August 2015)
 Published (First Online): 11082015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Reconstruction of Spectrum from Nonuniformly Sampled Signals using FFT
SungWon Park,
Senior Member, IEEE Texas A&M UniversityKingsville,
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 highspeed 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 nth 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.

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 highspeed 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 continuoustime 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 discretetime 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 highspeed 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 highspeed 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)

RECONSTRUCTION METHOD USING FFT
The discretetime Fourier transform (DTFT) of a uniformly sampled discretetime 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.

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)

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

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).

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

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)


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.


EXPERIMENTAL RESULT
B(n N, m) for
In matrix form, equation (18) becomes
N n N 1
In [4], an alternative discretetime 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 continuoustime 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.

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
Proposed method 
Method in [4] 

To compute X (k) or X d (k) 
LN log (LN ) for 2 2 FFT 
(LN )2 for alternative DFT 
To build NÃ—N matrix 
N3L or N N log N L if 2 2 FFT is used 
2N (for NÃ—N matrix) + N3 (for inverse matrix) 
To reconstruct spectrum 
N 3 N 2 3 2 L 
N 2 L 
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).

Y. C. Jenq, Digital spectra of nonuniformly sampled signals: Fundamental and highspeed waveform digitizers, IEEE Trans. Instrum. Meas., vol. 37, pp. 245251, June 1988.

Y. C. Jenq, Digital Signal Processing with Interleaved ADC systems, Journal of VLSI Signal Processing 39, pp. 267271, 2005.

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

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

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

P. Vandewalle, L. Sbaiz, J. Wandewalle, and M. Vetterli, Superresolution from unregistered and totally aliased signals using subspace methods, IEEE Trans. Signal Process., vol. 55, no. 7, pp. 36873702, July 2007.

Y. C. Jenq and L. Cheng, Digital spectrum o a nonuniformly sampled twodimensional signal and its reconstruction, IEEE Trans. Instrum. Meas., vol. 54, no. 3, pp. 11801187, June 2005.

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