DOI: 10.17587/prin.8.300-309

On the Equimorphic Computation of the Jevons Group Element Action over Boolean Functions

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

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

The solution of the equation in which an element of the Jevons group acts over a Boolean function reduces to the calculation of factor actions of the canonical representation of this element. According to average estimates a computer with a clock speed of 1 GHz processes (not including overhead) 1 MiB of data (equivalent to the Boolean function of 23 arguments) in approximately 30 minutes. This time is unacceptably large for many tasks of information processing. In this paper, we propose a model of an equimorphic calculator to solve the equation. It is based on three algorithms for three types of factors of the Jevons group canonical representation. Algorithms include elementary logical operations performed on machine words: logical multiplication, logical addition, right and left logical shifts, and assignment. These operations are applied to partitioning of the machine words on the equivalent to Boolean functions data. As a result, the performance of computations increases in proportion to the size of the machine word in compare to the processing of single values of the function. Moreover the machine words can be processed in a parallel way. So we can improve the performance of calculations by increasing the number of computing cores. Eventually, the performance of computations is increased by hundreds and thousands of times in relation to algorithms for processing individual values of the function. The algorithms are formulated for an abstract arithmetic logic device which corresponds to both IA-32 and IA-64/ AMD64 architectures of computer processors and to other architectures. For the possibility of working with different capacities, the necessary recommendations and calculation formulas for forming constants for a particular architecture are given. The article contains proofs of the correctness of the algorithms. Also we estimate their complexity. The algorithms can be used for both solving the equations of action of the Jevons group over Boolean functions and implementing such actions themselves.

Keywords: action on the set, the Jevons group, Boolean functions, equations of action on a set, equimorphic groups, abstract machines

pp. 300–309

For citation:
Kukartsev A. M., Kuznetsov A. A. On the Equimorphic Computation of the Jevons Group Element Action over Boolean Functions, Programmnaya Ingeneria, 2017, vol. 8, no. 7, pp. 300—309.

The reported study was funded by RFBR and the government of Krasnoyarsk kray according to the research project № 17-47-240318.