Academic literature on the topic 'Minimization of Boolean functions in the Reed-Muller basis'

This paper reports a study that has established the possibility of improving the effectiveness of the method of figurative transformations in order to minimize Boolean functions on the Reed-Muller basis. Such potential prospects in the analytical method have been identified as a sequence in the procedure of inserting the same conjuncterms of polynomial functions followed by the operation of super-gluing the variables. The extension of the method of figurative transformations to the process of simplifying the functions of the polynomial basis involved the developed algebra in terms of the rules for simplifying functions in the Reed-Muller basis. It was established that the simplification of Boolean functions of the polynomial basis by a figurative transformation method is based on a flowchart with repetition, which is actually the truth table of the predefined function. This is a sufficient resource to minimize functions that makes it possible not to refer to such auxiliary objects as Karnaugh maps, Weich charts, cubes, etc. A perfect normal form of the polynomial basis functions can be represented by binary sets or a matrix that would represent the terms of the functions and the addition operation by module two for them. The experimental study has confirmed that the method of figurative transformations that employs the systems of 2-(n, b)-design, and 2-(n, x/b)-design in the first matrix improves the efficiency of minimizing Boolean functions. That also simplifies the procedure for finding a minimum function on the Reed-Muller basis. Compared to analogs, this makes it possible to enhance the performance of minimizing Boolean functions by 100‒200 %. There is reason to assert the possibility of improving the efficiency of minimizing Boolean functions in the Reed-Muller basis by a method of figurative transformations. This is ensured by using more complex algorithms to simplify logical expressions involving a procedure of inserting the same function terms in the Reed-Muller basis, followed by the operation of super-gluing the variables.

This paper reports a study that has established the possibility of improving the effectiveness of the method of figurative transformations in order to minimize Boolean functions on the Reed-Muller basis. Such potential prospects in the analytical method have been identified as a sequence in the procedure of inserting the same conjuncterms of polynomial functions followed by the operation of super-gluing the variables. The extension of the method of figurative transformations to the process of simplifying the functions of the polynomial basis involved the developed algebra in terms of the rules for simplifying functions in the Reed-Muller basis. It was established that the simplification of Boolean functions of the polynomial basis by a figurative transformation method is based on a flowchart with repetition, which is actually the truth table of the predefined function. This is a sufficient resource to minimize functions that makes it possible not to refer to such auxiliary objects as Karnaugh maps, Weich charts, cubes, etc. A perfect normal form of the polynomial basis functions can be represented by binary sets or a matrix that would represent the terms of the functions and the addition operation by module two for them. The experimental study has confirmed that the method of figurative transformations that employs the systems of 2-(n, b)-design, and 2-(n, x/b)-design in the first matrix improves the efficiency of minimizing Boolean functions. That also simplifies the procedure for finding a minimum function on the Reed-Muller basis. Compared to analogs, this makes it possible to enhance the performance of minimizing Boolean functions by 100‒200 %. There is reason to assert the possibility of improving the efficiency of minimizing Boolean functions in the Reed-Muller basis by a method of figurative transformations. This is ensured by using more complex algorithms to simplify logical expressions involving a procedure of inserting the same function terms in the Reed-Muller basis, followed by the operation of super-gluing the variables.

Cryptographic methods today are a crucial tool for constructing information security systems. At the same time, to solve the problem of encrypting large amounts of information, block or stream symmetric ciphers are mainly preferred because of their efficiency and proven cryptographic strength, including against perspective quantum cryptanalysis. The effectiveness of modern symmetric ciphers largely depends on the cryptographic S-boxes applied in their construction, the quality of which largely determines the degree of implementation of the concepts of diffusion and confusion by the cryptographic algorithm, while the presence of large sets of cryptographically high-quality S-boxes is also important, in the terms of their application as a long-term key. Today, the Nyberg construction is well-known and widely applied in ciphers, including widespread AES block symmetric cipher. This construction allows you to synthesize high-quality S-boxes that harmoniously satisfy the main criteria for cryptographic quality, however, the set of S-boxes synthesized using this construction is small, which makes the task of developing new methods for synthesizing large sets of cryptographically high-quality S-boxes highly relevant. At the same time, as research shows, the constructions of extended Galois fields are a promising raw material for solving this problem. In this paper, the Galois field transform matrices of order N=256 are constructed for all isomorphic representations of the extended Galois field GF(256) which are analogous to the Reed-Muller transform but for the case of many-valued logic functions. As part of the research, the isomorphism invariant row numbers of the Galois field transform matrices are identified, which allows to obtain bijective S-boxes, as well as bijective S-boxes that correspond to the main criteria for cryptographic quality of component Boolean functions such as algebraic degree of nonlinearity, distance of nonlinearity, error propagation criterion, and criterion of minimization of correlation of output and input vectors of the S-box. At the same time, the cardinality of the set of synthesized S-boxes is ~23 times higher than the cardinality of the set of S-boxes of the Nyberg construction, which allows them to be used as a long-term key. The proposed S-boxes can become the basis for improving the effectiveness of existing symmetric cryptographic algorithms and developing new ciphers.

This paper presents the results of an experimental comparison of methods for the synthesis of combinational logic circuits that implement specified Boolean functions. The following methods were considered: the method of Akers, bi-decomposition, the methods of cascades, Minato-Morreale, Reed-Muller and DSD-decomposition. The comparison was based on an estimate of power, delay and area of synthesized logic circuits. The evaluation was carried out without the process of technology mapping of the circuits. These parameters were chosen because they are the main criteria for technology-independent optimization, where these methods are widely used. Boolean functions with the number of arguments from 4 to 10 were used as input data. They were generated on the basis of information on the frequency of occurrence of various NPN-equivalence classes of Boolean functions of 4 variables. As a result of the study, it was found that the Minato-Morreale method is the most universal in solving technology-independent optimization problems and can be used for different criteria.

The increased number of complex functional units exerts high power-density within a very-large-scale integration (VLSI) chip which results in overheating. Power-densities directly converge into temperature which reduces the yield of the circuit. An adverse effect of power-density reduction is the increase in area. So, there is a trade-off between area and power-density. In this paper, we introduce a Shared Reed-Muller Decision Diagram (SRMDD) based on fixed polarity AND-XOR decomposition to represent multioutput Boolean functions. By recursively applying transformations and reductions, we obtained a compact SRMDD. A heuristic based on Genetic Algorithm (GA) increases the sharing of product terms by judicious choice of polarity of input variables in SRMDD expansion and a suitable area and power-density trade-off has been enumerated. This is the first effort ever to incorporate the power-density as a measure of temperature estimation in AND-XOR expansion process. The results of logic synthesis are incorporated with physical design in CADENCE digital synthesis tool to obtain the floor-plan silicon area and power profile. The proposed thermal-aware synthesis has been validated by obtaining absolute temperature of the synthesized circuits using HotSpot tool. We have experimented with 29 benchmark circuits. The minimized AND-XOR circuit realization shows average savings up to 15.23% improvement in silicon area and up to 17.02% improvement in temperature over the sum-of-product (SOP) based logic minimization.

In this paper, we consider the problem of logic simplification for a special class of logic functions, namely complementary Boolean functions (CBF), targeting low power implementation using static CMOS logic style. The functions are uniquely characterized by the presence of terms, where for a canonical binary 2-tuple, D(mj) ∪ D(mk) = { } and therefore, we have | D(mj) ∪ D(mk) | = 0 [19]. Similarly, D(Mj) ∪ D(Mk) = { } and hence | D(Mj) ∪ D(Mk) | = 0. Here, 'mk' and 'Mk' represent a minterm and maxterm respectively. We compare the circuits minimized with our proposed method with those corresponding to factored Reed-Muller (f-RM) form, factored Pseudo Kronecker Reed-Muller (f-PKRM) form, and factored Generalized Reed-Muller (f-GRM) form. We have opted for algebraic factorization of the Reed-Muller (RM) form and its different variants, using the factorization rules of [1], as it is simple and requires much less CPU execution time compared to Boolean factorization operations. This technique has enabled us to greatly reduce the literal count as well as the gate count needed for such RM realizations, which are generally prone to consuming more cells and subsequently more power consumption. However, this leads to a drawback in terms of the design-for-test attribute associated with the various RM forms. Though we still preserve the definition of those forms viz. realizing such functionality with only select types of logic gates (AND gate and XOR gate), the structural integrity of the logic levels is not preserved. This would consequently alter the testability properties of such circuits i.e. it may increase/decrease/maintain the same number of test input vectors needed for their exhaustive testability, subsequently affecting their generalized test vector computation. We do not consider the issue of design-for-testability here, but, instead focus on the power consumption of the final logic implementation, after realization with a conventional CMOS process technology (0.35 micron TSMC process). The quality of the resulting circuits evaluated on the basis of an established cost metric viz., power consumption, demonstrate average savings by 26.79% for the samples considered in this work, besides reduction in number of gates and input literals by 39.66% and 12.98% respectively, in comparison with other factored RM forms.