| Collecting Butterflies (1991) | |||||||||||||||
Abstract | |||||||||||||||
| Collecting butterflies 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 tacked 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-andconquer 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. Acknowledgments The presentation of divide and conquer algorithms owes much to several attempts to explain it to colleagues, and in particular to Richard Bird. We are grateful to David Murphy and Lars Rossen for many comments and suggestions. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||