Image Processing

where W = exp(−j2π/16) = 0.9239 – j0.3827. This product uses six nontrivial operations of multiplication by the twiddle factors W^t, t = 1, 2, 3, 5, 6, 7. The eight-point DFT requires two operations of multiplication. Therefore the calculation of 24 eight-point DFTs in the splitting of the 16 × 16-point DFT requires 24 · 8 operations of multiplication. The calculation of the four-point DFTs over the modified splitting-signals of length four was described in Example 2.3. Each such transform uses two operations of multiplication. The total number of operations of multiplication required to calculate the 16 × 16-point DFT by the paired transform is calculated by

${m^{\prime }}_{16,16}=24\left(m_8+8-2\right)+12\left(m_4+4-2\right)=24\left(2+6\right)+12\left(2\right)=192+24=216.$

We note for comparison, that ...