Двухуровневый логический синтез (1132260)

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

Текст из файла

Лекция 3.Двухуровневый логический синтезМатематические модели и методы синтеза СБИСОсень 2014Двухуровневый логический синтез• Реализация булевых функций в виде ДНФ ипрограммируемые логические матрицы(ПЛМ)• Эвристические подходы к минимизацииДНФ• Обобщенно-монотонное разложениебулевых функций• Основные этапы алгоритма ESPRESSOРеализация булевых функций в видеДНФПрограммируемые логическиматрицы (ПЛМ)• Реализация системыбулевых функций наоснове ДНФ• Первая интегральнаясхема TMS2000 (TexasInstruments, 1970)• Оптимизация числалитералов приводит куменьшению площадисхемы.Минимизация ДНФ – основныеподходы• Известные методы минимизации ДНФ– Эквивалентные преобразования. Сложно применим прибольшом числе переменных и неясно как оценить качествополученного результата.– Метод карт Карно.

Применим только при малом числепеременных.– Метод Квайна. Экспоненциальная сложность в худшемслучае.• Эвристические подходы - свойства.– Поиск ДНФ близких к минимальным.– Последовательное (итеративное) улучшение текущегорешения.• Эвристические подходы– Градиентный метод– Алгоритм ESPRESSOАлгоритм ESPRESSO – общая идея• Пример – функция 4-хпеременных, заданнаятаблицей• Указаны толькоединичные наборы• Покрытие построено изнекоторого набораимпликант функции (необязательно простых)1 03 4 2 0010 0110 1111 11 011Грани10*0*20*10310014110151*1*1110111111Алгоритм ESPRESSO – общая идея• «Расширение» граней (EXPAND)– последовательноепреобразование граней вмаксимальные грани• Для каждой грани может бытьнесколько различных способовсделать её максимальной• В нашем примере«расширяются» грани 2 , 3 , 4• Полученное покрытие состоиттолько из максимальных граней• Полученное покрытие может небыть тупиковым илиминимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**10310014110151*1*1110111111Алгоритм ESPRESSO – общая идея• «Расширение» граней (EXPAND)– последовательноепреобразование граней вмаксимальные грани• Для каждой грани может бытьнесколько различных способовсделать её максимальной• В нашем примере«расширяются» грани 2 , 3 , 4• Полученное покрытие состоиттолько из максимальных граней• Полученное покрытие может небыть тупиковым илиминимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**1031**14110151*1*1110111111Алгоритм ESPRESSO – общая идея• «Расширение» граней (EXPAND)– последовательноепреобразование граней вмаксимальные грани• Для каждой грани может бытьнесколько различных способовсделать её максимальной• В нашем примере«расширяются» грани 2 , 3 , 4• Полученное покрытие состоиттолько из максимальных граней• Полученное покрытие может небыть тупиковым илиминимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**1031**14**0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Расширение» граней (EXPAND)– последовательноепреобразование граней вмаксимальные грани• Для каждой грани может бытьнесколько различных способовсделать её максимальной• В нашем примере«расширяются» грани 2 , 3 , 4• Полученное покрытие состоиттолько из максимальных граней• Полученное покрытие может небыть тупиковым илиминимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**1031**14**0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Тупиковое покрытие» –удаление граней, которыепокрываются другимимаксимальными гранями(IRREDUNDANT)• В нашем примере можноудалить 3• Полученное покрытиеявляется тупиковым• Полученное покрытие можетне быть минимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**1031**14**0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Тупиковое покрытие» –удаление граней, которыепокрываются другимимаксимальными гранями(IRREDUNDANT)• В нашем примере можноудалить 3• Полученное покрытиеявляется тупиковым• Полученное покрытие можетне быть минимальным1 03 4 2 0010 0110 1111 11 011Грани10*0*2**104**0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Сужение» граней (REDUCE) –последовательное уменьшениекаждой из граней при сохранениипокрытия• Результирующее покрытие состоитне только из максимальных граней• Позволяет изменить формупокрытия• Порядок «сужения» граней имеетважное значение• Является ключевым шагом, так какпозволяет в дальнейшемпроизвести такое «расширение»граней, которое позволит покрытьдругие грани• В нашем примере можно «сузить»,например, 2 и 41 03 4 2 0010 0110 1111 11 011Грани10*0*20*104**0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Сужение» граней (REDUCE) –последовательное уменьшениекаждой из граней при сохранениипокрытия• Результирующее покрытие состоитне только из максимальных граней• Позволяет изменить формупокрытия• Порядок «сужения» граней имеетважное значение• Является ключевым шагом, так какпозволяет в дальнейшемпроизвести такое «расширение»граней, которое позволит покрытьдругие грани• В нашем примере можно «сузить»,например, 2 и 41 03 4 2 0010 0110 1111 11 011Грани10*0*20*1041*0151*1*1110111111Алгоритм ESPRESSO – общая идея• «Сужение» граней (REDUCE) –последовательное уменьшениекаждой из граней при сохранениипокрытия• Результирующее покрытие состоитне только из максимальных граней• Позволяет изменить формупокрытия• Порядок «сужения» граней имеетважное значение• Является ключевым шагом, так какпозволяет в дальнейшемпроизвести такое «расширение»граней, которое позволит покрытьдругие грани• В нашем примере можно «сузить»,например, 2 и 41 03 4 2 0010 0110 1111 11 011Грани10*0*20*1041*0151*1*1110111111Алгоритм ESPRESSO – общая идея1 03 4 2 0010 0110 1111 11 01111101 03 4 2 0010 01111110 1111 1111 01110111111ГраниГрани10*0*10*0*2**102**1041**141**151*1*51*1*«Расширение» граней11«Тупиковое покрытие»Алгоритм ESPRESSO• Этапы алгоритма– «Сужение» граней (REDUCE)– «Расширение» граней (EXPAND)– «Тупиковое покрытие» (IRREDUNDANT)• Разработка алгоритма началась в компании IBM и былазавершена в университет Berkeley• Литература– Brayton, Hachtel, McMullen, Sangiovanni-Vincentelli, LogicMinimization Algorithms for VLSI Synthesis, Kluwer AcademicPress, 1984– Richard L.

Rudell, (1986-06-05), “Multiple-Valued LogicMinimization for PLA Synthesis” Memo No. UCB/ERL M86-65 (U.California Berkeley M.S. Thesis)– Giovanni DeMicheli, Synthesis and Optimization of DigitalCircuits, McGraw Hill, 1994Задача проверки тождественности• Дано:– ДНФ для ФАЛ f (в PCN формате).• Задача:– Установить, является ли ФАЛ f тождественноравной 1.Рекурсивная проверка тождественности• Разложение Шеннона:• Основные вопросы:– Выбор переменной: по какой переменной лучше всегопроводить разложение?– Критерий останова: когда можно остановить рекурсию?– Особенности реализации: как эффективно хранитьподфункции в памяти?Обобщенно-монотонные ФАЛ иполяризованные ДНФРекурсивное разложения ФАЛ пообобщенно-монотонным ФАЛПостроение тупиковых ДНФ –процедура IRREDUNDANT• Метод Квайна––––Построение сокращенной ДНФРазмер сокращенной ДНФНахождение всех тупиковых ДНФГрадиентный метод• Процедура IRREDUNDANT– Построение тупиковой ДНФ на основеподмножества простых импликант, образующихпокрытие ФАЛ– Использование рекурсивного разложения пообобщенно-монотонным ФАЛПостроение тупиковых ДНФ –процедура IRREDUNDANT.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций