4-ary Boolean functions

From Wikiversity
Jump to navigation Jump to search
Venn diagram of the Boolean function
0000 0001 0001 0110

There are = 65536 4-ary Boolean functions, which correspond to 16-bit binary strings.


Big equivalence classes (bec)[edit | edit source]

Compare: Big equivalence classes of 3-ary Boolean functions

When binarily colored tesseracts can be transformed into each other by actions in the tesseract's symmetry group C4, they are essentially the same.
The corresponding Boolean functions are often called equivalent and belong to the same big equivalence class (bec).
The 65536 functions belong to 1 + 1 + 4 + 6 + 19 + 27 + 50 + 56 + 74 + 56 + 50 + 27 + 19 + 6 + 4 + 1 + 1 = 402 becs.

The following sortable table (in the collapsed box) shows the 402 becs with some key features.
The default order is that of the numbers in column N. Sorting by # sorts also by N.
The numbers in column weight are the hamming weights of the functions, i.e. the number of ones in the binary strings.
Column sec tells the number of secs in the bec. Column f tells the number of functions in the bec.
The function with the smallest numerical value is shown in column F as an example. It's numerical value is shown in column N.
becs with an entry in column sona are related to subgroups of nimber addition.
The entry in column wec denotes the Walsh equivalence class the bec belongs to.
The nonlinearity of all functions in the bec is shown in column nonlin.
Functions with nonlinearity 0 are linear, those with nonlinearity 6 are bent.
To sort by more than one column you can hold the shift-key and than click the other sort buttons. *

Greatest big equivalence classes (ggbec)[edit | edit source]

Walsh equivalence classes (wec)[edit | edit source]

32768 = 215


2048 = 211
8192 = 213
12288 = 212 * 3
8192 = 213
2048 = 211


Ring count vectors (rcv)[edit | edit source]

A step back:
The 16 2-ary Boolean functions correspond to the subsets of the nested set or hereditarily finite set V3 = P3({}) = { {} , {{}} , {{{}}} , {{},{{}}} }.
That is hard to read, so the nested sets are represented by nested rings of different size.

In the same way every 4-ary Boolean function corresponds to a subset of V4 = P4({}):

This set corresponds to the tautology. The cardinality of the subsets of V4 corresponds to the weight of the functions, in this case 16. Without the outer ring there are four different sizes of rings in these graphics. By counting also the smaller rings, the concept of weight can be refined, which leads to a 4-place ring count vector (rcv) for every 4-ary Boolean function. For the tautology it is (16,32,32,16).


For the next function the rcv is (8,16,16,8):


The vectors are not always so regular. For the next function it is (7,10,8,4):


Every set of 4-ary Boolean functions has a 5-place rcv where the first digit is the set's cardinality. E.g. the set that contains only the above-mentioned function has the rcv (1,7,10,8,4).

Sets of functions that are of some interest are equivalence classes. The last four digits in the rcvs of equivalence classes usually have the pattern n,2n,2n,n.

In the ggbec table above only the first digits are shown, because the rcvs have the pattern n,8n,16n,16n,8n. This is also true for the wec table, because a wec is a union of many ggbecs.

Every rcv has a leading one for the surrounding set, but for the sake of brevity it was omitted here. With it the sums are Sloane's A116549.

Hamming weight 8[edit | edit source]

There are = 12870 balanced 4-ary Boolean functions (with 8 ones in their binary string).

They belong to 74 becs, which are linked in the following table:

10 11 12 13 14 15 16

0T

08 0T 08 08

0T 04 088 088

042 08 08

04

0T

0T3 0TT 088

0T2 088 0TT

043 088 088 0TT

0T2 0T 088

0T1 041 088

088 01823

044 044 044 03823 02822 01812 02813

03812

0S4

0S4

0T1 043 0T3

041

088 02833 02S24

02811

01S34

03S14

04013

04022

0 11 22 33 4 0 11 2222 33

0 111 222 3 S 1 222 333 4

0 1 222 333 S 111 222 3 4

0 222222 4 0 1111 3333

The numbers 0, 4, 8, T (twelve) and S (sixteen) tell the number of dots in the last line of the small matrices.
The subscripts on the left side tell the rank of the lines without dots in the small matrices.
(The top row with rank 0 is always without dots, so the 0 is always there.)
The subscripts on the right side tell the rank of the lines full of dots.

The rank of a line is the number of negated arguments.
(Compare big matrices, where the arguments are shown. The top line of a matrix has rank 0, the last line has rank 4.)

The dots in the big matrices show the bits that differ from the top line in the whole bec (the whole file).
The dots in the small matrices show the bits that differ from the top line in the sec (the actual matrix).

Big equivalence classes that are complements (and thus form a gbecs) are linked next to each other.
Links are bold when the bec contains self complementary secs with 16 elements.

Subgroups of nimber addition[edit | edit source]

See: Subgroups of nimber addition#Z24

Bent functions[edit | edit source]

There are 896 4-ary Bent functions,
which belong to four different greater big equivalence classes (gbecs).

Their nonlinearity is and their Hamming weight is .

Only the functions with Hamming weight 6 are shown. Those with Hamming weight 10 are their complements.


Belongs to BEC 391
with 16 functions.
    
The simplest example
of a 4-ary bent function:

Belongs to BEC 381
with 3*16 functions.
    
Belongs to BEC 382
with 12*16 functions.
    
Belongs to BEC 383
with 12*16 functions.



It's worth taking a look at the distribution of dots in the small matrices in the bec files.
They are all closely related to permuted Walsh matrices,
which is not the case for any other 4-ary Boolean functions.
Even more: Only the bent functions have 8 dots in every row (except the top row) of the small matrices.
Walsh permutation; bent functions

About the bec files[edit | edit source]

The files in this category describe big equivalence classes (becs).
They contain 24 sections, showing 16×16 sec matrices and a number between 0 and 23, representing a permutation of the four arguments.
The big matrices and the small matrices on the right show the same background colors representing binary numbers, but they differ in the dots.
In the big matrices the dots show which fields differ from the top row in the top matrix, while in the small matrices the dots show which fields differ from the top row of the matrix itself.
The numbers in the small left matrices show how the bits of the Boolean function in the top row of the top matrix are permuted. Their top rows are bit permutations.





Wikimedia Commons has media related to 4-ary Boolean functions.
Retrieved from "https://en.wikiversity.org/w/index.php?title=4-ary_Boolean_functions&oldid=2191775"