Permutationen

Im Zusammenhang mit Butterfly- und de Bruijn-Graphen ist die folgende Permutation und ihre Umkehrung von Bedeutung

Definition 3 (Shuffle- und Unshuffle-Permutation)      Die Shuffle-Permutation $\sigma_{l, p}$ ist eine Abbildung

$$\sigma_{l, p}: {\rule[0pt]{0.21mm}{8pt}\hspace*{0.08mm}{\sf N}} \to {\rule[0pt]{0.21mm}{8pt}\hspace*{0.08mm}{\sf N}},$$

$$\sigma_{l, p}((a_{n-1}, \dots, a_{p+l}, a_{p+l-1}, a_{p+l-2}, \dots, a_{p}, a_{p-1}, \dots, a_{0})_2)$$ (6)

$$= (a_{n-1}, \dots, a_{p+l}, a_{p+l-2}, \dots, a_{p}, a_{p+l-1}, a_{p-1}, \dots, a_{0})_2$$

Es werden also in der Dualdarstellung einer Zahl l Stellen ab der Position p zyklisch nach links rotiert.

Die Unshuffle-Permutation $\sigma_{l, p}^{-1}$ ist die Umkehrabbildung zu $\sigma_{l, p}$.

Beispiele: $\sigma_{4, 2}((10100110)_2) = (10001110)_2$,      $\sigma_{4, 2}^{-1}((10001110)_2) = (10100110)_2$.