Programming Research Group Technical Report TR-4-89

Deriving the fast Fourier algorithm by calculation

Geraint Jones

October 1989, 23pp.

This paper reports an explanation of an intricate algorithm in the terms of a potentially mechanisable rigorous-development method. It uses notations and techniques of Sheeran, and Bird and Meertens. We have claimed that these techniques are applicable to digital signal processing circuits, and have previously applied them to regular array circuits.

This paper shows that they can deal with an apparently very different and more complex algorithm: the fast Fourier transform. Similar papers to this one perform most of the same calculations, but experiment with different ways of expressing the algorithms and their development.

This paper was presented at the Glasgow Functional Programming Group Workshop, Fraserburgh, Scotland, 21-23 August 1989. It has also been published in Functional programming, Glasgow 1989, eds. Kei Davis and John Hughes, Springer Workshops in Computing, 1990.

It is available as a 83,673 byte compressed PostScript file.

The text of the Orwell script in the appendix of this paper is available as a compressed text file.