Skip to main content
Engineering LibreTexts

6.5: The Automatic Generation of Winograd's Short DFTs

  • Page ID
    1997
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Introduction

    Efficient prime length DFTs are important for two reasons. A particular application may require a prime length DFT and secondly, the maximum length and the variety of lengths of a PFA or WFTA algorithm depend upon the availability of prime length modules.

    This discusses automation of the process Winograd used for constructing prime length FFTs for \(N<7\) and that Johnson and Burrus extended to \(N<19\). It also describes a program that will design any prime length FFT in principle, and will also automatically generate the algorithm as a C program and draw the corresponding flow graph.

    Winograd's approach uses Rader's method to convert a prime length DFT into a \(P-1\) length cyclic convolution, polynomial residue reduction to decompose the problem into smaller convolutions, and the Toom-Cook algorithm. The Chinese Remainder Theorem (CRT) for polynomials is then used to recombine the shorter convolutions. Unfortunately, the design procedure derived directly from Winograd's theory becomes cumbersome for longer length DFTs, and this has often prevented the design of DFT programs for lengths greater than \(19\).

    Here we use three methods to facilitate the construction of prime length FFT modules. First, the matrix exchange property is used so that the transpose of the reduction operator can be used rather than the more complicated CRT reconstruction operator. This is then combined with the numerical method for obtaining the multiplication coefficients rather than the direct use of the CRT. We also deviate from the Toom-Cook algorithm, because it requires too many additions for the lengths in which we are interested. Instead we use an iterated polynomial multiplication algorithm. We have incorporated these three ideas into a single structural procedure that automates the design of prime length FFTs.

    Matrix Description

    It is important that each step in the Winograd FFT can be described using matrices. By expressing cyclic convolution as a bilinear form, a compact form of prime length DFTs can be obtained.

    If \(y\) is the cyclic convolution of \(h\) and \(x\), then \(y\) can be expressed as

    \[y=C\left [ Ax.\ast Bh \right ] \nonumber \]

    where, using the Matlab convention, .* represents point by point multiplication. When \(A\), \(B\) and \(C\) are allowed to be complex, \(A\) and \(B\) are seen to be the DFT operator and \(C\), the inverse DFT. When only real numbers are allowed, \(A\), \(B\) and \(C\) will be rectangular. Using the matrix exchange property this form can be written as

    \[y=RB^{T}\left [ C^{T}Rh.\ast Ax \right ] \nonumber \]

    where \(R\) is the permutation matrix that reverses order.

    When \(h\) is fixed, as it is when considering prime length DFTs, the term \(C^TRh\) can be precomputed and a diagonal matrix \(D\) formed by

    \[D=diag{C^{T}Rh} \nonumber \]

    This is advantageous because in general, \(C\) is more complicated than \(B\), so the ability to “hide" \(C\) saves computation. Now y=RBTDAxy=RBTDAx" role="presentation" style="position:relative;" tabindex="0">


    This page titled 6.5: The Automatic Generation of Winograd's Short DFTs is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?