Programming Research Group Technical Monograph PRG-91

Geraint Jones and Mary Sheeran (University of Glasgow)

February 1991, 38 pages, ISBN 0-902928-69-4

This monograph contains three papers about butterfly circuits. Circuits of this form turn up in many signal processing applications, and networks of the same shape are found in parallel algorithms for many sorts of message-passing computers. Unfortunately their presentation is usually bottom-up and consequently difficult to understand. In these papers we give top-down analyses of such circuits in the style of Ruby - a language of relations and higher-order functions in which circuits are represented as relations on the signals which pass between them.

The first paper -- The study of butterflies -- introduces the algebra of the combining forms with which butterfly circuits will be described. It goes on to show that butterfly forms arise naturally when certain sorts of problem are tackled by a divide-and-conquer strategy.

Butterfly circuits are probably most familiar from their application to the implementation of the fast Fourier transform. The second paper -- A fast flutter by the Fourier transform -- takes the recursive equation which describes the divide-and-conquer calculation of the Fourier transform and shows how it can be implemented by butterfly circuits and by various related regular layouts.

The third paper -- Sorts of butterflies -- shows how Ruby is used to describe and analyse permutation and comparator networks. It explains a periodic sorting network that is suitable for implementation on silicon.