Walsh permutation; bent functions

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


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):

From 1110 1000 1000 0001 to 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.

From 0111 1000 1000 1000 to wp( 2, 1, 8, 4)

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
Powers of wp( 4, 8, 9, 6).svg Powers of wp( 8, 4,10, 5).svg Powers of wp( 2, 9, 8, 6).svg Powers of wp( 8,12, 2, 3).svg Powers of wp( 2, 5,10, 4).svg Powers of wp( 4,12, 3, 2).svg

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)

From 1100 1010 0110 0000 to wp(12, 4, 3, 1)


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
Powers of wp( 2,13,10, 6).svg Powers of wp(10,13, 2, 3).svg Powers of wp( 6, 5,11, 4).svg Powers of wp( 4,12,11, 6).svg Powers of wp( 6,13, 3, 2).svg Powers of wp( 8,12,10, 7).svg

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.

From 1100 1010 1001 0000 to wp(12, 4,11, 5)