Walsh permutation; bit permutation

From Wikiversity
Jump to navigation Jump to search
Walsh permutation Rdrup.svg

The term bit permutation was chosen by the author for Walsh permutations whose compression matrices are permutation matrices.

Ordered in rows like the corresponding finite permutations (Sloane'sA055089) they form the infinite array Sloane'sA195665.

3-bit[edit]

An extract of the table of 3-bit Walsh permutations:

CV   CM   D Σ # Permutation
Inversion Vector
IN IS PM FPC Cy
0 1 2 4

[1,0,0;
0,1,0;
0,0,1]

+ 3 0 0 1 2 3   4 5 6 7
0 0 0 0   0 0 0 0
 0

[0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,1,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;

0,0,0,0, 1,0,0,0;
0,0,0,0, 0,1,0,0;
0,0,0,0, 0,0,1,0;
0,0,0,0, 0,0,0,1]

Fanoperm124.svg &1   0
1 2 1 4

[0,1,0;
1,0,0;
0,0,1]

3 722 0 2 1 3   4 6 5 7
0 0 1 0   0 0 1 0
 2

[0,0,0,0,0,0,0;
1,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
1,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,0,1,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;

0,0,0,0, 1,0,0,0;
0,0,0,0, 0,0,1,0;
0,0,0,0, 0,1,0,0;
0,0,0,0, 0,0,0,1]

Fanoperm214.svg &2   3   (2+2)>
2 1 4 2

[1,0,0;
0,0,1;
0,1,0]

3 288 0 1 4 5   2 3 6 7
0 0 0 0   2 2 0 0
 4

[0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,1,1,0,0,0,0;
1,1,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,0,0, 1,0,0,0;
0,0,0,0, 0,1,0,0;

0,0,1,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;
0,0,0,0, 0,0,1,0;
0,0,0,0, 0,0,0,1]

Fanoperm142.svg &2   3   (2+2)>
3 4 1 2

[0,1,0;
0,0,1;
1,0,0]

+ 3 1032 0 2 4 6   1 3 5 7
0 0 0 0   3 2 1 0
 6

[0,0,0,0,0,0,0;
0,0,1,0,0,0,0;
0,1,1,0,0,0,0;
1,1,1,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,0,1,0, 0,0,0,0;
0,0,0,0, 1,0,0,0;
0,0,0,0, 0,0,1,0;

0,1,0,0, 0,0,0,0;
0,0,0,1, 0,0,0,0;
0,0,0,0, 0,1,0,0;
0,0,0,0, 0,0,0,1]

Fanoperm412.svg &4   9   (3+3)>
4 2 4 1

[0,0,1;
1,0,0;
0,1,0]

+ 3 2210 0 4 1 5   2 6 3 7
0 0 1 0   2 0 3 0
 6

[0,0,0,0,0,0,0;
1,0,1,0,1,0,0;
0,0,0,0,0,0,0;
1,0,1,0,0,0,0;
0,0,0,0,0,0,0;
1,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,0,0,0, 1,0,0,0;
0,1,0,0, 0,0,0,0;
0,0,0,0, 0,1,0,0;

0,0,1,0, 0,0,0,0;
0,0,0,0, 0,0,1,0;
0,0,0,1, 0,0,0,0;
0,0,0,0, 0,0,0,1]

Fanoperm241.svg &4   9   (3+3)>
5 4 2 1

[0,0,1;
0,1,0;
1,0,0]

3 2354 0 4 2 6   1 5 3 7
0 0 1 0   3 1 3 0
 8

[0,0,0,0,0,0,0;
1,0,1,0,1,0,0;
0,1,0,0,0,0,0;
1,1,1,0,0,0,0;
0,0,0,0,0,0,0;
1,0,0,0,0,0,0;
0,0,0,0,0,0,0]

[1,0,0,0, 0,0,0,0;
0,0,0,0, 1,0,0,0;
0,0,1,0, 0,0,0,0;
0,0,0,0, 0,0,1,0;

0,1,0,0, 0,0,0,0;
0,0,0,0, 0,1,0,0;
0,0,0,1, 0,0,0,0;
0,0,0,0, 0,0,0,1]

Fanoperm421.svg &2   3   (2+2)>


4-bit[edit]

Applying a permutation pn of 0,...,3 on the reverse binary digits of numbers 0,...,15 gives a permutation Pn of these 16 elements.

p23 permutes (0,1,2,3) into (3,2,1,0). P23 = wp(23,22,21,20) = wp(8,4,2,1) is the 4-bit bit-reversal permutation.

Applying all permutations p0,...,p23 of 0,...,3 on the digits of 0,...,15 gives the bit permutations P0,...,P23, which also form the symmetric group S4.
But the big permutations have to be composed in a different way, to get corresponding results:

Rdrdo.svg See example calculations.

Loupe light.svg     Cycle graphs of S4
The 4×4 matrices of the permutations pn are the transposed compression matrices
of the Walsh permutations Pn, here represented by their 16×16 matrices.


Rdrdo.svg Walsh permutation; inversions#Bit permutations