Всеукраїнська науково-практична конференція



Сторінка52/60
Дата конвертації11.05.2018
Розмір3.74 Mb.
1   ...   48   49   50   51   52   53   54   55   ...   60

КУКУРУДЗЯК В.А., ДЕЙБУК В.Г.


ЧЕРНІВЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ЮРІЯ ФЕДЬКОВИЧА

(УКРАЇНА)

СИНТЕЗ ЗВОРОТНИХ ВІДМОВОСТІЙКИХ МУЛЬТИПЛЕКСОРІВ



Зворотна логіка останнім часом використовується в нанотехнологіях, оптичному та квантовому комп’ютинзі. В роботі використано принципи еволюційної електроніки та генетичні алгоритми для синтезу зворотних мультиплексорів. Синтез проведено в базисі відмовостійких зворотних вентилів Фредкіна. Отримана схема мультиплексора 4×1 є оптимальною за часом затримки, апаратною складністю та квантовою ціною.
Сучасні комп’ютерні системи будуються на основі традиційної незворотної цифрової електроніки. Вказана незворотність неминуче веде до розсіяння енергії вже на рівні найпростіших логічних елементів, що пов’язано з втратою інформації. Причому величина розсіяного тепла пропорційна до кількості втрачених бітів. Уникнути вказаних втрат інформації, а відтак зменшити теплове випромінювання комп’ютерних систем можна лише за рахунок використання пристроїв, збудованих на основі зворотної логіки. Логічний елемент є зворотним, якщо він здійснює бієктивне відображення вхідних сигналів у вихідні. Останнім часом зворотна логіка знаходить все ширше використання в пристроях низькопотужної електроніки, оптичного та квантового комп’ютингу, біоінформатиці, а також нанотехнологіях, де, поряд з іншими, важливою умовою є екстремально низьке розсіяння тепла. Однак синтез базових пристроїв зворотної електроніки є значно складнішою задачею, оскільки ще не розроблені методи та засоби такого синтезу.

На сьогодні запропоновано багато зворотних логічних елементів, зокрема, вентилі Фейнмана, Тоффолі, Переса, Фредкіна та ін[1]. Однак лише деякі з них є функціонально повними і зберігають парність вхідних сигналів. Перевірка парності є одним з основних методів виявлення помилок в цифрових логічних системах, що вимагає також прийняття відповідних заходів на апаратному рівні для їх корекції. Саме тому важливим є синтез зворотних вентилів та мереж, що зберігають парність. Основні логічних операцій AND, OR, XOR та ADD можуть бути реалізовані з використанням зворотного мультиплексора 4×1[2]. Для синтезу останнього нами використано в якості базисного зворотний логічний елемент Фредкіна, який є функціонально повним, зберігає парність і є елементом контрольованого обміну, виконуючи перетворення:



де А, В, С – вхідні, P, Q, R – вихідні сигнали.

У даній роботі запропоновано вдосконалений підхід до синтезу квантових зворотних мультиплексорів, що ґрунтується на використанні генетичних алгоритмів. Такий підхід до зворотного логічного синтезу пов’язаний з необхідністю врахування кількох додаткових умов, а саме, заборона розгалуження за входом та виходом (теорема про заборону клонування [1]) та заборона обернених зв’язків, тобто подача вихідних сигналів логічних елементів на їх входи. Генетичні алгоритми [3] належать до адаптивних мета-евристичних алгоритмів пошуку оптимального розв’язку різного роду проблем на основі еволюційної ідеї природної селекції та генетики. Вони використовують інтелектуальний випадковий пошук для вирішення проблеми оптимізації у великих просторах станів за багатьма критеріями. До переваг цих алгоритмів можна віднести: а) обробляються не параметри самої задачі, а їх закодована форма; б) пошук варіантів та розв’язків здійснюється не з однієї точки, а з так званої популяції; в) використовується лише цільова функція; г) застосовують імовірнісні, а не детерміновані правила вибору.

В якості параметрів оптимізації нами були вибрані:



  • мінімальна кількість елементів;

  • мінімальна кількість зайвих виходів та входів;

  • мінімальна кількість логічних помилок вихідного сигналу;

  • мінімальна часова затримка;

  • мінімальна квантова вартість.

Оскільки хромосома є набором генів, а схема – певне послідовно-паралельне розташування логічних вентилів Фредкіна, а також інформація про вхідні сигнали, то кожен ген представляє собою один послідовний крок обробки сигналів, що може складатися з кількох паралельно розміщених логічних елементів. Таким чином, аналізовані логічні схеми (хромосоми) представимо як набір горизонтальних ліній (пінів), вздовж яких передається інформація і вертикальних секцій, які можуть складатися з кількох логічних елементів, в яких відбувається паралельна обробка інформації, і які відповідають генам. При цьому кожен ген кодується у вигляді масиву пар цілих чисел, де перше число в кортежі позначає порядковий номер відповідного логічного елемента в гені, а друге число – порядковий номер піна даного логічного елемента (рис.1).

Оптимізована схема (рис.2,а) зворотного мультиплексора 4×1 використовує 3 елементи Фредкіна, має три зайві виходи, затримка мультиплексора рівна 3, квантова вартість становить 15. Як видно з таблиці істинності (рис. 2,б), яка генерується програмою, на логічному рівні схема працює коректно.



multiplexer.png



а)

таблиця переробл остання
Рис. 1. Хромосома схеми

б)

Рис. 2. Мультиплексор 4×1 на елементах



Фредкіна

Отже, в роботі запропоновано новий спосіб кодування хромосом у генетичному алгоритмі для моделювання схем зворотних мультиплексорів у базисі елементів Фредкіна. Отримана з допомогою такого підходу схема має оптимальні параметри затримки, апаратної складності, квантової вартості та кількості зайвих виходів, що демонструє ефективність та застосовність такого підходу.



ПЕРЕЛІК ЛІТЕРАТУРИ

    1. Nielsen M.A., Chuang I.L. Quantum computation and quantum information. NY: Cambridge University Press, 2001.

    2. Thomsen M.K., Gluck R., Axelsen H.B. Reversible arithmetic logic unit for quantum arithmetic // J. Phys. A, v. 43 (2010), 382002.

    3. Zebulum R.S., Pachecco M.C., Vellasco M.M. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. – CRC Press, 2002.


УДК 004.312


Поділіться з Вашими друзьями:
1   ...   48   49   50   51   52   53   54   55   ...   60


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка