From: pallav on
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
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
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. I’d dig out a
few references and tell you the titles, but it’s late here, and I
don’t 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, it’s
something else. I don’t know off-hand, and I’m 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 MATLAB’s FFTs are seen
by the programmer as sequential in, sequential out. Internally,
they’re doing bit reversals and a lot else. In hardware, you have to
be aware of every detail that’s hidden in the software. And you can
do an awful lot in hardware that you won’t see done in software.

You’re doing a 64 point radix 4 FFT. Presumably, it’s sequential in,
bit reverse out, after which you’d do the bit reversal. You’ll 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 don’t 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.

I’d have written a more detailed answer, but it’s late, so I’ll 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
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
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