Some questions about radix-4 FFT algorithm using fixed-point arithmetic
in [DSP]
|
Prev: Control System: Routh-Hurwitz Stability Criterion with GUI MATLAB V3.2
Next: Some questions about radix-4 FFT algorithm using fixed-point arithmetic
From: pallav on 7 Feb 2010 01:13 Hello all, I'm very new to signal processing and want to learn to implement some basic FFT algorithms in hardware. First, I coded up the radix-4 Cooley- Tukey FFT algorithm in Matlab and it is working fine (compared it against the Matlab's builtin FFT) when I use floating point number to represent my signal. For hardware implementation, the input data is a complex (a + jb). The real/imaginary are each 8 bits. For fixed point arithmetic, they are represented as 1 bit for sign, 7 bits for fraction. I'm trying to implement fixed-point FFT in Matlab but am getting very strange results. In practice, if the input data is 8 bits each, how many bits should one use for the internal multiplication/addition? how many bits for integer part and how many for fraction? Furthermore, how many bits for the output? It is possible that the output point trasnform could be greater than [-1,1]. Is there a general rule to determine this? Here is my Matlab code (in case anyone is curious): http://pastey.net/132596 I'm noticing for fixed-point the transform points getting saturated at -1,1 but not sure how many bits to use internally and how to divide them between integer/fraction. Any ideas would be most helpful. Kind regards.
From: pallav on 7 Feb 2010 01:17 Sorry - I should mention that my test signal is just cos(x) + jsin(x) (euler's formula). So the real/imaginary values are in [-1,1]. So I just pick 64 random degrees (0-360) and generate these values. The length of the transform is 64 points. Kind regards.
From: kevin on 7 Feb 2010 23:28 On Feb 7, 1:17 am, pallav <pallavgu...(a)gmail.com> wrote: > Sorry - I should mention that my test signal is just cos(x) + jsin(x) > (euler's formula). So the real/imaginary values are in [-1,1]. So I > just pick 64 random degrees (0-360) and generate these values. The > length of the transform is 64 points. > > Kind regards. You are going to have to do a lot of reading. There are dozens (at least) papers about fixed and floating point FFT error analysis, and a number of sections in textbooks devoted to the subject. Id dig out a few references and tell you the titles, but its late here, and I dont feel like spending the next hour or so going through my collection. You could also Google it and get quite a few hits, but you might get just as much from reading a few of the earlier papers and book sections. If I recall, a output of a radix 2 butterfly can achieve a maximum value of 2.1414... , and that occurs for full scale inputs with one of the 45 degree twiddles (+/-.707... types). With radix 4, its something else. I dont know off-hand, and Im not going to look it up right now. Be careful viewing something in software and then trying to convert it to hardware. You do realize, of course, that MATLABs FFTs are seen by the programmer as sequential in, sequential out. Internally, theyre doing bit reversals and a lot else. In hardware, you have to be aware of every detail thats hidden in the software. And you can do an awful lot in hardware that you wont see done in software. Youre doing a 64 point radix 4 FFT. Presumably, its sequential in, bit reverse out, after which youd do the bit reversal. Youll have 3 columns of radix 4 butterflies, so you need inter-stage twiddles between columns 1 and 2, and another between columns 2 and 3. Your outputs will be in radix 4 based order. A transpose will get you sequential results. You might consider a 2 stage radix 8 instead. A radix 8 butterfly only has the +/- .707... twiddles, so there are fewer non-trivial twiddles to deal with. And the +/- .707 twiddles dont require a full scale multiplier. Depending on your word size, you might be able to do them with as little as one or two full adders. Plus, you have only 2 columns of radix 8 butterflies, with only one group of inter-stage twiddles to deal with. Id have written a more detailed answer, but its late, so Ill stop here. But be prepared to do a lot of reading, and then a lot more when you start looking into the hundreds of different hardware architectures you might choose to use. Kevin McGee
From: kevin on 8 Feb 2010 00:32 On Feb 7, 11:28 pm, kevin <kevinjmc...(a)netscape.net> wrote: > If I recall, a output of a radix 2 butterfly can achieve a maximum > value of 2.1414... , I meant to write: a maximum of 2.414... Dang! Now it's even later than before. Kevin McGee
From: John Monro on 8 Feb 2010 01:53
kevin wrote: > On Feb 7, 11:28 pm, kevin <kevinjmc...(a)netscape.net> wrote: >> If I recall, a output of a radix 2 butterfly can achieve a maximum >> value of 2.1414... , > > > I meant to write: a maximum of 2.414... > > Dang! Now it's even later than before. > > Kevin McGee I say 2.828 Maybe we can average these values :-) Regards, John |