The basic ideas is to simply
reorder the
DFT computation to expose the redundancies in the
DFT , and
exploit these to reduce computation!
Three conditions must be satisfied to make
this map serve our purposes
Each map must be one-to-one from
to
, because we want to do the
same computation, just in a different
order.
The map must be cleverly chosen so that computation is
reduced
The map should be chosen to make the short-length
transforms be
DFTs . (Not essential, since fast algorithms for
short-length
DFT -like computations could be developed, but it
makes our work easier.)
Conditions for one-to-oneness of general index map
Case i
,
relatively prime (greatest common denominator
) i.e.
and/or
and
,
Case ii
,
not relatively prime:
and
and
,
or
and
and
,
where
,
,
,
,
,
,
,
integers
radix-2 ,
radix-4 eliminate all multiplies in short-length
DFTs, but have twiddle factors: PFA eliminates all twiddlefactors, but ends up with multiplies in short-length
DFTs .
Surprisingly, total operation counts end up being very similarfor similar lengths.