Smaller DFTs from bigger DFTs

January 22, 20198 comments

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$$

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. herehere, 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).

[ - ]
Comment by January 22, 2019 Thanks Aditya for the well structured article.

An application area is lte:using only 2k fft for 20 or 10 or 5Mhz

fft: pad 5MHz or 10Mhz lte symbols with zeros, decimate output to jump bins

ifft: pad centre with zeros, decimate output

zero insertion doesn't work with 2k fft for 15MHz as bins get shifted

I think one way to do fft of 2k on 15MHz is upsampling to 20 size then decimate by 2/3

and for ifft downsample the 2k output to 15 case

but one thing I do is proof of concept numerically in Matalb rather than through equations.

Kaz

[ - ]
Comment by January 22, 2019 Thanks Kaz. Upsampling by an integer factor, followed by downsampling by an integer factor is indeed the way to realize resampling by a rational factor. One can theoretically relate the various operations via z-transforms, though it is always good to do some numerical validation. Also, in practice, one would do a polyphase implementation for efficiency rather than independent upsampling and downsampling steps.

[ - ]
Comment by January 23, 2019 practically (in FPGAs at least) zero padding makes the only viable option. Any other method implies storage. interleaving requires least storage but saving entire signal just to repeat it is not recommended.

[ - ]
Comment by January 23, 2019 Agreed that repeating the sequence is hardly a practical solution!

I also just realized that repeating the sequence is essentially adding two sequences: one with zero-padding at the end and one with zero-padding in the front. So the resultant DFT is simply a sum of the DFTs of those two zero-padded sequences. Could have gotten to the answer easily by using the results from the "zero padding" section rather than deriving it from first principles. Oh well :)

[ - ]
Comment by January 23, 2019 Hi Aditya. Your blog is interesting! When I read to up to your following lines I decided to stop reading:

1. Zero-padding x with N/2

2. Interlacing x with N/2

3. Appending a replica of x to itself

I want to see if I can figure out how to use your black box under those three situations before I continue reading your solutions.

[ - ]
Comment by January 23, 2019 Thank you for the interest and encouragement Rick! I have benefited immensely from your writings over the years and really appreciate your feedback.

Just for fun, another interesting situation to explore is x' = [x(0) x(0) x(1) x(1) ... ], i.e. each sample is repeated twice to create an N-point sequence

[ - ]
Comment by January 23, 2019 Hi Aditya. Thank you for your kind words.

I was able to figure out how to use your black box under the 1, 2, & 3 scenarios. That was a fun mental exercise! But now you've "thrown me a curve ball" with your last x' = [x(0) x(0) x(1) x(1) ... ] scenario. That last scenario deserves contemplation. Ha ha.

[ - ]
Comment by January 23, 2019 Constructing x' = [x(0) x(0) x(1) x(1) ... ] is certainly not the best way to solve the problem at hand, but it does create interesting spectra. The left and right halves end up being mirror images of each other (at least in magnitude) and the middle term is 0. The first N/2 points have the N/2 point DFT one is looking for, but each term has a complex phase which must be undone. The phase terms have a cosine shaped amplitude.

DFTs can indeed create remarkable patterns!

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.