Sec. 5.

2 Properties of the DFT

TABLE 5.1 SYMMETRY PROPERTIES OF THE DFT

- - - - -

N-Point Sequence x ( n ) .
O s n s N - 1 N - P o i n t DFT

x(n) x (k)
x*(n) X*(N - k)
x*(N - n ) X* (k )
XR(~) +
X,.,(k) -- 4 [ ~ ( k ) X * ( N - k ) ]
J X I( n ) -
X,,,(k) = i [ ~ ( k ) X ' ( N - k)]
+
x,,(n) = $ [ . ~ ( n > x k ( N - n ) ] XR(~)
x,,,(n) = $ [ x ( n ) - x * ( N - n ) ] jX,(k)
Real Signals
Any real signal
x(n1

The symmctry properties given ahovc may be summarized as follows:

All the symmetry properties of the DFT can easily be deduced from (5.2.31). For
example, the DFT of the sequence
+
x,,(n) = i [ x p ( n ) x , ( N - n)]
X R ( ~=
) X>(k) + Xi(k)
The symmetry properties of the DFT are summarized in Table 5.1. Ex-
ploitation of these properties for the efficient computation of the DFT of special
sequences is considered in some of the problems at the end of the chapter.

5.2.2 Multiplication of Two DFTs and Circular Convolution

Suppose that we have two finite-duration sequences of length N , x , ( n ) and x2(r1).

Their respective N-point DFTs are
416 The Discrete Fourier Transform: Its Properties and Applications Chap. 5

If we multiply the two DFTs together, the result is a DFT, say Xt(k), of a se-
quence x 3 ( n ) of length N. Let us determine the relationship between x ~ ( R )and
the sequences X I (n) and x2 (n).
We have

The IDFT of ( X 3 ( k ) )is

1 N- 1

Suppose that we substitute for X l ( k ) and X z ( k ) in (5.2.35) using the DFTs given
in (5.2.32)and (5.2.33). Thus we obtain

The inner sum in the brackets in (5.2.36) has the form

where a is defined as
a = ej2n(m-n-l)/N

We observe that a = 1 when m - n - 1 is a multiple of N. On the other hand

aN= 1 for any value of a # 0. Consequently, (5.2.37) reduces to

Car=(:.
N-1
l = m - n + p ~ = ( ( m - n ) ) ~ . paninteger
(5.2.38)
f 4
otherwise
If we substitute the result in (5.2.38) into (5.2.36), we obtain the desired expression
for x 3 ( m ) in the form
N-1
x d m ) = ~ x ~ ( n ) x t ( -( nm) ) ~ rn =O. 1 . . .. .N - 1 (5.2.39)
nrO

The expression in (5.2.39) has the form of a convolution sum. However, it is

not the ordinary linear convolution that was introduced in Chapter 2, which relate -

the output sequence y ( n ) of a linear system to the input sequence x ( n ) and the
impulse response h(n). Instead, the convolution sum in (5.2.39) invohes the index -
Sec. 5.2 Properties of the DFT 417

((m- n ) ) N and is called circular convolution. Thus we conclude that multiplication

of the DFTs of two sequences is equivalent to the circular convolution of the two
sequences in the time domain.
The following example illustrates the operations involved in circular convo-
lution.
Example 5 3 1
Perform the circular convolution of the following two sequences:

Solution Each sequence consists of four nonzero points. For the purposes of illus-
trating the operations involved in circular convolution, it is desirable to graph each
sequence as points on a circle. Thus the sequences x l ( n ) and x 2 ( n ) are graphed as
illusttatcd in Fig. 5.8(a). We note that the sequences are graphed in a counterclock-
wise direction on a circle. This establishes the reference direction in rotating one of
the sequences relative to the other.
Now, x 3 ( m ) is obtained by circularly convolving x l ( n ) with x z ( n ) as specified by
(5.2.39). Beginning with m = 0 we have
3

~ ? ( ( - n ) is
) ~simply the sequence x 2 ( n ) folded and graphed on a circle as illustrated in
Fig. 5.8(b). In other words, the folded sequence is simply x z ( n ) graphed in a clockwise
direction.
The product sequence is obtained by multiplying x l ( n ) with x 2 ( ( - n ) ) r , point by
point. This sequence is also illustrated in Fig. 5.8(b). Finally, we sum the values in
the product sequence to obtain
x 3 ( 0 ) = 14
For m = 1 we have

-
It is easily verified that x2((1 n))4 is simply the sequence x 2 ( ( - n ) ) 4 rotated coun-
terclockwise by one unit in time as illustrated in Fig. 5.8(c). This rotated sequence
multiplies x l ( n ) to yield the product sequence, also illustrated in Fig. 5.8(c). Finally,
we sum the values in the product sequence to obtain x 3 ( l ) . Thus

For m = 2 we have

Now x2((2 - R ) ) ~is the folded sequence in Fig. 5.8(b) rotated two units of time in
the counterclockwise direction. The resultant sequence is illustrated in Fig. 5.8(d)
 1 2

x2(f)=2 2
Folded .sequence Product sequence

x 2 ( 2 )= 3 3
Folded sequence rotated by one unit in time Product sequence
(c)

~ ~ ('34 )
Folded sequence r o t d by two units in time

4 0 )= 1
Folded sequence rotated by three units in time

5.8 Circular convolution of two sequences.

Sec. 5.2 Properties of the DFT 419

along with the product sequence x l ( n ) x 2 ( ( 2- n)),. By summing the four terms in the
product sequence, we obtain
~ ~ (=2 14
)
For m = 3 we have

The folded sequence x2((-n))4 is now rotated by three units in time to yield ~ ~ ( ( 3 - n ) ) 4
and the resultant sequence is multiplied by xl(n) to yield the product sequence as
illustrated in Fig. 5.8(e). The sum of the values in the product sequence is

We observe that if the computation above is continued beyond m = 3 . we

simply repeat the sequence of four values obtained above. Therefore, the circular
convolution of the two sequences xi (n) and x2(n) yields the sequence

From this example, we observe that circular convolution involves basically

the same four steps as the ordinary linear convolution introduced in Chapter 2:
folding (time reversing) one sequence, shifring the folded sequence, multiplying the
two sequences to obtain a product sequence, and finally, summing the values of the
product sequence. The basic difference between these two types of convolution
is that, in circular convolution, the folding and shifting (rotating) operations are
performed in a circular fashion by computing the index of one of the sequences
modulo N. In linear convolution, there is no modulo N operation.
The reader can easily show from our previous development that either one
of the two sequences may be folded and rotated without changing the result of the
circular convolution. Thus
N-1
x 3 ( m )= x x 2 ( n ) x 1 ( ( m - n ) ) N rn =O. 1. . . . , N -1 (5.2.40)
n=O

The following example serves to illustrate the computation of x j ( n ) by means

of the DFT and IDFT.
Example 5 2 2
By means of the D m and IDFT, determine the sequence x3(n) corresponding to the
circular convolution of the sequences x i (n)and x2(n) given in Example 5.2.1.
Solution First we compute the DFTs of x l ( n ) and x2(n). The four-point DFT of
x l ( n ) is