автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Математическое обеспечение синтеза минимальных форм представления переключательных функций для САПР БИС

Введение.

I. Особенности и проблемы синтеза минимальных форм переключательных функций.

1.1. Основные понятия и определения .г.

1.2. Анализ методов получения простых импликант

1.2.1. Алгоритм Квайна

1.2.2. Алгоритм Мак-Класки

1.2.3. Алгоритм Свободы

1.2.4. Алгоритм Хва

1.3. Анализ методов решения задачи о кратчайшем покрытии

1.3.1. Метод Петрика-Мак-Класки

1.3.2. Эвристические алгоритмы решения задачи о покрытии

1.4. Быстрые алгоритмы минимизации булевых функций

1.4.1. Карты Карно

1.4.2. Метод конкурирующих интервалов

1.5. Выводы и постановка задач.

2. Повышение эффективности классических методов минимизации булевых функций.

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

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

2.3. Эффективный метод решения комбинаторной задачи о покрытии

2.4. Выводы

3. Анализ и синтез комбинационных схем с использованием спетра индексов.

3.1. Спектр индексов и его свойства.

3.2. Оценка эффективности минимизации

ДНФ булевых функций

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

3.4. Выводы

4. Разработка эффективных методов синтеза комбинационных автоматов.

4.1. Экономичный алгоритм приближенной минимизации ДНФ булевых функций

4.2. Метод типа "ветвей и границ"

4.3. Минимизация системы булевых функций

4.4. Определение оптимальной полярности выходных сигналов

4.5. Выводы

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

5.1. Исследование влияния критериев задачи о покрытии на точность решения

5.2. Исследование оценки эффективности минимизации булевых функций на основе распределения термов по индексам.

5.3. Анализ результатов автоматизированного логического синтеза комбинационных схем.

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

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

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

Однако актуальной задача минимизации стала лишь в 40-50 годах XX века в связи с применением языка алгебры логики для синтеза управляющих устройств и электронно-вычислительных машин (ЭВМ). В 50-80 годах было создано большое количество эвристических алгоритмов минимизации, разработаны различные методы и приемы, механические и электронные устройства, минимизирующие карты и диаграммы для поиска минимальных нормальных форм булевых функций.

Задача минимизации ДНФ булевых функций тесно связана с другими разделами математической кибернетики: теорией синтеза управляющих систем, теорией тестов, теорией кодирования, теорией автоматов и др. Эту задачу можно рассматривать как частный случай синтеза управляющих систем минимальных по сложности формул глубины 2 в базисе { V, &, - }. В связи с малой глубиной ДНФ имеют преимущества перед другими типами схем в плане надежности и быстродействия. Однако ДНФ существенно проигрывают им в плане схемной сложности. Тем не менее, ДНФ довольно часто используются в инженерной практике при построении схем для частично определенных функций, а также в тех случаях, когда при синтезе требуется обеспечить высокое быстродействие и надежность логических устройств. Так, например, нашедшие широкое применение при проектировании цифровых схем программируемые логические матрицы представляют собой устройства, реализующие системы булевых функций, заданных в виде ДНФ. ДНФ употребляются также для предварительных упрощений при построении формул глубины больше, чем 2. При построении тестов для схем часто используется прием, заключающийся в приведении исходной схемы к так называемой эквивалентной ДНФ. Методы минимизации ДНФ применяются также при синтезе автоматов для уменьшения числа состояний.

Несмотря на значительное количество публикаций [4, 6, 7, 15, 19-26, 29-42, 95-108, 111-116, 118-121, 127-130, 134-176], посвященных вопросам минимизации булевых функций, практически отсутствуют работы, в которых наряду с описанием алгоритмов был бы дан анализ основных показателей их эффективности.

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

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

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

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

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

Значительное повышение интереса к вопросам анализа алгоритмов привело к появлению исследований, целиком посвященных этим вопросам. Это в первую очередь монографии: А.Ахо, Дж. Хопкрофт, Дж.Уль-ман " Построение и анализ вычислительных алгоритмов", М., Мир, 1979; Э.Рейнгольд, Ю.Нивергельт, Н.Дэо "Комбинаторные алгоритмы. Теория и практика", М., Мир, 1980; серия книг Д. Кнута "Искусство программирования для ЭВМ", М., Мир, 1976-1978.

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

С другой стороны, исследования, посвященные вопросам логического синтеза цифровых устройств и теории автоматов (А.Д.Закревский "Логический синтез каскадных схем", М., Наука, 1981; В.А.Горбатов "Основы дискретной математики", М., Высшая школа, 1986; С.И.Баранов, В.А.Скляров "Цифровые устройства на программируемых БИС с матричной структурой", М., Радио и связь, 1986; К.Киносита, К.Асада, О.Ка-рацу "Логическое проектирование СБИС", М., Мир, 1988), не касаются проблем, связанных с эффективной реализацией описанных в них моделей и алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- принципы декомпозиции и алгоритмы минимизации многовыходных переключательных схем;

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

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

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

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

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

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

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

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

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

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

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

Основные положения и результаты диссертационной работы докладывались и были одобрены на Всесоюзном совещании-семинаре "Автоматизация проектирования устройств и систем СВЧ", г. Красноярск, 1982 г.; Всесоюзном совещании-семинаре "Гибкие автоматизированные производственные системы", г. Ленинград, 1984 г.; Всесоюзном совещании-семинаре "Теоретические и прикладные вопросы разработки, внедрения и эксплуатации САПР РЭА", г. Одесса, 1984 г.; III Всесоюзном совещании-семинаре "Методы решения оптимизационных задач на графах и сетях", г. Ташкент, 1984 г.; IX Всесоюзном симпозиуме по проблеме избыточности в информационных системах, г. Ленинград, 1986 г.; Всесоюзном совещании-семинаре "Теория и практика построения интеллектуальных интегрированных САПР РЭА и БИС", г. Алушта, 1987 г.; Всесоюзной научно-технической конференции "Совершенствование технических средств связи для решения проблем информатизации общества в новых условиях хозяйствования", г. Ленинград, 1991 г.; Международной конференции "Современные технологии обучения", Санкт-Петербург., 1998; II, III, IV и V Международных научно-практических конференциях "Системы и средства передачи и обработки информации", Одесса, 1998, 1999, 2000 и 2001 гг.; Международных научно-практических конференциях "Современные информационные и электронные технологии", Одесса, 1999 и 2000гг.; IV международной конференции по мягким вычислениям и измерениям "8СМ'2001", Санкт-Петербург, 2001; научно-технических конференциях (НТК) "Автоматизация проектирования радиоэлектронной и электронно-вычислительной аппаратуры", Пенза, 1982-1992 гг. (14 докладов); на 4-й и 5-й межотраслевых НТК (г. Уфа, 16-17 марта 1983 г., 1113 апреля 1989 г.); на республиканской НТК (г. Севастополь, 21-22 апреля 1986 г.); отраслевой НТК "Совершенствование технических средств для развития цифровых систем и сетей передачи информации", Ленинград, 1990г.; научно-техническом семинаре "Использование универсальной вычислительной техники при моделировании систем обработки информации", Усть-Нарва, 1990г.; НТК профессорско-преподавательского состава ЛЭИС им. проф. М.А.Бонч-Бруевича, 1984-1997 гг.

Основное содержание диссертации отражено в 65 печатных работах (в том числе в двух книгах).

Диссертация состоит из введения, шести разделов, заключения и приложения. Текстовой материал изложен на 184 машинописных страницах.

5.3. Выводы

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

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

3. Сравнение результатов оптимизации тестовых примеров продемонстрировало преимущество разработанных алгоритмов и программ по сравнению с алгоритмами и программами, используемыми в системе ABEL фирмы DATA I/O.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

169

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

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

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

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

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

1. Акимова И.Я. Задача о покрытии и ее приложения. Труды МВТУ, 1988, N512, с. 3-18.

2. Алексеев О.Г., Григорьев В.Ф. Некоторые алгоритмы решения задачи о покрытии и их экспериментальное исследование на ЭВМ. Журн. выч. мат. и мат. физ., т.34, 1984, N 10, с. 1565-1570.

3. Алексеев О.Г. Алгоритм решения задачи о покрытии. Изв. АН СССР, Техн. кибернетика, 1980, N 5.

4. Ачасова С.М. Алгоритмы синтеза автоматов на программируемых матрицах. М., Радио и связь, 1987, 135 с.

5. Баранов С.И., Синев В.И. Программируемые логические матрицы в цифровых системах (обзор). Зарубежная радиоэлектроника, 1979.

6. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М., Радио и связь, 1986, - 270 с.

7. Бибило П.Н. Декомпозиция булевых функций. В сб.: Проектирование устройств логического управления. М., 1984, с. 106-126.

8. Бибило П.Н. Свертка программируемых логических матриц с перетрассировкой промежуточных шин. Автоматика и выч. техника, 1997, №2, с. 75-84.

9. Бибило П.Н. Синтез дискретных устройств на базе ПЛИС. II. Управляющие системы и машины, 1998, №3, с.48-58.

10. Бибило П.Н., Лицкевич В.Г. Покрытие булевой сети библиотечными элементами. Управляющие системы и машины, 1999, №6, с. 16-24.

11. Бибило П.Н. Оценка сложности реализации матричных форм булевых функций схемами в базисе ПЛМ и УЛМ. Электронное моделирование, 1999, 21, №4, с. 57-63.

12. Васильев Ю.Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм. В сб.: Проблемы кибернетики. М., ФИЗ-МАТГИЗ, 1963, с. 5-62.

13. Ветухновский Ф.Я. О покрытиях графа системой окрестностей его вершин. Докл. АН СССР, 158, 1964, N 1, с. 21-24.

14. Ветухновский Ф.Я. Покрытия и минимальные покрытия графа системой окрестностей его вершин. В сб.: Дискретный анализ, 3, Новосибирск, 1964, с. 3-24.

15. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. -М., Наука, 1977, 351 с.

16. Глушков В.М., Капитонова Ю.В., Мищенко А.Т., Логическое проектирование дискретных устройств. Киев, Наукова думка, 1987, - 263 с.

17. Голов A.B., Лузин С.Ю. Оптимальный синтез многовыходных комбинационных автоматов. Материалы международной НТК "Системы и средства передачи и обработки информации". - Одесса, 1998, с.36.

18. Голов A.B., Лузин С.Ю. Эффективный алгоритм синтеза многовыходных комбинационных автоматов. // Технология и конструирование в электронной аппаратуре, 1999, №1, с.39-40.

19. Горбатов В.А., Демьянов В.Ф. Частотно-минимальный алгоритм покрытия булевых матриц. В сб.: Оптимизация дискретных систем управления. М., ГВЦ Госплана СССР, 1972, с. 48-57.

20. Горбатов В.А. и др. Автоматизация проектирования сложных логических структур. М., Энергия, 1978.

21. Горбатов В.А. Частотная матрица отношений и ее применения. Труды МЭИ. Вычислительная техника, 1964, т.53, с. 5-30.

22. Горбатов В.А. Теория частично упорядоченных систем. М., Сов. радио, 1976, - 248 с.

23. Горбатов В.А. Семантическая теория проектирования автоматов. М., Энергия, 1979,-264 с.

24. Горбатов В.А., Павлов П.Г., Четвериков В.Н. Логическое управление информационными процессами. М., Энергоатомиздат, 1984, - 304 с.

25. Горбатов В.А. Основы дискретной математики. М., Высшая школа, 1986,- 311 с.

26. Горбатов В.А. Фундаментальные основы дискретной математики. — М., Наука. Физматлит, 2000, -544с.

27. Григорьян Ю.Г. Арифметический метод минимизации булевых функций. В сб.: Теория автоматов, Киев, 1964, с. 23.

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

29. Дьяченко Ю.Г., Кармазинский А.Н. Получение минимальных логических формул. УСиМ, 1984, N 6, с. 28-30.

30. Журавлев Ю.И. Теоретико-множественные методы в алгебре логики. -Веб.: Проблемы кибернетики, вып. 8, М., Физ.мат., 1962.

31. Журавлев Ю.И. Локальные алгоритмы вычисления информации. Кибернетика, 1966, N2, с. 1-11.

32. Журавлев Ю.И. Оценка числа тупиковых ДНФ функции алгебры логики. Сиб. мат. журнал, 1962, Т. 3, N 5, с. 802-804.

33. Журавлев Ю.И. О различных понятиях минимальности ДНФ. Сиб. мат. журнал, 1960, Т. 1, N 4, с. 609-610.

34. Журавлев Ю.И., Коган А.Ю. Алгоритм построения ДНФ, эквивалентных произведению левых частей булевых уравнений нельсоновского типа. ЖВМ и МФ, т.26, 1986, N 8, с. 1243-1249.

35. Журавлев Ю.И., Коган А.Ю. Реализация булевых функций с малым числом нулей ДНФ и смежные задачи. ДАН СССР, 1985, т. 285, N4, с. 795799.

36. Закревский А.Д., Островский В.И. Оптимизация поиска кратчайшего покрытия. В сб.: Проблемы синтеза цифровых автоматов. - М., Наука, 1968.

37. Закревский А.Д. Оптимизация покрытий множеств. В сб.: Логический язык для представления алгоритмов синтеза релейных устройств. - М., Наука, 1965.

38. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М., Наука, 1971,-512 с.

39. Закревский А.Д. Логический синтез каскадных схем. М., Наука, 1981, -414 с.

40. Закревский А.Д. О приближенных методах решения логических задач. В сб.: Проблемы синтеза цифровых автоматов. М., Наука, 1967.

41. Закревский А.Д. Алгоритм минимизации слабо определенных булевых функций. Кибернетика, 1966, N 2, с. 53-60.

42. Закревский А.Д. Решение квазибулевых уравнений. Алгоритмы решения логико-комбинаторных задач. Минск, 1975, с. 10-12.

43. Зуев Ю.А. Задача о покрытии: локальный подход и метод типа ветвей и границ. ЖВМ и МФ, т. 19, N 6, 1979, с. 1566-1576.

44. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. М., Мир, 1988, -309 с.

45. Клемышев О.Ф. Некоторые задачи о покрытии. Изв. АН СССР, Техн. кибернетика, 1978, N 4.

46. Коган А.Ю. О нижних оценках сложности ДНФ булевых функций с малым числом нулей. ЖВМ и МФ, т.27, 1987, N 12, с. 1868-1877.

47. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978,-432 с.

48. Кузнецов И.Н. Алгоритмы оптимизации покрытий. Изв. АН СССР, Техн. кибернетика, 1973, N 1.

49. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М., Энергоатомиздат, 1988, - 480 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

65. Лузин С.Ю. Выбор полярности выходов в задаче минимизации многовыходных автоматов. Материалы международной НТК "Системы и средства передачи и обработки информации". - Одесса, 1999, с.67.

66. Лузин С.Ю. Об одном подходе к минимизации булевых функций. -Труды международной научно-практической конференции "Современные информационные и электронные технологии". Одесса, 2000, с. 29.

67. Лузин С.Ю. Использование спектра индексов в задаче минимизации булевых функций. Материалы международной НТК "Системы и средства передачи и обработки информации". - Одесса, 2000, с.76-77.

68. Лузин С.Ю. Асимптотически оптимальный метод получения простых импликант. // Автоматика и выч. техника, 2000, № 1, с.80-84.

69. Лузин С.Ю. Алгоритмы минимизации булевых функций. СПб, СПбГУТ, 2000, - 160с.

70. Лузин С.Ю. Декомпозиция задачи минимизации системы булевых функций. Материалы IV международной конференции по мягким вычислениям и измерениям "SCM'2001", Санкт-Петербург, 2001.

71. Лузин С.Ю. Определение полярности многовыходных автоматов. Труды международной научно-практической конференции "Современные информационные и электронные технологии". - Одесса, 2001, с. 171-172.

72. Лузин С.Ю. Минимизация булевых функций с использованием спектра индексов. // Автоматика и выч. техника, 2001, №3, с. 56-63.

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

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

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

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

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

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

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

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

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

82. Лузин С.Ю., Лутченков Л.С. Анализ и разработка алгоритмов логического синтеза. Спб, ГУТ им. проф. М.А. Бонч-Бруевича. 1996. - 105 с.

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

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

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

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

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

88. Лузин С.Ю., Полубасов О.Б. Логический синтез с использованием программы PLAST. //Международная конференция "Современные технологии обучения". Тез. докл. -СПб., 1998, с. 128.

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

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

91. Маматов Ю.А. Доказательство статистической оптимальности алгоритма Яблонского-Квайна-Мак-Класки в задаче о поиске кратчайшего покрытия. -ДАН СССР, 1976, 229, N 5, 1048-1050.

92. Мартинсонс Я.Я. Упрощение задачи типа покрытие конечного множества. Авт. и ВТ, 1984, N 5, с. 67-73.

93. Нгуен Ким Ань О некоторых характеристиках алгоритмов минимизации булевых функций. ДАН СССР, 1982, 267, N5, с. 1058-1062.

94. Новиков Я.А. Построение кратчайшей системы ДНФ по заданному множеству элементарных конъюнкций. Автоматизация процессов проектирования, Минск, 1983, вып. 1, с. 50-56.

95. Новиков Я.А. К достижению безубыточности ПЛМ. Алгоритмы логического проектирования, Минск, 1983, с.97-105.

96. Новоселов В.Г. Минимизация булевых функций (обзор). В сб.: Итоги исследований по кибернетике, Томск, 1968, с. 40-60.

97. Нурлыбаев А.И. О кратчайших ДНФ функций алгебры логики. Изв. АН Каз. ССР, сер. ФМ, 1984, N3, с. 65-67.

98. Оранов A.M. К синтезу дискретных схем в базисе ПЛИС. Изв. АН. Теория и системы управления, 1999, №2, с. 160-166.

99. Островский В.И. К исследованию свойств кратчайших покрытий. В сб.: Синтез дискретных автоматов и управляющих устройств. - М., Наука, 1968.

100. Поваров Г.Н. Метод минимизации булевых функций. Изв. АН СССР, Техн. кибернетика, 1982, N 4, с. 198-201.

101. Погарцев А.Г. К задаче построения минимальных представлений систем частично определенных булевых функций в классе ДНФ. Алгоритмы решения логико-комбинаторных задач. Минск, 1976, с. 87-103.

102. Погарцев А.Г. К минимизации слабоопределенных булевых функций. Алгоритмы решения логико-комбинаторных задач, Минск, 1975, с. 23-31.

103. Поспелов Д.А. Логические методы анализа и синтеза схем. М., Энергия, 1968, 328 с.

104. Поттосин Ю.В. Оптимизирующие преобразования моделей дискретных автоматов. ИФАК, симпозиум "Дискретные системы", Дрезден, 1977, т.1, с.75-84.

105. Прудников А.П., Брычков Ю.А., Маричев О.И. Интегралы и ряды. М., Наука, 1984.

106. Райзер Г. Дж. Комбинаторная математика. М., Мир, 1966г., 154с.

107. Рыцар Б.Е. Минимизация булевых функций методом расщепления конъюнктермов. -Управляющие системы и машины, 1998, №5, с. 14-22.

108. Рыцар Б.Е. Декомпозиция булевых функций методом q-разбиения.!. -Управляющие системы и машины, 1999, №6, с.29-42.

109. Рыцар Б.Е. Декомпозиция булевых функций методом q-разбиения.П. -Управляющие системы и машины, 2000, №1, с.56-65.

110. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задачи о покрытии. Кибернетика, 1984, N 6, с. 65-69.

111. Рузаев E.H., Канунов А.И., Муравьев C.B. Алгоритм нахождения минимального покрытия булевой матрицы. -Изв. вузов, 1981, N 8, с. 92-94.

112. Сапоженко A.A., Чухров И.П. Минимизация булевых функций в классе дизъюнктивных нормальных форм. Итоги науки и техники, сер. Теория вероятностей, мат. статистика и техническая кибернетика., т.25, 1987, с. 68-116.

113. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М., Наука, 1982, - 384 с.

114. Свобода А. Некоторые способы применения контактных сеток. Автоматика и телемеханика, 22, N 8, 1961, с. 1061-1070.

115. Сергиенко И.В., Рощин В.А. Один метод решения задачи о покрытии. ДАН УССР, 1983, N 9, сер. А.

116. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев, Наукова думка, 1985.

117. Скобелев В.Г. Комбинаторные алгоритмы построения дизъюнктивной нормальной формы. ДАН УССР, сер. А, 1989, N 2.

118. Соловьев В.В. Синтез конечных автоматов на PLS. Управляющие системы и машины, 1998, №5, с.23-28.

119. Тараканов В.Е. Комбинаторные задачи и (ОД)-матрицы. М., Наука, 1985, - 190 с.

120. Фридман А., Менон П. Теория и проектирование переключательных схем. М., Мир, 1978.

121. Черемисинова Л.Д. Минимизация площади матрицы Вайнберга, реализующей систему ДНФ. Управляющие системы и машины, 1999, №2, с.39-46.

122. Шестаков Е.А. Декомпозиция систем частичных булевых функций методом тождественных отображений. Автоматика и выч. техника. 1993. №2, с. 1726.

123. Штейн М.Е. Метод получения минимальной дизъюнктивной формы булевой функции. Вопросы радиоэлектроники, вып. 8, 1965, с. 76-90.

124. Штейн М.Е. К задаче проектирования комбинационных логических устройств. Изв. АН СССР, Техн. кибернетика, 1965, N 4, с. 70-76.

125. Чебурахин И.Ф. Задачи автоматизации и оптимизации аппаратной и программной реализации булевых функций. -Инф. технол., 1999, №2, с.28-34.

126. Черемисинова Л.Д. К синтезу комбинационных схем. Алгоритмы решения логико-комбинаторных задач, Минск, 1975, с. 100-105.

127. Шоломов А. Критерий сложности булевых функций. Проблемы кибернетики, N 17. М., Наука, 1966.

128. Юшманов С. Покрытие вершин графа кратчайшими простыми цепями. В кн.: Комбинаторно-алгебраические методы в прикладной математике, 1986, Горьковский ГУ, с. 178-200.

129. Яблонский С.В. Введение в дискретную математику. М., Наука, 1986,- 384 с.

130. Якубайтис Э.А., Шмаукстель Н.П. Методика нахождения минимальной дизъюнктивной нормальной формы функции, свободной от опасных состязаний. А и ВТ, N 11, 1965, с. 49-57.

131. Bar-Jehuda R., Even S. A localization theorem for approximating the weighted cover problem. Math. Studies 109, Annals of discrete math., 25, Amsterdam, 1985, p. 27-45.

132. Bar-Jehuda R., Even S. A linear time approximation algorithm for the weighted cover problem. J. Algorithms, 1981, 2, p. 198-203.

133. Bartlett K.A., Brayton R.K., Hachtel G.D., Jacoby R.M., udell R. Multilevel logic minimization using implicit don't cares. ICCD 86: Proc. IEEE Int. Conf. Comput. Des., VLSI Comput. Pop. Chester, N.Y., Oct. 6-9, 1986, p. 552-557.

134. Bermond J.C., Jackson F., Jager F. Shortest coverings of graphs with cycles. -J. Comb. Th., B35, 3, Des. 1983, p. 297-308.

135. Bowman R.M., Mc.Vey E.S. A method for fast approximate solution of large prime implicants charts. IEEE Trans. Elec. Comp., 1970.

136. Buonanno G., Sciuto D., Stefanelli R. Innovative Structures for CMOS Combinational Gates Synthesis. IEEE Trans, on Comp., vol. 43, No.4, 1994, p.385-399.

137. Clarkson K. A modification of the greedy algorithm for vertex cover. -Inform. Proc. Lett., 16, 1983, p. 23-25.

138. Edmonds J. Covers and packing in a family of sets. Bull. Amer. Math. Soc., v.68, 1962, N5, p. 494-499.

139. Friedman S.J., Supowit K.J. Finding the Optimal Ordering for Binary Decision Diagrams. IEEE Trans. Comput., vol. 39, N5, 1990, p. 710-713.

140. Gusfield D., Pitt L. Equivalent approximation algorithms for node cover. -Inf. Proc. Letters, 22, 1986, N6, p. 291-294.

141. Ghasala M.J. Irredundant disjunctive and conjunctive forms of boolean function. IBM J. Res. Develop., v.l, 1956, p. 171-176.

142. Hwa H.R. A method for generating prime implicants of a boolean expressions. IEEE Trans. Elec. Comp., C-23, 1974, p. 637-641.

143. Hulme B.L., Worrel R.B. A prime implicant algorithm with factoring. -IEEE Trans. Comp., C-24, 1975, p. 1129-1131.

144. Karnaugh M. The map method for synthesis of combinational logic circuits. AIEE Trans. Commun/ Electron., vol.72, p.593-598, Nov. 1953.

145. Lemke C.E., Salkin H.M., Spielberg K. Set covering by single-branch enumeration with linear-programming subproblem.- Oper. Res., 1971, 19, N4, p. 998-1025.

146. Mc.Cluskey E.J. Minimization of Boolean functions. Bell Sys. Tech.J., 1956, vol.35, No.6., p. 1417-1444.

147. Mc.Cluskey, Edward J., Logic Design Principles, Englewood Cliffs, NJ: Prentice-Hall, 1986.

148. Mott T.H., Carrol C.C. Numerical procedures for boolean functions minimization. -IEEE Trans. Comput., 1964, EC-13, N4, p. 470-471.

149. Monien B., Speckenmeyer E. Some futher approximation algoritms for the vertex cover problem. Lecture Notes in Comput. Science, 1982.

150. Mohring R.H. Graph Problem to Gate Matrix Layout and PLA Folding. -Computing Suppl. 7, 17-51 (1990)

151. Morreal E. Recursive operations for prime implicant and irredundant normal form determination. IEEE Trans. Comput., 1970, C-19, p. 504-509.

152. Nelson R.J. Simplest normal truth functions. -J. Symb. Logic, 1955, v.20, N2, p. 105-108.

153. Necula N.M. An algorithm of the approximate minimization of boolean functions. -IEEE Trans. Comput., 1968, C-17, p. 770-782.

154. Pyne J.B., Mc Cluskey E.J. The reductor of redundancy in solving prime implicant tables. -IEEE Trans. Elec. Comp., 1962, v.l 1, N4, p. 473-482.

155. Pyne J.B., Mc Cluskey E.J. An essay on prime implicants.- M, v.9, N4, Des. 1961, p. 604-631.

156. Perkins Sharon R., Rhyne Tom. An algorithm for identifying and selecting the prime implicants of a multiple-output boolean function. -IEEE Trans. Comput-Aid. Des. Inegr. Circuit and Syst.-1988, 7, N11, p. 1215-1218.

157. Petrick S.R. A direct determination of the irredundant forms of a boolean functions from the set of prime implicants. Air Force Cambrige Res. Centre, 1956.

158. Quine W.V. A way to simplify truth functions. Amer. Math. Monthly, 1955, v.62, N9, p.627-631.

159. Quine W.V. The problem of simlifying truth function. Amer. Math. Montly, 1952, v.59, N8, p.521-531.

160. Qwine W.V. On cores and prime implicants of truth func- tions. Amer. Math. Monthly, 1959, v.66, N9, p.755-760.

161. Reusch B. Generation of prime implicants. -IEEE Trans. Comput., 1975, C-24, p.924-930.

162. Rhyne T.V., Noe P.S., Mc Kinney., Pooch U.W. A new technique for fast minimization of switching functions. IEEE Trans. Comput, C-26, 1977, p. 757764.

163. Roth R. Computer solution to minimum-cover problem. Operat. Res., 1969, 17, N3, p. 455-465.

164. Roth J.P. An algoritnm for the problem of Qwine.-Bull. Amer. Math. Soc., v.62, 1956, p. 262.

165. Sasao T. Input Variable Assignment and Output Phase Optimization of PLA's. IEEE Trans. Comput., vol. C-33, N10, 1984, p. 879-894.

166. Svoboda A. Ordering of implicants. IEEE Trans. Comput., 1967, EC-16, N1, p. 100-105.

167. Slagle J.R., Chang C.L., Lee R.C.T. A new algorithm for generating prime implicants. IEEE Trans. Comput., C-19, N4, 1970, p. 304-310.

168. Sureschander. Minimization of switching functions a fast technique. -IEEE Trans. Comput., N7, 1975, p. 756.

169. Tison P. Generalization of consensus theory. IEEE Trans., 1967, C-16, p. 446-456.

170. Taconet B. New prime implicant algorithm, based on mono-tonicity properties. -Electron. Lett., 1984, 20, N2, p. 89-90.

171. Unger S.H. The essence of logic circuits. Englewood Cliffs, NJ, Prentice-Hall, 1989.

172. Wey Chin-Long, Chang Tsin Yuan. PLAYGROUND: minimization of PLAs with mixed ground true outputs. -25th ACM/IEEE Des. Autom. Conf., Anaheim, June 12-15, NJ., 1988, p. 421-426.