Gray code permutation powers

From Wikiversity
Jump to navigation Jump to search
Walsh permutation
G3
G32
G33
powers of the 3-bit Gray code

The n-bit Gray code Gn is a permutation of the integers from 0 to 2n − 1, whose only fixed points are 0 and 1.

The powers of Gn form the the cyclic group Zn, if n is a power of 2.
In general they form the the cyclic group Zm, with (which is A062383(n−1)).

n 1 2 3..4 5..8 9..16 17..32
m 1 2 4 8 16 32

Gray matrix[edit | edit source]

The following sections show the powers for n = 2 .. 5.   (A more readable version for n = 6 can be found here.)
Each row has the exponent k on the left, then the vector abbreviating the Walsh permutation, and on the right the permutation itself.
It can be seen, that each m×2n matrix is the top left corner of the next one.
This leads to the infinite matrix G = Sloane'sA195467 whose rows are Gk.

2-bit[edit | edit source]

0         1   2         0   1   2   3
1         1   3         0   1   3   2

3-bit[edit | edit source]

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

4-bit[edit | edit source]

0         1   2   4   8         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1         1   3   6  12         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8
2         1   2   5  10         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12
3         1   3   7  15         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10

5-bit[edit | edit source]

0         1   2   4   8  16         0   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
1         1   3   6  12  24         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8  24  25  27  26  30  31  29  28  20  21  23  22  18  19  17  16
2         1   2   5  10  20         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12  20  21  22  23  17  16  19  18  30  31  28  29  27  26  25  24
3         1   3   7  15  30         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10  30  31  29  28  25  24  26  27  17  16  18  19  22  23  21  20
4         1   2   4   8  17         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  17  16  19  18  21  20  23  22  25  24  27  26  29  28  31  30
5         1   3   6  12  25         0   1   3   2   6   7   5   4  12  13  15  14  10  11   9   8  25  24  26  27  31  30  28  29  21  20  22  23  19  18  16  17
6         1   2   5  10  21         0   1   2   3   5   4   7   6  10  11   8   9  15  14  13  12  21  20  23  22  16  17  18  19  31  30  29  28  26  27  24  25
7         1   3   7  15  31         0   1   3   2   7   6   4   5  15  14  12  13   8   9  11  10  31  30  28  29  24  25  27  26  16  17  19  18  23  22  20  21

The 5×5 matrices can be found on page 48 of Matters Computational by Jörg Arndt (2010), which can be found here: jjj.de/fxt

Zhegalkin matrix[edit | edit source]

powers of the 4-bit Gray code   (rows G40 ... 3)
binary Walsh matrix
W: 256×256 binary Walsh matrix
Ж: 8×256 Zhegalkin matrix
S: 1, 3, 5, 15, 17, 51, 85, 255   (sequence corresponding to an 8×8 Sierpiński triangle)

The image on the right shows the four powers of G4.
The dual matrix below shows the separated binary digits of the integer entries.
It's columns correspond to the entries of Zhegalkin permutation Ж2 (row 2 of Sloane'sA197819),
which is the Walsh permutation corresponding to the 4×4 lower triangular Sierpiński triangle.

The whole integer matrix can be derived from this binary matrix:
Each of the other elements of the dual matrix is a stretch of its neighbor with the smaller place value,
i.e. the left half is doubled, and the right half vanishes.

The infinite Zhegalkin matrix Ж is the infinite Gray matrix G mod 2.

Let stretchsum be a function that receives a binary matrix whose left column has only zeros,
and returns the integer matrix created by adding up its stretches multiplied with binary place values.
Then G = stretchsum(Ж).

Let W be the infinite binary Walsh matrix (whose 16×16 top left corner is shown on the right), and Wi the binary Walsh function in row i,
and let S = Sloane'sA001317 = 1, 3, 5, 15... be the integer sequence corresponding to the Sierpiński triangle,
then Ж = WS, i.e. the rows of W whose indices are in S.

That means that the Gray code power Gk = stretchsum(WS(k)).