Time-domain analysis of discrete-time systems - Continuous and Discrete Time Signals and Systems - page 446

(i) The DT sequence x [ k ] = 0 outside the range k ℓ 1 ≤ k ≤ k u 1 . Note that it is
possible for x [ k ] to have some zero values within the range k ℓ 1 ≤ k ≤ k u 1 .
The length K x of x [ k ] is given by K x = ( k u 1 − k ℓ 1 + 1) samples.
(ii) The DT sequence h [ k ] = 0 outside the range k ℓ 2 ≤ k ≤ k u 2 . As for x [ k ] ,it
is possible for h [ k ] to have intermittent zero values within the range k ℓ 2 ≤
k ≤ k u 2 . The length K h of h [ k ] is given by K h = k u 2 − k ℓ 2 + 1 samples.

Add the appropriate number of zeros to the two sequences x [ k ] and h [ k ] so
that they have the same length K 0 ≥ ( K x + K h − 1) . The procedure of adding
zeros to a sequence is referred to as zero padding. The periodic extensions of
zero-padded x [ k ] and h [ k ] are denoted by x p [ k ] and h p [ k ] , which have the
same fundamental period of K 0 ≥ ( K x + K h − 1) . Mathematically, the single
periods of x p [ k ] and h p [ k ] are defined as follows:

x [ k ] k ℓ 1 ≤ k ≤ k u 1

x p [ k ] = (10.20a)

0 k u 1 < k ≤ K 0 + k ℓ 1 − 1

and

h [ k ] k ℓ 2 ≤ k ≤ k u 2

h p [ k ] = (10.20b)

0 k u 2 < k ≤ K 0 + k ℓ 2 − 1 .

It can be shown that the linear convolution between x [ k ] and h [ k ] can be
obtained from the periodic convolution between x p [ k ] and h p [ k ] using the fol-
lowing relationship:

x [ k ] ∗ h [ k ] = x p [ k ] ⊗ h p [ k ] ,

for ( k ℓ 1 + k ℓ 2 ) ≤ k ≤ ( k u 1 + k u 2 ) .

Definition 10.3 provides us with an alternative algorithm for implementing
the linear convolution through the periodic convolution. The advantage of the
above approach lies in computationally efficient implementations of the peri-
odic convolution, which are much faster than the implementations of the linear
convolution. Chapter 12 presents one such approach using the discrete Fourier
transform (DFT) to compute the periodic convolution.

Algorithm 10.4 Computing linear convolution from periodic convolution

(1) Consider two time-limited DT sequences x [ k ] and h [ k ]. The DT sequence
x [ k ] = 0 outside the range k ℓ 1 ≤ k ≤ k u 1 of length K x = k u 1 − k ℓ 1 + 1
samples. Similarly, the DT sequence h [ k ] = 0 outside the range k ℓ 2 ≤ k ≤
k u 2 of length K h = k u 2 − k ℓ 2 + 1 samples.
(2) Select an arbitrary integer K 0 ≥ K x + K h − 1.
(3) Compute the periodic extension x p [ k ]of x [ k ] using Eq. (10.20a).
(4) Compute the periodic extension h p [ k ]of h [ k ] using Eq. 10.20b).