Walsh permutation; bent functions
Walsh permutation |
Each bent function corresponds to a Walsh permutation, as shown in the following examples.
All bent functions in the same sec correspond to the same Walsh permutation.
Below are four examples how a Walsh permutation follows from a bent function. This is the meaning of the matrices:
- sec matrix of the bent function
- same matrix, XORs with top row indicated by circles
- only the XORs from last matrix
- rows complemented that had a 1 in the leftmost position (permuted binary Walsh matrix)
- permutation matrix corresponding to the permuted Walsh matrix
There are four big equivalence classes of 4-ary bent functions with Hamming weight 6.
BEC 391[edit | edit source]
BEC 391 with only one SEC corresponds to the complemented bit permutation wp(14,13,11, 7):
BEC 381[edit | edit source]
BEC 381 with 3 SECs corresponds to the bit permutations wp(2,1,8,4), wp(4,8,1,2) and wp(8,4,2,1).
They correspond to the simple permutations with the numbers 7, 16 and 23 - the three permutations of 4 elements that have two 2-cycles.
BEC 382[edit | edit source]
BEC 382 with 12 SECs corresponds to 12 Walsh permutations with the following compression vectors:
4 8 9 6 6 9 1 2 |
8 4 10 5 10 5 2 1 |
2 9 8 6 6 1 9 4 |
8 12 2 3 12 4 3 1 |
2 5 10 4 10 1 8 5 |
4 12 3 2 12 8 1 3 |
The cubes of these permutations are the three bit permutations mentioned in the section above.
The cube of wp(12, 4, 3, 1) is wp(4, 8, 1, 2)
BEC 383[edit | edit source]
BEC 383 with 12 SECs corresponds to 12 Walsh permutations with the following compression vectors:
2 13 10 6 14 1 9 5 |
10 13 2 3 12 4 11 5 |
6 5 11 4 10 9 8 7 |
4 12 11 6 14 9 1 3 |
6 13 3 2 12 8 9 7 |
8 12 10 7 14 5 3 1 |
The squares of these permutations are the complements of the bit permutations that correspond to the six transpositions of four elements.
The square of wp(12, 4, 11, 5) is wp(14, 11, 13, 7). That is the complement of wp(1, 4, 2, 8), which corresponds to the transposition of four elements that swaps the two in the middle.