Jump to content

4-ary Boolean functions

Add links
From Wikiversity
Studies of Boolean functions
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 A116549.

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=2710921"