3.4 The prime factor algorithm

General index maps

$$n=(K_1{n}_1+K_2{n}_2)\mod N$$ $$n=(K_3{k}_1+K_4{k}_2)\mod N$$ $$n_1$$

0 1 N 1 1

0 1 N 1 1

0 1 N 2 1

0 1 N 2 1

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 $0$ to $N-1$ , 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

$N_1$ , $N_2$ relatively prime (greatest common denominator $1$ ) i.e. $\gcd (N_1, N_2)=1$

$K_1=a{N}_2$ and/or $K_2=b{N}_1$ and $\gcd (K_1, N_1)=1$ , $\gcd (K_2, N_2)=1$

Case ii

$N_1$ , $N_2$ not relatively prime: $\gcd (N_1, N_2)> 1$

$K_1=a{N}_2$ and $K_2\neq b{N}_1$ and $\gcd (a, N_1)=1$ , $\gcd (K_2, N_2)=1$ or $K_1\neq a{N}_2$ and $K_2=b{N}_1$ and $\gcd (K_1, N_1)=1$ , $\gcd (b, N_2)=1$ where $K_1$ , $K_2$ , $K_3$ , $K_4$ , $N_1$ , $N_2$ , $a$ , $b$ integers

Conditions for arithmetic savings

• $K_1{K}_4\mod N=0$ exclusive or $K_2{K}_3\mod N=0$ Common Factor Algorithm (CFA). Then $$X(k)={\mathrm{DFT}}_{Ni}(\text{twiddle factors}{\mathrm{DFT}}_{Nj}(x(n_1, n_2)))$$
• $K_1{K}_4\mod N$ and $K_2{K}_3\mod N=0$ Prime Factor Algorithm (PFA). $$X(k)={\mathrm{DFT}}_{Ni}({\mathrm{DFT}}_{Nj})$$ No twiddle factors!

Conditions for short-length transforms to be dfts

$K_1{K}_3\mod N=N_2$ and $K_2{K}_4\mod N=N_1$

Operation counts

• $N_2$ length- $N_1$ DFTs $N_1$ length- $N_2$ DFTs $$N_2{N}_1^2+N_1{N}_2^2=N(N_1+N_2)$$ complex multiplies
• Suppose $N=N_1{N}_2{N}_3{N}_{\mathrm{M}}$ $$N(N_1+N_2++N_M)$$ Complex multiplies