MIT OpenCourseWare http://ocw.mit.edu 2.161 Signal Processing: Continuous and Discrete Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.1 MASSACHUSETTS INSTITUTE OF TECHNOLOGY DEPARTMENT OF MECHANICAL ENGINEERING 2.161 Signal Processing – Continuous and Discrete Data Resampling: Interpolation (Up-sampling) and Decimation (Down-sampling) 1 Up-Sampling (Interpolation) by an Integer Factor Consider a data set {fn} of length N, where fn = f(nΔT ), n = 0 . . . N − 1 and ΔT is the sampling interval. The task is to resample the data at a higher rate so as to create a new data set {fˆ n}. of length KN, representing samples of the same continuous waveform f(t), sampled at intervals ΔT/K. Figure 1(a) shows a cosinusoidal data set with N = 8 samples, and Fig. 1(b) shows the 1 1 (a) original data set 0.5 2 4 6 8 (8 samples) 0.5 0 0 −0.5 −0.5 −1 −1 10 20 30 (b) interpolated data set (32 samples) Figure 1: (a) a data set with N = 8 samples, and (b) an interpolated data set (K = 4) derived from (a). same data set interpolated by a factor K = 4. 1.1 Frequency Domain Method This method is useful for a finite-sized data record. Consider the DFTs {Fm} and {Fˆ m} of a pair of sample sets {fn} and {fˆ n}, both recorded from f(t) from 0 ≤ t < T , but with sampling intervals ΔT and ΔT/K respectively. Let N and KN be the corresponding sample sizes. It is assumed that ΔT has been chosen to satisfy the Nyquist criterion: 1D. Rowell August 18, 2008 1Let F (jΩ) = F {f(t)} be the Fourier transform of f(t), and let f(t) be sampled at intervals • ΔT to produce f∗(t). Then 1 ∞ � 2πn�� F ∗(jΩ) = � F j �Ω − (1)ΔT ΔT n=0 is periodic with period 2π/ΔT , and consists of scaled and shifted replicas of F (jΩ). Let the total sampling interval be T to produce N = T /ΔT samples. If the same waveform f(t) is sampled at intervals ΔT/K to produce fˆ∗(t) the period of its • Fourier transform Fˆ∗(jΩ) is 2πK/ΔT and ˆ K ∞ � 2πKn�� F ∗(jΩ) = � F j �Ω − (2)ΔT ΔT n=0 which differs only by a scale factor, and an increase in the period. Let the total sampling period be T as above, to generate KN samples. We consider the DFTs to be sampled representations of a single period of F ∗(jΩ) and Fˆ∗(jΩ).• The equivalent line spacing in the DFT depents only on the total duration of the sample set T , and is ΔΩ = 2π/T in each case: � � 2πm��Fm = F ∗ j , m = 0, 1, . . . N − 1 T Fˆ m = Fˆ∗ �j � 2πm�� , m = 0, 1, . . . KN − 1. T ˆFrom Eqs. (1) and (2) the two DFTs {Fm} and �Fm � are related: ⎧ KFm m = 0, 1, . . . , N/2 − 1⎪Fˆ m = ⎨ 0 m = N/2, . . . , NK − N/2 − 1 ⎪ KFm−(K−1)N m = N K − N/2, . . . , KN − 1⎩ The effect of increasing N (or decreasing ΔT ) in the sample set, while maintaining T = NΔT• constant, is to increase the length of the DFT by raising the effective Nyquist frequency ΩN . π Nπ ΩN = = ΔT T Figure 2 demonstrates these effects by schematically, by comparing the DFT of (a) a data set of length N derived by sampling at intervals ΔT , and (b) a data set of length 2N resulting from sampling at intervals ΔT/2. The low frequency region of both spectra are similar, except for a scale factor, and the primary difference lies in the “high frequency” region, centered around the Nyquist frequency, in which all data points are zero. The above leads to an algorithm for the interpolation of additional points into a data set, by a constant factor K: 1. Take the DFT of the original data set to create {Fm} of length N. 2. Insert (K − 1)N zeros into the center of the DFT to create a length KN array. 3. Take the IDFT of the expanded array, and scale the sequence by a factor K. Appendix A describes a simple MATLAB function to interpolate a real data set using this method. 20 N / 2FN3 N / 22 Nm- N / 2m0FN2 NmmN y q u i s t f r e q u e n c yN y q u i s t f r e q u e n c yN u m b e r o f s a m p l e s : NS a m p l i n g i n t e r v a l : DTN u m b e r o f s a m p l e s : 2 NS a m p l i n g i n t e r v a l : DT / 2( a )( b )Figure 2: Envelopes of (a) the DFT of a sample set with N samples, and (b) the DFT of the same waveform with 2N samples. 1.2 A Time-Domain Method We now examine an interpolation scheme that may implemented in real-time using time domain processing alone. As before, assume that the process f(t) is sampled at intervals ΔT , generating a sequence {fn} = {f(nΔT )}. Now assume that K − 1 zeros are inserted between the samples to form a sequence {fˆ k} at intervals ΔT/K. This is illustrated in Fig. 3, where a data record with N = 8 samples has been expanded by a factor K = 3 to form a new data record of length N = 24 formed by inserting two zero samples between each of the original data points. We now examine the effect of inserting K − 1 samples with amplitude 0 after each sample. The DFT of the original data set is N−1 fne−j 2πmn Fm = � N , m = 0 . . . N − 1 n=0 and for the extended data set {fˆ n}, n = 0 . . . KN − 1 KN −1 ne−j 2πmn Fˆ m = � fˆ KN , m = 0 . . . KN − 1 n=0 However, only the original N samples contribute to the sum, so that we can write N−1 Kke−j 2πmk Fˆ m = � fˆ N k=0 = Fm, m = 0 . . . KN − 1 since fˆ Kk = fk. We note that {Fm} is periodic with period N , and {Fˆ m} is periodic with period KN, so that {Fˆ m} will contain K repetitions of {Fm}. This is illustrated in Fig. 4, which shows 30 1 2 3 n f n 0 1 2 3 4 5 6 7 (a) Initial data set, N=8 0 5 10 15 20 0 1 2 3 n (b) Data set with two samples interpolated between samples, N=24 n f …