An example of an *8*-input butterfly network is illustrated in
Figure 1. The nodes in this graph represent
switches, and the edges represent wires. Each node in the network has
a distinct label , where *r* is the row, and *l* is the level.
In a butterfly with *N* inputs, the row is a -bit binary
number and the level is an integer between *0* and . The
nodes on level *0* and are called the *inputs* and *
outputs*, respectively. For , a node labeled is
connected to nodes and , where denotes *r*
with bit *l* complemented (bit *0* is the most significant, bit the least).

In a butterfly, messages are typically sent from the switches on level
*0*, called the *inputs*, to those on level , called the
*outputs*. In a *one-to-one* routing problem, each input is
the origin of at most one message, and each output is the destination
of a most one message. One-to-one routing is also called *
permutation routing*.

**Figure 1:** An *8*-input butterfly network.

- 2.1 Dilated butterflies
- 2.2 Splitter networks
- 2.3 Randomly-wired splitter networks and multibutterflies

Mon Jul 22 19:56:03 EDT 1996