I'm thinking about having a play with a software-based radio, based on a
heavily hacked-up radio and an IF-to-AF down-converter (basically, tap
the IF, downconvert to AF, then use a sound card to digitise it). In any
case, enough about the hardware -- that's not the issue.
I've got some code for an FFT from the O'Reilly "C++ Cookbook" (section
11.17, example 11-33):
template<class Iter_T>
void fft(Iter_T a, Iter_T b, int log2n)
{
typedef typename iterator_traits<Iter_T>::value_type complex;
const complex J(0, 1);
int n = 1 << log2n;
for (unsigned int i=0; i < n; ++i) {
b[bitReverse(i, log2n)] = a[i];
}
for (int s = 1; s <= log2n; ++s) {
int m = 1 << s;
int m2 = m >> 1;
complex w(1, 0);
complex wm = exp(-J * (PI / m2));
for (int j=0; j < m2; ++j) {
for (int k=j; k < n; k += m) {
complex t = w * b[k + m2];
complex u = b[k];
b[k] = u + t;
b[k + m2] = u - t;
}
w *= wm;
}
}
}
(According to the book, an earlier version of this code was posted to
this group -- the book very helpfully doesn't give a date/time or Message-
ID or even a subject to help find it...)
How would I go about converting this from an FFT to an inverse-FFT?
I've had a quick look round the 'net, and the most I've found was a quick
note on Wikipedia -- "the inverse DFT is the same as the DFT, but with
the opposite sign in the exponent and a 1/N factor". Do I really just
need to flip the sign on PI (i.e. make it negative)?
Sorry if this seems like a stupid question, it just seems a little too
easy...!
Thanks,
--
Phil.
usenet09@philpem.me.uk
http://www.philpem.me.uk/
If mail bounces, replace "09" with the last two digits of the current
year.
Converting FFT to inverse-FFT
Started by ●December 15, 2009
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote: ...> (According to the book, an earlier version of this code was posted to > this group -- the book very helpfully doesn't give a date/time or Message- > ID or even a subject to help find it...)Search comp.dsp for the author's name. That should narrow it down.> How would I go about converting this from an FFT to an inverse-FFT? > > I've had a quick look round the 'net, and the most I've found was a quick > note on Wikipedia -- "the inverse DFT is the same as the DFT, but with > the opposite sign in the exponent and a 1/N factor". Do I really just > need to flip the sign on PI (i.e. make it negative)? > > Sorry if this seems like a stupid question, it just seems a little too > easy...!It is that easy. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote:> > How would I go about converting this from an FFT to an inverse-FFT? >Scale by factor 1/N and use -sin(x) instead of sin(x).> Sorry if this seems like a stupid question, it just seems a little too > easy...!Stupid question indeed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote:> > How would I go about converting this from an FFT to an inverse-FFT? >Scale by factor 1/N and use -sin(x) instead of sin(x).> Sorry if this seems like a stupid question, it just seems a little too > easy...!Stupid question indeed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote:> > How would I go about converting this from an FFT to an inverse-FFT? >Scale by factor 1/N and use -sin(x) instead of sin(x).> Sorry if this seems like a stupid question, it just seems a little too > easy...!Stupid question indeed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote:> > How would I go about converting this from an FFT to an inverse-FFT? >Scale by factor 1/N and use -sin(x) instead of sin(x).> Sorry if this seems like a stupid question, it just seems a little too > easy...!Stupid question indeed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●December 15, 20092009-12-15
Philip Pemberton wrote:> > How would I go about converting this from an FFT to an inverse-FFT? >Scale by factor 1/N and use -sin(x) instead of sin(x).> Sorry if this seems like a stupid question, it just seems a little too > easy...!Stupid question indeed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●December 15, 20092009-12-15
On 15 Dec 2009 12:46:41 GMT, Philip Pemberton <usenet09@philpem.me.uk> wrote:>How would I go about converting this from an FFT to an inverse-FFT? > >Do I really just >need to flip the sign on PI (i.e. make it negative)?Another way to accomplish the same thing is to use the forward FFT algorithm for both the forward transform and the inverse transform, but reverse the time-order of the outputs of the inverse transform. [0,1,2,...,N-1] becomes [0,N-1,N-2,...,1]. Greg
Reply by ●December 15, 20092009-12-15
On Tue, 15 Dec 2009 08:54:54 -0500, Jerry Avins wrote:> Search comp.dsp for the author's name. That should narrow it down.Huh, I can't believe I didn't think of that first... I guess I'm too used to books cribbing code from USENET and then saying nothing about where it came from.>> How would I go about converting this from an FFT to an inverse-FFT? >> >> I've had a quick look round the 'net, and the most I've found was a >> quick note on Wikipedia -- "the inverse DFT is the same as the DFT, but >> with the opposite sign in the exponent and a 1/N factor". Do I really >> just need to flip the sign on PI (i.e. make it negative)? >> >> Sorry if this seems like a stupid question, it just seems a little too >> easy...! > > It is that easy.Do I need to apply any additional processing to the input data? What about the "1/n factor"? Thanks, -- Phil. usenet09@philpem.me.uk http://www.philpem.me.uk/ If mail bounces, replace "09" with the last two digits of the current year.
Reply by ●December 15, 20092009-12-15
On 15 Des, 16:46, Philip Pemberton <usene...@philpem.me.uk> wrote:> Do I need to apply any additional processing to the input data?No.> What about the "1/n factor"?It's there to ensure that the round-trip y = ifft(fft(x)); returns the same data as the input (to within numerical precision). The theory is that Parseval's identity hold, that the DFT'd data should have the same norm as the input data: sum(x[n]^2) == sum(|X[k]|^2) where X = dft(x). In practice, this would mean that one needs a 1/sqrt(N) scaling factor both in the DFT and IDFT. To save some computations the convention is to drop the scaling factor in the forward DFT and instead compensate with an 1/N scaling factor in the IDFT. The downside of all this is that Parseval's identity does *not* hold with the FFT, one needs to include the missing scaling factors. Rune
