next up previous contents
Nächste Seite: Graphen Aufwärts: Permutationen und Graphen Vorherige Seite: Permutationen und Graphen   Inhalt

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

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


$\displaystyle \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)
$\displaystyle = (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$.



Jörg Haeger 2001-05-07