Skip to main content

# 9.1: Introduction

• • Contributed by C. Sidney Burrus
• Maxfield and Oshman Professor Emeritus (Electrical and Computer Engineering) at Rice University

Learning Objectives

• To study the Prime Factor Algorithm and the Winograd Fourier Transform Algorithm

The prime factor algorithm (PFA) and the Winograd Fourier transform algorithm (WFTA) are methods for efficiently calculating the DFT which use, and in fact, depend on the Type-1 index map from Multidimensional Index Mapping. The use of this index map preceded Cooley and Tukey's paper but its full potential was not realized until it was combined with Winograd's short DFT algorithms.

The number theoretic basis for the indexing in these algorithms may, at first, seem more complicated than in the Cooley-Tukey FFT; however, if approached from the general index mapping point of view of Multidimensional Index Mapping, it is straightforward, and part of a common approach to breaking large problems into smaller ones. The development in this section will parallel that in The Cooley-Tukey Fast Fourier Transform Algorithm.

The general index maps of Multidimensional Index Mapping must satisfy the Type-1 conditions which are

$K_1=aN_2\; \text{and}\; K_2=bN_1\; \text{with}\; (K_1N_1)=(K_2N_2)=1$

$K_3=cN_2\; \text{and}\; K_4=dN_1\; \text{with}\; (K_3N_1)=(K_4N_2)=1$

The row and column calculations in The Index Map are uncoupled by which for this case are

$((K_1K_4))_N=((K_2K_3))_N=0$

In addition, to make each short sum a DFT, the KiKi" role="presentation" style="position:relative;" tabindex="0">