Представление логических схем (1132264)

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

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

Лекция 1.Представление логических схемМатематические модели и методы синтеза СБИСВесна 2016План лекции• Двоичные решающие диаграммы (BDD) ипредставление булевых функций в виде BDD.Различные типы BDD.• Связь BDD с контактными схемами и схемами изфункциональных элементов.• Основные операции над BDD.

Выбор оптимальногопорядка переменных разложения и его значениедля упорядоченных BDD.• Представление логических схем с использованиемBDD.• Особенности построение эффективныхвычислительных систем для манипуляций с BDD.Структурная и функциональнаямодель• Структурная модель– Описывает элементы из которых состоит схемаи связи между ними– Необходима для построения топологии• Функциональная модель– Описывает поведение (функцию) каждогоэлемента схемы– Анализ поведения схемы– ВерификацияСтруктурная и функциональнаямодель• Нужен специальный математическийаппарат, позволяющий описывать всемножество функций, реализуемых схемой• Требуются математические моделипозволяющие– связать структурную и функциональную модели– эффективно решать основные задачи анализа исинтеза схемы, а также различные задачиверификации схемОсновные представлениялогических схем• Представления булевых функций––––Таблица истинностиДНФ (Positional cube notation)Двоичные решающие диаграммы (BDD)Другие• Представление логических схем––––Графовые модели с использованием BDDAdd-Inverter GraphsЛогические сетиДругиеДвоичные решающие диаграммы(BDD)• BDD Σ от БП x1,…,xn – ориентированныйациклический граф с одним или болееистоками и двумя стоками.• Стоки помечены символами “0” и “1”, любаядругая вершина имеет пометку xi, 1≤i≤n.• Истоки (и, возможно, другие вершины)помечены специальными символами,характеризующими булевы функции (БФ),реализуемые в этих вершинах.Структура BDD - примерыFGAABBBCCBA0101Двоичные решающие диаграммы(BDD)• Каждое ребро является ребром 0-типа(«прерывистые») или ребром 1типа(«непрерывные»)• Из каждой вершины исходит два ребра:одно ребро 0-типа и одно ребро 1-типа.• Ребро 0-типа (1-типа) проводит, еслипеременная, приписанная вершине изкоторой исходит ребро, равна 0 (1).Функционирование BDD - примерыF(A, B, C)G(A,B)AABBCCBA0101F(0, 1, 1) = 1BF(0, 1) = 0Представление булевых функций ввиде BDD• В любой вершине BDD Σ реализуется БФ f –БФ проводимости от этой вершины BDD Σ кеё стоку с пометкой “1” (заметим, что БФпроводимости от вершины BDD Σ к её стоку спометкой 0 равна ¬f).• BDD Σ реализует систему БФ, которыереализуется в вершинах, помеченныхспециальными символами.• Сложность L(Σ) BDD Σ – число ее вершин, неявляющихся стокамиРеализация булевых функций припомощи BDD - примерыF(A, B, C)G(A,B)AABBCCBA0101F(A, B, C) = A+B+C+1BF(A, B) = ABРазличные типы BDD••••Разделяемые BDDУпорядоченные BDDПриведенные BDDДругие типы BDD– Binary moment diagrams– Zero-suppressed decision diagrams– Free binary decision diagrams– Parity decision diagrams– Multiple terminal decision diagramsРазделяемые BDD• В каждой вершине BDDреализуется некотораяфункция• BDD Σ реализует систему БФ,которые реализуется ввершинах, помеченныхспециальными символами.• Совместное использованиеподфункцийOutAGFBAABACB0C1Упорядоченные BDD• Упорядоченная BDD (OBDD) от БП x1,…,xn –BDD, в которой на любом пути от входа квыходам переменные встречаются в одном итом же «глобальном» порядке.Упорядоченные BDD - примерыF(A, B, C)G(A,B)AABBCCBA0101A>B>CBНеупорядоченная BDDПриведенные BDD• Операции приведения BDD:– удаление вершины, у которой обе исходящиедуги идут в одну и ту же вершину;– слияние (отождествление) двух вершин,обладающих тем свойством, что БФпроводимости от каждой из них к выходамBDD равны.• Приведенная BDD – упорядоченная BDD, ккоторой применены все возможные операцииудаления и слияния.Приведенная BDD - примерыFFAABBCCCC0101BПриведенная BDD - примерыFFABBCCCC0101Разделяемые приведенныеупорядоченные BDD• Randal E.

Bryant. "GraphBased Algorithms for BooleanFunction Manipulation". IEEETransactions on Computers, C35(8):677–691, 1986.• Представляют одну изосновных структур данных,используемых для хранениябулевых функций, которыереализуются в узлахлогической схемы.Связь BDD с контактными схемами• BDD представляет собой, по существу,специальный класс контактных схем.Связь BDD со схемами изфункциональных элементов• Используя мультиплексоры, попроизвольной BDD можно получить схему изфункциональных элементов, реализующуюте же БФ, что и исходная BDD.Выбор оптимального порядкаразложения переменных BDD• Порядок переменных может очень сильновлиять на сложность получаемой ROBDD длязаданной БФ.• Для заданной БФ сложность получаемой ROBDDможет быть как линейной, так иэкспоненциальной в зависимости от выборапорядка разложения по переменным.• Проблема выбора для заданной БФоптимального по сложности получаемой OBDDпорядка БП является NP-трудной.Выбор оптимального порядкаразложения переменных BDDВыбор оптимального порядкаразложения переменных BDD• Рассмотрим следующиеБФ: = ,1 ,…, = 1 ∨ ⋯ ∨ ∨ .=1• Лемма 1.

Пусть = , … , −+1 . Для любых двухподмножеств ′ , ′′ ∈ , ′ ≠ ′′ , выполняется неравенство:−≠ −′′′ .• Доказательство. Достаточно рассмотреть переменную, котораявходит в ′ и не входит ′′ (или наоборот). Для одной израссматриваемых БФ указанная переменная будетсущественной, а для другой – нет.min −1• Следствие.

Мощность множества = равна 2 . ∈ 2Выбор оптимального порядкаразложения переменных BDD• Лемма 2. Пусть 1 = , , −1 , −1 , … , 1 , 1 - порядокразложения переменных. Тогда сложность ROBDD,реализующей БФ и имеющий порядок разложенияпеременных 1 , равна 2.• Доказательство. Рассмотрим разложение БФ попеременным и := −1 ,= −1 , =0−1 =0 =1= −1 ,−1 =1= 1.• Следовательно, = 2 + −1 .11• Учитывая, что 0 = 0, решим рекуррентное1уравнение: = 2.1Выбор оптимального порядкаразложения переменных BDD• Лемма 3.

Пусть 2 = , … , , , … , 1 - порядок разложенияпеременных. Тогда сложность ROBDD, реализующей БФ иимеющий порядок разложения переменных 2 , не меньше, чем2 .• Доказательство. Рассмотрим последовательное разложение БФ по переменным , … , 1 := −1 ,= −1 , =0 −1−1−1 =0−1 =0 =1= −2 , −1−2 ,−1=−1 =1−1 =1= −2−1 ,= −2,−1 .• Нетрудно видеть, что при таком порядке разложения попеременным в качестве подфункции появятся все БФ множества.• Так как все БФ множества попарно различны и = 2 , то всоответствующей ROBDD будет не менее 2 вершин.Основные операции над BDD• Оператор условного перехода (if-then-else (ITE)): , , ℎ = ⋅ ∨ ⋅ ℎ.• Оператор ITE может быть применен для рекурсивногопостроения ROBDD: , , ℎ = ⋅ ∨ ⋅ ℎ == ⋅∨⋅ℎ∨ ⋅∨⋅ℎ=1= =1⋅= , =1=1∨,=1=1,ℎ⋅ℎ=1=1=0∨ , ==0=1⋅,=0=1∨,ℎ⋅=0=1=0=,где – первая по порядку разложения переменная в ROBDD.• Терминальные случаи рекурсии: 1, , = 0, , = , 1,0 = , , = .Пример применения оператора ITE кROBDD = (, , )FGHBAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,=1, =0,=0,A==0??FGHBAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,=1, =0,=0,A==0= , 1, , , …??FGHBAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,=1= , 1, , , , 0, , =0,=0,A==0=??FGHBAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,=1= , 1, , , , 0, = , , (, 0, ), =0,=0,A==0=?FGHBAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,= , 1, , , , 0, = , , , =1, =1, 0, =0,=0,A==0==1B, =0, 0, ==0GHB??FAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,= , 1, , , , 0, = , , , =1, =1, 0, =0,=0,A==0==1B, =0, 0, ==0GH= , , , 1,0,1 , …B??FAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,= , 1, , , , 0, = , , , =1, =1, 0, =0,=0,A==0==1B, =0, 0, ==0GH= , , , 1,0,1 , (0,0, )B??FAADCDBC0B1Пример применения оператора ITE кROBDDI = , , == , =1,=1,= , 1, , , , 0, = , , , =1, =1, 0, =0,=0,A==0==1= , , , 1,0,1 , (0,0, )= , , , 0, B, =0, 0, ==0FGH=BAADCDBC0B1Основные операции над BDD• Любая бинарная и унарная булева операцияможет быть получена при помощи оператораITE и констант 0 и 1 (мультиплексорная БФ содной адресной переменной и константыобразуют полную систему): , = , , 0 , = , 1, = (, 0,1)Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCBDDORANDOutGКомандыпостроения BDDA1 A = CreateVar(‘A’);A01Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCORANDOutGКомандыпостроения BDD12BDDABA = CreateVar(‘A’);B = CreateVar(‘B’);A0B1Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCORANDOutGКомандыпостроения BDD123BDDA = CreateVar(‘A’);B = CreateVar(‘B’);C = CreateVar(‘C’);ABACB0C1Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCORANDOutFGAКомандыпостроения BDD1234BDDA = CreateVar(‘A’);B = CreateVar(‘B’);C = CreateVar(‘C’);F = AND(A, B);ABACB0C1Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCORANDOutGFGBAКомандыпостроения BDD12345BDDA = CreateVar(‘A’);B = CreateVar(‘B’);C = CreateVar(‘C’);F = AND(A, B);G = AND(B, C);ABACB0C1Представление логических схем сиспользованием BDDЛогическая схемаAANDFBCANDOutAOROutGFGBAКомандыпостроения BDD123456BDDA = CreateVar(‘A’);B = CreateVar(‘B’);C = CreateVar(‘C’);F = AND(A, B);G = AND(B, C);Out = OR(F,G);ABACB0C1Особенности построения эффективныхсистем для манипуляции с BDD••••Разделяемые ROBDD.Помеченные ребра (Attributed Edges).Таблица уникальных вершин (Unique Table).Таблица последних вычислений (ComputedTable).• Управление памятью• Динамическое переупорядочивание.Особенности построения эффективныхсистем для манипуляции с BDDITE(F,G,H)(result,terminal_case) = Terminal_Case(F,G,H)if terminal_case thenreturn result(result,in_computed_table) = Computed_Table_Has_Entry(F,G,H)if in_computed_table thenreturn resultx = Top_Variable(F,G,H)T = ITE(F.true_edge(x),G.true_edge(x),H.true_edge(x))F = ITE(F.false_edge(x),G.false_edge(x),H.false_edge(x))if T == F thenreturn TR = Find_Or_Add_Unique_Table(x,T,F)Insert_Computed_Table((F,G,H),R)return R.

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

Тип файла PDF

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

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

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