I saw the Winograd radix-8 kernel algorithm below, shown in the image. Comparing to the mathematical formula of Cooley-Tukey, there is a multiplication by $\cos$ and $\sin(\pi/8)$, which can't be easily realized by the combinations of $1$ and $\sqrt{1/2}$, which are the components used in Winograd.

As we can't realize something out of nothing, what is the mathematical trick to prove the Winograd and Cooley-Tukey are equivalent? Are there any such proof online I can read?

  • Winograd algorithm:

    enter image description here

  • Cooley-Tukey algorithm:

    enter image description here

  • $\begingroup$ i think there is a typo at the bottom left (regardiing $q(8)$) of the Winograd slide. $\endgroup$ – robert bristow-johnson Jul 6 '17 at 2:52
  • $\begingroup$ Yes, it should be a subtract instead of equal. $\endgroup$ – kelvin Jul 6 '17 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.