Главная > Оптика > Оптические вычисления
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

9.3. Проблемы создания логических схем для волоконно-оптических систем

9.3.1. Методы минимизации и оптимального присваивания переменных

История развития методов логической минимизации является и длинной, и достаточно интересной. Процессминимизации с точки зрения процедуры вычислений является настолько сложным, что, даже используя для выполнения этой задачи

суперкомпьютер, все равно требуется вводить более 30 переменных. Процесс поиска все более эффективных подходов начался разработкой таких точных методов, как алгоритмы Квина—Маккласки [24] и Шейнманна [25], и привел к созданию таких эвристических подходов, как MINI [26] и ESPRESSO [27]. В работе [28] было установлено, что для определенных видов функций использование 2-разрядных декодеров с оптимальным присваиванием переменных может быть гораздо более эффективным, чем применение традиционных двухуровневых ПЛМ, т. е. ПЛМ с -разрядным декодером. В качестве примера следует заметить, что для операции -разрядного сложения без переноса цифр в разрядах и -разрядного декодера число минимизированных термов экспоненциально зависит от тогда как для 2-разрядного декодера и при оптимальном присваивании переменных число термов пропорционально Для 2-разрядного декодера оптимальное присвоение переменных представляет собой просто процедуру правильного попарного «соединения» входных сигналов в каждом декодере, т. е. попарное сложение соответствующих битов от двух складываемых чисел, а не просто сложение произвольных 2 битов в пределах каждого из чисел. Кроме того, для еще большего уменьшения числа логических элементов в системе фазы выходных сигналов часто тоже могут быть оптимизированы. Для случая применения декодеров, позволяющих использовать многозначных входных сигналов и обеспечивающих формирование двоичных выходных сигналов (т. е. декодеров, работающих с основанием и позволяющих преобразовать проблема оптимального присвоения переменных становится одной из основных задач кодирования входного сигнала [29].

В противоположность случаю ПЛМ с -разрядным декодером ПЗУ полностью декодирует входных сигналов, создавая все возможные минтермов (элементарных конъюнктивных форм). Этот тип устройств фактически требует использования только одной комбинации логических элементов. С точки зрения математики различие между ПЗУ и ПЛМ может быть рассмотрено как разница между устройствами, способными проводить полное декодирование входных переменных, и устройствами, способными проводить только частичное декодирование переменных входного сигнала. Цель, которую преследовали авторы при написании данного раздела, заключается в исследовании промежуточной области между ПЗУ и обычными ПЛМ путем анализа влияния возможностей декодеров высоких порядков на число комбинаций логических элементов в ПЛМ. В следующих двух частях этого раздела будет показано, что, хотя число комбинаций, необходимых для реализации конкретной функции, всегда монотонно уменьшается с увеличением порядка декодера, необходимые производительность вычислений

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

<< Предыдущий параграф Следующий параграф >>
Оглавление