Q. Explain about Butterfly permutation?

Butterfly permutation:  This kind of permutation is attained by interchanging the most significant bit in address with least significant bit.

Figure: Butterfly permutation

E.g. X_n-1,   X_n-2, and X₁.X₀ = X₀ X_n-2 ....... X₁ X_n-1

 001↔100,    010↔010

 011↔110,

An interconnection network derived from this permutation is the butterfly network. A butterfly network falls under the type of blocking networks and it doesn't permit an arbitrary connection of N inputs to N outputs without conflict. The butterfly network is customized in Benz network.  The Benz network comes under non-blocking network and it is produced by combining two butterfly networks end to end, in a manner that data flows forward by one and in reverse by the other.