In this section we consider the sampling problem where, unless there is
sufficient redundancy, there will be a loss of information caused by removing
data in the time domain and aliasing in the frequency domain.

The sampling process or the down sampling process creates a new shorter or
compressed signal by keeping every
M
t
h
M
t
h
sample of the original sequence. This process is best seen as done in two
steps. The first is to mask off the terms to be removed by setting
M
−
1
M
−
1
terms to zero in each
length-
M
M
block (multiply
x
(
n
)
x
(
n
)
by
⨿
M
(
n
)
⨿
M
(
n
)
),
then that sequence is compressed or shortened by removing the
M
−
1
M
−
1
zeroed terms.

We will now calculate the length
L
=
N
/
M
L
=
N
/
M
DFT of a sequence that was obtained by sampling every
M
M
terms of an original
length-
N
N
sequence
x
(
n
)
x
(
n
)
.
We will use the orthogonal properties of the basis vectors of the DFT which
says:

∑
n
=
0
M
−
1
e
−
j
2
π
n
l
/
M
=
{
M
if
n
is an integer multiple of
M
0
otherwise
∑
n
=
0
M
−
1
e
−
j
2
π
n
l
/
M
=
{
M
if
n
is an integer multiple of
M
0
otherwise

(1)
We now calculate the DFT of the down--sampled signal.

C
d
(
k
)
=
∑
m
=
0
L
−
1
x
(
M
m
)
W
L
m
k
C
d
(
k
)
=
∑
m
=
0
L
−
1
x
(
M
m
)
W
L
m
k

(2)
where

N
=
L
M
N
=
L
M
and

k
=
0
,
1
,
⋯
,
L
−
1
k
=
0
,
1
,
⋯
,
L
−
1
.
This done by masking

x
(
n
)
x
(
n
)
.

C
d
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
⨿
M
(
n
)
W
N
n
k
C
d
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
⨿
M
(
n
)
W
N
n
k
=
∑
n
=
0
N
−
1
x
(
n
)
[
1
M
∑
l
=
0
M
−
1
e
−
j
2
π
n
l
/
M
]
e
−
j
2
π
n
k
/
N
=
∑
n
=
0
N
−
1
x
(
n
)
[
1
M
∑
l
=
0
M
−
1
e
−
j
2
π
n
l
/
M
]
e
−
j
2
π
n
k
/
N
=
1
M
∑
l
=
0
M
−
1
∑
n
=
0
N
−
1
x
(
n
)
e
j
2
π
(
k
+
L
l
)
n
/
N
=
1
M
∑
l
=
0
M
−
1
∑
n
=
0
N
−
1
x
(
n
)
e
j
2
π
(
k
+
L
l
)
n
/
N
=
1
M
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
=
1
M
∑
l
=
0
M
−
1
C
(
k
+
L
l
)

(3)
The compression or removal of the masked terms is achieved in the frequency
domain by using

k
=
0
,
1
,
⋯
,
L
−
1
k
=
0
,
1
,
⋯
,
L
−
1
.
This is a
length-

L
L
DFT of the samples of

x
(
n
)
x
(
n
)
which is the sum of

M
M
shifted versions of

C
(
k
)
C
(
k
)
,
the DFT of

x
(
n
)
x
(
n
)
.
Unless

C
(
k
)
C
(
k
)
is sufficiently bandlimited, this causes aliasing and

x
(
n
)
x
(
n
)
is not unrecoverable.

It is instructive to consider an alternative derivation of the above result.
In this case we use the IDFT given by

x
(
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
W
N
−
n
k
.
x
(
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
W
N
−
n
k
.

(4)
The sampled signal gives

y
(
n
)
=
x
(
M
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
W
N
−
M
n
k
.
y
(
n
)
=
x
(
M
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
W
N
−
M
n
k
.
for

n
=
0
,
1
,
⋯
,
L
−
1
n
=
0
,
1
,
⋯
,
L
−
1
.
This sum can be broken down by

y
(
n
)
=
1
N
∑
k
=
0
L
−
1
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
W
N
−
M
n
(
k
+
L
l
)
.
y
(
n
)
=
1
N
∑
k
=
0
L
−
1
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
W
N
−
M
n
(
k
+
L
l
)
.
=
1
N
∑
k
=
0
L
−
1
[
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
]
W
N
−
M
n
k
.
=
1
N
∑
k
=
0
L
−
1
[
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
]
W
N
−
M
n
k
.
>From the term in the brackets, we have

C
s
(
k
)
=
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
C
s
(
k
)
=
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
as was obtained in
(

Equation 3).

Now consider still another derivation using shah functions. Let

x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)

(5)
>From the convolution property of the DFT we have

C
s
(
k
)
=
L
⨿
L
(
k
)
*
C
(
k
)
C
s
(
k
)
=
L
⨿
L
(
k
)
*
C
(
k
)
therefore

C
s
(
k
)
=
∑
l
=
0
M
−
1
C
(
k
+
L
l
)
C
s
(
k
)
=
∑
l
=
0
M
−
1
C
(
k
+
L
l
)

(6)
which again is the same as in
(

Equation 3).

We now turn to the down sampling of an infinitely long signal which will
require use of the DTFT of the signals.

C
s
(
ω
)
=
∑
m
=
−
∞
∞
x
(
M
m
)
e
−
j
ω
M
m
C
s
(
ω
)
=
∑
m
=
−
∞
∞
x
(
M
m
)
e
−
j
ω
M
m

(7)
=
∑
n
x
(
n
)
⨿
M
(
n
)
e
−
j
ω
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
e
−
j
ω
n
=
∑
n
x
(
n
)
[
1
M
∑
l
=
0
M
−
1
e
−
j
2
π
n
l
/
M
]
e
−
j
ω
n
=
∑
n
x
(
n
)
[
1
M
∑
l
=
0
M
−
1
e
−
j
2
π
n
l
/
M
]
e
−
j
ω
n
=
1
M
∑
l
=
0
M
−
1
∑
n
x
(
n
)
e
−
j
(
ω
−
2
π
l
/
M
)
n
=
1
M
∑
l
=
0
M
−
1
∑
n
x
(
n
)
e
−
j
(
ω
−
2
π
l
/
M
)
n
=
1
M
∑
l
=
0
M
−
1
C
(
ω
−
2
π
l
/
M
)
=
1
M
∑
l
=
0
M
−
1
C
(
ω
−
2
π
l
/
M
)

(8)
which shows the aliasing caused by the masking (sampling without compression).
We now give the effects of compressing

x
s
(
n
)
x
s
(
n
)
which is a simple scaling of

ω
ω
.
This is the inverse of the stretching results in
(

(Reference)).

C
s
(
ω
)
=
1
M
∑
l
=
0
M
−
1
C
(
ω
/
M
−
2
π
l
/
M
)
.
C
s
(
ω
)
=
1
M
∑
l
=
0
M
−
1
C
(
ω
/
M
−
2
π
l
/
M
)
.

(9)
In order to see how the various properties of the DFT can be used, consider an
alternate derivation which uses the IDTFT.

x
(
n
)
=
1
2
π
∫
−
π
π
C
(
ω
)
e
j
ω
n
ⅆ
ω
x
(
n
)
=
1
2
π
∫
−
π
π
C
(
ω
)
e
j
ω
n
ⅆ
ω

(10)
which for the down--sampled signal becomes

x
(
M
n
)
=
1
2
π
∫
−
π
π
C
(
ω
)
e
j
ω
M
n
ⅆ
ω
x
(
M
n
)
=
1
2
π
∫
−
π
π
C
(
ω
)
e
j
ω
M
n
ⅆ
ω
The integral broken into the sum of

M
M
sections using a change of variables of

ω
=
(
ω
1
+
2
π
l
)
/
M
ω
=
(
ω
1
+
2
π
l
)
/
M
giving

x
(
M
n
)
=
1
2
π
∑
l
=
0
M
−
1
∫
−
π
π
C
(
ω
1
/
M
+
2
π
l
/
M
)
e
j
(
ω
1
/
M
+
2
π
l
/
M
)
M
n
ⅆ
ω
1
x
(
M
n
)
=
1
2
π
∑
l
=
0
M
−
1
∫
−
π
π
C
(
ω
1
/
M
+
2
π
l
/
M
)
e
j
(
ω
1
/
M
+
2
π
l
/
M
)
M
n
ⅆ
ω
1
which shows the transform to be the same as given in
(

(Reference)).

Still another approach which uses the shah function can be given by

x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)

(11)
which has as a DTFT

C
s
(
ω
)
=
(
2
π
M
)
⨿
2
π
/
M
(
ω
)
*
C
(
ω
)
C
s
(
ω
)
=
(
2
π
M
)
⨿
2
π
/
M
(
ω
)
*
C
(
ω
)
=
2
π
M
∑
l
=
0
M
−
1
C
(
ω
+
2
π
l
/
M
)
=
2
π
M
∑
l
=
0
M
−
1
C
(
ω
+
2
π
l
/
M
)

(12)
which after compressing becomes

C
s
=
2
π
M
∑
l
=
0
M
−
1
C
(
ω
/
M
+
2
π
l
/
M
)
C
s
=
2
π
M
∑
l
=
0
M
−
1
C
(
ω
/
M
+
2
π
l
/
M
)
which is same as
(

(Reference)).

Now we consider the effects of down--sampling on the z-transform of a signal.

X
(
z
)
=
∑
n
=
−
∞
∞
x
(
n
)
z
−
n
X
(
z
)
=
∑
n
=
−
∞
∞
x
(
n
)
z
−
n

(13)
Applying this to the sampled signal gives

X
s
(
z
)
=
∑
n
x
(
M
n
)
z
−
M
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
z
−
n
X
s
(
z
)
=
∑
n
x
(
M
n
)
z
−
M
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
z
−
n

(14)
=
∑
n
x
(
n
)
∑
l
=
0
M
−
1
e
j
2
π
n
l
/
M
z
−
n
=
∑
n
x
(
n
)
∑
l
=
0
M
−
1
e
j
2
π
n
l
/
M
z
−
n
=
∑
l
=
0
M
−
1
∑
n
x
(
n
)
{
e
j
2
π
l
/
M
z
}
−
n
=
∑
l
=
0
M
−
1
∑
n
x
(
n
)
{
e
j
2
π
l
/
M
z
}
−
n
=
∑
l
=
0
M
−
1
X
(
e
−
j
2
π
l
/
M
z
)
=
∑
l
=
0
M
−
1
X
(
e
−
j
2
π
l
/
M
z
)
which becomes after compressing

=
∑
l
=
0
M
−
1
X
(
e
−
j
2
π
l
/
M
z
1
/
M
)
.
=
∑
l
=
0
M
−
1
X
(
e
−
j
2
π
l
/
M
z
1
/
M
)
.

(15)
This concludes our investigations of the effects of down--sampling a
discrete--time signal and we discover much the same aliasing properties as in
sampling a continuous--time signal. We also saw some of the mathematical steps
used in the development.