0.1 Algorithms  (Page 5/5)

The sum over $x_{4n_4}$ is now substituted with $U_k$ (where $k=0,\cdots ,N/4-1$ ), while the sums over $x_{8n_8+2}$ and $x_{8n_n-2}$ are respectively substituted with $Y_k$ and $Y_k^{\text{'}}$ (where $k=0,\cdots ,N/8-1$ ) and the sums over $x_{4n_4+1}$ and $x_{4n_4-1}$ respectively substituted with $Z_k$ and $Z_k^{\text{'}}$ (where $k=0,\cdots ,N/4-1$ ), simplifying [link] thus:

As with earlier examples, computation is factored out of [link] by exploiting periodicity in the sub-transforms and symmetries in the twiddle factors. [link] is first expressed as a parametric equation of eight parts:

where $k=0,\cdots ,N/8-1$ and $\forall p\in \left\{0,\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8}\right\}$ . By exploiting periodicity in the sub-transforms:

and the following symmetries in the twiddle factors:

[link] is rewritten thus:

By applying terms with the appropriate scaling, viz. ${\alpha }_{N,k}=s_{N/4,k}/s_{N,k}$ , ${\beta }_{N,k}=s_{N/8,k}/s_{N/2,k}$ , ${\gamma }_{N,k}=s_{N/4,k+N/8}/s_{N,k+N/8}$ , ${\delta }_{N,k}=s_{N/2,k}/s_{N,k}$ and ${ϵ}_{N,k}=s_{N/2,k+N/8}/s_{N,k+N/8}$ , [link] now becomes:

Assuming that the scaling factors are absorbed into precomputed twiddle factors where possible (e.g., ${\alpha }_{N,k}{\omega }_N^k$ is a single precomputed constant), computing [link] requires about $(68/8)N$ real operations, in contrast to $(72/8)N$ operations for [link] . Further assuming that operations are skipped in the cases where precomputed constants are of the form $\pm 1$ or $\pm i$ , a further 28 real operations are saved in [link] . Thus the arithmetic cost of [link] can be expressed with the following recurrence relation:

Bernstein gives the exact solution of [link] as  [link] :

for $n\ge 2$ .

[link] is scaled by $s_{N,k}$ , but if the application is convolution in frequency, the scaling could beabsorbed into the filter, and the cost of scaling the results back to $X_k$ avoided. Otherwise, a split-radix FFT can be used to change basis, absorbing the scaling into the twiddle factors of the $x_{4n_4+1}$ and $x_{4n_4-1}$ terms:

where $Z_k$ and $Z_k^{\text{'}}$ are now recursively computed with the tangent FFT of [link] , and the $U_k$ terms are themselves computed with [link] . The arithmetic cost of computing the tangent FFT in the traditional basis is thus expressed:

giving rise to Van Buskirk's exact operation count of  [link] :

for $n\ge 2$ .