hi i'm working on an article about fft in pd and was generating some lists and graphs. i stuck, because the rfft produces only N/2 channels of real part and i expected to see one more? any help? marius.
It is normal to use only the first N/2 elements of an array result of a FFT of N samples of an audio signal in order to represent frequency decomposition or spectral representation.
I am taking a guess at what the problem is as N/2 figures prominently in many parts of the FFT process, due to the clever means of the FFT of reducing number of calculations required from order of N squared to order of N * log2 N instead.
The size of an array result of a FFT is the same size as the number of samples. So if there are N samples a real domain FFT on these samples is held in an array of size N.
The formula used to determine a frequency represented by an FFT is sample rate * rfft[i] / N using usual meanings
A magnitude scaling formula is also used.
A practical limitation on the accuracy of estimates of frequency determinations is predicted by the Nyquist Sampling Theorem, which states sampling frequency must be twice that of highest frequency that needs to be determined.
Hence array results of the FFT for i > N/2 are deemed unreliable.
John Heenan
-----Original Message----- From: marius schebella [mailto:marius.schebella@chello.at] Sent: Thursday, 24 January 2002 8:58 PM To: pd-list@iem.kug.ac.at Subject: [PD] fftchannels
hi i'm working on an article about fft in pd and was generating some lists and graphs. i stuck, because the rfft produces only N/2 channels of real part and i expected to see one more? any help? marius.
Messageagain
----- Original Message ----- From: John Heenan To: pd-list@iem.kug.ac.at Sent: Thursday, January 24, 2002 11:33 AM Subject: RE: [PD] fftchannels
The size of an array result of a FFT is the same size as the number of
samples. So if there are N samples a real domain FFT on > these samples is held in an array of size N.
John Heenan
in the help-patch of the rfft- i also read "the rfft outputs N/2 + 1 real parts". so the first value represents the DC and the last (N/2+1) should represent the nyquist... the imag-parts for both are always 0. (thatŽs the N/2-1).
marius.
I find the documentation in PD terse and so confusing. Normally I go the source code if I want to understand what is going on. In this case it is probably not much of a help as FFT is an infamous area in itself. In PD the FFT routines are written by Kevin Peterson, MIT Media Lab, EMS. In themselves they are terse and not exposed in a convenient object oriented style.
There are N array elements (or parts) to an FFT result from N samples. The FFT results are complex numbers (i.e. values with real and/or imaginary parts).
This above is purely a mathematical operation. Interpreting the results in the context of samples that represent audio is not mathematics. The complex results can be transformed into another array of pairs of numbers that can be said to represent 'magnitude' and 'phase'. To fully reconstitute the original samples with a inverse fft it is necessary to use the original FFT complex array.
For human auditory perception phase has little consequence.
In DSP (Digital Signal Processing) it is normal to indicate each element i up to the first N/2 elements of a FFT array result can be used to represent the magnitude of a frequency or a frequency bin (range of frequencies). The particular frequency or end point of a frequency bin is given by the equation sample rate * i / N The equation I gave in my previous posting was incorrect.
The actual magnitude of the frequency or bin is scaled or normalised.
For i = N/2 the frequency represented is the Nyquist frequency (half the sampling rate), since sample rate * (N/2) / N = sample rate / 2. N for FFT must be a power of two and so is always an even number.
PD allows you to plot the real and/or imaginary outlets of the rfft~ object.
I have read the full text of the help patch. It is implied there are N/2
- 1 parts of a real FFT that have values and there are other parts with
value 0. Of the N/2 + 1 parts with values it is stated two parts have no imaginary component. It is stated these are the DC and Nyquist parts.
This is just information. It is not the job of PD to explain or interpret this.
The statement in PD is technically true. There are values produced for i
N/2, however they are said in DSP literature to correspond to
'negative frequencies' and are generally ignored (using mathematics to over interpret physical phenomena causes endless philosophical horrors). At any rate these values don't have to be interpreted if the Nyquist sampling rule is applied. How convenient.
John Heenan
-----Original Message----- From: marius schebella [mailto:marius.schebella@chello.at] Sent: Thursday, 24 January 2002 10:00 PM To: pd-list@iem.kug.ac.at Subject: Re: [PD] fftchannels
Messageagain
----- Original Message ----- From: John Heenan To: pd-list@iem.kug.ac.at Sent: Thursday, January 24, 2002 11:33 AM Subject: RE: [PD] fftchannels
The size of an array result of a FFT is the same size as the number of
samples. So if there are N samples a real domain FFT on > these samples is held in an array of size N.
John Heenan
in the help-patch of the rfft- i also read "the rfft outputs N/2 + 1 real parts". so the first value represents the DC and the last (N/2+1) should represent the nyquist... the imag-parts for both are always 0. (that´s the N/2-1).
marius.
For those who may be upset by the lack of purity of 'ignoring' beautiful mathematics by ignoring fft values that correspond to values above the Nyquist cut-off frequency, there is a physical phenomena that it may be able to construe as linked to interpreting these values. The phenomena is called aliasing. I am not suggesting it can be an interpretation. Aliasing is akin to a disease in DSP (digital signal processing), to be avoided at all costs.
For the record, for a real FFT, for point N/2 + 1 to point N - 1, The real part of point N/2 + j is the same as the real part of point N/2
- j
The imaginary part of point N/2 + j is the same as the negative of the imaginary part of point N/2 - j
In fact if you want to obtain the real inverse fft to reconstitute signal values and values of the fft above N/2 have been ignored then it is necessary to reinsert them.
John Heenan
-----Original Message----- From: John Heenan [mailto:john@auscyber.com] Sent: Friday, 25 January 2002 4:44 AM To: pd-list@iem.kug.ac.at Subject: RE: [PD] fftchannels
The statement in PD is technically true. There are values produced for i
N/2, however they are said in DSP literature to correspond to
'negative frequencies' and are generally ignored (using mathematics to over interpret physical phenomena causes endless philosophical horrors). At any rate these values don't have to be interpreted if the Nyquist sampling rule is applied. How convenient.
HI Marius,
I noticed a line,
*(--out) = 0; /* to hell with it */
in d_fft.c... suspicious. It looks like rfft~ is dropping the Nyquist bin. I'll put that on the dolist.
cheers Miller
On Thu, Jan 24, 2002 at 10:58:16AM +0100, marius schebella wrote:
hi i'm working on an article about fft in pd and was generating some lists and graphs. i stuck, because the rfft produces only N/2 channels of real part and i expected to see one more? any help? marius.
-
John Heenan -
marius schebella -
Miller Puckette