VOOZH about

URL: https://en.wikiversity.org/wiki/Linear_Boolean_functions

⇱ Linear Boolean functions - Wikiversity


Jump to content
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 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
👁 Image
truth tables
👁 Image
Zhegalkin indices
Walsh
weight
Walsh
index
leader Walsh ¬ Walsh
Q Ж Q Ж
0 0 0 0 👁 Image
0 0 3 👁 Image
15 1
1 1 0 2 👁 Image
10 2 1 👁 Image
5 3
1 2 2 2 👁 Image
12 4 1 👁 Image
3 5
2 3 2 0 👁 Image
6 6 3 👁 Image
9 7

3-ary

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


4-ary

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

misc.

[edit | edit source]

The Zhegalkin indices of these sets of 3-ary BF form truth tables of linear functions. (The entries 0 and 1 are missing from the columns on the left.)

👁 Image
balanced
👁 Image
strength 2   (family size 4)