Q9Digital Signal Processing

(a) Discrete Fourier Transform and Its Properties

The Discrete Fourier Transform (DFT) transforms a finite-length, N-point discrete-time sequence x(n) (n=0,1,...,N-1) into an N-point discrete frequency-domain sequence X(k) (k=0,1,...,N-1), defined as:

The DFT can be understood as sampling the sequence's continuous discrete-time Fourier transform (DTFT) at N equally-spaced frequency points around the unit circle, spaced 2*pi/N radians apart - this is precisely why the DFT, unlike the continuous DTFT, is computable using a finite number of arithmetic operations, and is therefore the practical tool used for numerical/computational frequency-domain analysis of finite-length signals.

Properties of the DFT

• Linearity: DFT{ax1(n)+bx2(n)} = aX1(k)+bX2(k) for constants a, b - the DFT of a linear combination of sequences equals the same linear combination of their individual DFTs.
• Periodicity: both x(n) and X(k), when extended beyond their defined range using the DFT/IDFT formulas, are implicitly periodic with period N, a direct consequence of the finite summation and the periodic nature of the complex exponential basis functions.
• Circular time shift: DFT{x((n-n0) mod N)} = X(k)e^(-j2pikn0/N) - shifting a sequence circularly (with wraparound) in the time domain corresponds to multiplying its DFT by a linear-phase complex exponential factor.
• Circular convolution: multiplication of two sequences' DFTs, X1(k)*X2(k), corresponds to CIRCULAR (not ordinary linear) convolution of the two time-domain sequences, x1(n) circularly convolved with x2(n) - this distinction from linear convolution is of major practical importance, since implementing linear convolution via DFT-based fast computation requires appropriate zero-padding of both sequences to avoid the wraparound effects inherent to circular convolution.
• Parseval's theorem (energy conservation): sum over n of |x(n)|^2 = (1/N)*sum over k of |X(k)|^2 - the total signal energy computed in the time domain equals (up to the 1/N scaling factor) the total energy computed from the frequency-domain DFT coefficients, reflecting the fact that the DFT is an energy-preserving (up to scaling) orthogonal transformation.
• Conjugate symmetry (for real-valued sequences): if x(n) is real-valued, its DFT satisfies X(N-k) = X*(k) (the complex conjugate relationship), meaning only approximately half of the N DFT coefficients are independent, a property extensively exploited to reduce computation and storage requirements when processing real-valued signals.

(b) N-Point DFT of x(n) = a^n*u(n), 0<=n<=N-1

Applying the DFT definition directly to the given finite exponential sequence:

This is a finite geometric series with common ratio r = ae^(-j2pi*k/N), and the sum of a finite geometric series is (1-r^N)/(1-r) (for r not equal to 1):

Since (e^(-j2pik/N))^N = e^(-j2pik) = cos(2pik) - jsin(2pik) = 1 for any integer k (a full number of complete revolutions around the unit circle), the term (ae^(-j2pik/N))^N simplifies to a^N * 1 = a^N. Substituting this simplification:

Result: this closed-form expression, X(k)=(1-a^N)/(1-ae^(-j2pi*k/N)), is the standard, well-known N-point DFT of a truncated real exponential sequence, showing that the geometric-series structure of the original time-domain sequence directly produces this compact closed-form frequency-domain result, avoiding the need to compute the summation term-by-term for each individual k value - this closed-form result is widely used as a standard, easily-verified test case in DFT/FFT algorithm textbooks and problem sets.

Among the properties of the DFT, the circular convolution property is of particular practical significance: multiplication of two sequences' N-point DFTs, X1(k) and X2(k), followed by an inverse DFT, yields not the linear convolution of the two original time-domain sequences x1(n) and x2(n), but rather their N-point circular (periodic) convolution, in which one sequence is conceptually wrapped around a circle of length N before the convolution sum is computed - this distinction is of central importance in practical DSP applications such as fast (FFT-based) linear filtering, where the desired linear convolution result must be obtained indirectly, typically via explicit zero-padding of both sequences to a length at least equal to the sum of their individual lengths minus one, specifically to avoid the time-domain aliasing (wrap-around distortion) that would otherwise corrupt a naive circular-convolution-based fast-filtering implementation.

The DFT's circular time-shift and circular frequency-shift (modulation) properties are dual to one another and directly parallel the corresponding shift properties of the continuous Fourier transform, but with the crucial distinction that all shifts are interpreted modulo N (circularly) rather than linearly - a circular shift of x(n) by n0 samples multiplies its DFT X(k) by the complex exponential factor e^(-j2pik*n0/N), a relationship that underlies efficient implementations of circular correlation and is also the theoretical basis for understanding how the phase of the frequency-domain samples X(k) encodes the precise time-domain alignment of periodic or quasi-periodic signal components.

The closed-form DFT result X(k) = (1-a^N)/(1-ae^(-j2pi*k/N)) derived for this exponential sequence provides a useful sanity check at k=0: substituting k=0 gives X(0) = (1-a^N)/(1-a), which correctly matches the direct definition X(0) = sum of x(n) over all n = sum of a^n from n=0 to N-1, the standard finite geometric series formula, confirming the correctness of the general closed-form expression; this closed-form result is also frequently used as a standard reference case in DSP textbooks and examinations precisely because it exercises the geometric-series summation technique central to evaluating the DFT (and DTFT) of exponential and related sequences analytically, a technique that generalizes directly to computing the DFT of damped sinusoids and other exponentially-weighted signal models common in practical signal analysis.

It is also useful to note the special case a=1 in this derivation: substituting a=1 into x(n)=a^nu(n) for 0<=n<=N-1 reduces the input to a simple rectangular pulse of unit height and length N, and the general closed-form DFT result X(k)=(1-a^N)/(1-ae^(-j2pik/N)) correspondingly reduces (after applying L'Hopital's rule or a direct limiting argument, since both numerator and denominator vanish as a approaches 1 at k=0) to the standard Dirichlet-kernel form for a rectangular pulse's DFT, consistent with the closed-form rectangular-pulse DFT expression used elsewhere in this examination paper, providing a useful cross-check that the general exponential-sequence DFT formula derived here correctly specializes to this well-known simpler case.

It is also worth relating the DFT computed here to the underlying Discrete-Time Fourier Transform (DTFT) of the same infinite-duration sequence a^nu(n) (extended for all n>=0 rather than truncated to N samples): the DTFT of the full infinite sequence is the well-known geometric-series closed form 1/(1-ae^-jw), a continuous function of w, whereas the N-point DFT computed here represents N equally-spaced samples of a related but distinct finite-length-sequence transform (since truncating the infinite sequence to N samples before transforming is not the same operation as sampling the infinite sequence's DTFT), a subtlety that is important to keep in mind whenever using the DFT as a practical, computable approximation to an underlying continuous spectrum of an infinite or very long sequence.