Acest răspuns se concentrează pe pic permutările așa cum sunt utilizate în contextul DES pentru permutări de biți IP, IP-1, și E. Numerează biții începând de la $1$, ca în DES.
A permutare de biți este o funcție $g$ pe platou $\{0,1\}^n$ de $n$-bit bistring. Este în întregime definit de un vector de $n$ numere întregi distincte $p_i$ cu $1\le p_i\le n$, și proprietatea care pentru orice șir de biți $x$ și orice număr întreg $i$ cu $1\le i\le n$, număr de biți $i$ a imaginii de șir de biți $x$ dupa functie $g$ este numărul de biți $p_i$ de $x$.
Cu alte cuvinte, fiecare bit de intrare trece la bitul de ieșire alocat în mod unic și bitul de ieșire $i$ este bit de intrare $p_i$.
Fiecare permutare de bit este a bijectie pe platou $\{0,1\}^n$. În mod echivalent: fiecare permutare de biți este o permutare a setului de $n$-bit bistring. Sunt $n!$ astfel de permutări de biți, față de cele mult mai mari $(2^n)!$ astfel de permutări. Subsetul de permutări de biți este închis sub compoziția funcției: aplicarea oricăror două permutări de biți fixe produce o permutare de biți.
Notă: unii autori folosesc transpunere de biți sau chiar transpunere pentru a desemna o permutare a bitului așa cum este definită mai sus și a o distinge de o permutare. Nu asta voi face în cele ce urmează, dar ar putea fi ceea ce are în vedere OP.
A transpunere de biți este o permutare specială a bitului $n$-bit șiruri de biți, definite în întregime de două numere întregi $\ell$ și $c$ cu $n=\ell\cdot c$. este $n$ numere întregi $p_i$ sunt $p_i=1+((i-1)\bmod c)\cdot c+\lfloor (i-1)/c\rfloor$, pentru $1\le i\le n$.
Cu alte cuvinte, când scriem biții de intrare ca $\ell=n/c$ linii şi $c$ coloane și biții de ieșire ca $c$ linii şi $\ell$ coloane, coloană de ieșire $j$ vine de la linia de intrare $j$.
De exemplu, cu $\ell=3$ și $c=2$, transpunerea de biți are $p_1=1$, $p_2=3$, $p_3=5$, $p_4=2$, $p_5=4$, $p_6=6$, care este cel mai bine reprezentat ca
1 3 5
2 4 6
Uneori, permutarea bitului cu $p_i=\ell\cdot c-((i-1)\bmod c)\cdot c-\lfloor (i-1)/c\rfloor$ este, de asemenea, considerată o transpunere alternativă de biți. Cu $\ell=3$ și $c=2$, transpunerea de biți alternativă are $p_i$
6 4 2
5 3 1
Când $n$ este un pătrat și $\ell,c$ sunt nespecificate, se presupune că sunt $\sqrt n$, și astfel de transpoziții de biți pătrați sunt involuții.
Înjumătățirea blocului inițial și eventuala schimbare a jumătăților ar fi o permutare sau o transpunere?
În DES, transformarea (constând din IP urmată de înjumătățire) de la intrarea pe 64 de biți la LR este o permutare de biți (deci o permutare a setului $\{0,1\}^n$, dar asta este mult mai puțin specific). este $p_i$ sunt date în tabelul IP:
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
O schimbare foarte regulată de linii o face
64 56 48 40 32 24 16 8
63 55 47 39 31 23 15 7
62 54 46 38 30 22 14 6
61 53 45 37 29 21 13 5
60 52 44 36 28 20 12 4
59 51 43 35 27 19 11 3
58 50 42 34 26 18 10 2
57 49 41 33 25 17 9 1
care este transpunerea alternativă a bitului pătrat pentru $n=64$. Prin urmare, IP este aproape o transpunere.
Când este văzută ca funcționând pe LR, schimbarea jumătăților este o mică permutare, care $p_i$ sunt date de:
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
Nu este o transpunere de biți, dar este o permutare de biți foarte regulată (cum sunt transpozițiile de biți) și o involuție (care sunt transpozițiile de biți pătrați).
