sampling â creating a discrete signal from a continuous process. ¯ downsampling (decimation) .... Frequency Domain An
Sampling Signals Overview:
We use the Fourier transform to understand the discrete sampling
and re-sampling of signals. One key question is when does sampling or re-sampling provide an adequate representation of the original signal?
Terminology:
sampling – creating a discrete signal from a continuous process. downsampling (decimation) – subsampling a discrete signal upsampling – introducing zeros between samples to create a longer signal
aliasing – when sampling or downsampling, two signals have same sampled representation but differ between sample locations. Matlab Tutorials: samplingTutorial.m, upSample.m
320: Sampling Signals
c A.D. Jepson and D.J. Fleet, 2005
Page: 1
Sampling Signals I(x)
continuous signal x
I[n]
●
●
sampled signal
● ●
●
● ●
●
● ●
●
●
●
●
●
●
● ●
n g[m]
downsampling
●
●
● ●
●
I[n]
●
●
●
●
2
g[m]
m f[n]
upsampling
●
●
● ●
●
●
●
● ●
●
320: Sampling Signals
●
●
g[m]
● ●
●
●
●
●
2
f[n]
n
Page: 2
Up-Sampling Consider up-sampling a signal I [n] of length N :
Increase number of samples N by a factor of ns. Step 1. Place ns 1 zeros after every sample of I [n], to form f [n] 0
of length nsN , namely
(
f0 [n] =
I [n=ns ]
for n mod ns
0
otherwise.
= 0;
(1)
Raw Upsampled Signal
Signal
1.5
2
1
1.5 1
0.5 0
0
f
I[n]
0.5
−0.5
0
−0.5
−1
−1
−1.5 −2 0
5
10 n
320: Sampling Signals
15
−1.5 0
5
10
15 n
20
25
30
Page: 3
Up-Sampling (Cont.)
Step 2. Interpolate signal f : f = S f ; for some smoothing kernel S [n]: 0
0
(2)
Here, in order for f [n] to interpolate f0[n], we require that S [0] = 1 and S [jns ] = 0 for nonzero integers j . Sinc Filtered Upsampled Signal (b) 1.5 1
f[n]
0.5 0 −0.5 −1 −1.5 0
5
10
15 n
20
25
30
Many smoothing kernels can be used (see upSample.m).
320: Sampling Signals
Page: 4
Frequency Analysis of Up-Sampling Step 1. Fourier transform of the raw up-sampled signal f0[n]:
F (f [n])[k]
X
Nns
0
=
n=0 N 1
X
1
X
N
i!ks n
f0 [n]e
=
1
s
f0 [jns ]ei!k jns
j =0 s
I [j ]ei!k jns
j =0
Here !ks
2
= Nn k , s
F (f )[k] =
X
N
1
0
so the last line above becomes 2
I [j ]ei N kj
j =0
F (I )[k];
N ns
for
2
k < N2ns :
(3)
Since F (I ) is N -periodic, equation (3) implies that F (f0) consists of ns copies of
F (I ) concatenated together.
Amplitude Spectrum of Raw Upsampled Signal 6
5
5
4
4 |FT|
|FT|
Amplitude Spectrum of I[n] 6
3
3
2
2
1
1
0
−5
0 k
320: Sampling Signals
5
0 −15
−10
−5
0 k
5
10
15
Page: 5
Fourier Analysis of Up-Sampling Step 2 Recall Step 2 is to form f [n]
S
=
f , for some interpolation filter S . 0
However, notice from the inverse Fourier transform that (for N even) I [j ] =
=
1
X
N=2
1
2
I^[k ]ei N kj
N
k= N=2 N=2 ns
X
N ns
1
2 kjn i Nn s s
f^0 [k ]e
=
f [jns ]:
(4)
k= N=2
Here we used f (jns) = I (j ) in the last line. Notice the left term in the last line above is ns times the inverse Fourier transform of B [k ]f^0[k ] where B is the box function, B [k ]
= 1
N=2
for
k
< N=2 and
B [k ] = 0 otherwise. We can therefore evaluate this inverse Fourier
transform at every pixel n, and not just at the interpolation values jns, to construct a possible interpolating function f [n] f [n] = ns
F
1
(B (k )f^0 [k ]): Sinc Filtered Upsampled Signal (b)
Amp. Spec. (Upsampled Sig.(r), Sinc Filter(g), Filtered Sig.(b) 12
1.5 1
10
0.5 f[n]
|FT|
8 6
0
4
−0.5
2
−1
0 −15
(5)
−10
−5
320: Sampling Signals
0 k
5
10
15
−1.5 0
5
10
15 n
20
25
30
Page: 6
Down-Sampling Consider down-sampling a signal I [n] of length N :
Reduce number of samples N by a factor of ns, where ns is a divisor of N .
Define the comb function:
X
(N=ns )
C (n; ns) =
1
Æn;mns
m=0 I [n]
ns ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
ns = 4
●
n
Step 1. Introduce zeros in I [n] at unwanted samples. g0 [n] = C [n; ns ]I [n]:
(6)
Step 2. Downsample signal g : 0
g [m] = g0 [mns ]; for 0
320: Sampling Signals
m < N=ns:
(7)
Page: 7
Frequency Domain Analysis of Down-Sampling Proposition 1. The Fourier transform of the comb function is another comb function:
F (C [n; ns]) = nN C [k; N=ns]:
(8)
s
∧
C(ω) −π
2π ns
ns = 4 π ω
0
Recall the frequency ! and wave number k are related by ! the spacing in the plot above is !s
2
N
2
2
= N k.
So
= Nn = n . s s
Proposition 2. Pointwise product and convolution of Fourier transforms. Suppose f [n] and g [n] are two signals of length N (extended to be N -periodic). Then
F (f [n]g[n])
=
F (f ) F (g) N= 1 X ^
1
N
2
N
1
f [j ] g^[k
j ]:
(9)
j = N=2
where f^ and g^ denote the Fourier transforms of f and g , respectively. The proofs of these two propositions are straight forward applications of the definition of the Fourier transform given in the preceeding notes, and are left as exercises. 320: Sampling Signals
Page: 8
Fourier Analysis of Down-Sampling Step 1 Recall Step 1 is to form g0[n] = C [n; ns]I [n]. By Prop. 1 and 2 above, we have
F (g ) 0
= =
=
F (C [n; ns]I [n]) N 1 C [; N=ns ] I^[] ns N N= X 1 2
ns 1
ns
C [j ; N=ns ]I^[k
j = N=2+1 ns r0
X
I^[k
r= r0 +1
r
N ns
j]
];
(10)
where, due to the periodicity of I^[k ], we can use any integer r0 (eg. r0 = ns =2 for even ns ). ∧
∧
I(ω)
−π
2π ns
g0(ω) 0
π ω
−π
0
ns = 4 π ω
Therefore g^0[k ] consists of the sum of replicas I^[k
rN=ns ] of the
Fourier transform of the original signal I , spaced by wavenumber N=ns or, equivalently, by frequency !s
2
= n . s
Note the Fourier transform g^0 has period 2 , so the contribution sketched above for !
can be shifted 2 to the left.
320: Sampling Signals
Page: 9
Fourier Analysis of Down-Sampling Step 2 In Step 2 we simply drop the samples from g0[n] which were set to zero by the comb function C [n; ns]. That is g [m] = g0 [mns ]; for 0
m < N=ns:
In terms of the Fourier transform, it is easy to show
F (g)[k] = g^[k] = g^ [k]; 0
N=(2ns )
for
Rewriting this in terms of the frequency !s;k
k < N=(2ns): =
2 (N=ns )
k (note g [m] is
a signal of length N=ns ), and the corresponding frequency !k =
(11)
2
= Nk
!s;k ns of the longer signal g0 [n], we have g^[!s;k ] = g^0 [!k ] = g^0 [!s;k =ns ]; for ∧
f(ω)
ns = 4
−π
ωs
0
!s;k < :
(12)
original signal
π ω
∧
g(ω)
downsampled signal
−π
0
π
4π ω
∧
f(ω) −π
320: Sampling Signals
upsampled and filtered signal 0
π ω
Page: 10
Nyquist Sampling Theorem Sampling Theorem: Let f [n] be a band-limited signal such that f^[! ] = 0
for all j! j > !0
for some !0 . Then f [n] is uniquely determined by its samples g [m]
=
f [m ns ] when !s =2 =
where 0
ns
= 2=!0 .
> !0
or equivalently ns
0 f^[k ] = 0
for all j!k j > !0:
Then f (x) is uniquely determined by its samples I [m] = f (m ) when
