Complexity of not 2^n FFT

Hi,

what is the complexity of FFT computed on block lenght other then power 
of 2 ?
Is it still NlogN ?
Is this possible to write fast algorith if N is not power of 2 (loss of 
symmetry) ?

Thank you

Roman

Roman Rumian wrote:

> Hi,
>
> what is the complexity of FFT computed on block lenght other then power
> of 2 ?
> Is it still NlogN ?

roughly, but it depends on the radix

>
> Is this possible to write fast algorith if N is not power of 2 (loss of
> symmetry) ?
>

Yes.  Take a look at Smith & Smith's handbook of fast fourier transforms
(ieee press).  You might also look at blahut's book.  The full citations
are on the data sheet for the 16 point fft core found on my website.

>
> Thank you
>
> Roman

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

"Ray Andraka" <ray@andraka.com> wrote in message
news:401FA657.2575343D@andraka.com...
> > what is the complexity of FFT computed on block lenght other then power
> > of 2 ?
> > Is it still NlogN ?
>
> roughly, but it depends on the radix

Even if you had a prime-length FFT, you could do it in O(N log N) time with
the chrip-Z transform.

I wonder if there are any practical situations in which you'd actually want
to do that?

"Roman Rumian" <usun_torumian@agh.edu.pl> wrote in message
news:bvo36f$74g$1@galaxy.uci.agh.edu.pl...

> what is the complexity of FFT computed on block lenght other then power
> of 2 ?
> Is it still NlogN ?
> Is this possible to write fast algorith if N is not power of 2 (loss of
> symmetry) ?

Well, non power of 2 DFTs come in 3 flavors:
1) Product of relative prime factor,
2) Prime powers, and
3) Primes.

In case (1) above, there are a couple of ways to combine subtransforms
of length equal to the relative prime factors that avoid the phase or
twiddle factors necessary between stages of the Cooley-Tukey FFT, one
using the Chinese remainder theorem and another is that effectively
uses phi(M) different versions for each subtransform of length M.
I've never seen anyone implement the latter version for big M because
all the constants required could blow out cache.  For big M the
twiddle factors are down in the noise in any case.

If you want relative prime factor modules to build up solutions to
case (1) you need to also address cases (2) and (3).  I have some
of the latter two cases on my website,
http://home.comcast.net/~kmbtib/index.html .  Although I recently
concluded that many of my computational kernals are not optimal,
they still are relatively efficient compared to other approaches
I have seen.

Case (2) is amenable to Cooley-Tukey, but there are some refinements
possible that are a bit different from what works with powers of 2. I
tend to think of the prime power problem as three different cases:
powers of 2, powers of 3, and powers of larger primes.

To handle powers of larger primes, you are going to want to think
about the first power first, and this is case (3).  There are 2
main methods used for attacking this problem: Rader's method which
reduces the problem of computing a DFT of prime order P to that
of computing a convolution of composite order P-1, and the chirp-z
method which in fact works for any order and is very tempting to
use to solve any non-power-of-2 DFT problem in O(N*log(N)) time
because one relatively simple code can to the trick.  The most
efficient solutions at least for small P seem to require
suffering through the irregular number-theoretic agony of Rader.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

Matt Timmermans wrote:
> Even if you had a prime-length FFT, you could do it in O(N log N) time with
> the chrip-Z transform.
> 
> I wonder if there are any practical situations in which you'd actually want
> to do that?

I initially added an O(N log N) prime-size algorithm to FFTW for fun 
(using Rader's algorithm, not chirp-z), but the response from users was 
surprisingly positive.  Apparently, you have lots of applications where 
the user passes in some data to be transformed (e.g. an image, or a 
time-series measurement), and you don't want it to suddenly take hours 
if the user unluckily picked a prime size, but you don't mind losing a 
factor of 10, say.

Ray Andraka wrote:
> 
> The full citations
> are on the data sheet for the 16 point fft core found on my website.
> 

His data sheet says in part:

"The FFT core is used to transform a time domain sequence
to a frequency domain representation of the data. Inverse
Fourier Transforms may be obtained by conjugating the
input and output of the FFT. When combined with
reordering memory and a phase rotator, this 16 point kernel
can be used as a building block for larger transforms."

     AND

"The FFT core set uses the Winograd 16 point Fast Fourier
Transform algorithm to compute the 16 point discrete Fourier
transform of a complex vector. The core accepts 16 bit data
on the real and imaginary inputs and outputs 16 bit data on
each of the real and imaginary outputs."


1. Can someone point me to description of "Winograd" and/or other 16 
point transform? I suspect the smallness will allow me to see what's 
going on. I suffer from plaint in another thread of getting lost in 
'formal math'.

2. Can someone point me to description of how one would combine "small 
FFT's" to make a "large FFT"? Here i also suspect the explanation 
would be illuminating of how/why FFT/FT works.

[ Now if a certain gentleman on this forum could speed up publishing 
process, I might decrease bandwidth. PS an interlibrary loan system 
with acronym "MOIBUS" has first edition listed as available -- but CAN 
NOT deliver ;[

Matt Timmermans wrote:
> 
> Even if you had a prime-length FFT, you could do it in O(N log N) time with
> the chrip-Z transform.
> 
> I wonder if there are any practical situations in which you'd actually want
> to do that?

Sample rate conversion comes to mind.


Bob
-- 

"Things should be described as simply as possible, but no
simpler."

                                             A. Einstein

Richard Owlett wrote:

> Ray Andraka wrote:
> >
> > The full citations
> > are on the data sheet for the 16 point fft core found on my website.
> >
>
> His data sheet says in part:
>
> "The FFT core is used to transform a time domain sequence
> to a frequency domain representation of the data. Inverse
> Fourier Transforms may be obtained by conjugating the
> input and output of the FFT. When combined with
> reordering memory and a phase rotator, this 16 point kernel
> can be used as a building block for larger transforms."
>
>      AND
>
> "The FFT core set uses the Winograd 16 point Fast Fourier
> Transform algorithm to compute the 16 point discrete Fourier
> transform of a complex vector. The core accepts 16 bit data
> on the real and imaginary inputs and outputs 16 bit data on
> each of the real and imaginary outputs."
>
>

I refer you to the references on the data sheet.  Blahut's book has a
better treatment of the Winograd algorithm from a how it works
perspective, but you'll need to be comfortable with matrix math.
Smith&Smith gives more of a cookbook style treatment showing how to do the
winograd transform without explaining much as to where it comes from.
Basically, the FFT can be represented as a matrix multiplication.  The
Winograd transform decomposes the oeprations into three matrix multiplies,
the first and last of which have factors that use only combinations of 1
and j, while the middle multiply is a diagonal matrix.  The Winograd
algorithm is tailored to minimizing the number of multiplications needed
to perform the transform.  In the case of the 16 point winograd transform,
there are 18 real multiplies.

> 1. Can someone point me to description of "Winograd" and/or other 16
> point transform? I suspect the smallness will allow me to see what's
> going on. I suffer from plaint in another thread of getting lost in
> 'formal math'.

There are several algorithms for combining FFTs.  These are described in
enough detail to use in Smith and Smith.  The particular method I referred
to in the data sheet is the mixed radix algorithm.  Basically, you arrange
the input data in a matrix, then take the first pass of n point FFTs
across the m rows (doing m FFTs), then there is a phase rotation on each
point (a twiddle factor, if you will), followed by taking the FFTs down
the columns of the twiddled outputs from the first FFT.  There is also
some reordering that goes on to get the data out in natural order.  The
FFT Demystified link on the links page of my website also has a decent
primer on FFTs, particularly on making larger FFTs from smaller kernels.

>
>
> 2. Can someone point me to description of how one would combine "small
> FFT's" to make a "large FFT"? Here i also suspect the explanation
> would be illuminating of how/why FFT/FT works.
>
> [ Now if a certain gentleman on this forum could speed up publishing
> process, I might decrease bandwidth. PS an interlibrary loan system
> with acronym "MOIBUS" has first edition listed as available -- but CAN
> NOT deliver ;[

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930     Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

 "They that give up essential liberty to obtain a little
  temporary safety deserve neither liberty nor safety."
                                          -Benjamin Franklin, 1759

On Tue, 03 Feb 2004 14:51:03 -0600, Richard Owlett
<rowlett@atlascomm.net> wrote:

  (snipped)
>
>[ Now if a certain gentleman on this forum could speed up publishing 
>process, I might decrease bandwidth. PS an interlibrary loan system 
>with acronym "MOIBUS" has first edition listed as available -- but CAN 
>NOT deliver ;[


Hi Richard,

  since when do we allow gentlemen on this 
newsgroup?   ;-)

[-Rick-]

Hello Richard,
You may want to check out E. Oran Brigham's "The Fast Fourier Transform." He
covers a lot of the introductory FFT stuff, and I think you will find it
ueful.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



"Richard Owlett" <rowlett@atlascomm.net> wrote in message
news:102029je006lb5e@corp.supernews.com...
> Ray Andraka wrote:
> >
> > The full citations
> > are on the data sheet for the 16 point fft core found on my website.
> >
>
> His data sheet says in part:
>
> "The FFT core is used to transform a time domain sequence
> to a frequency domain representation of the data. Inverse
> Fourier Transforms may be obtained by conjugating the
> input and output of the FFT. When combined with
> reordering memory and a phase rotator, this 16 point kernel
> can be used as a building block for larger transforms."
>
>      AND
>
> "The FFT core set uses the Winograd 16 point Fast Fourier
> Transform algorithm to compute the 16 point discrete Fourier
> transform of a complex vector. The core accepts 16 bit data
> on the real and imaginary inputs and outputs 16 bit data on
> each of the real and imaginary outputs."
>
>
> 1. Can someone point me to description of "Winograd" and/or other 16
> point transform? I suspect the smallness will allow me to see what's
> going on. I suffer from plaint in another thread of getting lost in
> 'formal math'.
>
> 2. Can someone point me to description of how one would combine "small
> FFT's" to make a "large FFT"? Here i also suspect the explanation
> would be illuminating of how/why FFT/FT works.
>
> [ Now if a certain gentleman on this forum could speed up publishing
> process, I might decrease bandwidth. PS an interlibrary loan system
> with acronym "MOIBUS" has first edition listed as available -- but CAN
> NOT deliver ;[
>
>
>
>