Algorithms and Parallel Computing

19.1 INTRODUCTION

The discrete Fourier transform (DFT) is a very important algorithm that finds use in many applications such as telecommunications, speech processing, image processing, medical imaging such as in computer assisted tomography (CAT), radar (synthetic aperture radar), sonar, and antenna array (phased arrays) [120, 121]. A very important application nowadays is the use of DFT techniques in orthogonal frequency division multiplexing (OFDM) as an efficient data modulation scheme. This technique is also extended for use in multiple-input multiple-output (MIMO) systems where each transmitter/receiver has multiple antennas to simultaneously transmit/receive multiple data streams in what is known as OFDM-MIMO systems [122]. This is not the forum to discuss what is OFDM and how it differs from the classic frequency division multiplexing (FDM). Excellent textbooks on digital communication cover such topics [113]

The DFT algorithm finds the spectrum of a periodic discrete-time signal with period N. The spectral component X(k) is obtained by the equation

(19.1)

where W_N is the twiddle factor, which equals the Nth root of unity and is given by

(19.2)

The dependence graph of the eight-point DFT algorithm is shown in Fig. 19.1. Input samples x(n) are represented by the vertical ...