НАУКА и ОБРАЗОВАНИЕ

Файл статьи: Zkbl143.pdf (449.00Кб)

УДК 004.312, 530.145	Россия, МГТУ им. Н.Э. Баумана

Предметом исследования в данной статье являются схемы из обратимых логических вентилей. Необратимость вычислений может привести в будущем к значительным тепловым потерям во время вычислительного процесса. Обратимые схемы могут найти широкое применение в устройствах, работающих в условиях ограниченных вычислительных ресурсов.

В настоящее время широко изучается вопрос синтеза обратимых схем. Перед алгоритмом синтеза может встать задача снижения вентильной сложности синтезированной схемы. Одним из способов решения этой задачи является применение таблиц эквивалентных замен композиций вентилей. Недостатком данного подхода является необходимость построения таблиц замен, долгое время поиска замены по таблице и невозможность построить универсальную таблицу замен, подходящую для произвольной обратимой схемы. Цель настоящей работы - разработать способ решения задачи снижения вентильной сложности обратимой схемы без использования таблиц эквивалентных замен композиций вентилей.

В статье делается обобщение представления вентиля k-CNOT для случая нулевого значения на некоторых контролирующих входах. Предлагается в описании таких вентилей использовать множество прямых и множество инвертированных контролирующих входов. Вводится понятие независимости двух обратимых вентилей. Два независимых вентиля, стоящих в схеме рядом друг с другом, могут быть поменяны местами без изменения задаваемого схемой преобразования. Рассматриваются различные условия независимости двух вентилей, накладываемые в том числе и на множество прямых и множество инвертированных контролирующих входов. Доказывается, что два вентиля являются независимыми, если найдется хотя бы один общий контролирующий вход, различающийся только своим типом (прямой или инвертированный).

Рассматриваются различные эквивалентные замены композиций двух вентилей k-CNOT и накладываемые при этом ограничения на множество прямых и множество инвертированных контролирующих входов. Приводится доказательство корректности этих замен путем сравнения задаваемого композицией вентилей преобразования до и после замены. В доказательстве широко используются операции над множеством прямых и множеством инвертированных контролирующих входов. Показывается, что два одинаковых вентиля, стоящих рядом в схеме, могут быть исключены из схемы. Показывается, что в некоторых случаях композицию двух вентилей можно заменить одним вентилем, если вентили отличаются друг от друга только одним контолирующим входом. Часть предлагаемых в работе эквивалентных замен не уменьшает вентильной сложности, однако позволяет получить новые обратимые вентили. После применения таких замен в некоторых случаях можно найти новую пару вентилей, удовлетворяющих условию замены, уменьшающей вентильную сложность. Предлагаемый в данной статье набор эквивалентных замен существенно расширен по сравнению с наборами замен, описываемых в других работах.

Приведено описание алгоритма снижения вентильной сложности обратимой схемы, использующего условия независимости вентилей и предлагаемые эквивалентные замены композиций вентилей. Алгоритм основан на поиске пары вентилей, которые удовлетворяют условию какой-либо замены и которые могут быть перемещены друг к другу без изменения результирующего преобразования схемы (проверяются предлагаемые в работе условия независимости вентилей). Приведен пример работы алгоритма снижения вентильной сложности обратимой схемы для некоторой абстрактной обратимой схемы.

Достоинством предлагаемого способа решения задачи снижения вентильной сложности обратимой схемы является отсутствие необходимости построения таблиц замен и возможность снижения вентильной сложности произвольной схемы, состоящей из вентилей k-CNOT. В дальнейшем предполагается оценить временную сложность предложенного алгоритма снижения вентильной сложности.

Список литературы

1. Bennett C.H. Logical Reversibility of Computation // IBM Journal of Research and Development. 1973. Vol. 17, no. 6. P. 525-532. DOI: 10.1147/rd.176.0525
2. Feynman R.P. Quantum Mechanical Computers // Foundations of Physics. 1986. Vol. 16, no. 6. P. 507-531. DOI: 10.1007/BF01886518
3. Toffoli T. Reversible Computing // In book: Automata, Languages and Programming. Springer Berlin Heidelberg, 1980. P. 632-644. DOI: 10.1007/3-540-10003-2_104 (Ser. Lecture Notes in Computer Science; vol. 85.).
4. Shende V.V., Prasad A.K., Markov I.L., Hayes J.P. Synthesis of Reversible Logic Circuits // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2006. Vol. 22, no.6. P. 710-722. DOI: 10.1109/TCAD.2003.811448
5. Закаблуков Д.В., Жуков А.Е. Исследование схем из обратимых логических элементов // Информатика и системы управления в XXI веке: сб. трудов молодых ученых, аспирантов и студентов. Вып. 9. М.: МГТУ им. Н.Э. Баумана, 2012. С. 148-157.
6. Закаблуков Д.В. Синтез схем из обратимых элементов // ХX Всероссийская научно-практическая конференция "Проблемы информационной безопасности в системе высшей школы", МИФИ (Москва, 01-06 февраля 2013 г.): тез. докл. М.: МИФИ, 2013. С. 100-101.
7. Iwama K., Kambayashi Y., Yamashita S. Transformation Rules for Designing CNOT-based Quantum Circuits // Proceedings of the 39th annual Design Automation Conference (DAC'02). 2002. P. 419-424. DOI: 10.1145/513918.514026
8. Khlopotine A.B., Perkowski M.A., Kerntopf P. Reversible Logic Synthesis by Iterative Compositions // Proc. of the International Workshop on Logic Synthesis. 2002. P. 261-266.
9. Yang G., Song X., Hung W.N., Perkowski M.A. Fast Synthesis of Exact Minimal Reversible Circuits Using Group Theory // Proceedings of the 2005 Asia and South Pacific Design Automation Conference (ASP-DAC'05). 2005. P. 1002-1005. DOI: 10.1145/1120725.1120777
10. Miller D.M., Maslov D., Dueck G.W. A Transformation Based Algorithm for Reversible Logic Synthesis // Proceedings of the 40th annual Design Automation Conference (DAC'03). 2003. P. 318-323. DOI: 10.1145/775832.775915
11. Miller D.M. Spectral and Two-Place Decomposition Techniques in Reversible Logic // Proceedings of the 45th Midwest Symposium on Circuits and Systems Conference (MWSCAS'02). 2002. P. 493-496. DOI: 10.1109/MWSCAS.2002.1186906
12. Saeedi M., Sedighi M., Zamani M.S. A Novel Synthesis Algorithm for Reversible Circuits // Proceedings of International Conference on Computer-Aided Design (ICCAD'07). 2007. P. 65-68. DOI: 10.1109/ICCAD.2007.4397245
13. Yang G., Song X., Hung W.N., Xie F., Perkowski M.A. Group Theory Based Synthesis of Binary Reversible Circuits // Proceedings of the Third international conference on Theory and Applications of Models of Computation (TAMC'06). 2006. P. 365-374. DOI: 10.1007/11750321_35