Wave Walker DSP

DSP Algorithms for RF Systems

Most Popular

Brand New Book!

DSP for Beginners: Simple Explanations for Complex Numbers! The second edition includes a new chapter on complex sinusoids.

bookCover2Ed
examples1
examples2
eulersFormula
radians
negativeFrequency
adding
posNegAngles
complexSinusoidPhase
Previous image
Next image
Discrete Fourier Transform (DFT) of Complex Sinusoid
May 1, 2023

Table of Contents

Introduction

This blog derives the frequency response of a complex sinusoid using the discrete Fourier transform (DFT). The derivation starts by apply the discrete time Fourier transform (DTFT) of the complex sinusoid, simplifying the summation as a geometric series, and evaluating the DTFT at specific frequencies of the DFT.

Check out these other blogs:

Discrete Time Fourier Transform

The discrete-time Fourier transform (DTFT) is defined as [Oppenheim1999, p.48]

(1)   \begin{equation*}X\left( e^{j\omega} \right) = \sum_{n=-\infty}^{\infty} x[n]e^{-j\omega n}. \end{equation*}

A realizable (ex: can be built in the real world) digital system must deal with signals which are finite length. A finite length complex sinusoid is defined according to

(2)   \begin{equation*}x[n] =\begin{cases}e^{j\omega_c n}, & 0 \le n \le N-1 \\0, & \text{otherwise}.\end{cases}\end{equation*}

Substituting (2) into (1),

(3)   \begin{equation*}\begin{split}X\left( e^{j\omega} \right) & = \sum_{n=0}^{N-1} e^{j\omega_c n}e^{-j \omega n} \\& = \sum_{n=0}^{N-1} e^{j \left( \omega_c - \omega \right) n }.\end{split}\end{equation*}

Geometric Series

The sum of m points in a finite length geometric series is defined as

(4)   \begin{equation*}S_{m} = \sum_{p=0}^{m-1} a r^{p}\end{equation*}

which is evaluated as (reference)

(5)   \begin{equation*}S_{m} = \frac{a\left( 1-r^m \right)}{1-r}.\end{equation*}

The result in (3) can be written as the geometric series with terms

(6)   \begin{equation*}a = 1,\end{equation*}

(7)   \begin{equation*}r = e^{j\left( \omega_c - \omega \right),\end{equation*}

(8)   \begin{equation*}m = N.\end{equation*}

Substituting (6)-(8) into (5),

(9)   \begin{equation*}X\left( e^{j\omega} \right) = S_{N} = \frac{1-e^{j\left(\omega_c - \omega\right)N}}{1-e^{j\left(\omega_c - \omega\right)}}.\end{equation*}

Applying L'Hospital's Rule

Equation (9) is undefined when \omega = \omega_c therefore L’Hospital’s rule is applied,

(10)   \begin{equation*}X\left( e^{j \omega} \right) |_{\omega=\omega_c} = \dfrac{\frac{\partial}{\partial \omega} \left( 1-e^{j\left(\omega_c - \omega\right)N \right)}}{\frac{\partial}{\partial \omega} \left( 1-e^{j\left(\omega_c - \omega\right) \right)}}.\end{equation*}

Simplifying (10),

(11)   \begin{equation*}\begin{split}X\left( e^{j \omega} \right) |_{\omega=\omega_c} & = \frac{-jNe^{j\left( \omega_c - \omega\right)N}}{-je^{j\left( \omega_c - \omega\right)}} \\& = Ne^{j\left( \omega_c - \omega \right) \left(N-1\right)} \\& = N.\end{split}\end{equation*}

The frequency response can therefore be written as

(12)   \begin{equation*}X\left( e^{j \omega}\right) = \begin{cases}\dfrac{1-e^{j\left(\omega_c - \omega\right)N}}{1-e^{j\left(\omega_c - \omega\right)}}, & \omega \neq \omega_c \\N, & \omega = \omega_c.\end{cases}\end{equation*}

Discrete Fourier Transform (DFT) of Complex Sinusoid

The DFT is a simplified case of the DTFT where the frequencies \omega are only evaluated at

(13)   \begin{equation*}\omega = \frac{2\pi k}{N}\end{equation*}

where k = 0, 1, 2, \dots, N-1, [Oppenheim1999, p.542]. Substituting (13) into (12),

(14)   \begin{equation*}X[k] = \begin{cases}\dfrac{1-e^{j\left(\omega_c - 2\pi k/N\right)N}}{1-e^{j\left(\omega_c-2\pi k/N\right)}}, & 2\pi k/N \neq \omega_c \\N, & 2\pi k/N = \omega_c.\end{cases}\end{equation*}

The DFT (14) can be further simplified as 

(15)   \begin{equation*}X[k] = \begin{cases}e^{j\alpha\left(N-1\right)/2}\cdot \dfrac{\sin\left( \alpha N/2 \right)}{\sin \left( \alpha/2 \right)}, & 2\pi k/N \neq \omega_c, \\N, & 2\pi k/N = \omega_c.\end{cases}\end{equation*}

 

Comparing to Simulation

Figures 1-3 compare equation (15) to NumPy’s DFT function for sinusoids with frequencies \omega_c = \pi/4, 3\pi/4, 0.57\pi and N=4096.

Figure 1: The discrete Fourier transform (DFT) of a complex sinusoid with frequency pi/4.
Figure 1: The discrete Fourier transform (DFT) of a complex sinusoid with frequency pi/4.
Figure 2: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 3pi/4.
Figure 2: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 3pi/4.
Figure 3: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 0.57pi.
Figure 3: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 0.57pi.

You may have noticed that all of the sinusoid’s energy is contained within a single bin when \omega_c is of the form 2 \pi k / N as in Figures 1 and 2. For Figure 3, the energy is spread across multiple frequency bins. Figure 4 shows a zoomed in version of Figure 3 for more clarity.

Figure 4: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 0.57pi (zoom view).
Figure 4: The discrete Fourier transform (DFT) of a complex sinusoid with frequency 0.57pi (zoom view).

The sinusoid’s energy is spread across multiple bins because the sinusoid does not complete an integer number of cycles of frequency \omega_c in N samples. This effect is related to the frequency resolution of the DFT.

Conclusion

The discrete time Fourier transform (DTFT) and discrete Fourier transform (DFT) of a complex sinusoid were derived. The analytic equation was compared for correctness against a numerical DFT function. 

Check out these other blogs:

God, the Lord, is my strength; he makes my feet like the deer’s; he makes me tread on my high places. Habakkuk 3:19

Leave a Reply

This website participates in the Amazon Associates program. As an Amazon Associate I earn from qualifying purchases.