Câu trả lời này tập trung vào chút hoán vị như được sử dụng trong ngữ cảnh của DES cho hoán vị bit IP, IP-1, và E. Nó đánh số các bit bắt đầu từ $1$, như trong DES.
Một hoán vị bit là một chức năng $g$ trên bộ $\{0,1\}^n$ của $n$-bit bistrings. Nó hoàn toàn được xác định bởi một vectơ của $n$ số nguyên phân biệt $p_i$ với $1\le p_i\le n$và thuộc tính cho bất kỳ chuỗi bit nào $x$ và bất kỳ số nguyên nào $i$ với $1\le i\le n$, số bit $i$ của hình ảnh của chuỗi bit $x$ theo chức năng $g$ là số bit $p_i$ của $x$.
Nói cách khác, mỗi bit đầu vào đi đến bit đầu ra được gán duy nhất và bit đầu ra $i$ là bit đầu vào $p_i$.
Mỗi hoán vị bit là một phép chiếu trên bộ $\{0,1\}^n$. Tương tự: mỗi hoán vị bit là một hoán vị của tập hợp $n$-bit bistrings. Có $n!$ hoán vị bit như vậy, so với lớn hơn nhiều $(2^n)!$ hoán vị như vậy. Tập hợp con của các hoán vị bit được đóng theo thành phần chức năng: áp dụng hai hoán vị bit cố định bất kỳ sẽ tạo ra một hoán vị bit.
Lưu ý: một số tác giả sử dụng chuyển vị bit hoặc thậm chí chuyển vị để chỉ định một hoán vị bit như được định nghĩa ở trên và phân biệt nó với một hoán vị. Đó không phải là những gì tôi sẽ làm sau đây, nhưng nó có thể là những gì OP nghĩ đến.
Một chuyển vị bit là một hoán vị bit cụ thể của $n$-bit chuỗi bit, hoàn toàn được xác định bởi hai số nguyên $\ell$ và $c$ với $n=\ell\cdot c$. Của nó $n$ số nguyên $p_i$ là $p_i=1+((i-1)\bmod c)\cdot c+\lfloor (i-1)/c\rfloor$, vì $1\le i\le n$.
Nói cách khác, khi chúng ta viết các bit đầu vào là $\ell=n/c$ dòng và $c$ cột và các bit đầu ra dưới dạng $c$ dòng và $\ell$ cột, cột đầu ra $j$ đến từ dòng đầu vào $j$.
Ví dụ, với $\ell=3$ và $c=2$, chuyển vị bit có $p_1=1$, $p_2=3$, $p_3=5$, $p_4=2$, $p_5=4$, $p_6=6$, được biểu diễn tốt nhất dưới dạng
1 3 5
2 4 6
Đôi khi, hoán vị bit với $p_i=\ell\cdot c-((i-1)\bmod c)\cdot c-\lfloor (i-1)/c\rfloor$ cũng được coi là một chuyển vị bit thay thế. Với $\ell=3$ và $c=2$, chuyển vị bit thay thế có $p_i$
6 4 2
5 3 1
Khi nào $n$ là hình vuông và $\ell,c$ không xác định, chúng được coi là $\sqrt n$, và các chuyển vị bit vuông như vậy là cách mạng.
Liệu việc chia đôi khối ban đầu và sự hoán đổi hai nửa cuối cùng có phải là hoán vị hay chuyển vị không?
Trong DES, phép biến đổi (bao gồm IP theo sau là giảm một nửa) từ đầu vào 64-bit sang LR là một phép hoán vị bit (do đó, một phép hoán vị của tập hợp $\{0,1\}^n$, nhưng điều đó ít cụ thể hơn nhiều). Của nó $p_i$ được đưa ra trong bảng 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
Một sự hoán đổi dòng rất thường xuyên làm cho nó
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
đó là chuyển vị bit vuông thay thế cho $n=64$. Do đó, IP gần như là một chuyển vị bit.
Khi được coi là hoạt động trên LR, việc hoán đổi các nửa là một hoán vị bit, điều này $p_i$ được cho bởi:
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
Đó không phải là chuyển vị bit, nhưng đó là một hoán vị bit rất bình thường (giống như chuyển vị bit) và một phép nghịch đảo (tức là chuyển vị bit vuông).
