On 2/25/12 5:41 AM, Philippe Strauss wrote:
> On 25 f&#4294967295;v, 10:44, Rick Lyons<R.Lyons@_BOGUS_ieee.org>  wrote:
>> On Fri, 24 Feb 2012 07:35:19 -0800 (PST), Philippe Strauss
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> <friendship7...@gmail.com>  wrote:
>>> Guys (Gals:),
>>
>>> I've changed the domain of my website containing some article on DSP:
>>
>>> http://www.strauss-acoustics.ch/
>>
>>> (previouslywww.philou.ch)
>>
>>> contains :
>>
>>> Pure javascript HTML5 canvas bilinear image interpolation
>>> Easy to read C Fast Fourier Transform (FFT) signal processing code
>>> FIR filter design experiment using the simplex method
>>> Z&#4294967295;lzer-Boltze (ZB) peak/notch parametric EQ in C
>>> An Objective Caml, object based computation pipeline pattern
>>
>>> Regards.
>>
>> Hello Philippe Strauss,
>>     Can you please tell me, is it possible to
>> make your FFT C code run on a 16-bit, fixed-point,
>> microcontroller chip?
>>
>> Thanks,
>> [-Rick-]
>
> Rick,
>
> No I haven't any fixed point or integer target in head when coding it,
> but given that it's a plain radix2 or 4 as found in references books
> on the topic, and relatively readable, maybe someone with such
> interest could add scaling between each butterfly loops relatively
> easily.

you mean, between the FFT passes, right?  for a simple radix2 
tukey-cooley FFT, there are log2(N) passes (where N is the number of FFT 
points).

this is called "block floating point".  the whole idea is that your 
fixed point data goes into each pass scaled to have an additional *2* 
guard bits on the left (the signed integer data would have the 3 MSBs 
identical).  this means that the magnitude of the numbers are no more 
than 1/4 full scale.  (audio guys would say it has 12 dB of headroom.)

so imagine your complex number as lying in a square of with each side of 
width 1/4 full scale.  multiplying by the DFT twiddle factor will only 
rotate the complex number which *could* increase the real or imaginary 
part by a factor sqrt(2).  then you add it to another complex number in 
the butterfly.  so the worst-case growth of either the real or imaginary 
values coming outa the butterfly is

     1/4  +  sqrt(2) * 1/4  =  0.604

so you are not going to overflow.

or if the butterfly is the other gender (decimation-in-time vs. 
decimation-in-frequency, i can't remember which is which), then the 
complex numbers are added before scaling with the twiddle factor.  then 
the worst case growth is

     sqrt(2) * (1/4 + 1/4)  =  0.707

so, in block floating point, you need to test each result to see if it 
has exceeded 1/4 full scale, and if it has, you set a bit that tells you 
for the next pass, you must divide the result of the butterfly by 2 (and 
increase the block exponent by 1 to keep the bookkeeper happy).

i realize that looking at this doesn't seem to guarantee against 
overflow in the worst case because 0.604 and 0.707 both exceed 0.5, but 
i know that this is how the block-floating FFT was supposed to work for 
the Mot (now Freescale) DSP56xxx chips.  if any result exceeded 1/4 in 
magnitude, a sticky bit was set that would tell you to change the 
scaling in the next pass.  it appears to me that it would possibly fail 
in preventing overflow and saturation given some data that was set up to 
the worst case.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On 25 f&#4294967295;v, 10:44, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
> On Fri, 24 Feb 2012 07:35:19 -0800 (PST), Philippe Strauss
>
>
>
>
>
>
>
>
>
> <friendship7...@gmail.com> wrote:
> >Guys (Gals:),
>
> >I've changed the domain of my website containing some article on DSP:
>
> >http://www.strauss-acoustics.ch/
>
> >(previouslywww.philou.ch)
>
> >contains :
>
> >Pure javascript HTML5 canvas bilinear image interpolation
> >Easy to read C Fast Fourier Transform (FFT) signal processing code
> >FIR filter design experiment using the simplex method
> >Z&#4294967295;lzer-Boltze (ZB) peak/notch parametric EQ in C
> >An Objective Caml, object based computation pipeline pattern
>
> >Regards.
>
> Hello Philippe Strauss,
> &#4294967295; &#4294967295;Can you please tell me, is it possible to
> make your FFT C code run on a 16-bit, fixed-point,
> microcontroller chip?
>
> Thanks,
> [-Rick-]

Rick,

No I haven't any fixed point or integer target in head when coding it,
but given that it's a plain radix2 or 4 as found in references books
on the topic, and relatively readable, maybe someone with such
interest could add scaling between each butterfly loops relatively
easily.


Regards.

On Fri, 24 Feb 2012 07:35:19 -0800 (PST), Philippe Strauss
<friendship7net@gmail.com> wrote:

>Guys (Gals:),
>
>I've changed the domain of my website containing some article on DSP:
>
>http://www.strauss-acoustics.ch/
>
>(previously www.philou.ch)
>
>contains :
>
>Pure javascript HTML5 canvas bilinear image interpolation
>Easy to read C Fast Fourier Transform (FFT) signal processing code
>FIR filter design experiment using the simplex method
>Z&#4294967295;lzer-Boltze (ZB) peak/notch parametric EQ in C
>An Objective Caml, object based computation pipeline pattern
>
>Regards.

Hello Philippe Strauss,
   Can you please tell me, is it possible to 
make your FFT C code run on a 16-bit, fixed-point, 
microcontroller chip?

Thanks,
[-Rick-]

Guys (Gals:),

I've changed the domain of my website containing some article on DSP:

http://www.strauss-acoustics.ch/

(previously www.philou.ch)

contains :

Pure javascript HTML5 canvas bilinear image interpolation
Easy to read C Fast Fourier Transform (FFT) signal processing code
FIR filter design experiment using the simplex method
Z�lzer-Boltze (ZB) peak/notch parametric EQ in C
An Objective Caml, object based computation pipeline pattern

Regards.