Stephan M. Bernsee wrote:

> On 2004-08-11 05:43:51 +0200, stevenj@alum.mit.edu (Steven G. Johnson) 
> said:
> 
>> The output is still (in general) complex, but that's intrinsic to the
>> Fourier transform...even if you just want the amplitudes, as far as I
>> know there is no way to exploit this for a substantial speed gain.
> 
> 
> You could use the Fast Hartley transform. It's entirely real and conveys 
> the same information as the Fourier transform (for real inputs of 
> course). The magnitudes can be calculated from the transform output.

It takes a small amount of extra processing to recover the amplitudes.
The Fast Hartley Tranform is a minor repackaging of the specialized
varsions of the Fast Fourier Transform. (No free lunch in evidence
here!)

> If I understand the OP correctly, he is able to use floating point maths 
> for the actual transform and is just wondering whether he could use his 
> integers directly as input - that is very possible and easy to do, just 
> make sure you use floats for the computation and your magnitude output 
> to avoid qunatization issues.
> 
> Mark, "extreme numbers" doesn't sound right to me. "Extreme" suggests 
> something about their value. What about "enhanced numbers" or "flexible 
> numbers"? ;-)

On 2004-08-11 15:20:12 +0200, Jerry Avins <jya@ieee.org> said:

> Stephan M. Bernsee wrote:
> 
>    ...
> 
>> Mark, "extreme numbers" doesn't sound right to me. "Extreme" suggests 
>> something about their value. What about "enhanced numbers" or "flexible 
>> numbers"? ;-)
> 
> How about planar numbers, as compared to linear?
> 
> Jerry

Yes, I like that. Makes it intuitively clear what it's all about...
-- 
Stephan M. Bernsee
http://www.dspdimension.com

Hi,

Thank you to everyone that replied to my original post. I think I understand
the issue a bit better now.

Many Thanks

RG

"rg" <rg1117@hotmail.com> wrote in message
news:cfbg5r$7se$1@news.freedom2surf.net...
> Hi all,
>
> I have been looking at some fft libraries libraries and since DSP is not
my
> main area, there are some things that I am confused about. I noticed that
> all major fft libraries, e.g. FFTW & kissfft, use complex data types in
> which to store both the input and the output of the fourier transform.
>
> I was wondering, must this always be the case, or is it possible to just
use
> array of primitive data types like floats or integers. My application for
> fft is to perform spectral analysis on sound data that is stored as 16 bit
> integers. I normally have to copy this data to the real part of the
complex
> arrays, but I was wondering, would it be reasonable to have an FFT library
> that works directly on the array of integer. The only information that I
> need is the amplitude of the various frequency bins in a given frame and
> nothing more (e.g. phase information).
>
> I hope somebody can explain this situation to me. Many Thanks for your
help
> in advance.
>
> RG
>
>

Stephan M. Bernsee wrote:

   ...

> Mark, "extreme numbers" doesn't sound right to me. "Extreme" suggests 
> something about their value. What about "enhanced numbers" or "flexible 
> numbers"? ;-)

How about planar numbers, as compared to linear?

Jerry
-- 
... the worst possible design that just meets the specification - almost
a definition of practical engineering.                     .. Chris Bore
������������������������������������������������������������������������

> Mark, "extreme numbers" doesn't sound right to me. "Extreme" suggests 
> something about their value. What about "enhanced numbers" or "flexible 
> numbers"? ;-)

I prefer "Complete Numbers", since real numbers and imaginary numbers
are only a subset of C. Ever since school the name "complex" annoyed
me, because they are not really complex in the traditional sense of
the word.

Anyway, the point I was going to make was, for FFT of real data see
Maurice Bellanger's Book, "Digital Processing of Signals" which gives
a nice treatment.

On 2004-08-11 05:43:51 +0200, stevenj@alum.mit.edu (Steven G. Johnson) said:

> The output is still (in general) complex, but that's intrinsic to the
> Fourier transform...even if you just want the amplitudes, as far as I
> know there is no way to exploit this for a substantial speed gain.

You could use the Fast Hartley transform. It's entirely real and 
conveys the same information as the Fourier transform (for real inputs 
of course). The magnitudes can be calculated from the transform output.

If I understand the OP correctly, he is able to use floating point 
maths for the actual transform and is just wondering whether he could 
use his integers directly as input - that is very possible and easy to 
do, just make sure you use floats for the computation and your 
magnitude output to avoid qunatization issues.

Mark, "extreme numbers" doesn't sound right to me. "Extreme" suggests 
something about their value. What about "enhanced numbers" or "flexible 
numbers"? ;-)
-- 
Stephan M. Bernsee
http://www.dspdimension.com

"rg" <rg1117@hotmail.com> wrote...
> I have been looking at some fft libraries libraries and since DSP is not my
> main area, there are some things that I am confused about. I noticed that
> all major fft libraries, e.g. FFTW & kissfft, use complex data types in
> which to store both the input and the output of the fourier transform.

Note that all "major" FFT libraries also support specialized
transforms for purely real input data...i.e., an array of real numbers
as input.  This gains you about a factor of 2 in speed.

The output is still (in general) complex, but that's intrinsic to the
Fourier transform...even if you just want the amplitudes, as far as I
know there is no way to exploit this for a substantial speed gain.

(Of course, you still have to copy your array of integers, if that's
your input format, into an array of float/double, but this is a pretty
minor computational cost.  You could pretty easily modify an
out-of-place FFT routine to avoid this extra copy if you really
wanted.)

Cordially,
Steven G. Johnson

Randy Yates <yates@ieee.org> writes:
> [...]
> Yeah, that's one application. In general, they are a transform of elements
> taken from a finite field GF(p) (p a prime). 
>
> Mikko Tommila (which is linked from the page quoted by the guy you quoted, Mark),
>
>   http://www.apfloat.org/ntt.html
>
> has a whirlwind tour. However, I wouldn't expect to understand to any
> depth what he says there unless you've had at least a course in number
> theory and preferably some abstract algebra as well.
>
> --RY

PS: It may be interesting to note that Reed-Solomon codes (of block
error correcting code fame) can be viewed as a class of codes which
have a NTT resulting in 2t zeros, t the design distance of the code.
-- 
%  Randy Yates                  % "And all that I can do
%% Fuquay-Varina, NC            %  is say I'm sorry, 
%%% 919-577-9882                %  that's the way it goes..."
%%%% <yates@ieee.org>           % Getting To The Point', *Balance of Power*, ELO
http://home.earthlink.net/~yatescr

Mark Borgerding <mark@borgerding.net> writes:

> axlq wrote:
>> In article <cfbg5r$7se$1@news.freedom2surf.net>, rg <rg1117@hotmail.com> wrote:
> [snip]
>>>My application for fft is to perform spectral analysis on sound
>>>data that is stored as 16 bit integers. I normally have to copy
>>>this data to the real part of the complex arrays, but I was
>>>wondering, would it be reasonable to have an FFT library that works
>>>directly on the array of integer.
>
>> I've heard of NTT (Number Theoretic Transform) that seems like an FFT
>> using integers.  I've also heard of purely integer FFT algorithms.
>
> NTTs are a cool way of convolving two polynomials (think huge numbers,
> as used in crypto) by multiplying them in the frquency domain.

Yeah, that's one application. In general, they are a transform of elements
taken from a finite field GF(p) (p a prime). 

Mikko Tommila (which is linked from the page quoted by the guy you quoted, Mark),

  http://www.apfloat.org/ntt.html

has a whirlwind tour. However, I wouldn't expect to understand to any
depth what he says there unless you've had at least a course in number
theory and preferably some abstract algebra as well.

--RY

>
> It is based on the same principle used in fast convolution filtering (
> incidentally, I just presented two sessions about this at the comp.dsp
> conference).
>
>
>> Ah, here we go.  See http://www.jjj.de/fft/fftpage.html which has
>> links to C source for an integer FFT.
>
> FWIW, kissfft can also be compiled to use fixed-point (integer)
> operations in the FFT.   At a quick glance, I can see several
> advantages kissfft has over the above link:
> 	- arbitrary size, above is <= 1024
> 	- mixed radix, above is radix 2 only
> 	- clear licensing; kissft is bsd licensed, above is ???
> 	- correct rounding in multiplication, above always truncates
>
>
> HOWEVER ...
>
> I would NOT recommend using a fixed-point fft on a machine that has a
> fpu.  The fixed-point fft will be both slower and less accurate.
>
>
> -- Mark

-- 
%  Randy Yates                  % "She's sweet on Wagner-I think she'd die for Beethoven.
%% Fuquay-Varina, NC            %  She love the way Puccini lays down a tune, and
%%% 919-577-9882                %  Verdi's always creepin' from her room." 
%%%% <yates@ieee.org>           % "Rockaria", *A New World Record*, ELO   
http://home.earthlink.net/~yatescr

axlq wrote:
> In article <cfbg5r$7se$1@news.freedom2surf.net>, rg <rg1117@hotmail.com> wrote:
[snip]
>>My application for fft is to perform spectral analysis on sound
>>data that is stored as 16 bit integers. I normally have to copy
>>this data to the real part of the complex arrays, but I was
>>wondering, would it be reasonable to have an FFT library that works
>>directly on the array of integer.

> I've heard of NTT (Number Theoretic Transform) that seems like an FFT
> using integers.  I've also heard of purely integer FFT algorithms.

NTTs are a cool way of convolving two polynomials (think huge numbers, 
as used in crypto) by multiplying them in the frquency domain.

It is based on the same principle used in fast convolution filtering ( 
incidentally, I just presented two sessions about this at the comp.dsp 
conference).


> 
> Ah, here we go.  See http://www.jjj.de/fft/fftpage.html which has
> links to C source for an integer FFT.

FWIW, kissfft can also be compiled to use fixed-point (integer) 
operations in the FFT.   At a quick glance, I can see several advantages 
kissfft has over the above link:
	- arbitrary size, above is <= 1024
	- mixed radix, above is radix 2 only
	- clear licensing; kissft is bsd licensed, above is ???
	- correct rounding in multiplication, above always truncates


HOWEVER ...

I would NOT recommend using a fixed-point fft on a machine that has a 
fpu.  The fixed-point fft will be both slower and less accurate.


-- Mark