Revisiting the Basics - Digital Signal Processing: A Practitioner's Approach - page 25

Convolution is also known as filtering and it is also equivalent to multiplying two
polynomials, H ð z Þ U ð z Þ . If we have a sequence h k of length m and a sequence u k
of length N, then we can see that the output sequence is of size m þ N.
Consider the computational complexity of (2.6). Computing u 1 h k needs m
multiplications and m additions. Assuming there is not much difference between
addition and multiplication, in the floating-point domain, the computational burden
is 2m operations for one term, and the whole of (2.6) requires ð 2m N þ N 1 Þ
operations. For N ¼ 100 which are typical values, we need to perform

10 099 operations. As an engineering approximation, we can estimate this as 2mN
operations.
Computing the convolution of two sequences using (2.6) is computationally
expensive. Less expensive methods are available based on discrete Fourier trans-
forms (DFTs). This is because there are fast methods for computing DFTs.

; m ¼ 50 ;

2.1.5.2 Autocorrelation Function

Another important operation between two sequences, say u k and h k ; is correlation.

Typically u k is an input sequence to a linear system and h k is the impulse response
of the same system. The correlation function is defined as

¼ X

n ¼ N

r uh
k

u n þ 1 h k þ n : ð 2 : 7 Þ

n ¼ 0

This is also written using the convolution operator as y k ¼ u k h k , where h k is
the conjugate symmetric part of h k . When both sequences in (2.7) are the same and
equal to the impulse response h k then r u k becomes the autocorrelation 3 function r k
of the system, shown in Figure 2.4(a). The autocorrelation function r k has special

6

1

5

0.5

4

0 3

2

−0.5

1

−1

0

−200 −100 0 100 200

0 0.1 0.2 0.3 0.4 0.5

(a) (b)

Figure 2.4 Relation between autocorrelation r k and power spectrum jj H ð j !Þjj

3 r ð t Þ¼ R 1 1 h ðÞ h ð t Þ d :