COLLECTING BUTTERFLIES

Abstract

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.