β(an, an-1, .. a2, a1) = {a1, an-1, .. a2, an}
Informally, the most and least significant bits in the binary representation of the network port label are interchanged, and this is illustrated in the figure which shows the bipartite graph for a butterfly permutation.
Two variants of the straightforward butterfly permutation are possible, the kth sub-butterfly and the kth super-butterfly. The kth sub-butterfly permutation is performed by interchanging bits one and k in the binary representation of x, thus
βk(an, an-1, .. a1) = {an, .. ak+1, a1, ak-1, .. ak}
whereas the kth super-butterfly permutation is performed by interchanging bits n and k, thus
βk(an, an-1, .. a1) = {ak, an-1, .. ak+1, an, ak-1, .. a1}
Visualising these permutations, as bipartite graphs, is left as an exercise for the reader.