Ленина Факультет "Вычислительной математики и кибернетики"

Казанский Муниципальный Институт

им. В.И. Ульянова-Ленина

Факультет "Вычислительной арифметики и кибернетики"

Кафедра "Теоретической кибернетики"


Методы и структуры данных в построении и анализе СБИС

Курс лекций

Лектор:

доцент кафедры

теоретической кибернетики

Мубаракзянов Р. Г.


Составители: студенты Ленина Факультет "Вычислительной математики и кибернетики" 3 курса

Бурмистров И., Складчиков Д.О.


Казань 2005


Введение
Истинное методическое пособие представляет собой конспект курса лекций, прочитанных в вешнем семестре 2005 г. для студентов третьего курса факультета ВМК КГУ и посвященных анализу алгоритмов Ленина Факультет "Вычислительной математики и кибернетики" и структур данных, применяемых в построении и анализе СБИС1. Невзирая на актуальность данной темы, в русской литературе фактически отсутствует материал на данную тему. Курс базируется в главном на книжке “C. Meinel, T. Theobald. Algorithms Ленина Факультет "Вычислительной математики и кибернетики" and data Structures in VLSI Design. – Springer, 1998”, также на статьях разных создателей и собственных результатах лектора. В составлении пособия оказали помощь студенты 3 курса Бурмистров И., Складчиков Д.О.

Создатель заблаговременно приносит извинения Ленина Факультет "Вычислительной математики и кибернетики" за незавершенность и неполноту изложения. Работа по созданию пособия длится и создатель будет признателен за любые замечания по тексту изложения.


^ Лекция 1. Вводные понятия. Булевы функции.

Основными компонентами компов и других цифровых систем Ленина Факультет "Вычислительной математики и кибернетики" являются схемы. В схемах провода соединяют определённым образом один либо несколько заряженных входных портов с одним либо несколькими выходными портами. В простейшей модели различаются два напряжения на входах и выходах: заряжено, которое Ленина Факультет "Вычислительной математики и кибернетики" обозначается «1», и незаряжено, которое обозначается «0». В реальности, таковой бинарное представление символизирует, что заряд не выходит за границы 2-ух непересекающихся непрерывных интервалов зарядки.

СБИС представляет собой сложную комбинацию (соединение) ограниченного Ленина Факультет "Вычислительной математики и кибернетики" числа главных, либо многофункциональных, частей, которые производят ординарную логическую операцию. Хотя операции зависят не от четкого значения входного сигнала, а от соответственного интервала зарядки, можно моделировать (кодировать) входные и выходные значения многофункциональных Ленина Факультет "Вычислительной математики и кибернетики" частей «0» и «1», таким макаром, элементы и схемы с n входами и одним выходом, соответствуют фукциям: .

В 1936 году рассмотрение таких схем из многофункциональных частей предложил Шеннон (C.E.^ Shennon). Он показал, что главные законы Ленина Факультет "Вычислительной математики и кибернетики" математической логики и теории множеств, сформулированные G Boole в его книжке в 1854 году, могут быть применены в описании и анализе схем.


^ Булева алгебра – это огромное количество А, содержащее 0 и 1, 0 ≠ 1, и две бинарные операции Ленина Факультет "Вычислительной математики и кибернетики" (, ) и унарную операцию ¯ , если для производится

1) коммутативный закон:

,

;


2) распределительный закон:

,

;

3) существование нейтрального элемента:

(для сложения),

(для умножения);

4) существование отрицания:

(для сложения),

(для умножения);


Будем рассматривать только конечные алгебры, при всем этом принято считать Ленина Факультет "Вычислительной математики и кибернетики", что операция ¯ имеет ценность над  , а  имеет ценность над +. Примем также запись ab для a  b.

Примеры:

1) 2s – огромное количество подмножеств алгебра подмножеств (2S, , , ¯, , S) – Булева алгебра;

2) для n  1, пусть n Ленина Факультет "Вычислительной математики и кибернетики" имеет только разные обыкновенные делители: n=p1p2…pk, p1 < p2<…

Булева алгебра удовлетворяет принципу двойственности:


Определение: Если G – некое равенство Ленина Факультет "Вычислительной математики и кибернетики" в булевой алгебре (A, ,  ,0, 1) то G – двоякое равенство, приобретенное из G обоюдной подменой + на  и «0» на «1»:

К примеру, если , то .


Аксиома 1. (Принцип двойственности) Пусть G’ – двоякое равенство для G Ленина Факультет "Вычислительной математики и кибернетики". Если G – верное выражение в теории булевых алгебры, то G’ также поистине.

Подтверждение разумеется, потому что теоремы сохраняют истинность булевой алгебры при переходе к двояким равенствам. Таким макаром, исходя из принципа двойственности довольно обосновать Ленина Факультет "Вычислительной математики и кибернетики" выражения в булевой алгебре только в одной из 2-ух версий.


Аксиома 2. (Основной закон вычислений) Для всех в булевой алгебре (A; , , 0,1) производятся:

1) законы идемпотепции: , ;

2) характеристики нейтральности частей: ;

3) поглощения: ;

4) ассоциативности: ;

5) законы Де Ленина Факультет "Вычислительной математики и кибернетики" – Моргана:  , ;

^ 6) двойственность отрицания: .


Докажем, к примеру, закон поглощения: .

Другие подтверждения опустим.

^ Булевы функции – это функции, описываемые выражениями булевой алгебры, либо булевыми формулами.


Определение. Пусть – булева алгебра. Выражение, содержащее переменные , знаки ¯ и элементы А именуются булевой Ленина Факультет "Вычислительной математики и кибернетики" формулой над переменными, если производится последующее:

^ 1) элемент A – булева формула;

2) – булевы формулы;

3) Если F и G – булевы формулы, то

- - булева формула;

- - булева формула;

- - булева формула

4) выражение является булевой формулой, если оно Ленина Факультет "Вычислительной математики и кибернетики" может быть получено конечным числом применений правил 1,2,3.


Замечание. Можно опускать скобки (ценности).


Булева формула индуцирует булеву функцию:

- есть элемент A при подмене на .


Определение. Пусть - булева алгебра. Функция от n переменных: - булева функция, если она Ленина Факультет "Вычислительной математики и кибернетики" может быть порождена булевой формулой. Будем гласить, что F представляет f.


Определение. Булевы функции от n переменных эквивалентны, если их значения совпадают на всех 2n входных векторах из .


Аксиома 3. f – эквивалентна g Ленина Факультет "Вычислительной математики и кибернетики" : .

Подтверждение. Из аксиом и главных законов можно показать, что неважно какая формула может быть переписана в виде суммы:

, где

.

Таким макаром, неважно какая булева функция совершенно точно определяется коэффициентами , которые зависят Ленина Факультет "Вычислительной математики и кибернетики" только от .


Следствие 1. Количество разных булевых функций равно .

^ Лекция 2. Переключательные функции.

Таким макаром, рассматривая разные булевы функции, довольно разглядеть значения функции на , и, в предстоящем, будем рассматривать особый случай булевой алгебры с Ленина Факультет "Вычислительной математики и кибернетики" 2-мя элементами, является теоретической основой построения схем. Значимость этой алгебры была показана ещё в 1910 году физиком Эренфестом (Ehrenfest), занимавшимся разработкой переключательных схем в телефонных сетях. Наибольшее продвижение получило исследование в 1936-38 гг. в Ленина Факультет "Вычислительной математики и кибернетики" Стране восходящего солнца, США, СССР. Но одной из важных была работа Шеннона.

Итак, разглядим последующую булеву алгебру :


Определение. Функция от n переменных , именуется переключательной функций. ^ Будем обозначать переключательные функции .


Из следствия Ленина Факультет "Вычислительной математики и кибернетики" 1 следует, что количество разных булевых функций в Bn , а количество разных переключательных функций также переключательная функция является булевой функцией.

Потому, в предстоящем, будем исспользовать термин «Булева функция», подразумевая переключательную функцию.

Схема с Ленина Факультет "Вычислительной математики и кибернетики" n входами и m выходами описывается «m» - кой , где - булевы функции. Обозначим такие функции .

Аксиома. Число разных булевых функций от n –переменных с m выходом равно .


Терминология: Для f B

1) – 1-набор либо Ленина Факультет "Вычислительной математики и кибернетики" выполнимый набор, если f = 1.

2) 1 – огромное количество: L= ;

0 – огромное количество:

3) Переменная x существенна, если набор

.

Функция f может быть отождествлена со своим 1-множеством L, поточнее является характеристической функцией собственного 1-множества:


Булева функция от 2 либо меньше переменных:

  1. от Ленина Факультет "Вычислительной математики и кибернетики" 0 переменных: константы 0,1:



b) от 1 переменной:

с) от 2 переменных:

- v – дизъюнкция (+)

-  - конъюнкция ( )

- …


Подфункция выходит при фиксации неких значений переменных.


Аксиома (разложение Шеннона). Пусть f – булева функция от n переменных для подфункций :, производится .

Подтверждение Ленина Факультет "Вычислительной математики и кибернетики" разумеется.


Замечание. Каждой переменной можно поставить в согласовании: элемент если xi =n ,то xi нефиксирована (свободна): Существует подфункций от n переменных (не непременно разных).


Следствие 2. и правильно:

1) Разложение Шеннона Ленина Факультет "Вычислительной математики и кибернетики" по -му аргументу:

;

2) «Двойственное» разложение Шеннона:

;

3) Разложение Шеннона относительно :

.

Подтверждение:

1) разумеется;

2) следует из признака двойственности;

3) следует из того, что одно из слагаемых равно нулю.

^ Лекция 3. Принципиальные характеристики Булевых функций.

Существует ряд параметров Ленина Факультет "Вычислительной математики и кибернетики" булевых функций, узнаваемых из курса дискреиной арифметики: монотонность, симметричность и т.д.

Определение . - однообразно вырастает ( убывает) по i-му аргументу, если для хоть какого aBn, f(a1 ,…, ai-1 ,0, 1i+1 ,…, an )= f(a1 ,…, ai-1 ,1,ai Ленина Факультет "Вычислительной математики и кибернетики"+1 ,…, an).

Если функция однообразно растёт (убывает) по каждому собственному аргументу она именуется возрастающей (убывающей).


Аксиома. f – однообразно возрастающая (убывающая)функция

.


Аксиома. однообразно растёт (убывает) по i – му аргументу f может Ленина Факультет "Вычислительной математики и кибернетики" быть представлена: , для g и h, независимых от x.


Симметрические функции.


Определение. Функция именуется симметрической неважно какая перестановка значeний переменных не изменят значения функции .

Таким макаром, функция симметрическая она находится в зависимости от количества Ленина Факультет "Вычислительной математики и кибернетики" единиц посреди переменных, но не от их позиций. Как следует, симметрические функции совершенно точно определяются их значениями на векторах: , .

Замечание. симметрических функций.


Существует ряд принципиальных симметрических функций:

  1. функция Четности (Parity)



  1. функция голосования Ленина Факультет "Вычислительной математики и кибернетики" (Majority)



  1. Пороговая функция:



  1. Оборотная пороговая функция



  1. Интервальная функция



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


Стоит упомянуть еще последующую функцию:


Определение. Взвешенная пороговая функция с весами и порогом если Ленина Факультет "Вычислительной математики и кибернетики" =1 .

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




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

^ Лекция 4. Вычислимые функции и сложность вычислений Ленина Факультет "Вычислительной математики и кибернетики" (неформальное введение).

До того как гласить о представлении функции, нам необходимо объяснить некие понятия теории вычислимости и трудности.

Одна из целей теории трудности – разбиение функций зависимо от трудности на разные классы.

Из Ленина Факультет "Вычислительной математики и кибернетики" предшествующего курса вы знакомы с иерархией Хомского:

Но существует и другое разбиение функций.

^ Какие функции вычислимы?

Тезис Черча. Интуитивно вычислимые функции – функции, вычислимые машинами Тьюринга.

Существую разные модели вычислений:

1) Интуитивная Ленина Факультет "Вычислительной математики и кибернетики" вычислимость – вычислимость программками.

2) Машина Тьюринга (МТ) – это … (популярная модель)

3) …

Но для нас принципиальна не только лишь вычислимость , да и сложность вычисления.

Перечислим принципиальные моменты.

Время вычисления.

МТ – обычное вычисление: время  количество тактов.

Класс P Ленина Факультет "Вычислительной математики и кибернетики" (полином и экспонента).

Есть функции, для которых не удается отыскать полиномиальный метод.

Класс NP – недетерминированное вычисление.

Задачка определения эквивалентна задачке вычисления. Пример: Раскраска и k – раскраска.


P = N P?

N P Ленина Факультет "Вычислительной математики и кибернетики" – полные задачи.

Сводимость.

Задачки. Разбиение; Гамильтонов цикл.

^ Лекция 5. Представление функций.

Представление функций должно удовлетворять последующим требованиям:

  1. Довольно куцее и действенное.

  2. Позволяет манипулировать и вычислять функции.

  3. Визуализация определенных параметров функции.

  4. Давать подсказку идеи Ленина Факультет "Вычислительной математики и кибернетики" для технологий реализации и т.д.


Нам известны некие представления:

  1. Таблицы истинности (резвое вычисление, резвое выполнение бинарных операций). Хотя сложность линейная относительно размера таблицы, но экспоненциально относительно количества переменных. Размерность таблицы экспоненциальна .

  2. ДНФ, КНФ Ленина Факультет "Вычислительной математики и кибернетики" (СДНФ, СКНФ), полином Жегалкина (без отрицаний) – 2-х уровневые обычные формы.


Определение. Представление именуется

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

- совершенным, если для булевой функции единственное представление такового типа Ленина Факультет "Вычислительной математики и кибернетики".


ДНФ, КНФ – не являются совершенным представлением. Для совершенных представлений, чтоб найти эквивалентность функций довольно проверить идентичность их представлений. Но с другой стороны, СДНФ (СКНФ) имеют огромную длину: сложность ДНФ (длина ДНФ Ленина Факультет "Вычислительной математики и кибернетики" – количество входящих в нее литералов) для СДНФ максимальна посреди всех эквивалентных ДНФ.

Аксиома 1. 3-SAT – NP-полна. (3-КНФ).

Аксиома 2. INEQU (С, С) – NP-полна.

Подтверждение: 3 - SAT ^ INEQU : С = С , С = 0.

Следствие. Эквивалентность КНФ – Co-NP-полна Ленина Факультет "Вычислительной математики и кибернетики".


Операции не всегда комфортны. К примеру, ни равенство , ни не может быть решено относительно f.

– поле в алгебраическом смысле, таким макаром, результаты теории алгебраических полей могут быть перенесены на .


Аксиома Ленина Факультет "Вычислительной математики и кибернетики" 3. Полином Жегалкина – совершенное представлений булевых функций.

Подтверждение. Неважно какая ДНФ представима через полином Жегалкина булева функция представима в виде полинома Жегалкина. С другой стороны, количество полиномов Жегалкина равно: , т.е. количеству всех Ленина Факультет "Вычислительной математики и кибернетики" булевых функций, что и обосновывает аксиому.


Аксиома 4. Функция , где для

Подтверждение. .

Пусть в наборе ровно l единиц в ^ P количество мономов, равных 1 и содержащих k переменных, равно , количество единичных мономов .


3) СФЭ.

Переход от Ленина Факультет "Вычислительной математики и кибернетики" 2-х уровневой к многоуровневым формам позволяет отыскать более малогабаритное представление булевых функций.

Пусть = - огромное количество базисных функций (именуется базисом, если нельзя удалить ни одной функции из без уменьшения замыкания ).

-СФЭ «S» - от Ленина Факультет "Вычислительной математики и кибернетики" n переменных – ациклический граф с верхушками 2-х типов:

- входные верхушки (без входящих дуг), помеченные 0, 1 либо , i =1,..,n;

- многофункциональные верхушки – верхушки, помеченные , имеет входящих дуг: .

Любая верхушка v представляет булеву функцию, подобающую последующим Ленина Факультет "Вычислительной математики и кибернетики" индуктивным правилам:

1) Если v помечена 0 (1) 0 (1);

2) если v помечена ;

3) если v помечена и имеет входящих дуг, выходящих из : .


Обозначив m узлов , как выходные узлы СФЭ, эта схема определяет функцию .

Пример. Полный сумматор – отлично популярная Ленина Факультет "Вычислительной математики и кибернетики" базисная компонента в построении чипов. Эта схема вычисляет для 3 входных битов (с – бит переноса): – стандартный базис.





Глубина СФЭ – число многофункциональных уровней в СФЭ – соответствует временным затратам.


Определение. Базис полон, если Ленина Факультет "Вычислительной математики и кибернетики" -СФЭ – соответствует универсальному представлению, другими словами булева формула может быть представлена в - СФЭ.


Пример.

1) - стандартный базис - полон (ДНФ, КНФ);

2) - полон;

3) , - полон;

40 - неполон, потому что он генерирует только однообразно растущие функции.


Даже для фиксированного базиса Ленина Факультет "Вычислительной математики и кибернетики" представление булевой функции разносторонне. Нас интересует представление в СФЭ с маленьким количеством вершин.


Определение. -СФЭ- сложность булевой функции f – малое число вершин -СФЭ, представляющей f .


ДНФ и КНФ – особые формы СФЭ, потому Ленина Факультет "Вычислительной математики и кибернетики" СФЭ-сложность в стандартном базисе менее ДНФ- (КНФ-)трудности. С другой стороны, почти всегда СФЭ-сложность наименее ДНФ- (КНФ-) трудности.

Но СФЭ-модель как и раньше имеет недочет: неприемлемая временная сложность Ленина Факультет "Вычислительной математики и кибернетики" проверки эквивалентности схем.


Аксиома. Эквивалентность СФЭ над стандартным базисом – со NP - полна.

Подтверждение. Неувязка  соNP,


4) Формулы, как СФЭ.

В СФЭ экономия происходит, а именно, в связи с тем, что выход элемента может Ленина Факультет "Вычислительной математики и кибернетики" подаваться на вход нескольких частей. Другими словами, верхушки могут иметь несколько выходных дуг. Конкретно это свойство нередко позволяет выстроить малогабаритное представление в виде СФЭ. Но это приводит к трудности решения разных Ленина Факультет "Вычислительной математики и кибернетики" задач.


Определение. Для -базиса -формула – это -СФЭ, степень финала каждой верхушки которой равна 1.


Следствие. -СФЭ – формула она состоит из деревьев.

Разумеется, взаимно - однозначное соотношение меж -формулами и булевыми формулами.

Анализ представления функции Ленина Факультет "Вычислительной математики и кибернетики" в виде -формулы намного проще, чем в виде СФЭ, к примеру нижние оценки трудности определенных функций. Но эквивалентность булевых формул – соNP-полна.

^ Лекция 6. Бинарные диаграммы решений .

5) Бинарные диаграммы решений.

Определение. Бинарное дерево решений (б Ленина Факультет "Вычислительной математики и кибернетики". д. р.) – дерево, в каком:

- внутренние верхушки помечены переменными и имеют ровно 2 выходные дуги.

- листья помечены 0 и 1.

Замечание. Можно представить, что кпждая переменная читается 1 раза.


Пример. (х х) (х х)

а Ленина Факультет "Вычислительной математики и кибернетики") Полное дерево

б) Неполное дерево

в) Изменение порядка чтения переменных значительно оказывает влияние на размер б. д. р ( порядок х, х, х, х)


Бинарные диаграммы решений (Lee ,1959), ветвящиеся программки (branching programs -5) (Mask Ленина Факультет "Вычислительной математики и кибернетики", 1976) либо бинарные программки (BP): направленный ациклический граф с 2-мя стоками, помеченными 0,1, и внутренними верхушками, помеченными х и имеющими две выходных дуги, конечные 0 и 1.

^ Размер (сложность) бинарной программки – количество её вершин.


Пример. х х Ленина Факультет "Вычислительной математики и кибернетики" х х

В отличие от бинарных деревьев решений в бинарных программках повторное чтение переменных может дать бинарную программку наименьшего размера (нереально удалить верхушку, в какой переменная читается повторно, потому что ее можно достигнуть разными Ленина Факультет "Вычислительной математики и кибернетики" способами).


Бинарные программки можно рассматривать и для представления функций с несколькими выходами из ^ B. При всем этом выделяется m исходных вершин.




Неувязка перевода 1-го представления булевой функции в другое.

Бинарная Ленина Факультет "Вычислительной математики и кибернетики" программка ДНФ. Строим моном для каждого пути. Потом разглядим дизъюнкцию мономов.

Бинарная программка -СФЭ (-полный базис).

Разглядим булеву функцию sel (x, y, z) = y + x f

а) Заменим каждую верхушку, помеченнную x, на sel-вершину Ленина Факультет "Вычислительной математики и кибернетики" с одним из входов, равным x, двигаясь от финишных вершин.

б) Изменим направление всех дуг.

в) Заменяем все sel-вершины на -СФЭ.


^ Лекция 7. Ограниченные классы бинарных программ. Сложность заморочек для бинарных программ Ленина Факультет "Вычислительной математики и кибернетики".


Лекция 8. Требование к структурам данных в формальной верификации схем.


Итак, существует несколько типов представления булевых функций:

1. Задание значений функции (табл. истинности).

2. Способ вычисления булевой функции (СФЭ).

3. Описание схемы определения значений Ленина Факультет "Вычислительной математики и кибернетики" функции (ВР).


Эти представления имеют значительные различия:


1. Размер: таблица истинности и ДНФ ( х1+х2+..+хn ), с другой стороны х1+х2+..+хn , представленная в виде полинома Жегалкина имеет слагаемыми различные мономы.

2. ^ Ресурсы, требующиеся для вычисления функции Ленина Факультет "Вычислительной математики и кибернетики": к примеру, время

(Таблица истинности – сходу, формула - вычисление).

3. Ресурсы, требуемые для представления результата булевых операций над 2-мя функциями (f  g). (Для СФЭ стремительно, для ВР1  NP-сложно).

4. Сложность определения параметров функции (напр. «функция Ленина Факультет "Вычислительной математики и кибернетики" – константа?»: просто для ВР1; NP-сложно для КНФ: f  SAT f=const, f(0,..,0)=0 )

5. Сложность определения фиктивности переменной (полином Жегалкина: переменная существенна  заходит в полином Жегалкина, для КНФ  NP-сложно: f  SAT Ленина Факультет "Вычислительной математики и кибернетики"  для новейшей переменной х0 , х0f значительно находится в зависимости от f).

^ Верификация схем
Таким макаром, нереально отыскать безупречную форму представления булевых функций. Потому принципиально расставить ценности. Нас интересует построение схем. Разглядим две Ленина Факультет "Вычислительной математики и кибернетики" задачи из области верификации схем. Эти трудности очень важны, но не считая того, являются подпроблемами огромных заморочек.


Логические схемы: комбинационные схемы, схемы с элементами памяти.

Комбинационные схемы не имеют частей памяти.

Хотя Ленина Факультет "Вычислительной математики и кибернетики" схемы с элементами памяти более функциональны, исследование комбинационных схем очень принципиально:

1. Сами по для себя: как вычисление функции за один шаг.

2. Схемы с элементами памяти являются расширением комбинационных схем Ленина Факультет "Вычислительной математики и кибернетики".

При построении схем принципиальна их многофункциональная правильность. Описание параметров схемы именуется спецификацией. Разработка логической схемы сводится к итерационным шагам: спецификация – реализация: реализация на i-ом шаге задаёт спецификацию i+1 шага.

Подтверждение многофункциональной правильности осуществляется Ленина Факультет "Вычислительной математики и кибернетики".

1. Оценка поведения спецификации и реализации на большенном числе входящих векторов.

2. Формальная верификация (математическое подтверждение).

3. Частичная верификация (математическое подтверждение, что реализация удовлетворяет по последней мере неким принципиальным свойствам поведения спецификации): свойство надежности Ленина Факультет "Вычислительной математики и кибернетики" (определенные «плохие» действия не могут произойти); свойство жизнеспособности (может быть, что определеные «хорошие» действия произойдут).


Формальная верификация комбинационных схем.


При моделировании схем рассматриваются сети логических частей. Логический элемент – это простая схема, соединяющая транзисторы так Ленина Факультет "Вычислительной математики и кибернетики", чтоб рассчитывалась определенная Булева операция на входах. Задачка «логического синтеза» - улучшить схему соответственно определенным аспектам: количество частей, размер чипа, экономия энергии, задержки…

Для решения этих задач разрабатывались системы логического Ленина Факультет "Вычислительной математики и кибернетики" синтеза. Разрабатывались такие системы и в академических центрах:

- MINI (I^ BM Reslorch,1974)

- ESPRESO (Berkley,1984)

(Калифорния)

- MIS (Berkley,1987)

- BOLD (Un Colorado at Boulder,1989)

- SIS (Berkley,1992).


Главные требования к представлениям функций:

1) т.к. в главном схемы – это Ленина Факультет "Вычислительной математики и кибернетики" сети логических частей, то появляется необходимость представления функции, являющейся выходной для элемента на входы которого поданы другие булевы функции:



^ Булевы операции должны осуществляться отлично.

2) Минимизация числа частей: спецификация, реализация – эквивалентны ли они Ленина Факультет "Вычислительной математики и кибернетики"?

Многофункциональная эквивалентность должна производиться отлично (неувязка SAT, т.е. выполнимость схемы).

3) Схемы с памятью.



Описание таких схем может быть осуществлено с помощью KDA.

Эквивалентность KDA: Если состояние кодируется 80 битами, то получаем Ленина Факультет "Вычислительной математики и кибернетики" 280 состояний. Время существования Вселенной 234 лет≈244 часов≈256 секунд , как следует, если даже обрабатывать 2 миллиона состояний за секунду, то не хватило бы всего времени существования Вселенной для анализа эквивалентности такового автомата.

Достаточно длительно оценивалась Ленина Факультет "Вычислительной математики и кибернетики" работа системы на большенном огромном количестве входов (1994, Intel Pentium-ненадежность проверки). Современная формальная верификация базирована на действенном представлении огромного количества состояний, либо характеристической функции огромного количества состояний ( т.е. Булевой функции Ленина Факультет "Вычислительной математики и кибернетики").

Главные препядствия KDA (напр. проверка эквивалентности) можно решаться отлично.

^ Лекция 9. OBDD - действенная структура данных.

Начало исследования OBDD для VLSI-дизайна положили работы Брайнта (Bryant, 1986г.). Последующие характеристики очень важны.

1) Редуцированная ^ OBDD Ленина Факультет "Вычислительной математики и кибернетики" совершенное представление Булевой функции.

2) Манипулирование редуцированнами OBDD может производиться отлично.

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


Определения.

Определение 1. Пусть   порядок огромного количества переменных {x1,……,xn}: {x(1),……,x (n)}. OBDD (ordered binary Ленина Факультет "Вычислительной математики и кибернетики" decision diagram)  упорядоченная бинарная диаграмма решений) с порядком чтения переменных   это ациклический орграф, имеющим ровно 1 корень, 2 финишные верхушки, не имеющие выходных дуг. Эти финишные верхушки помечены 0 и 1 (0-вершина, 1-вершина). Любая Ленина Факультет "Вычислительной математики и кибернетики" нефинальная верхушка помечена переменной хi и имеет 2 выходные дуги, помеченные 0 и 1. Порядок, в каком переменные встречаются на  пути в графах соответствуют порядку , т.е. если дуга ведет от верхушки помеченной хi к верхушке помеченной Ленина Факультет "Вычислительной математики и кибернетики" хj  -1(i)< -1(j).


Определение 2. OBDD представляет Бул. функцию f  Bn , если  a  Bn вычисленный путь на а, т.е. путь от корня до финишной верхушки в согласовании с а, добивается верхушку, помеченную f Ленина Факультет "Вычислительной математики и кибернетики" (a).


Верхушка OBDD с меткой хi определяет разложение Шеннона:

Если OBDD имеет корень, помеченный хi , и представляет f(x1,……,xn), то , где fXi = f(x1,……,xi-1,1, xi+1,…, xn);




Пример.




Определение 3. Пусть Ленина Факультет "Вычислительной математики и кибернетики" P1, P2 – OBDD. P1 и P2 -изоморфны (P1  P2) , если  биекция  меж верхушками P1 и P2 :

1) пометка v и  (v) совпадает;

2) для a{0,1}, если a-дуга от v ведет к w, то Ленина Факультет "Вычислительной математики и кибернетики" a-дуга от  (v) ведёт к  (w).

Определение 4. OBDD именуется редуцированной, если

- не существует верхушки v: 1-дуга и 0-дуга от v ведет к одной верхушке w;

- не существует 2-х вершин v Ленина Факультет "Вычислительной математики и кибернетики" и w: OBDD с корнями v и w - изоморфны: OBDD(v)≈OBDD(w).

Определение 5. 2 правила редукции OBDD:

Правило «удаления»: если 1-дуга и 0-дуга от верхушки v ведут к одной верхушке W, то можно Ленина Факультет "Вычислительной математики и кибернетики" перенаправить дуги, входящие в v, на вход W.

Правило «склеивания»: если u и v помечены одной и той же переменной, и 1-дуги от n и v ведут к одной верхушке, и 0-дуги Ленина Факультет "Вычислительной математики и кибернетики" - - - -  можно отожествить n и v, удалив одну из этих вершин, перенаправив все ее входящие дуги к оставшейся верхушке.




^ Лекция 10. Характеристики редуцированных OBDD.

Т.1. OBDD - редуцирована  когда неприменимо ни одно из правил редуцирования Ленина Факультет "Вычислительной математики и кибернетики".

Подтверждение. Необходимость. OBDD редуцирована ни одно из правил не может быть использовано.

Достаточность. Пусть не может быть применимо правило «удаления»

 1 свойство редуц. ^ OBDD выполнено.

Пусть OBDD имеет 2 верхушки v и W и OBDD(v Ленина Факультет "Вычислительной математики и кибернетики")≈OBDD(W).

 а) 1-сын (u)=1-сын(v), 0-сын (u)=0-сын (v)  может быть применимо правило «склеивания»

б) Пусть u =1-сын(u)1-сын(v)=v либо 0-сын(u) 0-сын(v)

Пусть 1 неравенство выполнено Ленина Факультет "Вычислительной математики и кибернетики"  OBDD (u)  OBDD (v)

Повторим функцию с u и v. На каждом шаге миниатюризируется огромное количество переменных, которые могут встречаться в под-OBDD, потому менее, чем за n шагов процесс приведет к Ленина Факультет "Вычислительной математики и кибернетики" способности применить правило «склеивания», т.к. 1-вершина и 0-вершина схожи.


Покажем, что  Б. функция имеет совершенное представление в виде ^ OBDD при фиксированном порядке чтения переменных.

Дальше для простоты будем Ленина Факультет "Вычислительной математики и кибернетики" рассматривать естественный порядок: x1,….,xn . Разглядим xi-вершину v.

На пути от корня до v читаются xj: j  i-1.

Если вход c1,...,cn соответствует вычисленному пути, ведущему через v  OBDD(v) вычисляет подфункцию fX1=C Ленина Факультет "Вычислительной математики и кибернетики"1,…,Xi-1=Ci-1


Т.2. Пусть Si огромное количество подфункций f, приобретенных при фиксированнии переменных{xj , j i-1}, для которых xi – существенна. Прямо до изоморфизма  единственная OBDD малого размера для f с порядком Ленина Факультет "Вычислительной математики и кибернетики" x1,….,xn . Эта OBDD имеет |Si| вершин, помеченных xi.


Подтверждение: 1) Поначалу построим наименьшую OBDD P для f, которая для хоть какого i содержит ровно |Si| вершин, помеченных xi .

- Если f Ленина Факультет "Вычислительной математики и кибернетики" константа, то P является графом с 2-мя верхушками (обе финишные).

- Инд. предположение : для  j ≥ i+1  gSj в P имеется ровно 1 верхушка xj-вершина v : OBDD (v) вычисляет g.


- Инд. переход : разглядим i. Пусть  и Ленина Факультет "Вычислительной математики и кибернетики" является константами либо Sj для некого j ≥ i+1.

Для h введем верхушку vh. Пометим её xi и поправим 1-дугу в , a 0-дугу в .

P выч-т f, что доказывается также индуктивно Ленина Факультет "Вычислительной математики и кибернетики", т.к. P верно вычисляет подфункции: это правильно для финишных вершин : .

2) Минимальность P.

Подтверждение от неприятного. Если P не мала   , для которой существует i : содержит < |Si| вершин, помеченных xi.

Но  |Si| разных Ленина Факультет "Вычислительной математики и кибернетики" подфункций f вида fX1=C1,…,Xi-1=Ci-1 , значительно зависящих от xi .

Разглядим Q={(c1....ci-1) | fX1=C1,…,Xi-1=Ci-1  Si . Т.к. fX1=C1,…,Xi-1=Ci-1 принадлежат Si  пути, помеченные x1=c Ленина Факультет "Вычислительной математики и кибернетики"1,…,xi-1=c i-1 , ведут в верхушки, помеченные xi    Q : , но пути, помеченные и ведут в одну и ту же верхушку, что приводит к противоречию , т.к. корень ^ OBDD соответствует только одной Ленина Факультет "Вычислительной математики и кибернетики" подфункции.

3) Малая OBDD  изоморфна P.

Следуя предшествующим рассуждениям :  малая OBDD R с порядком x1,…,xn содержит для  подфункции g  Si верхушку, помеченную xi c отпрысками, gXi=1 и gXi=0   OBDD с этим Ленина Факультет "Вычислительной математики и кибернетики" же количеством вершин изоморфна P, а  OBDD R неизоморфная P имеет дополнительные верхушки  R неминимальна.

Аксиома 3. Пусть P – OBDD бул. функции f с порядком  P – изоморфна малый P| для f c   ни одно из правил Ленина Факультет "Вычислительной математики и кибернетики" редуцирования не может быть применимо к Р.

Поясним смысл утверждения.


Т3




Т.е. для малых ^ OBDD нереально использовать правила редуцирования. Остаётся только показать, что если P- неминимальна, то можно принять одно из Ленина Факультет "Вычислительной математики и кибернетики" правил редуцирования.

Подтверждение.

Пусть f – не константа, а  = (x1,….,xn). Из аксиомы 2 следует, что для  OBDD для f для каждой подфункции из Si содержит хотя бы одну xi-вершину. Если -минимальная   i Ленина Факультет "Вычислительной математики и кибернетики"  {1,…,n} P содержит > |Si| xi- вершин. Пусть k – максимум из таких i  в P  подфункция из S, j> k и  подфункция функции представляется в точности одной верхушкой. Т.к. существует более |Sk Ленина Факультет "Вычислительной математики и кибернетики"| xk-вершин) 

1) либо  xk-вершина u, вычисляющая g  Sk , т.е. g не находится в зависимости от xk .

2) либо  xk-вершин v и w, в каких рассчитывается одна и Ленина Факультет "Вычислительной математики и кибернетики" та же функция .

В случае

1) можно применить правило удаления для «u», т.к = .

2) сыновья v,w вычисляет и  применим правило склеивания.

Получаем противоречие.


Следствие : Для хоть какого п.ч.п.  редуцированная OBDD  б Ленина Факультет "Вычислительной математики и кибернетики".функции с п.ч.п.  определяется совершенно точно (с точностью до изоморфизма).

^ Лекция 11. Метод редукции.


Метод редукции
Мысль метода редукции ( = (x1,….,xn))

1. Перенумеруем все верхушки OBDD.

2. Для всех i:=n , n-1 , …1

2.1. Находим Vi – огромное Ленина Факультет "Вычислительной математики и кибернетики" количество xi- вершин.

2.2. Для всех v  Vi

2.2.1. Если id(0-сын(v))=id(1-сын(v)), то применяем к v правило удаления, в неприятном случае key(v) = (id(0-сын(v),1-сын (v))

2.3 Сортируем Ленина Факультет "Вычислительной математики и кибернетики" key(v) для Vi (key(vj) key(vj+1))

2.4 Для всех vj  V, j2

2.4.1 Если key(vj) = key(vj-1) , то удаляем vj-1 , переводя все входящие в неё дуги в vj





^ Главные конструкции Ленина Факультет "Вычислительной математики и кибернетики"
Если нам дана, к примеру, формула Б. функции  2 главных способа построения редуцированной OBDD

а) строим бинарное дерево решений

б) отождествляем финишные верхушки, имеющие схожие пометки

в) применяем метод редуцирования (недочет : большой размер)

2) Начинаем с Ленина Факультет "Вычислительной математики и кибернетики" корня :

а) определяем существенна ли переменная , если «да» строим верхушку с 2-мя отростками

б) для каждой новейшей верхушки определяем подфункции, т.е. пометку и новейшую верхушку (либо отождествляем с некий старенькой): (недочет: проверка Ленина Факультет "Вычислительной математики и кибернетики" существенности переменной и эквивалентности функций – сложны)

Пример :



=(1,2,3,4) :









;






Пусть   Б. операция: к примеру, конъюнкция либо дизъюнкция

=

Рекурсивная конструкция:

строим OBDD и для ( и ().

Вводим - верхушку, а-сын которой есть корень ,

Разложение f и g Ленина Факультет "Вычислительной математики и кибернетики" на подфункции связанно с необходимостью рассматривать 2n подфункций. Выходом является рекурсивная процедура с движением по узлам и . Каждому узлу новейшей ^ OBDD ставится в соотношение пара (f, g), где f, g – узлы и соответственно (пары Ленина Факультет "Вычислительной математики и кибернетики" образуют Table).


Метод:

Oper(F,G,) / вход: OBDD F и G для f и g с п.ч.п. бинарная операция/

/* выход: OBDD для f  g */

if (F и G – финишные Ленина Факультет "Вычислительной математики и кибернетики" верхушки)

then {Return (FG)}

else

if (F,G)  Table

then {Return (FG)}

else /*- 1-ая в  сущ-я для F либо G*/

{Строим новейшую - верхушку v

0-сын(v)=oper (

1-сын(v)=oper Ленина Факультет "Вычислительной математики и кибернетики" (

InsertTable(F,G,v)

Return(v)}


Приобретенные OBDD в общем случае не редуцированны.

Аксиома. Пусть f1 и f2 представлены OBDD и соответственно, тогда для хоть какой булевской операции  редуцированная OBDD Ленина Факультет "Вычислительной математики и кибернетики" P функции может быть построена за время порядка O(size(P1)size(P2).

Без подтверждения.


Аксиома. Пусть Б. функции представлены OBDD и соответственно, тогда тест на эквивалентность может быть выполнен за время O Ленина Факультет "Вычислительной математики и кибернетики"(size(P1)size(P2).


Для этого поначалу редуцируем и . Потом проверяется изоморфизм приобретенных OBDD (переход в глубину по обеим OBDD параллельно).


^ Лекция 12. Действенная реализация OBDD.

Хотя мы уже проявили, что ряд операций над OBDD Ленина Факультет "Вычислительной математики и кибернетики" могут быть выполнены отлично для практических приложений было нужно производить отлично по времени и памяти реализацию OBDD.


Главные идеи.


1) Центральной мыслью является представление отдельного узла OBDD с помощью трёх полей:

index Ленина Факультет "Вычислительной математики и кибернетики" (2 б) – индекс i переменной ,

2-поля (по 1-му слову) – ссылки на отпрыской узла.

Таким макаром количество переменных 65536. «Слово» позволит получать ссылку на адреса полного виртуального адресного места (при 32 – битной архитектуре слово = 4 б, а Ленина Факультет "Вычислительной математики и кибернетики" полное адресное место имеет размерность узлов.

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


2) Разделяемые (shared) OBDD.

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

Такое Ленина Факультет "Вычислительной математики и кибернетики" представление назовём разделяемые OBDD.


Пример:

, ,



В таких разделяемых OBDD можно достигнуть того, что любая подфункция представляется не пару раз, а только единожды. При всем этом представление OBDD будет не только лишь совершенным Ленина Факультет "Вычислительной математики и кибернетики", да и строго совершенным . При всем этом две эквивалентные функции f и g имеют не только лишь единую редуцированную OBDD, но при реализации соответствуют ссылке на один и тот же элемент памяти проверка на Ленина Факультет "Вычислительной математики и кибернетики" эквивалентность просит только одной операции сопоставления.


1 сверхбольшая печатная плата


lesnie-pozhari-v-sibiri-uzhe-derzhat-v-napryazhenii-vse-sluzhbi-internet-resurs-annewsru-26042011.html
lesnie-resursi-mineralno-sirevoj-kompleks-43-2-selskoe-hozyajstvo-44-3-ekonomika-64.html
lesnikov-v-rossii-budet-bolshe-informacionnoe-agentstvo-interfaks-14032012.html