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

rg wrote:
> 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
> 
> 

If you want an FFT of a real (non-complex) sequence, there are 
optimizations for this in both fftw and kissfft.

Sorry to disappoint you, but complex numbers still need to get involved 
with an FFT at some point.  If you are not tied to using a Fourier 
transform, but rather just need some spectral info, you might be able to 
use a DCT instead.  It can deal exclusively with real numbers.  You'll 
need to decide if a DCT is ok for your needs.

Complex numbers really aren't that bad.  They're like crabgrass -- they 
get a bum rap because of the name.  I'm going to start calling them 
"Extreme Numbers" whenever to give their image a boost.

Anyway, only about half the frequency spectrum is needed, since the 
other half is the Extreme Number conjugate.  I say "about half" since 
both the dc and Nyquist bin (if present) are needed to fully describe 
the signal.  Conveniently, the imaginary parts of these bins are zero 
for a real time signal, so these parts can be omitted for compression -- 
making the total number of floats the same in both the time and 
frequency domain. Cool, huh?.

I guess I'm throwing a lot of semi-useless information at you.  Here's 
what you probably wanted:

For real ffts in fftw, use
fftw[f?]_plan_dft_r2c_1d and ..._c2r_1d.

For real ffts in kissfft, include and use the
kiss_fftr.h and .c files from the "tools" directory.


Cheers,
   Mark

In article <cfbg5r$7se$1@news.freedom2surf.net>, 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.
>
>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.

A FFT of real data gives a complex result.  That's the way it is.

However, there is a trick you can use if you have only real input
data.  According to Numerical Recipes in C++, "the method is to pack
the real input array cleverly, without extra zeros, into a complex
array of half its length. One then performs a complex FFT on this
shorter length; the trick is then to get the required answer out of
the result."

...and they provide source code to do this.  Note that you can't get
away from complex data, but what they describe is a more efficient
way to calculate an FFT on real input data that has no imaginary
component.  At the end, you just calculate magnitude of each complex
pair.

See http://www.library.cornell.edu/nr/cbookcpdf.html and read chapter
12, especially section 12.3.

>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.

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

-Alex
[posted and emailed]

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

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

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

"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

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

> 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.

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
������������������������������������������������������������������������