Discrete and Digital Signals and Systems - Digital Signal Processing: An Introduction with MATLAB and Applications - page 85

The FFT algorithm can generally support real-time processing (at least on
modern computers and DSP chips).
MATLAB the Fast Fourier Transform algorithm is available on MATLAB as
fft .

2.4.1.4 Circular Convolution and Its Relation to the Linear Convolution

In time and frequency discretized systems the time domain signal and the fre-
quency domain signal are both periodic. Within these doubly discretized systems,
it is not only the input signal which is periodic, but also the impulse response and
frequency transfer function. To appreciate the implications of this last fact, con-
sider two time-domain signals x(n) and h(n) which are both periodic. Their linear
convolution

x ð n Þ h ð n Þ¼ X

1

x ð k Þ h ð n k Þ ð 2 : 19 Þ

k ¼1

diverges in general (i.e., does not exist). This is because both signals are infinitely
long and so the sum within ( 2.19 ) can easily be infinite. With periodic signals,
therefore, it is more natural to define a modified form of convolution known as
circular convolution. As will be seen subsequently, this is the kind of convolution
which is implemented implicitly in doubly discretized systems.
Assuming that two signals have identical periods of length N, then one con-
siders only one period of each signal and defines circular convolution as:

x ð n Þ h ð n Þ¼ X

N 1

x ð k Þ h ½ð n k Þ N ;

k ¼ 0

where p N = p modulo N for any integer p. The circular convolution x ð n Þ
h ð n Þ > is also periodic with the same period N.
Recall that the linear convolution of two non-periodic finite-length signals
x(n)*h(n) has length L = N x ? N y - 1. If one desires therefore to have x ð n Þ
y ð n Þ¼ x ð n Þ h ð n Þ over one period of the periodic signals x(n) and h(n), then one
has to artificially extend the length of both signals by zero-padding both x(n) and
h(n) to be of length L = N x ? N y - 1. That is, one adds extra samples to x(n) and
h(n), with these samples having the value 0.

2.4.1.5 I/O Relations Using Circular Convolution and the DFT

One of the key areas of application for the DFT is digital filtering. In DFT based
digital filtering one has an input signal x(n) and an impulse response h(n), and the
filtered output y(n) is given by the convolution of x(n) and h(n). Implementation of
the filtering in the time domain, however, requires O(N 2 ) operations, assuming
both x(n) and h(n) have N samples. One can take advantage of the efficiency of the