350 rub
Journal Radioengineering №3 for 2014 г.
Article in number:
System analysis of computational boolean function polynomial transform algorithms
Authors:
А.А. Аkinin - Ph.D. (Eng.), Voronezh State Technical University. E-mail: aayu@vorstu.ru
А.V. Achkasov - Ph.D. (Eng.), research institute of electronic engineering. E-mail: achkasov@list.ru
S.L. Podvalniy - Dr.Sci. (Eng.), professor, Voronezh State Technical University. E-mail: spodvalny@yandex.ru
S.V. Tjurin - Ph.D. (Eng.), professor, Voronezh State Technical University. E-mail: tsv@mail.ru
А.V. Achkasov - Ph.D. (Eng.), research institute of electronic engineering. E-mail: achkasov@list.ru
S.L. Podvalniy - Dr.Sci. (Eng.), professor, Voronezh State Technical University. E-mail: spodvalny@yandex.ru
S.V. Tjurin - Ph.D. (Eng.), professor, Voronezh State Technical University. E-mail: tsv@mail.ru
Abstract:
The unique advantage of polynomial logic converters is that their structural testing use the test vectors with unified bit structure. At the same time the sufficient and necessary number of test vectors to detect any single stuck-at faults does not exceed three times the number of arguments of a Boolean function.
The paper is intended to find the bests oft ware implementations of polynomial transformation algorithms of Boolean functions allowing the ir practical application in the FPGA, in both batch and unit production of digital equipment, using personal computing tools.
Thepapershowsseveralcompetingcomputationalgorithmsdevelopedinaccordancewiththeprinciplesofmultiple-choice system shaving different performance criterion as algorithmic (computational) and volume complexity criterion.
In particular, the approach to the automatic conversion of Boolean functions to Zhegalkin polynomial based on the method of undetermined coefficients and algorithm developed on the basis of identified logical laws of this approach is considered.
Two algorithms with the fundamentally reduced computational complexity are described. The computation complexity elimination means include the additional logic-arithmetic index code conversion.
An algorithm for a Boolean function conversion on the basis of the finite difference method based on Boolean functions differentiating features is also considered.
Another proposed algorithm use the well-known method implementing the Boolean function decomposition, taking into account the fractality of transformations of ordered vector component of the values of a Boolean function to the ordered components of the vector which are unknown coefficients of Zhegalkin polynomein its general form. This algorithm is ultimately based on undetermined coefficients method modified in a very interesting way.
This paper describes a novel approach to the polynomial expansion of n-argument Boolean functions combining the vector method of inverse finite difference method and binary fractal transformation method. As shown here in, this method is extremely focused on the binary-vector polynomial decomposition of Boolean functions for implementation by means of computer tools. The estimation of the computational complexity of the algorithm is done.
In conclusion, the graphs illustrating the comparison of computational complexity of n-argument Boolean function polynomial transformation algorithms for 32-bit computers are discussed in this paper. The main advantage of the algorithm in binary-vector polynomial decomposition of Boolean functions based on the composition of vector method of finite differences and reverse binary fractal transformation method having lower computational complexity is also highlighted.
Pages: 104-108
References
- Hirayama T., Nagasawa K., Nishitani Y., Shimizu K. Double Fixed-Polarity Reed-Muller Expressions: A New Class of AND-EXOR Expressions for Compact and Testable Realization // IPSJ Journal. 2001. V. 42. № 4. P. 983-991.
- Akinina Ju.S., Tyurin S.V. Al'ternativny'j podxod k obespecheniyu diagnostiruemosti dvuxurovnevy'x programmiruemy'x pol'zovatelem logicheskix matricz // Vestnik VGTU. 2003. Vy'p. 8.3. C. 32-35.
- Patent № 2413282 Rossijskaya Federacziya, MPK7 - G 06 F 011/22.
- Zhegalkin I.I. Arifmetizacziya simvolicheskoj logiki // Matematicheskij sbornik Moskovskogo matematicheskogo obshhestva. 1927. T. 354. S. 9-28.
- Zakrevskij A.D., Toropov N.R. Polinomial'naya realizacziya chastichny'x bulevy'x funkczij i sistem. M.: Editorial URSS. 2003. 200 s.
- Akinin A. A., Akinina Ju.S., Podval'ny'j S.L., Tyurin S.V. Avtomatizacziya polinomial'nogo razlozheniya bulevy'x funkczij na osnove metoda neopredelenny'x koe'fficzientov // Sistemy' upravleniya i informaczionny'e texnologii. 2011. T. 44. № 2. S. 4-8.
- Akinin A.A., Akinina Ju.S., Tyurin S.V. Avtomatizacziya polinomial'nogo razlozheniya bulevy'x funkczij na osnove metoda konechny'x raznostej // Sistemy' upravleniya i informaczionny'e texnologii. 2011. T 46. № 4. S. 69-73.
- Akinin A.A. Algoritm fraktal'nogo polinomial'nogo razlozheniya bulevy'x funkczij // Vestnik VGTU. 2011. T. 7. № 11. C. 85-88.
- Akinin A.A. Avtomatizacziya polinomial'nogo razlozheniya bulevy'x funkczij metodom fraktal'ny'x preobrazovanij // Materialy' V Mezhdunarodnoj nauchno-prakticheskoj konferenczii «Intellektual'ny'j potenczial molody'x ucheny'x Rossii i zarubezh'ya». M.: Sputnik+. 2012. S. 9-18.
- Akinin A.A., Akinina Ju.S., Tyurin S.V. Metod binarno-vektornogo polinomial'nogo razlozheniya bulevy'x funkczij // Sbornik trudov V Vserossijskoj NTK «Problemy' razrabotki perspektivny'x mikro- i nanoe'lektronny'x sistem 2012». M.: IPPM RAN. 2012. S. 55-60.
- Podval'ny'j S.L. Mnogoal'ternativny'e sistemy': obzor i klassifikacziya // Sistemy' upravleniya i informaczionny'e texnologii. 2012. T. 48. № 2. S. 4-13.
- Matematicheskaya e'ncziklopediya: Gl. red. I.M. Vinogradov. T. 1-A-G. M.: Sovetskaya e'ncziklopediya. 1977. 1152 s.
- Kriniczkij N.A. Ravnosil'ny'e preobrazovaniya algoritmov i programmirovanie. M.: Sov. radio. 1970. 304 s.
- Gavrilov G.P., Sapozhenko A.A. Zadachi i uprazhneniya po diskretnoj matematike: Ucheb. posobie. Izd. 3-e, pererab. M.: Fizmatlit. 2005. 416 s.
- Gorbatov V.A., Gorbatov A.V., Gorbatova M.V. Teoriya avtomatov: ucheb. dlya studentov vtuzov. M.: AST Astrel'. 2008. 559 s.
- Boxmann D., Postxof X. Dvoichny'e dinamicheskie sistemy'. M.: E'nergoatomizdat. 1986. 400 s.
- Matematicheskaya e'ncziklopediya: Gl. red. I.M. Vinogradov. T. 2-D-K. M.: Sovetskaya e'ncziklopediya. 1979. 1104 s.