4 Permutation Matrices Associated to Bent Functions
85
Depending on the number of non-zero values, we split the sets of all Boolean
functions into two subsets. The first set contains functions with 2 n−1 − 2 n/2−1 nonzero values and the other set contains their logic complements. In this area, logic
values 0 and 1 are usually encoded by 1 and −1, respectively, and interpreted as
integers.
4.2.2 Walsh Transform
Consider the finite dyadic group G n defined as the set of binary n-tuples under
the operation componentwise addition modulo 2, EXOR, whose elements can be
identified with the first 2 n non-negative integers B n = {0, 1, . . . , 2 n − 1}.
The discrete Walsh transform in Hadamard ordering is defined in matrix notation
by the (2 n × 2 n ) Walsh transform matrix
W(n) =
n
i=1
W(1), W(1) =
1 1
1 −1
,
where ⊗ denotes the Kronecker product of matrices.
For a function f on B n with the truth-vector F = [f (0), f (1), . . . , f (2 n − 1)] T ,
the Walsh spectrum S f = [S f (0), S f (1), . . . , S f (2 n − 1)] T is defined as
S f = W(n)F.
In computing the Walsh spectrum, the truth-vector F is replaced by the function
vector in the (0, 1) → (1, −1) encoding.
4.2.3 Walsh Transform and Bent Functions
Walsh spectral coefficients S f (i), i = 0, 1, . . . , 2 n − 1, of a bent function have the
same absolute value equal to 2 n/2 [8]. Due to that, bent functions are alternatively
defined as Boolean functions with a flat Walsh spectrum.
Definition 4.1 A Boolean function derived from the Walsh spectrum of a bent
function f by multiplication of the Walsh coefficients with 2 −n/2 is called the dual
function f d of f .
Example 4.2 Consider the function defined by the function vector
F 1 = [−1, −1, 1, −1, −1, 1, 1, 1, 1, 1, −1, 1, −1, 1, 1, 1]
T ,
85
Depending on the number of non-zero values, we split the sets of all Boolean
functions into two subsets. The first set contains functions with 2 n−1 − 2 n/2−1 nonzero values and the other set contains their logic complements. In this area, logic
values 0 and 1 are usually encoded by 1 and −1, respectively, and interpreted as
integers.
4.2.2 Walsh Transform
Consider the finite dyadic group G n defined as the set of binary n-tuples under
the operation componentwise addition modulo 2, EXOR, whose elements can be
identified with the first 2 n non-negative integers B n = {0, 1, . . . , 2 n − 1}.
The discrete Walsh transform in Hadamard ordering is defined in matrix notation
by the (2 n × 2 n ) Walsh transform matrix
W(n) =
n
i=1
W(1), W(1) =
1 1
1 −1
,
where ⊗ denotes the Kronecker product of matrices.
For a function f on B n with the truth-vector F = [f (0), f (1), . . . , f (2 n − 1)] T ,
the Walsh spectrum S f = [S f (0), S f (1), . . . , S f (2 n − 1)] T is defined as
S f = W(n)F.
In computing the Walsh spectrum, the truth-vector F is replaced by the function
vector in the (0, 1) → (1, −1) encoding.
4.2.3 Walsh Transform and Bent Functions
Walsh spectral coefficients S f (i), i = 0, 1, . . . , 2 n − 1, of a bent function have the
same absolute value equal to 2 n/2 [8]. Due to that, bent functions are alternatively
defined as Boolean functions with a flat Walsh spectrum.
Definition 4.1 A Boolean function derived from the Walsh spectrum of a bent
function f by multiplication of the Walsh coefficients with 2 −n/2 is called the dual
function f d of f .
Example 4.2 Consider the function defined by the function vector
F 1 = [−1, −1, 1, −1, −1, 1, 1, 1, 1, 1, −1, 1, −1, 1, 1, 1]
T ,