Smaller DFTs from bigger DFTs

• Basics
• DFT_FFT

Introduction

Let's consider the following hypothetical situation: You have a sequence $x$ with $N/2$ points and a black box which can compute the DFT (Discrete Fourier Transform) of an $N$ point sequence. How will you use the black box to compute the $N/2$ point DFT of $x$? While the problem may appear to be a bit contrived, the answer(s) shed light on some basic yet insightful and useful properties of the DFT.

On a related note, the reverse problem of computing an $N$ point DFT using a black box that can only compute an $N/2$ point DFT is elegantly addressed in this post (and in several textbooks, of course) and forms the backbone of the FFT algorithm.

We will consider three different solutions to this problem, each of which will highlight a distinct property of the DFT. The first step in each of these solutions is to create an $N$ point sequence which serves as input to our black box. 

1. Zero-padding $x$ with $N/2$ zeros
2. Interlacing $x$ with $N/2$ zeros
3. Appending a replica of $x$ to itself

The final step in each solution will be to select an appropriate $N/2$ point subsequence from the $N$ point output sequence produced by the black box. Each approach is discussed in a separate section below.

Before we proceed, let's explicitly write down the $N/2$ point DFT of $x$ we desire to compute.

$$X(k) = \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N/2}}, \; k=0,1, ..., {N \over 2}-1$$

Zero padding

Let's consider an approach where $N/2$ zeros are padded to the end of $x$ to construct the $N$ point sequence $\tilde{x} = [\underbrace{x}_{N/2} \; \underbrace{0 \; 0 \; ... \; 0}_{N/2}] = [x \; 0_{N/2}]$. The $N$ point DFT of $\tilde{x}$ is computed as

$$\tilde{X}(k) = \sum_{n=0}^{N-1} \tilde{x}(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} \underbrace{\tilde{x}(n)}_{=x(n)} e^{{-j2 \pi kn \over N}} + \sum_{n=N/2}^{N-1} \underbrace{\tilde{x}(n)}_{=0} e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

This has started to resemble the result we want, but one more step is required. Let's split the $N$ point sequence $\tilde{X}$ into even ($k=2m$) and odd terms ($k=2m+1$) and inspect the even terms

$$\tilde{X}(2m) = \sum_{n=0}^{N/2-1} x(n) e^{{-j4 \pi mn \over N}}, \; m=0,1, ..., {N \over 2}-1$$

$$ \implies \tilde{X}(2m) = \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi mn \over N/2}} = X(m), \; m=0,1, ..., {N \over 2}-1$$

Thus, we can extract the $N/2$ point DFT of $x$ from the DFT of its zero-padded version simply by sampling the even points. 

Notes

The zero padding operation increases the size of the DFT and results in a higher resolution of frequency bins. While only the even points in the DFT of the zero-padded sequence are relevant to us, the odd points provide an interpolation between the even points and hence result in an overall smoother spectral output. This "trick" can be used to get a smoother visualization of the spectrum or to get more refined estimates of the amplitudes of spectral bins of interest. Note, however, that zero-padding does not create any new information, i.e. frequency components which are otherwise unresolvable in the original input will not magically get resolved by padding the input with zeros. The only way to improve frequency resolution is to consider a longer segment of the input for analysis. This is a common point of confusion and has been addressed in many a blog (e.g. here, here, and here)

Extensions

What if we had padded the zeros at the start of the signal $x$ or had placed $x$ in the middle with $N/4$ zeros on either side? Those well-versed with properties of the DFT will immediately recognize these two configurations are merely circular shifts (mod $N$) of $\tilde{x} = [x 0_{N/2}]$, which can be related to a phase component in spectral domain. Nevertheless, it is instructive to walk through the analysis for one of them.

Let's say we defined $\tilde{x} = [0_{N/2} \; x]$. The $N$ point DFT of $\tilde{x}$ is computed as

$$\tilde{X}(k) = \sum_{n=0}^{N-1} \tilde{x}(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} \underbrace{\tilde{x}(n)}_{=0} e^{{-j2 \pi kn \over N}} + \sum_{n=N/2}^{N-1} \underbrace{\tilde{x}(n)}_{=x(n-N/2)} e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=N/2}^{N-1} x(n-N/2) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi k(n-N/2) \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}} \cdot \underbrace{e^{j \pi k}}_{(-1)^k}, \; k=0,1, ..., N-1$$

$$= (-1)^k \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

Similar to the zero-padding case we originally evaluated, the even terms of $\tilde{X}(k)$ give us precisely the result we need. The odd terms have the same magnitude as the case where the zeros were padded at the end (i.e. we still get the same smoothing effect in the magnitude spectrum), though their phase is shifted by $\pi$. A nearly identical analysis shows that when $N/4$ zeros each are padded on both sides of $x$, the desired $N/2$ point DFT can again be recovered by sampling the even points of the $N$ point DFT of the padded sequence.

Interlacing with zeros

This time let's insert a zero after each element of $x$ to construct $\tilde{x} = [x(0) \; 0 \; x(1) \; 0 \; ... \; x(N/2-1) \; 0]$. The $N$ point DFT of $\tilde{x}$ is computed as

$$\tilde{X}(k) = \sum_{n=0}^{N-1} \tilde{x}(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$=\sum_{n \text{ even}} \underbrace{\tilde{x}(n)}_{x(n)} e^{{-j2 \pi kn \over N}} + \sum_{n \text{ odd}} \underbrace{\tilde{x}(n)}_{0} e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{m=0}^{N/2-1} \underbrace{\tilde{x}(2m)}_{x(m)} e^{{-j4 \pi km \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{m=0}^{N/2-1} x(m) e^{{-j2 \pi km \over N/2}}, \; k=0,1, ..., N-1$$

We are very close. We already have $\tilde{X}(k) = X(k)$ for $0 \leq k \leq N/2-1$, but what about the remaining $N/2$ points? Let's evaluate $\tilde{X}(k)$ for $k \geq N/2$, or equivalently, $\tilde{X}(N/2+p)$ for $0 \leq p \leq N/2-1$. 

$$\tilde{X}(N/2+p) = \sum_{m=0}^{N/2-1} x(m) e^{{-j2 \pi (N/2+p)m \over N/2}}, \; p=0,1, ..., N/2-1$$

$$= \sum_{m=0}^{N/2-1} x(m) e^{{-j2 \pi pm \over N/2}} \cdot \underbrace{e^{-j 2 \pi m}}_{=1}, \; p=0,1, ..., N/2-1$$

$$ = \tilde{X}(p) = X(p), \; p=0,1, ..., N/2-1$$

This implies that the first $N/2$ points of the DFT of the zero-interlaced sequence exactly match our desired $N/2$ point DFT and the remaining $N/2$ points are merely a replica of the first $N/2$ points (and can therefore be discarded). 

Notes

Inserting  a zero after each sample results in a duplication of the spectrum. This result can be generalized, i.e. inserting $P$ zeros after each sample results in a $P$-fold replication of the spectrum. Further, by duality, interlacing the spectrum with zeros results in replication of the input sequence (at the output of the inverse DFT). This process of inserting zeros is referred to as upsampling in digital signal processing. I will not attempt to explain all the nuances of upsampling, but will refer the reader to the following post.

Repeating the sequence

Our final method is to construct an $N$ point sequence as follows: $\tilde{x} = [x \; x]$. The $N$ point DFT of $\tilde{x}$ is computed as

$$\tilde{X}(k) = \sum_{n=0}^{N-1} \tilde{x}(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} \underbrace{\tilde{x}(n)}_{=x(n)} e^{{-j2 \pi kn \over N}} + \sum_{n=N/2}^{N-1} \underbrace{\tilde{x}(n)}_{=x(n-N/2)} e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}} + \sum_{n=N/2}^{N-1} x(n-N/2) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}} + \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi k(n-N/2) \over N}}, \; k=0,1, ..., N-1$$

$$= \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}} + \sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}} \cdot \underbrace{e^{j k \pi}}_{(-1)^k}, \; k=0,1, ..., N-1$$

$$ = [1 + (-1)^k]\sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi kn \over N}}, \; k=0,1, ..., N-1$$

Like we did in the zero padding case, let's split the $N$ point sequence $\tilde{X}$ into even ($k=2m$) and odd terms ($k=2m+1$). The odd terms go to zero and the even terms can be written as

$$\tilde{X}(2m) = 2\sum_{n=0}^{N/2-1} x(n) e^{{-j2 \pi mn \over N/2}} = 2X(m), \; m=0,1, ..., {N \over 2}-1$$

Thus, similar to the zero padding case, we can get the desired result by sampling the even terms from the $N$ point DFT of $\tilde{x} = [x \; x]$.

Notes

Not surprisingly, we have derived the dual of the upsampling result. When we interlaced the input sequence with zeros, it ended up creating a replica in spectral domain. When we created a replica of the input sequence, it resulted in an upsampling effect in spectral domain. In both the zero padding and replication approaches, the desired result was contained in the even terms of the $N$ point DFT output. However, in the former case we got a smoothed version of the spectrum, whereas in the latter case we got an upsampled version of the spectrum.

Summary

In this post, we addressed the hypothetical problem of computing the $N/2$ point DFT of a sequence given a black box that can only compute an $N$ point FFT. We examined three different approaches, namely zero padding, upsampling, and replication of the signal, each of which allowed us to explore interesting and useful properties of the DFT, including the relations between the three approaches. The results derived here are well known (and can also be generalized), but I hope working through the detailed derivations in a simplified problem setup will be instructive for those getting their hands dirty with DFT/FFT based frequency analysis for the first time (or even those just revisiting familiar concepts).

Sign in