Discrete Fourier Transform (DFT) Archives

Discrete Fourier Transform (DFT) of a DFT-even sequence

July 11, 2022 DSP

The Beauty of Symmetry in Fourier Transform

In 1978, Fred Harris was a relatively unknown faculty member at the San Diego State University when he published his landmark paper titled On the use of windows for harmonic analysis with the discrete Fourier transform. That paper made him a superstar in DSP community. It presented a brief overview of signal windows and their impact on the detection of harmonic signals in the presence of broad-band noise and nearby harmonic interference. More importantly, he pointed out several common errors in the application of windows when used in the context of Discrete Fourier Transform (DFT). Today I am going to write about how the paper started: by clarifying a common misconception about regular signal symmetry vs DFT symmetry that baffled

May 2, 2021 DSP

Convolution and Fourier Transform

One question I am frequently asked is regarding the definition of Fourier Transform. A continuous-time Fourier Transform for time domain signal $x(t)$ is defined as \[ X(\Omega) = \int _{-\infty} ^{\infty} x(t) e^{-j\Omega t} dt \] where $\Omega$ is the continuous frequency. A corresponding definition for discrete-time Fourier Transform for a discrete-time signal $x[n]$ is given by \[ X(e^{j\omega}) = \sum _{n=-\infty} ^{\infty} x[n] e^{-j\omega n} \] where $\omega$ is the discrete frequency related to continuous frequency $\Omega$ through the relation $\omega = \Omega T_S$ if the sample time is denoted by $T_S$. Focusing on the discrete-time Fourier Transform for the discussion, here is the question often asked regarding these relations. The Question Why do we use the complex sinusoids

July 12, 2021 DSP

Generating Signals and Viewing the Spectrum

One of the most common questions DSP beginners have is how to generate the signals (particularly, sinusoids) and view their spectrum. They have a rough idea what time domain and frequency domain are about but struggle to construct the first few lines of code that open the gates towards a deeper understanding of signals. For this reason, I produce below an Octave (or Matlab) code that you can simply copy and paste to view and modify the results. Keep in mind that the code has been written for an explanation purpose, not conciseness or optimization. As you progress towards developing a reasonably complicated DSP system, the coding aspect becomes more important. The code is verified on Octave version 4.2.2. Notice

A bank of N filters each centered at discrete frequency k/N

March 19, 2020 DSP

Discrete Fourier Transform (DFT) as a Filter Bank

We have discussed before what a Discrete Fourier Transform (DFT) is and how to find the DFT of some commonly used signals. Here, we will see how a DFT acts as a (crude) bank of filters that can pass the signal contents around a desired frequency while blocking the rest. Let us start with the definition of the DFT. \begin{equation*} \begin{aligned} S_I[k]\: &= \sum \limits _{n=0} ^{N-1}\left[ s_I[n] \cos 2\pi\frac{k}{N}n + s_Q[n] \sin 2\pi\frac{k}{N}n\right] \\ S_Q[k] &= \sum \limits _{n=0} ^{N-1}\left[ s_Q[n] \cos 2\pi\frac{ k}{N}n – s_I[n] \sin 2\pi\frac{k}{N}n\right] \end{aligned} \end{equation*} for each $k$. In complex notation, this DFT is defined as \begin{equation*} S[k] = \sum \limits _{n=0} ^{N-1} s[n]\exp\left(-j2\pi\frac{k}{N}n\right) \end{equation*} In the above equation, $k$ is the index of

Symbolic representation of linear phase rotation that changes with frequency index

May 14, 2019 DSP

Effect of Time Shift in Frequency Domain

Children usually ask questions like “How many hours have passed?” And they have no idea about the start time to be taken as a reference. Just like the zero of a measuring tape, a zero reference for time plays a crucial role in analyzing the signal behaviour in time and frequency domains. Until now, we assumed that reference time $0$ coincides with the start of a sine and a cosine wave to understand the frequency domain. Later, we will deal with symbol timing synchronization problem in single-carrier systems and carrier frequency synchronization problem in multicarrier systems, both of which address the problem of finding this reference to prevent signal distortion. To solve those problems, we study the signals with arbitrary