DOI: 10.17587/prin.7.515-521

On Frequency Characteristics Jevons Group Action on Boolean Functions

A. M. Kukartsev, amkukarcev@yandex.ru, Siberian State Aerospace University named after academician M. F. Reshetnev, Krasnoyarsk, 6600014, Russian Federation

Corresponding author: Kukartsev Anatolii M., Senior Lecturer, Siberian State Aerospace University named after academician M. F. Reshetnev, Krasnoyarsk, 6600014, Russian Federation, e-mail: amkukarcev@yandex.ru

Many data processing algorithms are based on statistical methods. Entropy, as the assessment, is characteristic of input and output information objects of such algorithms. Some algorithms use not only entropy but a more detailed assessment — frequencies of symbols. An information object can be created using different alphabets. In particular the object of length 2ⁿ can be constructed on an alphabet of one, two, four, eight, etc. symbols. Construction of information objects with the same frequency characteristics in all its permissible alphabets simultaneously is a difficult problem. The data in modern computers is presented mostly in binary form. Special coding methods allow you to set an injection of information objects of any length into objects of length 2ⁿ. With this coding appears a natural bijection between the information object of length 2ⁿ and a Boolean function. Bit numbers in the binary form are actually arguments of a Boolean function, and bits of the information object are its values. Some transformations of Boolean functions preserve frequency characteristics of theirs information objects. Such transformations of the Boolean function are complements and/or permutations of its arguments. Both sets of acting elements are described by groups of inversion and permutation of variables. Together complements and permutations of arguments are presented by a larger structure — the Jevons group, which is a semi-direct product of these groups. We study the frequency properties of the Jevons group actions on Boolean functions in this article. We prove that frequency characteristics of the information object preserve in all permissible alphabets simultaneously. Also we show that there is a canonical decomposition of any element of the Jevons group. We offer to use these properties for solution of complex mathematical problems related with actions of the Jevons group and it subgroups on the set of Boolean functions. We show methods of creating information objects with the identical and/or equivalent frequency characteristics in all its permissible alphabets simultaneously. The obtained objects can be used for analysis and modification of data processing algorithms.

Keywords: Shannon entropy, action on the set, frequency analysis, the Jevons group, Boolean functions

pp. 515–521

For citation:
Kukartsev A. M. On Frequency Characteristics Jevons Group Action on Boolean Functions, Programmnaya Ingeneria, 2016, vol. 7, no. 11, pp. 515—521.

This work was supported by the Grant of Russian Federation President, project nos. MD-3952.2015.9