Theoretical Maximum of DFT

Question

For any discrete input signal between +1 and -1, what is the theoretical maximum DFT?

If the input is a cosine of $N$ samples with amplitude $A$, the peak spectral magnitude is $A*N/2$. But what about any arbitrary waveform?

A square wave with the same amplitude as the cosine is composed of various sines, the fundamental frequency of which has a greater magnitude than the square wave. Therefore the Fourier transform of a square wave with amplitude also between $1$ and $-1$ is greater than the cosine with amplitude between $+1$ and $-1$.

But generalizing this to any waveform, ie a triangle wave, sawtooth wave, and also non geometrically "nice" waves, all with amplitudes between $+1$ and $-1$, what is the theoretical maximum?

I want to know because I need to represent the output of a DFT with 16 signed bits. However if the magnitude of the DFT is greater than $2^{15}$ I would need to scale. I therefore need to determine if this will ever happen (for any input waveform) and how much the scaling factor should be.

Thank you very much,

Answer 1

A simple bound is just the number of samples. Indeed, for $$ X_k = \sum_{n=0}^{N-1} x[n]e^{-2i\pi kn/N}$$ then obviously:

$$ |X_k| \le \sum_{n=0}^{N-1} \left|x[n]\right|\left|e^{-2i\pi kn/N}\right|$$ hence $$ |X_k| \le \sum_{n=0}^{N-1} \left|x[n]\right|\le N$$ if $-1\le x[n]\le 1$. The $N$ bound is s attained for a given $k$ when you choose a complex $x[n]=\overline{e^{-2i\pi kn/N}} = e^{2i\pi kn/N}$. If your input allows a constant signal (equal to one), $x[n]=1$, then this is attained for the zeroth frequency $X_0 = \sum_{n=0}^{N-1} 1 = N$. As a side note, if the signal length is a power of $2$, this is quite convenient.

For more restricted inputs, like real, zero-average signals only, there could be a tighter bound. A recent paper presented at SampTA 2017 provides DFT bounds for some random sequences (Bernoulli): Bounds on Discrete Fourier Transform of Random Mask (published version).

Answer 2

An upper bound for the absolute value of the DFT coefficients can be derived as follows:

$$|X[k]|=\left|\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}\right|\le \sum_{n=0}^{N-1}|x[n]|\le N$$

if we assume that $|x[n]|\le 1$ holds. For most practical signals, this bound is not very tight.

Answer 3

Parseval's theorem states that the energy in the output of the DFT is proportional to the input energy. That proportionality factor depends on how you define the DFT (whether you divide by the length, the square root of the length, or not at all).

For all practical implementations of the DFT (especially FFTs), we don't do that normalization. So, for example, if you transform a constant 1-vector $(1,\quad1,\quad1,\quad1,\quad1,\ldots)$ of length $N$, you also get an energy of $N\cdot 1$ at the output.

This is the simplest example that I could think of, but it's also the example that answers your question: Take that DFT. It's bound to be 0 everywhere but for the DC carrier, which is the sum of all input elements.

So, that is, like your cosine-that-fits-into-your-DFT example, one example that concentrates all energy into a single bin, and hence yields the highest possible output bin for any given input of the same power.

Now, scale that input by $A$, and you'll get $A\cdot N$ as output. Done: the maximum output allowable for an input that consists of $A + 0j$ in all elements is $AN$. Now, linearity applies, and so if you feed in $A+Aj$, you get $AN+ANj$ in the one output bin. So, $AN$ is the maximum real and imaginary part at the output you can get if both your input real and imaginary part are restricted to be less than or equal in absolute to $A$.