An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits
In this paper, the problem of Boolean function's representation by the reversible circuits constructed of the Toffoli gates is considered. Interest in this problem is connected with actual studies of the possibility for realization of "cold" computations. It means that when performing...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Irkutsk State University
2018-09-01
|
| Series: | Известия Иркутского государственного университета: Серия "Математика" |
| Subjects: | |
| Online Access: | http://mathizv.isu.ru/assets/articles/c0195bec-9c18-4e30-be8f-56104e36dc28.pdf |
| _version_ | 1818021119530106880 |
|---|---|
| author | A.S. Frantseva |
| author_facet | A.S. Frantseva |
| author_sort | A.S. Frantseva |
| collection | DOAJ |
| description | In this paper, the problem of Boolean function's representation by the reversible circuits constructed of the Toffoli gates is considered. Interest in this problem is connected with actual studies of the possibility for realization of "cold" computations. It means that when performing such computations, there is no heat dissipation.
In general, reversible circuits realize reversible functions. Therefore, Toffoli-Fredkin's method for representation of the Boolean function by the reversible function is used.
In work, an algorithm for finding the minimal representation of the Boolean function in a class of the reversible circuits, which are constructed from Toffoli elements is described. The algorithm uses the polynomial normal forms or exclusive-or sum-of-products expressions (ESOPs) of the Boolean function in the operator representation and the problem of finding the minimal representation of the Boolean function in the certain class of operator bundles. The chosen class of operator bundles corresponds to a class of the extended polarized Zhegalkin polynomials, which includes a well-known class of the polarized Zhegalkin polynomials or Reed-Muller forms.
In conclusion, the computational results of the algorithm for minimizing the Boolean functions in the class of reversible circuits are given. |
| first_indexed | 2024-04-14T08:15:04Z |
| format | Article |
| id | doaj.art-88362c49ab7a4853b5ec5e2090ac662e |
| institution | Directory Open Access Journal |
| issn | 1997-7670 2541-8785 |
| language | English |
| last_indexed | 2024-04-14T08:15:04Z |
| publishDate | 2018-09-01 |
| publisher | Irkutsk State University |
| record_format | Article |
| series | Известия Иркутского государственного университета: Серия "Математика" |
| spelling | doaj.art-88362c49ab7a4853b5ec5e2090ac662e2022-12-22T02:04:26ZengIrkutsk State UniversityИзвестия Иркутского государственного университета: Серия "Математика"1997-76702541-87852018-09-01251144158https://doi.org/10.26516/1997-7670.2018.25.144An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic CircuitsA.S. FrantsevaIn this paper, the problem of Boolean function's representation by the reversible circuits constructed of the Toffoli gates is considered. Interest in this problem is connected with actual studies of the possibility for realization of "cold" computations. It means that when performing such computations, there is no heat dissipation. In general, reversible circuits realize reversible functions. Therefore, Toffoli-Fredkin's method for representation of the Boolean function by the reversible function is used. In work, an algorithm for finding the minimal representation of the Boolean function in a class of the reversible circuits, which are constructed from Toffoli elements is described. The algorithm uses the polynomial normal forms or exclusive-or sum-of-products expressions (ESOPs) of the Boolean function in the operator representation and the problem of finding the minimal representation of the Boolean function in the certain class of operator bundles. The chosen class of operator bundles corresponds to a class of the extended polarized Zhegalkin polynomials, which includes a well-known class of the polarized Zhegalkin polynomials or Reed-Muller forms. In conclusion, the computational results of the algorithm for minimizing the Boolean functions in the class of reversible circuits are given.http://mathizv.isu.ru/assets/articles/c0195bec-9c18-4e30-be8f-56104e36dc28.pdfreversible circuitToffoli functionsBoolean functionspolarized Zhegalkin polynomials or Reed-Muller forms |
| spellingShingle | A.S. Frantseva An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits Известия Иркутского государственного университета: Серия "Математика" reversible circuit Toffoli functions Boolean functions polarized Zhegalkin polynomials or Reed-Muller forms |
| title | An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits |
| title_full | An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits |
| title_fullStr | An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits |
| title_full_unstemmed | An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits |
| title_short | An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits |
| title_sort | algorithm for minimization of boolean functions in the class of toffoli reversible logic circuits |
| topic | reversible circuit Toffoli functions Boolean functions polarized Zhegalkin polynomials or Reed-Muller forms |
| url | http://mathizv.isu.ru/assets/articles/c0195bec-9c18-4e30-be8f-56104e36dc28.pdf |
| work_keys_str_mv | AT asfrantseva analgorithmforminimizationofbooleanfunctionsintheclassoftoffolireversiblelogiccircuits AT asfrantseva algorithmforminimizationofbooleanfunctionsintheclassoftoffolireversiblelogiccircuits |