Skip to main content ↑ ↓
Topic: Which Fourier transform algorithms are lossless? (Read 1341 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

Which Fourier transform algorithms are lossless?

This will be somewhat of an "explain like I'm 5" as I'm looking for a simple/simplified answer and don't understand most of those weird formulas at Wikipedia nor some of the very technical jargon thrown around.

Curious about the subject, I've been reading articles and wikis online and found some that say "Fourier transform is lossless", but can't imagine how it would be lossless as in software we usually have to choose an "FFT size". Doesn't that means it's taking a period of sound and averaging it?

Is it just the DFT that is lossless, or somehow the FFT is/can be lossless too?
How can a Fourier transform be lossless? Does it have to do with how it samples sound?
Could the MDCT be lossless?
What other Fourier analysis algorithms are and aren't lossless?
How much heavier is it to compute the DCT compared to FFT and other algorithms?

Re: Which Fourier transform algorithms are lossless?

Reply #1 –
An FFT takes a period of sound and divides it into frequency bands. The higher the FFT size, the more frequency resolution you get, but the less temporal resolution you get. Of course, the full image of a given FFT window is mostly sufficient to replicate its original time domain information, it is suggested to use a larger window than your sample window, and overlap the samplings.

For an example of convolution using FFT, with a sprinkling of comments:

https://bitbucket.org/losnoco/foo_input_adplug/src/master/simple_convolver.c

Basically, doing convolution in blocks using FFT is way faster than doing it sample by sample, dumb multiplying by every sample of the impulse onto the output. Probably off-topic, though.

Re: Which Fourier transform algorithms are lossless?

Reply #2 –
Quote from: MetaPixel on
Curious about the subject, I've been reading articles and wikis online and found some that say "Fourier transform is lossless",

Are they talking about the DFT (Fourier transform as done by computers) or the actual Fourier transform (math done on pen and paper)?  Pen and paper math is pretty lossless, if that even means anything.  DFT done by computers can be lossless, but can have tiny rounding error and so be lossy depending on how efficiently you want to implement it.

Quote from: MetaPixel on
but can't imagine how it would be lossless as in software we usually have to choose an "FFT size". Doesn't that means it's taking a period of sound and averaging it?

No, the size determines how many samples you are transforming at once.  The discrete Fourier transform takes a length of time and returns the frequencies in it.  The longer you the interval of time, the more precisely you can resolve frequencies in that time interval from one another at the expense of having less idea when in time they occured.  The product of time and frequency is actually constant, so the size just lets you decide how much time resolution you want to trade for frequency resolution.  Doesn't relate to how lossy/lossless it is.

Quote from: MetaPixel on
Is it just the DFT that is lossless, or somehow the FFT is/can be lossless too?

The FFT is a class of algorithms that can implement the DFT.  Since it is the only class that is ever used, for practical purposes they are the same thing.

Quote from: MetaPixel on
Could the MDCT be lossless?

Yes, for the same reason.

Quote from: MetaPixel on
What other Fourier analysis algorithms are and aren't lossless?

Any that implemented such that they have rounding error. 

Re: Which Fourier transform algorithms are lossless?

Reply #3 –
to be _really_ lossless, it would have to store results as infinite precision fractional numbers, which isn't possible. 
However, if you also encode/memoize the original amplitude resolution aka bit depth, you can set a margin of error to be small enough so that when you round values after inverse transform back to original resolution, it would exactly match original values. In that sense, yes, why not.
some ANC'd headphones + AutoEq-based impulse + Meier Crossfeed (30%)

Re: Which Fourier transform algorithms are lossless?

Reply #4 –
It's not lossless.     I'm not an expert, but you can't do FFT on one instant in time and you can't do DFT on a single sample so the individual-sample information is lost..    (And since digital audio in the computer is always sampled, it's always DFT.)

If you have a continuous-periodic complex signal, FFT can be mathematically perfect and reversible.   But real program material changes moment-to-moment.

Re: Which Fourier transform algorithms are lossless?

Reply #5 –
It's not done to a single sample, so this is not a problem.
some ANC'd headphones + AutoEq-based impulse + Meier Crossfeed (30%)

Re: Which Fourier transform algorithms are lossless?

Reply #6 –
Quote from: magicgoose on
to be _really_ lossless, it would have to store results as infinite precision fractional numbers, which isn't possible.

You don't have to store digits to infinite precision to be lossless.  Just enough that the rounding error doesn't round you up to the next digit.  That isn't that hard. 

Quote from: DVDdoug on
It's not lossless.     I'm not an expert, but you can't do FFT on one instant in time and you can't do DFT on a single sample so the individual-sample information is lost..    (And since digital audio in the computer is always sampled, it's always DFT.)

I am not able to make sense of this, but you can absolutely do an FFT of a single point.  The result is the same value back, which is lossless. 

Quote from: DVDdoug on
If you have a continuous-periodic complex signal, FFT can be mathematically perfect and reversible. 

The FFT can't be used on continuous or periodic signals.

Re: Which Fourier transform algorithms are lossless?

Reply #7 –
Quote from: saratoga on
Quote from: DVDdoug on
If you have a continuous-periodic complex signal, FFT can be mathematically perfect and reversible. 

The FFT can't be used on continuous or periodic signals.

You are correct, saratoga, but I'm sure that DVDDoug didn't have the mathematical/physical definition of "continuous-periodic signal" in mind when he said that. Instead, he probably was thinking on a periodic sampled signal in the sense of a sine wave or a similarly loopable signal.

In fact, if i remember correctly, DFT makes the assumption that the signal that is being sampled is periodic (in the sampled sense) so that the analysis can report the overall frequencies of the analysed sample.

Given that this would reduce considerably its usefulness, windowing functions are applied to the signal so that the resulting sample could ideally be looped without sound glitches and then doing overlapping analysis to be able to reconstruct what the windowing is altering.

It's sort of a simplistic way to explain it, but it's what the OP asked for.
Say we have a signal that is 12345678 and we have a DFT of 3 samples.
We would pad the beginning and end, so that we can have enough samples and not lose any part of the sample that interests us
We would group the samples as 012, 234, 456, 678, 800 (Ok, probably 3 samples is not a good idea in practice, but it's easier to describe)
We would apply a window over each of these blocks, which would affect the most the first and last sample of each group
We would analyse this and get the DFT data.
When reconstructing, we would overlap the output of the inverse DFT, effectively mixing it, and cut the extra samples that we know we added (that's the encoder delay and encoder padding of codecs )

In the end, DFT in itself is just an algorithm that transforms X amount of samples in the amplitude domain to X amount of samples in the frequency domain. It has no knowledge of sampling rate and bitdepth is only relevant in the sense of keeping rounding errors below the desired target.

Re: Which Fourier transform algorithms are lossless?

Reply #8 –
Quote from: MetaPixel on
This will be somewhat of an "explain like I'm 5" as I'm looking for a simple/simplified answer and don't understand most of those weird formulas at Wikipedia nor some of the very technical jargon thrown around.

Curious about the subject, I've been reading articles and wikis online and found some that say "Fourier transform is lossless", but can't imagine how it would be lossless as in software we usually have to choose an "FFT size". Doesn't that means it's taking a period of sound and averaging it?
Imagine a 2-element vector:
X= [x1 x2]

Next we do a linear transformation:
Y=X*W=[x1 x2]*[1 1;1 -1]
Y=[x1+x2 x1-x2]

X_hat = Y*[1 1; 1 -1]= [x1+x2 x1-x2] * [1 1; 1 -1]
=2[x1 x2] = 2*X

X_hat is identical to X as long as the summations and scaling can be done without loss of precision.

I think that getting exact results on a digital computer means doing fixed-point (integers) and allowing higher intermediate word widths than the range of inputs.

For audio, you may be operating on floating point input/intermediates and relatively large transforms. I don’t think that lossless is easily achieved in that case. You can get really small errors though, and interestingly the FFT can be more accurate than the DFT directly implemented.
Quote
How much heavier is it to compute the DCT compared to FFT and other algorithms?
The DCT can be computed as a FFT with some pre/post processing.

-k

Re: Which Fourier transform algorithms are lossless?

Reply #9 –
Quote from: knutinh on
I think that getting exact results on a digital computer means doing fixed-point (integers) and allowing higher intermediate word widths than the range of inputs.

For audio, you may be operating on floating point input/intermediates and relatively large transforms. I don’t think that lossless is easily achieved in that case. You can get really small errors though, and interestingly the FFT can be more accurate than the DFT directly implemented.


There is a famous paper on this:

https://www.researchgate.net/publication/2993190_Effects_of_Finite_Register_Length_in_Digital_Filtering_and_the_Fast_Fourier_Transform

(which is replicated in the author's even more famous textbook).  It turns out that rounding error in the FFT accumulates very, very slowly for fixed point, and even slower for floating point.  Thus in reality, even normal 32 bit floating point FFTs typically have no rounding error at all when used on audio signals unless the window size is enormous. 

For example:

Code: [Select]
test = single(fix(rand(1024,1)*2^20));
ft = fft(test);
ift = ifft(ft);

max(test-ift)

ans =

    0.2500


Thus a 1024 point FFT followed by a second 1024 point inverse FFT performed at 32 bit precision on a signal with 20 bits resolution produces a maximum rounding error of 1/4th of a bit.

Code: [Select]
>> max(test-round(ift))

ans =

     0

A simple rounding to the nearest quantization level removes all of the rounding error, showing that the transform and inverse transform were lossless.  Since you have to approximately square the window size to get an additional bit of rounding error, with a transform size of about 1 million, you have a pretty good chance that at least one sample will have half a bit of error and round the wrong way.  Doing it a few times here I got a mix of lossy (by 1 sample in a million digit transform) and lossless results.
 
SimplePortal 1.0.0 RC1 © 2008-2020