Jump to content

Linear Boolean functions

From Wikiversity
Studies of Boolean functions

Linear Boolean functions are Walsh functions and their negations. A Walsh function is a variadic XOR (a.k.a. parity function).
The set of arguments in that XOR can easily be expressed as an integer, which shall be called Walsh index.

The natural way to denote a linear function is as Walsh index and parity. Walsh functions have parity 0. Their negations have parity 1.
Sometimes a more arcane notation is useful, namely as leader and quadrant.
The leader is the right shift of the Walsh index. The quadrant is the first and last digit of the truth table expressed in an integer.
The tables below show the Walsh indices on gray and the quadrants on colored background.
The Walsh indices of functions with quadrants 0 and 3 are evil numbers 0, 3, 5, 6...   For quadrants 1 and 2 they are odious numbers 1, 2, 4, 7...

The columns marked with Ж show the Zhegalkin indices. Those of the Walsh functions are sequence Sloane'sA358126. Those of the negations are bigger by 1.

See also Linear and noble Boolean functions.


2-ary

[edit | edit source]
Walsh
weight
Walsh
index
leader Walsh ¬ Walsh
Q Ж Q Ж
0 0 0 0 0 0 3 15 1
1 1 0 2 10 2 1 5 3
1 2 1 2 12 4 1 3 5
2 3 1 0 6 6 3 9 7

3-ary

[edit | edit source]
8 Walsh functions (left) and their complements (right)
Walsh
weight
Walsh
index
leader Walsh ¬ Walsh
Q Ж Q Ж
0 0 0 0 0 0 3 255 1
1 1 0 2 170 2 1 85 3
1 2 1 2 204 4 1 51 5
2 3 1 0 102 6 3 153 7
1 4 2 2 240 16 1 15 17
2 5 2 0 90 18 3 165 19
2 6 3 0 60 20 3 195 21
3 7 3 2 150 22 1 105 23


4-ary

[edit | edit source]
16 Walsh functions (left) and their complements (right)
Walsh
weight
Walsh
index
leader Walsh ¬ Walsh
Q Ж Q Ж
0 0 0 0 0 0 3 65535 1
1 1 0 2 43690 2 1 21845 3
1 2 1 2 52428 4 1 13107 5
2 3 1 0 26214 6 3 39321 7
1 4 2 2 61680 16 1 3855 17
2 5 2 0 23130 18 3 42405 19
2 6 3 0 15420 20 3 50115 21
3 7 3 2 38550 22 1 26985 23
1 8 4 2 65280 256 1 255 257
2 9 4 0 21930 258 3 43605 259
2 10 5 0 13260 260 3 52275 261
3 11 5 2 39270 262 1 26265 263
2 12 6 0 4080 272 3 61455 273
3 13 6 2 42330 274 1 23205 275
3 14 7 2 49980 276 1 15555 277
4 15 7 0 27030 278 3 38505 279