4-ary Boolean functions

From testwiki
Jump to navigation Jump to search

Template:Boolf header

File:Venn 0000 0001 0001 0110.png
Venn diagram of the Boolean function
0000 0001 0001 0110

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


Big equivalence classes (bec)

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.
Template:Font *

Greatest big equivalence classes (ggbec)

Walsh equivalence classes (wec)

32768 = 215


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


Ring count vectors (rcv)

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 Template:Font.


For the next function the rcv is Template:Font:


The vectors are not always so regular. For the next function it is Template:Font:


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 (Template:Font,Template:Font).

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 Template:Font.

In the ggbec table above only the first digits are shown, because the rcvs have the pattern Template:Font,Template:Font. 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 Template:Oeis.

Subgroups of nimber addition

See: Subgroups of nimber addition#Z24

Bent functions

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

Their nonlinearity is 24−1−242−1=8−2=6 and their Hamming weight is 24−1±242−1=8±2 .

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


Template:Font
    
The simplest example
of a 4-ary bent function:
x1∧x2⊕x3∧x4
Template:Font
    
Template:Font
    
Template:Font



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.
Template:Rdrdo Walsh permutation; bent functions

About the bec files

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.




Template:Commons

Retrieved from "https://en.wikiversity.beta.math.wmflabs.org/w/index.php?title=4-ary_Boolean_functions&oldid=1111"