Discrete Time Fourier Transform & Its Properties - Signals and Systems

Representation of Discrete periodic signal.
A periodic discrete-time signal x[n] with period N can be represented by a discrete-time Fourier series (DTFS). The DTFS comprises two equations: the synthesis equation that reconstructs x[n] from its Fourier coefficients, and the analysis equation that computes those coefficients from x[n].

Choose any set of N consecutive integers for the summation interval. The synthesis equation is

x[n] = ∑_{k=0}^{N-1} a_k e^{j(2π/N) k n }

The analysis equation that gives the Fourier series coefficients is

a_k = (1/N) ∑_{m=0}^{N-1} x[m] e^{-j(2π/N) k m }

Because x[n] is periodic with period N, the Fourier series coefficients are periodic in k:

a_k = a_{k+N}

Discrete-Time Fourier Transform (DTFT) of an aperiodic finite-duration signal

Consider an aperiodic finite-duration discrete sequence x[n] such that x[n] = 0 for |n| > M for some finite integer M. From this finite aperiodic sequence we can form a periodic sequence by repeating one finite segment (one period) of x[n]. When we take the DTFS of that periodic extension and let the period tend to infinity, we obtain the DTFT of the original aperiodic sequence. The DTFT is the frequency representation of a (possibly aperiodic) discrete-time signal.

If we choose the period N larger than the non-zero duration of the original finite sequence, then inside one period the periodic sequence equals the original finite sequence. For such construction the Fourier series representation of the periodic extension is

Using the analysis equation for the Fourier series and replacing the finite summation limits by the period that contains the non-zero samples, the coefficients a_k become samples of the DTFT of the aperiodic sequence evaluated at discrete frequency points. Thus the DTFT X(ω) of x[n] is defined as

X(ω) = ∑_{n=-∞}^{∞} x[n] e^{-jωn}

Choosing the period so that the summation interval includes the non-zero samples, the Fourier series coefficients relate to samples of X(ω) at ω = 2πk/N. In particular, for finite-duration x[n],

and therefore the continuous DTFT X(ω) can be obtained by interpolation of these samples as N → ∞. In the frequency domain, the periodic extension in time corresponds to a discrete (impulsive) spectrum. The DTFT is the angular-frequency representation of the discrete-time signal x[n].

X(ω) is the angular representation of the Discrete-Time Fourier Transform (DTFT) of the signal x[n].

DTFT of a periodic discrete signal - alternate viewpoint

In continuous time, the Fourier transform of a periodic continuous signal is a train of impulses at harmonics of the fundamental frequency. The same concept applies in discrete time, but the discrete-time Fourier transform is inherently periodic in ω with period 2π. For a discrete periodic sequence the DTFT is thus a weighted train of impulses located at frequencies ω = 2π k / N (mod 2π).

The DTFT of a periodic sequence x[n] is a train of impulses at ω = 2π k / N; hence the Fourier transform can be written as a weighted sum of impulses:

Consider a periodic sequence x[n] with period N and Fourier series representation

Then the DTFT of the periodic signal x[n] can be expressed as

Properties of the DTFT

The DTFT shares many general transform properties that are useful for analysis and system design. Below are commonly used properties with their mathematical forms and brief explanations.

Periodicity

The DTFT X(ω) is periodic in ω with period 2π:

X(ω + 2π) = X(ω)

Linearity

Linearity: The DTFT is a linear transform. If x1[n] ↔ X1(ω) and x2[n] ↔ X2(ω), then for constants α and β,

which is written as

α x1[n] + β x2[n] ↔ α X1(ω) + β X2(ω)

Stability

Regarding stability as a mapping from input sequence to its DTFT magnitude: the DTFT integrals (or sums) may diverge for certain signals. In that sense the DTFT integral does not always converge for all bounded sequences. For example, if x[n] = 1 for all n, the DTFT does not converge (it is unbounded in the classical sense) because the infinite sum does not converge to a finite value.

Time shifting and frequency shifting

Time shifting: If x[n] ↔ X(ω), then x[n - n0] ↔ e^{-jω n0} X(ω).

Frequency shifting (modulation): Multiplication of x[n] by e^{jω0 n} shifts its DTFT: e^{jω0 n} x[n] ↔ X(ω - ω0).

Time reversal

For time reversal, define y[n] = x[-n]. The DTFT of y[n] is related to X(ω) as

Explicitly,

x[-n] ↔ X(-ω)

Time expansion (decimation in time index)

Time expansion where samples are retained at integer multiples is only meaningfully defined for integer expansion factors. If k is a positive integer and we form y[n] = x[kn], the new sequence consists of samples of x[n] taken every k samples. The DTFT of y[n] becomes a scaled and periodic summation of X(ω):

The resulting spectrum is a compressed and periodically replicated version of the original spectrum; aliasing can occur if the original spectrum is not bandlimited.

Convolution property (multiplication in frequency)

Convolution in time corresponds to multiplication in the frequency domain for LSI systems. Let h[n] be the impulse response of a discrete-time LSI system and let H(ω) be its DTFT (frequency response). If x[n] is the input and y[n] = x[n] * h[n] is the output (where * denotes convolution), then the DTFTs satisfy

That is,

y[n] = x[n] * h[n] ↔ Y(ω) = X(ω) H(ω)

Proof (derivation of convolution property)

The convolution sum is

y[n] = ∑_{k=-∞}^{∞} x[k] h[n - k]

Take DTFT of both sides and use linearity and the DTFT definition. Change the summation order and apply the definition of X(ω) and H(ω). For a fixed k put n - k = m to rearrange the summation. The algebraic steps lead to

and finally

Y(ω) = X(ω) H(ω)

This is a very useful result: it allows analysis of LSI systems by simple multiplication of frequency responses.

Symmetry properties

If x[n] ↔ X(ω), then the following hold:

In addition, if x[n] is real-valued, the DTFT satisfies conjugate symmetry:

Explicitly, for real x[n],

X(-ω) = X*(ω)

DTFT of cross-correlation sequence

Cross-correlation between two sequences x[n] and h[n] is defined (for one common convention) as r_{xh}[l] = ∑_{n} x*[n] h[n + l]. The DTFT of the cross-correlation sequence (when the DTFTs exist) is related to the DTFTs of the individual sequences by the product of one spectrum and the complex conjugate of the other.

Specifically, if R_{xh}(ω) denotes the DTFT of r_{xh}[l], then

R_{xh}(ω) = X*(ω) H(ω)

where X*(ω) denotes the complex conjugate of X(ω).

Examples and brief illustrations

Example 1 - DTFT of a finite rectangular sequence:

Let x[n] = 1 for n = 0,1,...,N-1 and 0 elsewhere. The DTFT is

X(ω) = ∑_{n=0}^{N-1} e^{-jωn} = e^{-jω(N-1)/2} ( \sin(Nω/2) / \sin(ω/2) )

where the exponential factor is a linear phase term and the ratio of sines gives the magnitude envelope (the discrete-time Dirichlet kernel). This example shows spectral leakage and main-lobe / side-lobe structure important in sampling and filter design.

Example 2 - Time shift effect:

If x[n] has DTFT X(ω), then x[n - n0] has DTFT e^{-jω n0} X(ω). If n0 is positive this multiplies the spectrum by a phase term that rotates with frequency without changing magnitude.

Conclusion

• For a discrete-time periodic signal the Fourier series coefficients satisfy a_k = a_{k+N} (periodicity in the coefficient index).
• DTFT may not converge for all bounded sequences; the transform integral or sum must be checked for convergence (the DTFT is not guaranteed to be finite for every bounded x[n]).
• Important properties include time shifting, frequency shifting, time reversal, and time expansion (for integer expansion factors) with corresponding effects in the frequency domain.
• The convolution property for LSI systems: convolution in time corresponds to multiplication of DTFTs in frequency; Y(ω) = X(ω) H(ω).
• Symmetry relations and the DTFT of cross-correlation sequences are useful in signal analysis: for real signals X(-ω) = X*(ω), and cross-correlation in time corresponds to multiplication by a conjugated spectrum in frequency.