Smaller DFTs from bigger DFTs

Aditya Dua 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$...


Smaller DFTs from bigger DFTs

Aditya Dua 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$...