Логическая оптимизация комбинационных логических схем (1183901)

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

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

Математические модели и методылогического синтеза СБИСОсень 2015Лекция 4План лекции• Логическая оптимизация комбинационныхлогических схем– Различные способы представления функций алгебрылогики (ФАЛ) (таблицы истинности, формулы,двоичные решающие диаграммы, схемы изфункциональных элементов). Сравнение указанныхпредставлений и их ограничения.– Комбинационные логические сети (КЛС). Задачаоптимизации КЛС (различные постановки задач,функционалы качества при оптимизации КЛС).Основные типы преобразований КЛС: исключение,разложение, экстракция, упрощение и подстановка.Способы представленияфункций алгебры логикиЛекция 4Способы представления функций алгебрылогики• Таблица истинности = (01101001)• Дизъюнктивная нормальная форма (ДНФ) = 1 ∨ 2 • Формула в заданном базисе = 1 |2 ∼ • Схема из функциональных элементов (СФЭ) в заданномбазисе1&∨2&Способы представления функций алгебрылогики• Двоичные решающиедиаграммы• Комбинационныелогические сетиF(A, B, C)A2BBCC01A>B>C1 = 2 ∨ 33 = 1 ∨ Сравнение различных представленийфункций алгебры логикиТаблицаистинностиДНФФормулаСФЭBDDКЛСДопустимоечислопеременныхМалоеСреднееБольшоеБольшоеБольшоеБольшоеУникальностьпредставления+---+-Зависимостьот базиса--++--СложностьпредставленияЛинейнаяотносительночисла входныхнаборовЗависит отФАЛЗависит отФАЛ ибазисаЗависит отФАЛ ибазисаЗависит отФАЛ ипорядкаследованияпеременныхЗависит отструктурыКЛСКомбинационные логическиесетиЛекция 4Структура комбинационныхлогических сетей• Комбинационная логическая сеть (КЛС) –ациклический ориентированныйпомеченный граф Σ = (, ) специальнойструктуры• Множество вершин = , , Σобразуют разбиение:– - множество основных входов– - множество основных выходов– Σ - множество внутренних вершин = (… )Внутренние вершиныкомбинационных логических сетей• Каждой внутренней вершине КЛС приписаны:– внутренняя переменная ∈ – ФАЛ , зависящая от переменных из множества ⊆ × , и соответствующая этой ФАЛпредставление в некоторой модели = (01101001)Таблица истинности = 1 ∨ 2 ДНФ = 1 |2 ∼ Формула :12 :&&1 :2∨0СФЭ и AIG1BDD1 = 2 ∨ 3 = 1 ∨ 3КЛСДуги комбинационных логическихсетей• Основные входы являются истоками• Основные выходы являются стоками• Дуга = , ∈ существует в КЛС Σ = , ,если ФАЛ, реализуемая в зависит от ФАЛ,реализуемой в = (… ) = (… , , … ) = (… , , … )Функционированиекомбинационных логических сетей• Основные входы реализуют тождественныеФАЛ• Так как граф КЛС является ациклическим, тоФАЛ (как функции основных входов),определяются последовательно на основетопологического порядка внутренних вершин = (… , (… ), … ) = (… )<Комбинационная логическая сеть пример121 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 512 = 1 ∨ 2 ∨ 3 5 ∨ 4 523 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 534 = 1 ∨ 2 ∨ 34345Комбинационная логическая сеть пример111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Оптимизация комбинационныхлогических сетей• Преобразование КЛС за счет специальныхопераций• Все операции должны сохранятьэквивалентность исходной и преобразованнойсхемы с точки зрения реализуемых выходныхфункций• Преобразования можно разделить на двакласса:– преобразования вершин (локальные)– преобразования структуры схемы (глобальные)Функционалы качества при оптимизациякомбинационных логических сетей• Сначала определяются функционалы качествадля внутренних вершин КЛС, а потом на ихоснове определяются функционалы качествадля КЛС в целом• Функционалы качества во внутреннейвершине определяется на основепредставления, которое используется длязадания ФАЛ, реализуемой в этой вершине• Для иерархических КЛС функционалы качестваопределяются рекурсивноФункционалы качества комбинационныхлогических сетей• Для ДНФ – Длина (A) – число элементарных конъюнкций в – Сложность(ранг) - число букв в • Для формулы – Ранг - число букв в – Сложность () – число операций в – Глубина - глубина корня формулы • Для СФЭ Σ– Сложность () – число функциональныхэлементов в Σ– Глубина - максимальная длина пути от входовдо выходов СФЭ Σ = 1 ∨ 2 ДНФ = 1 |2 ∼ Формула :12&&∨СФЭ и AIGФункционалы качества комбинационныхлогических сетей• Для BDD :– Сложность - числонетерминальных вершин в BDD – Глубина - глубина корня BDD 1ДНФ01BDD• Для КЛС Σ– Сложность () – сумма сложностейво всех внутренних вершинах КЛС Σ– Глубина - максимальнаявзвешенная глубина пути от входов довыходов КЛС Σ :21 = 2 ∨ 3 = 1 ∨ 3КЛСЗадача оптимизации комбинационныхлогических сетей• Построение КЛС для заданной системыФАЛ с наилучшими значения выбранныхфункционалов качества• Многокритериальная задача оптимизациивыбранных функционалов качества• Однокритериальная задача оптимизациивыбранного функционала качества сдополнительными ограничениями надругие функционалы качестваПространство решений задачи оптимизациикомбинационных логических сетей(Σ)21 = 2 ∨ 33 = 1 ∨ Решение с заданнымизначениями Σ и (Σ)Пространство решений (Design space)(Σ)Пространство решений задачи оптимизациикомбинационных логических сетей(Σ)21 = 2 ∨ 33 = 1 ∨ Не улучшаемое решениепо параметрам Σ и (Σ)Пространство решений (Design space)(Σ)Парето оптимальная кривая решениймногокритериальной задачи оптимизации(Σ)ПаретооптимальнаякриваяПространство решений (Design space)(Σ)Однокритериальная задача оптимизации сдополнительными ограничениями(Σ) Σ < ∗Оптимальноерешение призаданныхограничениях наглубинуПространство решений (Design space)(Σ)Преобразования комбинационныхлогических сетей• Исключение (ELIMINATION) – удаление внутренней вершиныКЛС и соответствующая подстановка ФАЛ, реализуемой этойвершиной в другие вершины• Разложение (DECOMPOSITION) – замена внутренней вершинынесколькими вершинами, которые формируют подсеть,реализующую такую же ФАЛ, что и исходная вершина• Извлечение (EXTRACTION) – добавление новой внутреннейвершины, которая реализует ФАЛ, являющейся подфункциейдля нескольких других внутренних вершин, и соответствующаяподстановка символа новой вершины в указанные вершины• Упрощение (SIMPLIFICATION) – оптимизация представленияФАЛ, реализуемой во внутренней вершине• Подстановка (SUBSTITUTION) – упрощение представления ФАЛ,реализуемой в вершине за счет увеличения числапеременных, от которых зависит указанная ФАЛПример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2454 = ∨ ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33-3+2=32, Глубина: 3-1=2.Пример разложения(DECOMPOSITION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример разложения(DECOMPOSITION)111 = ( ∨ ∨ ) ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример разложения(DECOMPOSITION)1 = ∨ ∨ 22 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2451 = 4 ∨ 1 53 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 312Сложность: 33-8+3+4=32, Глубина: 3.Пример извлечения (EXTRACTION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример извлечения (EXTRACTION)1234511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 52 = ( ∨ )53 = 2 ∨ 14 = 3 ∨ 235 = ( ∨ )(1 ∨ 2 ) ∨ 56 = 1 ∨ 227 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33, Глубина: 3.Пример извлечения (EXTRACTION)122 = 53 = ( ∨ )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = ∨ ∨ 33 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33-4-9+2+2+5=29, Глубина: 3.Пример упрощения (SIMPLIFICATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример упрощения (SIMPLIFICATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = ∨ 2Сложность: 33-6+2=29, Глубина: 3.Пример подстановки(SUBSTITUTION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 243 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Произведем экстракцию 3 ∨ 4 в вершинах 2 и 55Сложность: 33, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 53 = ( ∨ )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = ∨ ∨ 33 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33-4=29, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 9 539 = (3 ∨ 4 )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = 9 ( ∨ ) ∨ 533 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 29, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 9 539 = (3 ∨ 4 )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 53 = 2 ∨ 14 = 3 ∨ 25 = 9 ∨ 57 = 6 3 ∨ 6 3 ∨ 6 3234Сложность: 29-4+2=27, Глубина: 3..

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

Тип файла PDF

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

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

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