Q9Digital Signal Processing

(a) Properties of the DFT

The Discrete Fourier Transform possesses the same core set of properties detailed in the companion 2021 paper's u5-q5(a) answer: linearity (DFT of a linear combination equals the same linear combination of individual DFTs), periodicity (both x(n) and X(k) are implicitly periodic with period N when extended via the DFT/IDFT formulas), circular time and frequency shift properties (a circular shift in one domain corresponds to multiplication by a linear-phase complex exponential factor in the other domain), circular convolution (multiplication of two DFTs corresponds to circular, rather than ordinary linear, convolution of the corresponding time-domain sequences, a critical distinction requiring appropriate zero-padding when using DFT-based fast convolution to compute an ordinary linear convolution result), Parseval's theorem (preservation of signal energy, up to a scaling factor of N, between the time and frequency domain representations), and conjugate symmetry (for real-valued input sequences, X(N-k) equals the complex conjugate of X(k), meaning only about half of the N DFT coefficients carry independent information).

(b) DIT (Decimation-In-Time) FFT Algorithm

The Fast Fourier Transform (FFT) is a family of efficient algorithms for computing the DFT, exploiting the periodicity and symmetry properties of the complex exponential (twiddle factor) terms W_N^(kn)=e^(-j2pikn/N) to dramatically reduce the number of arithmetic operations required compared to direct computation of the DFT summation formula.

Decimation-In-Time principle: the DIT-FFT algorithm recursively splits the N-point input sequence x(n) into two interleaved (N/2)-point subsequences based on the parity (even/odd) of the sample index n: the even-indexed samples xe(m)=x(2m) and the odd-indexed samples xo(m)=x(2m+1), for m=0,1,...,(N/2)-1. The original N-point DFT can then be expressed in terms of the (N/2)-point DFTs of these two subsequences, Xe(k) and Xo(k):

where W_N^k=e^(-j2pik/N) is the twiddle factor. This decomposition can itself be applied recursively - each (N/2)-point DFT (Xe and Xo) can in turn be computed by further splitting into (N/4)-point even/odd subsequences, and so on, down to trivial 1-point DFTs (which are simply the input samples themselves), for an N that is a power of 2.

Computational savings: each stage of this recursive decomposition requires only N/2 complex multiplications (by twiddle factors) and N complex additions (the butterfly combination), and since there are log2(N) such recursive stages (for N a power of 2), the total computational cost of the FFT is O(N*log2(N)) complex multiplications/additions, a dramatic reduction compared to the O(N^2) operations required by direct DFT summation - for example, for N=1024, direct DFT computation requires on the order of 1,048,576 operations, while the FFT requires only on the order of 10,240 operations, over a hundredfold reduction, which is precisely why the FFT algorithm (in either its DIT or the complementary DIF form, discussed and applied numerically in the corresponding u5-q5or question) is the standard, universally-used practical method for computing the DFT of any signal of practical length in real-world digital signal processing applications.

Bit-reversed input ordering: a characteristic feature of the standard DIT-FFT algorithm implementation is that, due to the repeated even/odd index splitting performed at each recursive stage, the input samples must be supplied to the butterfly computation network in a specific bit-reversed order (the binary representation of each sample's index, with its bits reversed, gives the position at which that sample must be placed for the standard in-place butterfly computation to produce correctly-ordered output), a well-known implementation detail of practical FFT algorithms, addressed either by an explicit bit-reversal reordering step applied to the input data before the main butterfly computation, or by output the results themselves in bit-reversed order if the input is supplied in natural order (an alternative equivalent implementation choice).

Beyond the fundamental linearity, periodicity, and symmetry properties of the DFT, several additional properties are of particular practical importance in signal-processing applications: Parseval's theorem for the DFT states that the total energy of a finite-length sequence x(n), computed by summing |x(n)|^2 over all N samples in the time domain, equals (1/N) times the sum of |X(k)|^2 over all N frequency-domain samples, providing an essential energy-conservation check between the time and frequency domain representations of any signal and underlying the definition of the power spectral density estimate obtained from a signal's DFT in practical spectral-analysis applications.

The multiplication (circular convolution in frequency) property, dual to the well-known time-domain circular convolution property, states that multiplying two sequences x1(n) and x2(n) sample-by-sample in the time domain corresponds to (1/N) times the circular convolution of their respective DFTs X1(k) and X2(k) in the frequency domain - this property is the theoretical basis for understanding spectral leakage and windowing effects in practical spectral analysis, since applying a finite-length window function to a signal before taking its DFT (a time-domain multiplication) necessarily corresponds to a circular convolution (smearing) of the signal's true spectrum with the window function's own DFT in the frequency domain, explaining why window choice directly affects the sharpness and leakage characteristics of any windowed spectral estimate.

The Decimation-In-Time (DIT) FFT algorithm achieves its dramatic computational efficiency, reducing the direct DFT computation's O(N^2) complex multiplications down to O(Nlog2(N)), by recursively splitting the input sequence x(n) into its even-indexed and odd-indexed sub-sequences, computing the (N/2)-point DFT of each sub-sequence independently, and then combining these two shorter DFT results using the butterfly computation structure (which combines each pair of even/odd DFT outputs, appropriately weighted by the twiddle factor W_N^k = e^(-j2pi*k/N), to produce two of the full N-point DFT's output values) - this even/odd splitting and combining process is applied recursively log2(N) times (for N a power of 2), ultimately reducing the computation all the way down to trivial 2-point DFTs at the base of the recursion, with the characteristic 'butterfly' signal-flow-graph pattern, and the requirement for bit-reversed input (or output) ordering, both being direct structural consequences of this recursive even/odd decimation splitting process.

It is useful to note that the DIT algorithm's requirement for bit-reversed input ordering (or equivalently bit-reversed output ordering in the DIF variant) is not merely a computational curiosity but a direct, predictable consequence of the recursive even-odd splitting process, and practical FFT software implementations handle this requirement either through an explicit bit-reversal permutation step applied once before (DIT) or after (DIF) the butterfly computations, or by using specialized in-place butterfly-computation algorithms that write results directly into their bit-reversed storage locations, avoiding the need for a separate, distinct permutation pass and thereby further improving the overall computational and memory efficiency of a practical FFT implementation.