Revision 929498 of "Walsh permutation; bit permutation; calc" on enwikiversity

{| align=right
|[[Walsh permutation]]; [[Walsh permutation; bit permutation|bit permutation]] [[File:Rdrup.svg|link=]]
|}

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


<math>p_a * p_b * ... = p_x ~~~~ \Leftrightarrow ~~~~ ... * P_b * P_a = P_x</math>


__TOC__


==p<sub>1</sub> * p<sub>8</sub>==
<math>p_1 * p_8  = p_9 ~~~~ \Leftrightarrow ~~~~ P_8 * P_1 = P_9</math>

<source lang="matlab">
rowp1=[0 1 0 0;
       1 0 0 0;
       0 0 1 0;
       0 0 0 1];
rowp1*[1:4]'
ans =
     2
     1
     3
     4

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


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





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

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


ROWP1*ROWP8*[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:
ROWP8*ROWP1*[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
</source>


==p<sub>1</sub> * p<sub>3</sub> * p<sub>8</sub>==
<math>p_1 * p_3 * p_8 = p_6 ~~~~ \Leftrightarrow ~~~~ P_8 * P_3 * P_1 = P_6</math>

<source lang="matlab">
rowp1=[0 1 0 0;
       1 0 0 0;
       0 0 1 0;
       0 0 0 1];

rowp3=[0 0 1 0;
       1 0 0 0;
       0 1 0 0;
       0 0 0 1];

rowp8=[1 0 0 0;
       0 0 0 1;
       0 1 0 0;
       0 0 1 0];


ROWP1=[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];

ROWP3=[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];

ROWP8=[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];



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



ROWP8*ROWP3*ROWP1*[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
</source>


==p<sub>8</sub> * p<sub>3</sub> * p<sub>1</sub>==
<math>p_8 * p_3 * p_1 = p_{22} ~~~~ \Leftrightarrow ~~~~ P_1 * P_3 * P_8 = P_{22}</math>

<source lang="matlab">
rowp8*rowp3*rowp1*[1:4]'
ans =
     3
     4
     2
     1
%      The result is p22.
%      p8 after p3 after p1 = p22



ROWP1*ROWP3*ROWP8*[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
</source>


{{Lipedia}}
[[Category:Walsh permutation]]
[[Category:Walsh permutation]]
[[Category:Freshly started resources]]
[[Category:Resources last modified in July 2012]]