If-диаграмма решений

  • 06 окт. 2011 г.
  • 1271 Слова
Министерство связи и информатизации Республики Беларусь
Учреждение образования
«ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ»
Факультет электросвязи

КУРСОВОЙ ПРОЕКТ
На тему «IF-диаграмма решений»
по дисциплине
«Компьютерные технологии и системы автоматизированного проектирования цифровых устройств»

Выполнил студент гр.:

Проверил: Д.И. Черемисинов

Минск 2010
содержаниеВВЕДЕНИЕ 2
1 ДИАГРАММА ДВОИЧНЫХ РЕШЕНИЙ 3
2 IF-ДИАГРАММА РЕШЕНИЙ – IFDD 4
2.1 Построение IFD 4
2.2 Представление некоторых логических операций IF-диаграммами 5
2.3 Переход от BDD к IFD 6
3 ПОВЕДЕНЧЕСКАЯ МОДЕЛЬ IFD 7
ЗАКЛЮЧЕНИЕ 9
ЛИТЕРАТУРА 10

введение

Булева алгебра появилась в XIX в., но и по сей день является востребованной. Большинство логиков того времени либо игнорировали,либо резко критиковали систему Буля, но ее возможности оказались настолько велики, что она не могла долго оставаться без внимания. Через некоторое время стало понятно, что система Буля хорошо подходит для описания электрических переключателей схем. Это первым из ученых осознал американский логик Чарлз Сандерс Пирс и применил теорию для описания электрических переключательных схем. Ток в цепи можетлибо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.
С ростом мощности персональных компьютеров, возрастает сложностьописания его схемы, его процессора. Это приводит к сложным булевым функциям. И возникает вопрос как удобней представить булеву функцию.
Существует несколько представлений булевой функции (например, дизъюнктивная нормальная форма и конъюнктивная нормальная форма, таблица истинности и др.). Но данные представления перестали удовлетворять выше изложенным требованиям в связи со сложностью самихбулевых функций.
Безусловно, самый эффективный метод представления булевой алгебры, известный до настоящего времени – это метод двоичных разрешающих диаграмм (BDD).

1 Диаграмма двоичных решений

В основе построения диаграммы двоичных решений (binary decision diagram - BDD) лежит разложение Шеннона булевой функции f(x1,…,xn) по переменной xi:

f(x) = xi & fxi=1 + ~xi & fxi=0,(1)

где ~, &, + - логические операции отрицания, конъюнкции и дизъюнкции соответственно; fxi=1, fxi=0 – остаточные функции (кофакторы) от функции f(x) по xi=1 и xi=0 соответственно. Базовый фрагмент BDD показан на рис. 1. Он включает вершину, помеченную переменной xi, из которой исходят две дуги. Левая дуга, помеченная значением 1, направлена в кофактор fxi=1, правая, помеченнаязначением 0, направлена в кофактор fxi=0. При xi=1 выполняется проход от корня к левому листу и f(x)=fxi=1, при xi=0 выполняется проход от корня к правому листу и f(x)=fxi=0.

Рис. 1 – Базовый фрагмент диаграммы двоичных решений.

BDD представляет собой корневой ациклический ориентированный граф, нетерминальные вершины которого помечены переменными, терминальные вершины (листья) помечены значениями0 и 1. Каждая нетерминальная вершина имеет ровно две исходящие дуги. Если известны значения переменных, то из вершин, помеченных этими переменными, и дуг, помеченных значениями переменных, формируется путь на графе, соединяющий корень с одним из листов. Корню соответствует функция, листу – значение функции на данном наборе значений переменных.
BDD назывется упорядоченной (OBDD), если всепути от корня к листьям сохраняют одинаковый порядок следования переменных.
Диаграмма называется сокращенной упорядоченной (ROBDD), если в ней нет двух одинаковых поддиаграмм и нет вершин, обе исходящие дуги которой были бы направлены в одну и ту же вершину.

2 If-диаграмма решений – IFDD

2.1 Построение IFD

В основе построения if-диаграммы решений...
tracking img