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

• Автор: Лузин, Сергей Юрьевич
• Шифр специальности: 05.13.12
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Санкт-Петербург
• Количество страниц: 188 с. : ил

СОДЕРЖАНИЕ
Введение

I. Особенности и проблемы синтеза

МИ1ИМАЛБНЫХ ФОРМ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНК 1ИЙ.

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. Анализ результатов автоматизированного
логического синтеза комбинационных схем
5.4. Выводы
Заключение
Список ЛИТЕРАТУРЫ


II, III, IV и V Международных научно-практических конференциях “Системы и средства передачи и обработки информации”, Одесса, , , и гг. Международных научно-практических конференциях “Современные информационные и электронные технологии”, Одесса, и гг. IV международной конференции по мягким вычислениям и измерениям “$СМ’”, Санкт-Петербург, ; научно-технических конференциях (НТК) "Автоматизация проектирования радиоэлектронной и электронно-вычислительной аппаратуры", Пенза, - гг. НТК (г. Уфа, - марта г. НТК (г. Севастополь, - апреля г. НТК "Совершенствование технических средств для развития цифровых систем и сетей передачи информации", Ленинград, г. Использование универсальной вычислительной техники при моделировании систем обработки информации", Усть-Нарва, г. НТК профессорско-преподавательского состава ЛЭИС им. М.А. Бонч-Бруевича, - гг. Основное содержание диссертации отражено в печатных работах (в том числе в двух книгах). Диссертация состоит из введения, шести разделов, заключения и приложения. Текстовой материал изложен на 4 машинописных страницах. В первом разделе дан аналитический обзор современных моделей, методов синтеза комбинационных автоматов в классе ДНФ, получены асимптотические оценки комбинаторной сложности алгоритмов и необходимого для их реализации объема памяти, сформулированы перспективные направления повышения эффективности алгоритмов и программных систем на их основе и обоснована постановка задач диссертационной работы. Во взором разделе решается задача существенного повышения эффективности классического подхода к минимизации ДНФ булевых функций: приводятся новые алгоритмы получения простых импликант булевых функций, в частности, асимптотически оптимальный алгоритм, названный алгоритмом поразрядного выращивания, а также ряд подходов к повышению эффективности решения комбинаторной задачи о покрытии. В третьем разделе вводится понятие спектра индексов булевой функции, исследуются его свойства, приводятся методы определения эффективности минимизации ДНФ булевых функций, использующие свойства спектра индексов совокупности термов, образующих интервал, а также алгоритм, основанный на синтезе подобных спектров и идентификации соответствующих им интервалов. В четвертом разделе описаны новые эффективные подходы к минимизации булевых функций и систем булевых функций, в том числе: экономичный алгоритм, использующий принцип “поразрядного выращивания” для решения собственно задачи минимизации булевых функций, при этом рассмотрен вопрос выбора порядка нумерации независимых переменных на каждом из этапов; поиск с ограничением типа “ветвей и границ”, а также алгоритмы оптимизации многовыходных комбинационных автоматов, включая определение оптимальной полярности выходных сигналов. В пятом разделе приведены результаты экспериментальных исследований разработанных алгоритмов и программ. Проводится сравнительный анализ с пакетом ABEL фирмы DATA I/O (США), одним из мировых лидеров в области программного обеспечения систем логического синтеза. В заключении сформулированы основные научные и практические результаты работы. В приложении даются сведения, подтверждающие использование полученных результатов в народном хозяйстве страны. Теоретической основой логического синтеза дискретных устройств обработки и передачи информации является задача минимизации булевых функций. Минимизация логических функций заключается в приведении их к такой форме, которой соответствует минимальное число операций над логическими переменными. Это позволяет аппаратно реализовать логическую функцию при помощи минимального количества технических средств. Получение множества всех простых импликант булевой функции уже для числа независимых переменных п > может потребовать значительной памяти и большого времени работы ЭВМ. В свою очередь задача о покрытии относится к классу полиномиально неразрешимых задач. Поэтому на практике зачастую отказываются от поиска оптимального решения, используя различного рода эвристические алгоритмы. Данная глава посвящена анализу современных подходов к решению проблемы логического синтеза комбинационных схем.