Кафедра ИУ3
3 апреля 2012, 14:00

Аналитический синтез комбинационных схем

Докладчик: Выхованец В. С.

Организация: Институт проблем управления РАН, МГТУ им. Н. Э. Баумана

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