View article

Definition 1 (Butterfly). The r-dimensional butterfly consists of (r+ 1) 2r nodes and r2r+ 1 edges. A node is a pair〈 w, i〉, i is the level of the node, w is the row number (r-bit). An edge links two nodes〈 w, i〉 and〈 w, i〉 if and only if i= i+ 1 and either w= w, or w and w differs in the ith bit.