автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Модели и алгоритмы логического синтеза РЭС

На правах рукописи

РГБ ОД

ЛУЗИН Сергей Юрьевич ^ ^ ^В 1997

МОДЕЛИ И АЛГОРИТМЫ ЛОГИЧЕСКОГО СИНТЕЗА РЭС

Специальность 05.12.13 — Системы и устройства радиотехники и связи

АВТОРЕФЕ РАТ диссертации на соискание ученой степени доктора технических наук

САНКТ-ПЕТЕРБУРГ 1996

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. Л\. А. Бо.нч-Бруевича.

Официальные олнонгагты: д. т. п., проф. И. Г. Л1ИРОНЕНК.О,

д. т. н„ проф. И. Л. ЕРОШ, д. т. и., проф. Л. Ф. ГРИГОРОВСЖИП.

Ведущая организация: ГП «Дальняя связь».

Защита состоится 16 января 1997 г. в 14 часов на заседании диссертационного совета Д 118.01.02 Салкт-Петербургского государственного университета телекоммуникаций им. цроф. М. А. Бонч-Бруеанча по адресу: 191186, СПб, :наб. ,реки Мойки, 61.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан « ^. » . 1996 г.

Ученый секретарь специализированного совета д. т. н., профессор

В .Н.Гомг

Подписано к печати 29.11.96 г. ЛР 020475 от 10.03.92 г. Объо,м 2 печ. л. Тир. 100 экз. Бесплатно. Зак. 450.

Тип. СПбГУТ. 198320, СПб, ул. Свободы, 31

ОБЩАЯ ХАРАКТЕРИСТИКА РЛЬОТЫ

Актуальность проблемы. Успехи в области интегральной техно.ю-ии, достигнутые за последние 10-15 лет привели к созданию больших ■штегральных схем (БИС), содержащих десятки и сотни тысяч элемент» 1а одном кристалле. Быстрый рост размерности решаемых при разработке эИС задач приводит к необходимости постоянного развития теории и фактики автоматизированного проектирования.

Одним из наиболее трудоемких этапов проектирования цифровой аи-1аратуры является этап функционально-логического проектирования, теоретической основой которого является задача минимизации булевых функций.

Задача минимизации булевых функций в классе дизъюнктивных нор-и.ъ.ьных форм (ДНФ) состоит в построении по произвольно заданной бу-1евой функции реализующей ее формулы вида " дизъюнкция конъюнк-щй", содержащей минимальное число букв.

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

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

Эффективность решения той или иной задачи существенно зависит от степени адекватности математического описания (модели) объекта:

степени адекватности математической модели процесса (задачи-прототи па); эффективности выбранного метода решения.

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

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

Непрерывной рост степени интеграции аппаратуры при одновремен ном требовании существенного сокращения сроков ее разработки показы вают, что сущность целесообразного подхода к проектированию РЭС за ключается в конечном счете в разработке и внедрении интегрирований! ...., ( \аПР, позволяющей , ореративцо создавать проекты модулей рааличноп уровня иерархий и базирующейся на результатах анализа и разработю ^ действительно эф$екщрных методов минимизации ДНФ булевых функ

> ций как теоретическ<5й"0сн6вы логического синтеза'цифровых устройств.

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

системное исследование возможностей современных методов логи ческого синтеза, определение границ их применимости, необходимых дл реализации точных алгоритмов вычислительных ресурсов (комбинаторно] сложности, объема памяти) и возможной погрешности эвристических ме тодов как функции размерности задачи, а также выявление резервов _пс вышения их эффективности;

выявление и анализ комплекса действующих факторов, определяй: щих специфику логического проектирования узлов РЭС различного на

начения, и Формирование прогрессивных требований к ним с учетом сиовных тенденций развития отечественных и зарубежных разработок;

поиск эффективных критериев и разработка математических моде-ей решения задач основных этапов логического синтеза;

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

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

разработка программных компонентов перспективной интегрирован-ой САПР РЭС;

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

Методы исследования. Теоретические исследования диссертацион-ой работы строятся на основе методов анализа сложных систем, исследо-шия операций, математического моделирования, булевой алгебры, дис-эетного программирования, методов вычислительной математики н ис-(сственного интеллекта.

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

аналитические оценки эффективности (комбинаторной сложности и >ебуемого объема памяти) известных алгоритмов получения простых им-' гжкант булевых функций, а также асимптотические оценки точности эв-<стических методов решения задачи о пйкрыгии;

эффективные алгоритмы получения простых импликант булевых ункций, в частности асимптотически оптимальный в смысле быстродей-вия и требуемого объема памяти алгоритм, названный методом пораз-1дчого выращивания;

;сомплексные критерии и алгоритмы решения комбинаторной задами кратчайшем покрытия, обеспечнраюшне эффективней поиск оптималь-»IV реч'еи^й-

характеризация булевых функций на основе расг.-'■деления терме по индексам и исследование его свойств;

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

принципы и алгоритмы оптимизации многовыходных комбинацией ных автоматов, в том числе определение оптимальной полярности выхо; ных сигналов;

поинципы организации и состав специального программного обе« печения автоматизированной системы логического синтеза цифровых уи ройств.

На защиту выносятся следующие новые научные положения:

1. Метод "поразрядного выращивания" простых импликант булевы функций, основанный на поэтапном разбиении множества импликант и непересекающиеся подклассы с фиксированным значением общей част кода импликанты и отсечении классов, содержащих импликанты, участвс вавшие в склеивании на каком-либо из предыдущих этапов, являете асимптотически оптимальным в смысле минимума комбинаторной слоя ности и требуемого объема памяти ЭВМ.

2. Метол решения комбинаторной задачи о кратчайшем покрыта! основанный на вычислении оценки совокупности строк-претендентов отсечении бесперспективных вариантов путем выбора только одного I претендентов инцидентных каждому из столбцов, образующих минимаш

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

3. Распоеделение термов по индексам (РТИ) некоторой булево функции может быть представлено в виде композиции аналогичных ра( пределений (РТИ) составляющих ее интервалов, при этом каждое из РТ интервалов и их пересечений оудет представлять собой кортеж бином! альных коэффициентов.

4. Характеризация булевых функций на основе РТИ и использован» свойств РТИ совокупности термов, представляющих собой интервал, п< зволяют получить оценку эффективности минимизации булевых функцш в частности позволяет оез решения собственно задачи минимизации опр* делить кратчайшая ДНФ какой из реализаций функции прямой или и> верснои будет содержать меньшее число ттмо»

5. Использование саойыв РТИ интервалов и их пересечений да« возможность синтезировать РТИ, подобное заданному, что позволяет ре пизовать ч(Ь<Ьектцвнь1й ялгопитм миним-зации булевых функций, оси

ванный на синтезе подобных распределений термов по индексам и идентификации составляющих их интервалов.

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

7. Общесистемное применение прогрессивных принципов структурного построения специального программного обеспечения САПР ПЛУ (программируемых логических устройств) позволяет практически реализовать действительно системный подход к оптимальному шюектированию логических устройств и благодаря этому существенно повысить технический уровень, качество и экономическую эффективность разработки перспективной аппаратуры различного схемотехнического и эксплуатационного назначения.

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

Реализация в промышленности. Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены в инженерную практику и используются на промышленных предприятиях в гг. Санкт-Петербурге и Одессе, а также в учебном процессе СПбГУТ им. проф. М.А.Бонч-Бруевича, Балтийском ГТУ и Северо-Западном политехническом имнсти-гуте.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и были одобрены на Всесоюзном совещании-семинаре "Автоматизация проектирования устройств и сна см СВЧ", г. Красноярск, 1982 г.; Всесоюзном совещании-семинаре "Гиокис автоматизированные производственные системы", г. Ленинград, 1984 г.: Всесоюзном ггаещаниинсемииаре "Теоретические и прикл.ииые вопроси

разработки, внедрения и эксплуатации САПР РЭА", г. Одесса, 1984 (2 доклада); III Всесоюзном совещании-семинаре "Методы решения ош мизационных задач на графах и сетях", г. Ташкент, 1984 г.; IX Всесоюзнс симпозиуме по проблеме избыточности в информационных система г. Ленинград, 1986 г.; Всесоюзном совещании-семинаре "Теория и практ ка построения интеллектуальных интегрированных САПР РЭА и БИС г. Алушта, 1987 г.; Всесоюзной научно-технической конференции "Сове шенствование технических средств связи для решения проблем информ тизации общества в новых условиях хозяйствования", г. Ленинград, 1991 (2 доклада); научно-технических конференциях (НТК)"Автоматизация пр ектирования радиоэлектронной и электронно-вычислительной аппарат ры", Пенза, 1982-1992 гг. (14 докладов); на 4-й и 5-й межотраслевых Н1 (г. Уфа, 16-17 марта 1983 г., 11-13 апреля 1989 г.); на республиканок НТК (г. Севастополь, 21-22 апреля 1986 г.); отраслевой Н1 "Совершенствование технических средств для развития цифровых сисп и сетей передачи информации", Ленинград, 1990г.; научно-техннчесю семинаре "Использование универсальной вычислительной техники п моделировании систем обработки информации", Усть-Нарва, 1990г.; Н1 профессорско-преподавательского состава ЛЭИС им. проф. М.А.Боь Бруевича, 1984-1989, 1996 гг.

Публикации. Основное содержание диссертации отражено в 35 I чатных работах (в том числе в монографии) и в 16-и научно-техническ отчетах по НИР и ОКР, выполненных под научным руководством и п непосредственном участии автора.

Структура и объем работы. Диссертация состоит из введения, шее разделов, заключения и приложения. Основной материал работы и зло» на 194 машинописных страницах. Работа содержит 22 таблицы и 6 рис; ков. Список литературы включает 146 наименований отечественных и рубежных публикаций.

СОДЕРЖАНИЕ РАБОТЫ

В первом разделе дан аналитический обзор современных модел методов и алгоритмов синтеза комбинационных автоматов в классе ДН получены асимптотические оценки комбинаторной сложности алгорита и необходимого объема памяти, сформулированы перспективные напр ления повышения эффе^ивности алгоритмов и программных систем их основе и обоснована постановка задач диссертационной работы.

Основными показателями эффективности алгоритма являются оценки комбинаторной сложности и требуемого объема памяти. В работе шгоритмы оцениваются на примере функции, принимающей единичные шачения на всех 2" наборах переменных (заданную 2" конституентами). Рассмотрение функции, совпадающей с константой 1, полезно для оценки 'потенциальной" эффективности различных методов построения сокращенной ДНФ, так как оперзция склеивания для такой функции выполняется максимально возможное число раз.

Минимизация ДНФ булевых функций алгебраическими методами обычно проводится в два этапа:

- выделение множества простых импликант;

- выделение минимального по мощности подмножества простых импликант, достаточного для реализации исходной функции (задача о кратчайшем покрытии).

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

Условия склеивания можно выразить следующим образом.

Импликанты § и Ь склеиваются между собой в том и только л том случае, если:

а) их коды разностей совпадают, //, ;

б) индексы различаются на единицу, ,

с) коды импликант различаются на степень двух,

1„-1^2'к , 1ке{ 1,2,...,«}.

Иначе говоря, склеиваются две импликанты, различающиеся значением только одной переменной.

В работе рассмотрены три существенно различающихся алгоритма получения простых импликант: метод Мак-Класки, использующий обычное склеивание; метод Хва, использующий обобщенное склеивание и метод Свободы, использующий сканирование пространства импликант.

Показано, что для всех этих методов оценка требуемой памяти близ-

как 0(3").

Получены оценки комбинаторной сложности атгорптмов.

Для алгоритма Квайна-Мгк-Класки:

о ~

1 Для алгоритма Свободы: Для алгоритма Хва:

П.

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

Задача о покрытии некоторого множества может быть в принципе

решена тривиальным перебором всех 2" — 1 сочетаний непустых его подмножеств. Однако уже при п > 20 такой перебор практически неосуществим даже на ЭВМ.

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

Очевидно, что минимальная мощность нетривиального покрытия равна 2. Пусть существует покрытие столбцов булевой матрицы состоящее из 2 строк, и при этом:

1) строки, не входящие в оптимальное покрытие, имеют те же (или лучшие) опенки качества, что и строки, образующие оптимальное покрытие,

2) при выборе некоторой строки в покрытие после вычеркивания покрытых столбцов таблица остается циклической (в ней невозможно сжатие по строкам и столбцам).

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

Определена зависимость максимальной погрешности решения Д от мощности покрываемого множества (Ы)'

Стратегия 1 (алгоритм пер-ой группы).

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

Стратегия 2: Выбор строки, содержащей абсолютно максимальное личество единиц.

Таким образом, с ростом размерности задачй растет в общем случае погрешность решения (д ), получаемого при использовании эвристиче-их алгоритмов, причем при N —><=о погрешность решения может быть оль угодно большой.

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

Поскольку индекс импликант не превосходит их ранга (I < г), раз-[ение минитермов на классы по индексам не дает существенного сокра-ения перебора, т.к. с понижением ранга минитермов уменьшается и [ело классов разбиения при одновременном увеличении числа термов в [ассах. В то же время, число различных кодов разности быстро растет с »нижением ранга минитермов при одновременном уменьшении в геомет-(ческой прогрессии числа термов, имеющих одинаковые коды разности.

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

Таким образом:

- разбиение термов на классы с различными кодами разности позво-1ет существенно снизить комбинаторную сложность поиска простых им-ппсант по сравнению с разбиением по индексам;

- при разбиении термов по кодам разности сравнение импликант осу-ествл5£тся только внутри класса с определенным кодом разности. По-

скольку нет взаимодействия между классами, нет и необходимости сох нять в памяти одновременно термы всех классов;

- при склеивании импликант внутри класса с одним кодом разно* не образуется дубликаций термов. Поэтому, если при поиске простых I пликант класс термов с определенным кодом разности порождать тол! один раз, то дубликации термов не образуются и, следовательно, отпад необходимость в их устранении.

Метод, использующий разбиение по кодам разности Вначале путем попарного сравнения и склеивания минитермов к ранга лолучаются минитермы (к-1)-го ранга. Минитермы к-го ранга, уча вовавшие в склеивании, помечаются. Множество минитермов (к -.1) ранга разбивается на классы (от одного до к), при этом в каждом кла присутствуют только термы с одинаковыми кодами разности.

Далее каждый из классов рассматривается независимо от друг и выполняются описанные выше действия. Т.е. путем склеивания ми термов (к - 1)-го ранга получаются минитермы (к - 2)-го ранга ( п£>и эп термы, участвовавшие в склеивании, помечаются), которые в свою очер также разбиваются на классы, и т.д. до тех пор, пока в каждом из подкл ов не окажутся минитермы, склеивание которых невозможно.

Рассмотрение классов следует осуществлять в порядке возраста] кодов разности. Сначала получаются минитермы, код разности котор содержит единицу в первом разряде. Получая впоследствии классы т мов с кодом разности, содержащем единицы в разрядах 2,3 и т.д., склеп ние по первому разряду производить не нужно, т.к. все возможные т мы, имеющие единицу в первом разряде кода разности будут уже к т< времени получены. Однако для исключения поглощаемых имплмк проверку возможности склеивания по младшим разрядам производить обходимо. Т.е., если пара импликант склеивается, то обе они поме ются ( т.к. непомеченные импликанты - суть первичные), однако, если мер позиции склеивания меньше максимального номера позиции кода [ ности, содержащей единицу, то импликанта не порождается.

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

Метод поразрядного выращивания

Пусть минимизируемая функция представлена в виде сднф. Каж-ой элементарной конъюнкции поставлена в соответствие ее этикетка, явочная или десятичная. Все этикетки ранжированы в порядке возрастания.

В каждом из минитермов любая переменная может принимать од-о из трех значений: отсутствовать (-), присутствовать (1), присутствовать э знаком отрицания (0).

Сформулируем условия при которых первая перем "ная получает шдое из указанных значений.

Первая переменная отсутствует (-):

- два минитерма могут быть "склеены" по первой переменной, если к этикетки отличаются на единицу и при этом меньшее из чисел четно.

Первая переменная имеет инверсное значение (0):

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

Первая переменная присутствует (1):

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

Таким образом, осуществив сравнение только соседних элементов ассива этикеток, получим три класса минитермов:

- в первом отсутствует первая переменная;

- второй содержит первую переменную (все нечетные этикетки);

- третий содержит отрицание первой переменной (все четные эти-гпш).

Поскольку значение каждой переменной в каждом из классов опре-шено, можно понизить ранг минитермов путем деления значений их икеток на 2, отбросив остаток. Каждый из классов можно рассматривать ¡зависимо от остальных, разбить его на три подкласса и понизить на 1 1нг минитермов, предварительно выяснив при этом значение второй не-висимой переменной. Процедура продолжается до тех пор, пока в каж->м из подклассов не окажется по одному минитерму. Добавив к найден->му минитерму в порядке, обратном порядку получения, цепочку значе-

ний независимых переменных, соответствующую троичному коду пс класса, получим соответствующую импликанту.

В результате получаем троичное дерево выделения импликант, ка дая вершина которого соответствует получению из некоторого множест импликант трех новых множеств, в которых некоторая независимая пег мепиая принимает одно из значений: "О", "1","-".

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

Однако, для повышения эффективности алгоритма необходимо у< ранить возможность получения непервичных импликант.

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

- первый разряд кода равен единице для всех термов;

- если пара термов склеилась, то код результата склеивания являеп поразрядной дизъюнкцией двух кодов склеивающихся термов;

- если четный или нечетный терм участвовали в склеивании, очер ному разряду кода этого терма в подклассах "О" и. "1" присваивав' значение "О", в противном случае - "1".

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

Если какой-либо подкласс состоит из термов, все коды пометки торых содержат ноль в каком-либо фиксированном разряде, то этот п класс можно не рассматривать, поскольку в нем не могут быть получ; простые импликанты (каждая им пли канта данного подкласса будет пог щаться некоторой импликантой, полученной в каком-либо другом и классе).

Достоинством метода "поразрядного выращивания" является бь рая декомпозиция задачи и линейность поиска в каждой из подзадач.

Уточнение значения конкретной переменной в каждой из имплш осуществляется путем сравнения только пары соседних импликант. Та образом, комбинаторная сложность алгоритма не превосходит произа ния числа импликант и количества независимых переменных. Этот позволяет говорить об асимптотической оптимальности метода, поско; комбинаторная сложность его совпадает с нижней оценкой сложности рошо известной задачи о сравнении N действительных чисел, ра£ 0(Ы^1М)

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

Точность решения может быть повышена, если на каждом шаге получать оценки не для отдельного множества (строки), а для совокупности множеств (строк), пытаясь максимизировать мощность их объединения при одновременной минимизации их числа.

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

которая справедлива лпя произвольных множеств Бь Предположим, что даны подмножества Бь'..., Б,, (необязательно различные) некоторого конечного множества Б, и мы ищем мощность их объединения

Воспользуемся принципом включения-исключения:

1=1 /=1 ДО<><*Зл

(1)

Рассмотрим случай равномощных множеств с равной непустой мощностью их попарных пересечений, т.е.

V/,),к е\,п

5,1=5,

Наименьшая мощность объединения множеств достигается, если

V/61 ,П

из

/=1

1£/</£л

(=1

Наибольшая мощность ооъединения множеств достигается путе» максимизации третьей суммы в правой части выражения (1), т.е. в случае если

е1 ,п

Поскольку У/,к е\,п

*}) к

т

■Л ° ^ с 1

ОуГГ^^ , ТО

115,

I /=1

с]+3 С1 -.,.+<?• (-1 Г1 • с;

»-1

Запишем правую часть выражения (3) в виде:

1 = 1 4=0 '

(3)

(Второй член содержит знакопеременный биномиальный ряд, сумм которого оавна нулю)

л л-1.

/=1

/=1 /=1

л-1.

1=1

Таким образом,

№

\'=1

Получим матрицу ^ = где -транспонированная мат-

рица (/^ названа частотной матрицей отношений). Отметим,что =

Определим матрицу

/гд

(назовем ее матрицей приращений) сле-

гующим образом: = /

Таким образом, правая часть выражения ( 4 ) представляет собой истинную сумму элементов п -й строки матрицы /гЛ.

Нетрудно теперь получить оценку ( Лк ) минимального числа элементов ( строк ) в покрывающем множестве, включающем некоторую проку

Пусть число столбцов матрицы О равно N. Расположим элементы некоторой строки матрицы

(за ис-

слючением ) в порядке убывания:

Г > Г > Г •> к\кгкг—

Очевидно, что

1=1

Минимальное ¡, при котором справедливо выражение (5), и будет ' (скомой оценкой , уменьшенной на единицу (/ = А^ — 1). Оценим сте-гень точности решения задачи алгоритмом, использующим предложсн-1ую выше оценку (Л^).

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

Пусть оптим&пьное покрытие содержит р строк, а покрытие, соот-кяч твующее верхней границе - я строк.

Для определенности будем считать, что первые р строк образую! оптимальное пок"'тие, причем

V/ е1,ш V/Jel ,р

'/1=5,

V/ер+1,т

т= р+д

1 Р

Подставив эпги значения в (4), получим

р

из

1=1

Р

Из (2):

(6)

№

¡=р+1

д .=1 2

П)

Приравнивая правые части выражений (6) и (7), получим: q = 2 р- 3.

Таким образом, мощность покрытия, найденного алгоритмом, пользующим предложенную выше оценку (Л^ ), в худшем случае бу,

превышать мощность оптимального покрытия меньше, чем в два раза

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

Можно повысить точность решения без существенного увеличе комби»опорной сложности.

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

а) каждый столбец покрыт два раза;

б) имеются столбцы, покрытые однократно.

В первом случае имеем два оптимальных покрытия, легко (без пе-«бора) разделяемые. Во втором случае имеем обязательные строки и су-цественное сокращение задачи за счет выделения ядра покрытия.

Таким образом, в указанном случае переборная составляющая ока-ывается 0(к) вместо 0(2* ).

Пусть Р; = {,^ ,...,| семейство множеств инцидент-

шх элементу 5, (в таблице Квайна - множество строк, имеющих единицы »а пересечении со столбцом 1).

Два столбца 1 и j назовем независимыми, если /}п/> =0, т.е. они не содержат единиц в одинаковых строках.

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

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

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

Пусть для некоторой булевой функции, заданной в СДНФ, найдено распределение термов по индексам (РТИ) (индекс минитерма - число единиц в его двоичном представлении):

где 1. - число минитермов с индексом }.

Кортеж максимальной длины, не содержащий нулевых элементов назовем фрагментом распределения, или просто фрагментом.

В частности, распределение, не содержащее нулевых элементов или содержащее только "неразделяющие нули" (стоящие в начале и в кон це распределения) состоит из одного фрагмента.

Например, распределение 1(п) = { 0,5,3,1,0,3,3,0,4,2,0 } состоит и трех фра™,\...ов: { 5,3,1 }, { 3,3 }, { 4,2 }.

Теорема

Рг^г.ределение по индексам термов, образующих некоторый интер вал длины 2т , состоит из одного фрагмента длины ш +1 с элементам = С'т ( 1 = 0,1,...,т ). (Доказательство методом математической и* дукции.)

Следствие. Для существования интервала длины 2 необходим наличие кортежа 1т,1 длины к+ 1, такого, что

1т+. >С( ( j = 0,1,..„к; ш = 0,..л ).

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

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

Пусть задано РТИ: /д,/^...,/ .

Алгоритм

0. Я = 0; к = п. ( Я - оцешса; п - число независимых г ременных ).

1 Осуществляется генерация кортежа с элементами J. = С^ (1 0,...,к). _

2. Если существует некоторое значение г е 0, П—к, при котор У/ е 0,к Ir+.—J.> 0, то идти на п.З, иначе на п.5. 3.11 = 11+1.

4./ . = /-./ 0 = 1.....к);

■5. к = к - 1. Если к = 0, то КОНЕЦ, иначе на п.1.

Теорема. Непустое пересечение двух интервалов есть интервал. Доказательство от противного.)

При вычислений оценки, учитывающей пересечения интервалов, удем использовать тот факт, что непустое пересечение двух интервалов лъ также интервал длины 2т и ему соответствует кортеж длины m + 1 РТИ. Элементы кортежа равны (i = 0,..,m).

Вернемся к вышеизложенному алгоритму.

Пусть на некоторой (не первой) итерации после вычитания элемен->в сгенерированного кортежа J(k) из элементов распределения 1(п) полу-:ны отрицательные значения 1(п). Такая ситуация приводила либо к сме-ению позиции кортежа (г = г + 1), либо к уменьшению длины генерируе-ого кортежа ( к = к - 1 ).

Если отрицательные элементы распределения 1(п) могут быть покры-,i совокупностью из Сд (R à 2) кортежей длины не более к - 1, каж-лй из которых моделирует пересечение между парой выбранных интер-шов, то осуществляйся переход на п.4 с учетом мощности пересечений рмов.

Если этикетки/ импликант, являющихся элементами некоторого ин-рвала, ранжированы в порядке возрастания, то индексы импликант, рас-нюженных в этом же порядке образуют некоторую частично упорядо-:нную последовательность.

Будем записывать РТИ ярусами. Каждый ярус образуется термами, [я которых возрастание числовых значений кодов импликант сопровеж-1ется неубыванием индекса.

/. А А /, А

h A h h Л

^1 = 0 1,2 3 - II 1 2 1

л 5,6 7 15 1 2 1 1

Рг =

*--

0 1,2 3,5,6

а И. 15

Ш =

1 2 3

1 0 1 1

Анализ /2 (4) показывает, что для покрытия термов первого яруса необходимо минимум три интервала, и два интервала необходимо для покрытия термов второго яруса. Причем в данном случае использование термов первого яруса для расширения интервалов, образованных термами второго яруса (и наоборот) не может привести к уменьшению оценки. Опенка, полученная суммированием оценок каждого отдельного яруса, может оказаться завышенной. Точность оценки тем выше, чем меньше число ярусов.

Рассмотрим функцию

У = £0,3,4,7,8,11,12, /(4) =1,2,2,2.

0 3 1 0 1

4 7 /(4) = 1 0 1

8 11 1 0 1

12 1

Можно уменьшить число ярусов, воспользовавшись тем, что незави симые переменные могут быть синхронно перенумерованы. Осуществи! замену переменной X, на ДГ4, при этом изменятся значения некоторы ¡1 ик-'ток импликант:

F' =£0,1,4,5,10,11,14, /'(4) = 1,2,2,2.

Функция Р' логически эквивалентна функции однако име< одноярусное представление.

.Пусть задано РТИ некоторой булевой функции п переменных : /(и)={/0,/,,...,/„},

I, - число минитермов с индексом 1 ( индекс минитерма - чис. единиц в его двоичном представлении).

РТИ интервалаллины 2к: 1(ко) = { Ц } (/' еО,к; ] еО,п;)

j - минимальный индекс ср»ци кодов импликант, образующих

ЧГ^^В а/1

/)+; = С£ (/еО,к\ _/еО,и;).

Задача минимизации булевых функций может быть сведена к задаче синтеза вариантов разложения РТИ функции на составные части, представляющие собой РТИ интервалов, и проверке существования такого набора интервалов на реальном массиве импликант.

Будем синтезировать функции с одинаковыми РТИ в порядке возрастания числа составляющих их интервалов.

Решение, вообще говоря, не единственно. Так, например, разложение РТИ 1(4) = { 1,3,4,3,1 } на два интервала может быть получено тремя способами: 1(3,0) + 1(2,2); 1(2,0) +1(3,1); 1(3,0) + 1(3,1) -1(2,1). ( Со знаком минус - пересечение интервалов).

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

Кроме того, существенное усечение множества генерируемых вариантов происходил: благодаря проверке существования интервалов ла массиве импликант. Так, например, если ДНФ функции, РТИ которой приз дено выше, не содержит интервала со спектром 1(3,0), то возможен только один вариант разложения на два интервала: 1(2,0) + 1(3,1). Если при этом не существует и интервал с РТИ 1(3,1), то возможно разложение на три интервала, причем оно единственно: 1(2,0) +1(2,1) + 1(2,2).

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

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

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

Таким образом, начиная с некоторого момента, смежность определяется не для пары термов, а для пары классов.

Если за четным классом не следует нечетный с остатком кода, большим на единицу, то ко всем выращенным кодовым комбинациям данного класса добавляется 0 в старший разряд, а остаток делится на 2.

Если перед нечетным классом нет четного меньшего на единицу, то ко всем кодовым комбинациям данного класса добавляется единица в старший разряд, а остаток кода уменьшается на 1 и делится на 2.

Если за четным классом следует нечетный с остатком кода большим на единицу, то образуется класс, остаток кода которого получается делением на 2 остатка кода четного класса. В этот класс переходят все выращенные кодовые комбинации обоих (четного и нечетного) классов, причем

- если в смежных классах была пара одинаковых выращенных кодовых комбинаций, то в новом классе они представлены той же комбинацие? с добавлением черточки в старший разряд;

- если некоторая выращенная кодовая комбинация поглощается вы ращенной кодовой комбинацией из смежного класса, то в новый класс за носится поглощаемая кодовая комбинация с добавлением черточки ] старший разряд. Непоглощаемые кодовые комбинации переходят в новьп' гласс с добавлением 0 или 1 в старший разряд соответственно четному 1 почетному классам.

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

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

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

Пусть А и В пересекающиеся термы из класса 0;

С и D пересекающиеся термы го класса 1 и при этом

|АпС| = I А | /2 =|С |/2 .

Термы А и С склеиваются с высвобождением пересечения, если А\( АлВ) = С\ (С nD)

и

(AnB)n(CnD) = 0.

В этом случае вместо двух интервалов (0)А и (1)С получается один интервал (-)А\ (An В). Отметим, что поиск пары интервалов для подобного склеивания необходимо осуществлять в случае невозможности расширения их на данном шаге.

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

Оценки для классов "1" и "О" неуменьшаемы. Для класса "-" оценка может быть уменьшена, если для расширения интервалов классов "1" и "О" используются одни и те же термы класса "-".

Поскольку классы "1" и "0" не пересекаются, то избыточность при поразрядном выращивании может возникнуть только за счет неоптимального покрытия класса "-".

Чем меньше термов в классе тем меньше и потенциальная избыточность покрытия (разбиения). В частности, если класс "-" пустой, то разбиение неизбыточно, и оценка равняется сумме оценок двух классов ("1" и "0").

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

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

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

При переопределении двух переменных на множестве термов моя но выделить три класса:

- термы, в которых сов.падают значения переопределенных переме!

ньгх;

- термы, в которых 0 заменен на 1;

- термы, в которых 1 заменена на 0.

Поскольку в каждом из классов термы упорядочены по возраст; нию, то получить единый упорядоченный массив можно за линейное вр( мя, осуществив процедуру слияния.

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

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

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

интервалов осуществляется только согласованно с основным клас-в противном случае осуществляется разбиение, даже,если расширение можно.

Если терм в классе один, он может быть расширен за счет исполь-ания идентичных безразличных термов смежных классов тачающихся в одном разряде).

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

Тривиальный способ уменьшения оценки для системы - выбор поноете, при которой класс с максимальной оценкой переходит в нерабо-состояние (содержит отрицание всех функций). Более сложный путь -ныпение оценок классов за счет использования термов других классов.

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

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

В данном разделе приводится описание пакета прикладных про-1м (111111), предназначенного для ввода и коппектировки описаний кций синтезируемых устройств и формирования файлов для програм->ров ПЛМ. ППП позволяет пользователю выполнять автоматическую -мизацию функций синтезируемых устройств с целью минимизации ества термов, заданных в исходном описании функций.

Приводится формальное описание лингвистического обеспечена нотации Бэкуса.

В шестом разделе приведены результаты экспериментальных иссле ваний разработанных алгоритмов и программ. Проводится сравнительи анагчз с пакетом ABEL фирмы DATA I/O (США), одним из мировых деров в области программного обеспечения систем логического синтеза

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

Харакгеризация булевых функций на основе распределения Tepi по индексам и использование свойств РТИ совокупности термов, пр ставляющих собой интервал, позволили получить оценку эффективно минимизации булевых функций, в частности позволили без решения t ственно задачи минимизации определить кратчайшая ДНФ какой из рег заций функции прямой или инверсной будет содержать меньшее чи термов.

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

Вычислительный эксперимент проводился для функций с раз. ным числом независимых переменных п (до 20) и с различным чис термов С ДНФ N (до 12000). Для каждой из функций определялась о ка R, затем осуществлялась минимизация функции и определялось ч термов L и кратчайшей ДНФ. Такие же действия выполнялись и инверсного значения функции ( оценка R, число термов L ). Если в женил R—R и L— L оказывались одного знака, то считалось, оценка произведена правильно. Генерируя множество раз случайны! разом логическую функцию, по. ¡учили следующую зависимость

P=P(N,k,\P--R\),

где Р - вероятность правильной оценки.

Оказалось, что при любых N и к с ростом | R — R | растет и Р, и, как

гравило, Р достигает значения 1 уже при j R—R | = 1.

Сравнение предложенных новых методов решения задачи о покры--ии с уже существующими по точности , получаемых решений производи-юсь с использованием следующей оценки:

R

о _

R

где D\ - относительная точность г-го метода (показывает насколько I среднем меньше строк в покрытии, полученном I -ым методом по срав-гению с базовым); Р' - мощность покрытия, полученного i -м методом в

/ -ом испытании; Pj"" - мощность покрытия, полученного базовым ме-одом в j -ом испытании; R - число испытаний.

Сравнение производилось с помощью ЭВМ следующим образом.

Генерировалась случайным образом матрица, содержащая нули и диницы, размером 40x40 с плотностью р ( р - вероятность того, что [анный элемент матрицы равен 1). Эта матрица поступала на вход всех 1етодов, затем сравнивались мощности полученных решений с базовым. 1ля вычисления относительных точностей эксперимент повторялся много •аз. В качестве базового был взят метод наискорейшего спуска. Размер ттрицы был выбран исходя их двух ограничений: он должен быть доста-очно большим, чтобы была заметна разница в точности, и в то же время [остаточно малым, чтобы вычисления, повторяющиеся десятки раз, вы-голнялись за приемлемое время. По этим же причинам не применялось ыделение ядра, так как при таком размере это "зашумляет результаты.

Эксперимент показал, что предложенные новые методы поиска ратчайшего покрытия (при любой плотности таблицы Квайна) дают более очные результаты, чем метод наискорейшего спуска.

К недостаткам этих методов можно отнести больший по сравнению с [ервыми двумя объем вычислений. Однако время вычисления является ракгически приемлемым, а основным критерием является точность полу-аемых результатов

Приводится сравнение программных реализаций алгоритмов мини-гизации систем булевых функций с реализацией алгоритмов, используе-1ых в пакете логического синтеза ABEL фирмы I/O (США). Преимущество

новых методов в точности сказывается уже на небольших тестовых прю pax (3 функции четырех переменных и 4 функции шести переменных).

Оценка быстродействия разработанных программных средств про водилась на специально генерируемых однотипных тестовых примера: известным заранее результатом, различающихся числом независимых i ременных. Число переменных изменялось от 50 до 500. При этом вре решения изменялось в пределах 0.5 сек - 2.5 мин.

ЗАКЛЮЧЕНИЕ

Тема диссертации находится в русле актуального направления, от чающего запросам различных отраслей промышленности и имеющего с; ей целью создание эффективных методов и средств оптимального логи ского синтеза ЮС. В настоящей работе решена и практически реализок крупная научная и народнохозяйственнаяЗгроблема, непосредственно с занная с обеспечением автоматизированного логического синтеза циф; вых устройств за счет разработки, обобщения и внедрения принципов, i ■годов, математических моделей и алгошггмов логического проектирова» цифровых устройств.

Основные теоретические и практические результаты диссертаци ной работы заключаются в следующем.

1. На основе системного исследования возможностей совремеш методов логического синтеза определены границы их применимости, лучены аналитические зависимости доя определения необходимых , реализации точных алгоритмов вычислительных ресурсов (комбинатор] сложности, объема памяти) и возможной погрешности эвристических тодов. В частности, получены аналитические оценки эффективно (комбинаторной сложности и требуемого объема памяти) известных аг ритмов выделения простых импликант булевых функций, а также асимт тические оценки точности эвристических методов решения задачи о крытии.

2. Выявлен комплекс действующих факторов, определяющих спе фику логического проектирования узлов РЭС различного назначя сформулированы прогрессивные требования к ним, исследованы в нейшие свойства и выработаны принципы автоматизированного лоп ского проектирования РЭС.

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

эмов на классы с одинаковыми кодами разности, а также асимптотиче-л оптимальный в смысле быстродействия и требуемого объема памяти горитм, названный методом поразрядного выращивания.

4. Предложены комплексные критерии и алгоритмы решения комби-горной задачи о кратчайшем покрытии, обеспечивающие эффективный иск оптимальных решений. Метод решения комбинаторной задачи о етчайшем покрытии, основанный на вычислении оценки совокупности юк-претендентов и отсечении бесперспективных вариантов путем выбо-только одного из претендентов, инцидентных каждому из столбцов, об-$ующих минимальное по мощности внешне устойчивое множество, по-)ляет организовать направленный выбор вариантов и эффективный noie оптимальных решений.

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

6. Полученный критерий эффективности минимизации ДНФ булевых нкций, использующий свойства распределения термов по индексам, помяли реализовать эффективный алгоритм минимизации булевых функ-й, основанный на синтезе подобных распределений термов пс ндексам щентификации составляющих их интервалов.

7. Разработаны принципы и алгоритмы оптимизации многовыходных чоииационных автоматов, з том числе определение оптимальной поляр-сти выходных сигналов.

8. На основе разработанных моделей и алгоритмов созданы и адап-эованы к промышленным условиям эксплуатации быстродействующие эграммные средства логического синтеза электронных схем. разра-ганы программные компоненты перспективной интегрированной САПР С.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Доб.хинский Б.Н., Лузин С.Ю. Об эффективности одного аш ритма синтеза дискретных автоматов// Техника средств связи, сер. ТЕ 1991, вып. 3, с. 53-61.

2. Кочкина С.А., Лузин С.Ю. Быстрая оценка эффективности мик мизации булевых функций// Всесоюзная НТК "Совершенствование тех* ческих средств связи для решения проблем информатизации общества новых условиях хозяйствования": Тез. докл. - Л., 1991, с. 92-93.

3. Кмзанов Б.В., Лузин С.Ю., Фоменко Т.А. Порядное размещена плоскости связанных в сеть точечных объектов. Программное средство Гос. ФАП N 50880000152 от 14.03.88.

4. Куранов Б.В., Лузин С.Ю., Фадеев Ю.И. Автоматизация оцен параметров топологии соединений по результатам размещения элементо В сб.: Автоматизация конструкторского проектирования РЭА и ЭВ ПДНТП. Пенза, 1988, с.26-27

5. Куранов Б.В., Лузин С.Ю. Автоматизация исследований качест проектирования печатного монтажа на этапе размещения элементов РС (ЭВА). - В сб.: Автоматизация научных исследований / ВЗМИ, -М., 19) с.13-16.

6. Куранов Б.В., Фадеев Ю.И., Лузин С.Ю. Автоматизация раз» щения элементов схем с многозвенными электрическими цепяи ЛЦНТИ, -Л., 1989, И.Л. N 248-89.

7. Лапшин Б.А., Лузин С.Ю., Лугченков Л.С. К вопросу разработ математических моделей при решении задач конструирования РЭА// Т ника средств связи, 1983, сер. ТПС, вып. 3, с. 105-110.

8. Лузин С.Ю. Метод минимального покрытия при решении за; компоновки и размещения модулей //Технкка средств связи, 1983, с ТПС, вып.12, с.78-86.

9. Лузин С.Ю. Минимизация булевых функций на основе синт распределения термов по индексам //Сб. науч. трудов учебных институ связи, 1996, вып. 162, с. 27-30

10. Лузин С.Ю. К решению задачи о клике // Техника срЗдст? свя 1984, сер. ТПС, вып.9, с.74-79.

11. -1узин С.Ю. Алгоритм решения задачи о клике // В сб.: Мете и программы решения оптимизационных задач на графах и сетях / ВЦ' АН СССР .- Новосибирск:, 1984, с.80-81.

.12. Лузин С.Ю. О выделении в графе максимума клик // Техника едств связи, 1985, сер. ТПС, вып 11, с.112-119.

13. Лузин С.Ю. К вопросу срвместного решения задач размещения ЭТ и трассировки // Средства связи, 1985, вып.2, с.36-38.

14. Лузин С.Ю. Новый подход к минимизации ДНФ булевых функ-:й// В сб.: Автоматизация проектирования РЭА и ЭВА / ПДНТП. - Пенза, 92, с. 56-57.

15. Лузин С.Ю. Эффективный алгоритм решения задачи о покрытии Техника средств связи, 1990, сер. ТПС, вып. 2, с. 33-39.

16. Лузин С:Ю., Добжинский Б.Н. Синтез: логических схем про-шшенной робототехники. - Межвуз. сб.: Электромеханические элементы бототехнических систем/ЛИАП. - Л., 1985, вып. 178, с. 143-150.

17. Лузин С.Ю., Добжинский Б.Н. К вопросу о минимизации функ-:й алгебры логики // Техника средств связи, 1984, сер. ТПС, вып. 12, с. -73.

18. Лузин С.Ю., Добжинский Б.Н., Перли А.Г. Эффективный метод [деления первичных импликант булевых функций. - Техника средств язи, сер. ОТ, 1989, вып. 6, с. 44-50.

19. Лузин С.Ю., Кочкина С.А. Выбор критерия в задаче минимиза-л' комбинационных схем // Техника средств связи, 1990, сор. ТПС, вып. с. 67-72.

20. Лузин С.Ю., Кочкина С.А. Быстрая оценка эффективности ми-[мизации комбинационных сусем //Всесоюзная НТК ,"Совершен-Ьование технических средй% связи для решения проблем информатиза-ги 'общества в новых условиях хозяйствования": Тез. докл., -Л., 1991. 38-40.

21. Лузин С.Ю.? Кочкина С.А. Оценка эффективности минимизации гических схем// Техника средств связи, 1991, сер. ТПС, вып. 3, с. 83-88.

22. Лузин С.Ю., Кочкина С.А. Критерий эффективности реализации левых функций // В сб.: Автоматизация проектирования РЭА и ЭВА / [ЩТП. -Пенза, 1991, с. 83-84.

23. Лузин С.Ю., Куранов Б.В. Повышение эффективности автома-ческого проектирования печатного монтажа для схем с высоким содср-шием многозвенных цепей //В сб.: Автоматизация конструкторского оектирования РЭА и ЭВА/ПДНТП, - Пенза, 1987, с.6-9.

24. Лузин С.Ю., Куранов Б.В. Расположение компонентов элек-онних схем в плоском коммутационном пространстве на основе реше-1Я задачи о наименьшем покрытии //В сб.: Автоматизация конструктор-Ого проектирования РЭА и ЭВА / ПДНТП. - Пенза, 1985, с.41-43.

25. Лузин С.Ю., Куранов Б.В. Сравнительный анализ методов реш ния комбинаторной задачи о покрытии //В сб.: Автоматизация констру торского проектирования РЭА и ЭВА / ПДНТП. - Пенза, 1986, с. 50-51.

26. Лузин С.Ю., Лутченков Л.С. Анализ и разработка алгоритмов л гического синтеза / СПбГУТ. - СПб, 1996.

27. Лузин С.Ю., Лутченков Л.С. Осуществление символьных пр образований на ЭВМ в задачах оптимизации аппаратуры средств связи Техника средств связи, 1983. сер. ТПС, вып. 1, с. 93-98.

28. Лузин С.Ю., Лутченков Л.С., Куранов Б.В. Подсистема aaiow тического размещения элементов НЭА с альтернативным использовамж различных математических моделей электрических схем проектируем! узлов //н сб.: Автоматизация конструкторского проектирования РЭА ЭВА / ПДНТП, - 11енза, 1984, с.67-69.

29. Лузин С.Ю., Морозкк В.П. Сокращение избыточности булев! функций // IX симпозиум по проолеме избыточности в инфор.мационш системах: Тез. докл., -Л., 1986, т.З, с.141-142.

30. Луши С.Ю., Перова Н.В., Пиппа H.A. Об одном подходе к зада компоновки узлов РЭА // Техника средств связи, 1990, сер. ТПС, вып. 3, 45-51.

31. Лузин С.Ю., Перова Н.В., Пиппа H.A. Новый подход к зада разбиения графа // В сб.: Автоматизация конструкторского проектирован РЭА и ЭВА / ПДНТП, - Пенза, 1989, с. 58-60.

32. Лузин С.Ю., Перли А.Г. Разработка методов логического синте устройств на ПЛМ // В сб.: Автоматизация проектирования РЭА и ЭВ/ ПДНТП, Пенза, 1990, с. 77-78.

. 3. Лузин С.Ю., Серебрякова Е.А. Осуществление символьных п] образований на ЭВМ при расчете сложных многополюсников // Техни средств связи, 1983, сер. ТПС, вып. 1 с. 86-91.

34. Лузин С Ю.^ Соболев H.H., Толопилло С.С. Интегрирован! САПР, реализующая сквоз'.ой цикл проектирования ячеек РЭА // В с Прикладные программные средства автоматизации конструкторского п| оптирования РЭА и ЭВА / ПЦНТИ. -Пенза, 1990, вып. 4, с. 18-20.

35. Лузин С.Ю.. Сорокин С В., Вахабов М.Т., Ткачев Д.Б. ППП ci lew комбинационных автоматов //Всесоюзная НТК "Совершенствоваь технических средств связи для решения проблем информатизации обще г,л г. новых \сло: ия\ хозяйствования". Тез. докл. - Л., 1991, с. 90-91.