Store a FFT with a minimal amount of data

Question

I have an array x of length 1024 (stored as 16 bits integers, named for example np.int16 in numpy/python), i.e. the size of x is 1024*2 = 2048 bytes.

(Remark : x comes from an audio .wav file, stored as 16 bits integers, as it is very common. But it is also very common to interpret it as a float array, with values in $[-1, +1]$ by doing: x = x * 1.0 / 2^16)

When I take fft(x), as the input was real, there is some symmetry that makes that I only need to store half of the array fft(x), that's often also called rfft(x) : real fft.

• This means that, by taking fft, I translated 1024 real numbers into 512 complex numbers (i.e. can be viewed as 1024 real numbers again) : in a mathematical point of view, we have the same amount of data :

  1024 real coefficients -- rfft --> 1024 real coefficients

But in a programmaing point of view, is it possible to store, losslessly* and without compression, the fft of an array of 1024 elements of type int16 (using 2048 bytes) with 2048 bytes maximum ?

If not, what is the minimum number of bytes required to store the fft of such an array?

remark (*) : by losslessly I mean that the original x can be recovered later

Answer 1

In general, quantizing an FFT result is a lossy process. Given that the FFT twiddle factors are transcendental functions, any finite storage size will result in adding some quantization noise; and that noise increases as the resulting format decreases in bit size. For extremely sparse FFT results, it may be possible to compress those results, but those are statistically very rare cases.

Answer 2

OK, I can provide you an (almost) answer:

If you are using a lifting based realization of the complex twiddle factor multiplication with quantized coefficients, the word length will increase with three times the coefficient word length after performing the multiplication. Hence, a direct evaluation would give the initial data word length plus three times the coefficient word length plus 10 (which is the two-logarithm of 1024). This what is needed to store the exact result of the DFT computation using a direct computation. If you instead are using an FFT algorithm, you would be looking at at most nine twiddle factor stages, each adding three times the coefficient word length number of bits.

I guess neither of these numbers are actually what you are looking for, since you probably do not want to write your own DFT/FFT. Also, with these numbers, the question "What do you need the DFT for?" and "How good approximation of the DFT do you need?" arise pretty rapidly.

Answer 3

This is not exactly an answer (I hope it will become it soon) but a result based on experience :

import numpy as np
from scipy.io.wavfile import read, write
from scipy.fftpack import rfft, irfft

(fs, x) = read('nowomannocry_16bit_mono.wav')

y = rfft(x)
M = max(abs(y))
y *= 1.0 * (2**23-1) / M               # mapped into [-2^23, 2^23 -1]
y = np.round(y)
y = np.int32(y)   # here we store the fft by using the full width of 24 bits 

z = irfft(y) * M / (2**23-1)
z = np.round(z)
z = np.int16(z)
print z - x, max(abs(z-x))
# [0 0 0 ..., 0 0 0] 0

According to this small test (done on Bob Marley's No woman no cry, 16 bit, mono ;)), 24 bits seem to be enough to store the FFT of the original signal, in such a way that the original signal can be recovered by RFFT.

I tried with 16, 20, 22 bits, and it wasn't enough.

These are only experiences, but can something be proven in this direction ?