Linear Boolean functions

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 Walsh index with the LSB leveled to 0. (So the leader is always an even number.)
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 A358126. Those of the negations are bigger by 1.

See also Linear and noble Boolean functions.

## 2-ary

[edit | edit source]

matrix

truth tables | Zhegalkin indices
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  | 2  | 2  |  | 12  | 4  | 1  |  | 3  | 5
2  | 3  | 2  | 0  |  | 6  | 6  | 3  |  | 9  | 7

## 3-ary

[edit | edit source]

matrix

truth tables | Zhegalkin indices

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  | 2  | 2  |  | 204  | 4  | 1  |  | 51  | 5
2  | 3  | 2  | 0  |  | 102  | 6  | 3  |  | 153  | 7
1  | 4  | 4  | 2  |  | 240  | 16  | 1  |  | 15  | 17
2  | 5  | 4  | 0  |  | 90  | 18  | 3  |  | 165  | 19
2  | 6  | 6  | 0  |  | 60  | 20  | 3  |  | 195  | 21
3  | 7  | 6  | 2  |  | 150  | 22  | 1  |  | 105  | 23

## 4-ary

[edit | edit source]

16 Walsh functions (left) and their complements (right)

matrix

| truth tables

Zhegalkin indices

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  | 2  | 2  |  | 52428  | 4  | 1  |  | 13107  | 5
2  | 3  | 2  | 0  |  | 26214  | 6  | 3  |  | 39321  | 7
1  | 4  | 4  | 2  |  | 61680  | 16  | 1  |  | 3855  | 17
2  | 5  | 4  | 0  |  | 23130  | 18  | 3  |  | 42405  | 19
2  | 6  | 6  | 0  |  | 15420  | 20  | 3  |  | 50115  | 21
3  | 7  | 6  | 2  |  | 38550  | 22  | 1  |  | 26985  | 23
1  | 8  | 8  | 2  |  | 65280  | 256  | 1  |  | 255  | 257
2  | 9  | 8  | 0  |  | 21930  | 258  | 3  |  | 43605  | 259
2  | 10  | 10  | 0  |  | 13260  | 260  | 3  |  | 52275  | 261
3  | 11  | 10  | 2  |  | 39270  | 262  | 1  |  | 26265  | 263
2  | 12  | 12  | 0  |  | 4080  | 272  | 3  |  | 61455  | 273
3  | 13  | 12  | 2  |  | 42330  | 274  | 1  |  | 23205  | 275
3  | 14  | 14  | 2  |  | 49980  | 276  | 1  |  | 15555  | 277
4  | 15  | 14  | 0  |  | 27030  | 278  | 3  |  | 38505  | 279
*[LSB]: least significant bit