Walsh permutation; bit permutation; calc

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

Finite permutations p and corresponding bit permutations P are composed in opposite directions:




p1 * p8[edit]

p1 = [0 1 0 0;
      1 0 0 0;
      0 0 1 0;
      0 0 0 1];
p1 * [1:4]'
ans =
     2
     1
     3
     4

p8 = [1 0 0 0;
      0 0 0 1;
      0 1 0 0;
      0 0 1 0];
p8 * [1:4]'
ans =
     1
     4
     2
     3


p1 * p8 * [1:4]'
ans =
     4
     1
     2
     3
%      The result is p9.
%      p1 after p8 = p9





P1 = [1 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;
      0 1 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 0 0 0  1 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  0 1 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 0 0 0  1 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  0 1 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 0 0 0  1 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  0 1 0 0;
      0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];
P1 * [0:15]'
ans =
     0
     2
     1
     3
     4
     6
     5
     7
     8
    10
     9
    11
    12
    14
    13
    15

P8 = [1 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 0;
      0 0 0 0  1 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 0  0 0 0 0  1 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 0  0 0 0 0  1 0 0 0;
      0 0 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 0 0;
      0 0 0 1  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  0 0 0 1  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  0 0 0 1  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  0 0 0 1];
P8 * [0:15]'
ans =
     0
     1
     4
     5
     8
     9
    12
    13
     2
     3
     6
     7
    10
    11
    14
    15


P1 * P8 * [0:15]'
ans =
     0
     4
     1
     5
     8
    12
     9
    13
     2
     6
     3
     7
    10
    14
    11
    15
%      The result is not P9 but P10, the inverse permutation of P9.
%      The row permutation matrices of the big permutations have to be multiplied like column permutation matrices from right to left
%      to get the result corresponding to the small permutations:
P8 * P1 * [0:15]'
ans =
     0
     2
     4
     6
     8
    10
    12
    14
     1
     3
     5
     7
     9
    11
    13
    15
%      The result is P9.
%      P1 before P8 = P9


p1 * p3 * p8[edit]

p1 = [0 1 0 0;
      1 0 0 0;
      0 0 1 0;
      0 0 0 1];

p3 = [0 0 1 0;
      1 0 0 0;
      0 1 0 0;
      0 0 0 1];

p8 = [1 0 0 0;
      0 0 0 1;
      0 1 0 0;
      0 0 1 0];


P1 = [1 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;
      0 1 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 0 0 0  1 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  0 1 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 0 0 0  1 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  0 1 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 0 0 0  1 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  0 1 0 0;
      0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];

P3 = [1 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;
      0 0 0 0  1 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 1 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 0 0 0  0 1 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 0 0 0  1 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  0 0 0 0  1 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 1 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 0 0 0  0 1 0 0;
      0 0 0 0  0 0 0 0  0 0 0 0  0 0 0 1];

P8 = [1 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 0;
      0 0 0 0  1 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 0  0 0 0 0  1 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 0  0 0 0 0  1 0 0 0;
      0 0 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 0 0;
      0 0 0 1  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  0 0 0 1  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  0 0 0 1  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  0 0 0 1];



p1 * p3 * p8 * [1:4]'
ans =
     1
     2
     4
     3
%      The result is p6.
%      p1 after p3 after p8 = p6



P8 * P3 * P1 * [0:15]'
ans =
     0
     1
     2
     3
     8
     9
    10
    11
     4
     5
     6
     7
    12
    13
    14
    15
%      The result is P6.
%      P1 before P3 before P8 = P6


p8 * p3 * p1[edit]

p8 * p3 * p1 * [1:4]'
ans =
     3
     4
     2
     1
%      The result is p22.
%      p8 after p3 after p1 = p22



P1 * P3 * P8 * [0:15]'
ans =
     0
     8
     4
    12
     1
     9
     5
    13
     2
    10
     6
    14
     3
    11
     7
    15
%      The result is P22.
%      P8 before P3 before P1 = P22