Автор: Пользователь скрыл имя, 04 Марта 2013 в 13:55, курсовая работа
Потребность в вычислениях возникла у людей на самых ранних стадиях развития человеческого общества. Причем с самого начала для облегчения счета люди использовали различные приспособления. Многие из них были весьма интересными и остроумными по принципу действия, но все они обязательно требовали, чтобы в процессе вычислений активно участвовал человек-оператор. Качественно новый этап развития вычислительной техники наступил с изобретением и созданием электронных вычислительных машин, которые работают автоматически, без участия человека, в соответствии с заранее заданной программой.
Минимальные ДНФ и их цена по Квайну имеет вид:
ТДНФ1 |
= |
МДНФ1 |
|
ТДНФ2 |
= |
МДНФ2 |
|
ТДНФ3 |
= |
МДНФ3 |
|
ТДНФ4 |
= |
МДНФ4 |
|
ТДНФ5 |
= |
МДНФ5 |
|
ТДНФ6 |
= |
МДНФ6 |
|
ТДНФ7 |
= |
МДНФ7 |
|
ТДНФ8 |
= |
МДНФ8 |
|
ТДНФ9 |
= |
МДНФ9 |
|
ТДНФ10 |
= |
МДНФ10 |
|
ТДНФ11 |
= |
МДНФ11 |
|
ТДНФ12 |
= |
МДНФ12 |
|
СМДНФ1 = СМДНФ2 = СМДНФ3 = СМДНФ4 = СМДНФ5 = СМДНФ6 = СМДНФ7 = СМДНФ8 = СМДНФ9 = СМДНФ10 = СМДНФ11 = СМДНФ12 = 2*2+3*3=11
Найдем минимальную
K0= |
||||||
0 |
0 |
0 |
0 |
0 |
0 |
x |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
0 |
0 |
0 |
1 |
1 |
0 |
7 |
0 |
0 |
1 |
1 |
1 |
x |
9 |
0 |
1 |
0 |
0 |
1 |
0 |
11 |
0 |
1 |
0 |
1 |
1 |
0 |
13 |
0 |
1 |
1 |
0 |
1 |
0 |
14 |
0 |
1 |
1 |
1 |
0 |
x |
15 |
0 |
1 |
1 |
1 |
1 |
x |
16 |
1 |
0 |
0 |
0 |
0 |
x |
17 |
1 |
0 |
0 |
0 |
1 |
x |
22 |
1 |
0 |
1 |
1 |
0 |
0 |
25 |
1 |
1 |
0 |
0 |
1 |
0 |
26 |
1 |
1 |
0 |
1 |
0 |
0 |
27 |
1 |
1 |
0 |
1 |
1 |
0 |
28 |
1 |
1 |
1 |
0 |
0 |
x |
29 |
1 |
1 |
1 |
0 |
1 |
x |
30 |
1 |
1 |
1 |
1 |
0 |
x |
31 |
1 |
1 |
1 |
1 |
1 |
x |
Находим сокращенную КНФ.
K'0= |
K'1= |
K'2= |
K'3= |
K'4= |
Æ | ||||
~ |
00000 |
000x0 |
0xx11 |
x1xx1 |
|||||
00010 |
x0000 |
x1x01 |
|||||||
~ |
10000 |
0001x |
x10x1 |
||||||
00011 |
1000x |
x1x11 |
|||||||
01001 |
0x011 |
x11x1 |
|||||||
~ |
10001 |
00x11 |
11xx1 |
||||||
01011 |
01x01 |
11x1x |
|||||||
01101 |
x1001 |
x111x |
|||||||
10110 |
1x001 |
111xx |
|||||||
11001 |
x1011 |
||||||||
11010 |
x1101 |
||||||||
~ |
00111 |
011x1 |
|||||||
~ |
01110 |
1x110 |
|||||||
~ |
11100 |
11x01 |
|||||||
11011 |
110x1 |
||||||||
~ |
01111 |
11x10 |
|||||||
~ |
11101 |
1101x |
|||||||
~ |
11110 |
0x111 |
|||||||
~ |
11111 |
x1110 |
|||||||
0111x |
|||||||||
1110x |
|||||||||
111x0 |
|||||||||
11x11 |
|||||||||
x1111 |
|||||||||
111x1 |
|||||||||
1111x |
Строим таблицу покрытия (см. таблица 5) и определяем ядро булевой функции.
Таблица 5
00010 |
00011 |
01001 |
01011 |
01101 |
10110 |
11001 |
11010 |
11011 |
||
x1xx1 |
~ |
~ |
~ |
~ |
~ |
A | ||||
0xx11 |
~ |
~ |
B | |||||||
11xx1 |
~ |
~ |
C | |||||||
11x1x |
~ |
~ |
D | |||||||
x111x |
E | |||||||||
111xx |
F | |||||||||
x1x01 |
~ |
~ |
~ |
G | ||||||
x10x1 |
~ |
~ |
~ |
~ |
H | |||||
x1x11 |
~ |
~ |
I | |||||||
x11x1 |
~ |
J | ||||||||
B |
D |
Строим сокращенную таблицу покрытия (см. таблица 6)
00010 |
00011 |
10110 |
11010 |
||
0xx11 |
~ |
B | |||
11x1x |
~ |
D | |||
B |
D |
Существует единственная экстремаль – х1хх1. Из сокращенной таблицы покрытий, включающей 3,4,5, 7, 9 столбцы и 1, 3, 4-9 строки, следует, что существует одно тупиковое покрытие:
ТКНФ1 |
= |
x1xx1 |
0xx11 | ||
11x1x |
Минимальные КНФ и их цена по Квайну имеет вид:
ТКНФ1
|
=
|
|
СМКНФ1 = 2*1+3*2=8
Карты Карно - это специальным образом организованные таблицы соответствия: столбцы и строки таблицы соответствуют всевозможным наборам не более двух переменных, причем эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных. Благодаря этому соседние по вертикали и горизонтали клетки отличаются только одной переменной. Клетки, расположенные симметрично по краям таблицы также считаются соседними и отличаются одной переменной.
Для ДНФ клетки наборов, на которых функция принимает значение «1» заполняются «1». Нулевые клетки не заполняются. Для КНФ клетки наборов, на которых функция принимает значение «0» заполняются «0». Единичные клетки не заполняются.
Аналогично n-мерному кубу, совокупности двух соседних клеток соответствует 1-куб, 4-х соседних клеток - 2-куб т.д.
Считывание минтермов осуществляется по следующему правилу: клетки, образующие S-куб дают минтерм (n-s)-го ранга, в который входят те (n-s) переменных, которые сохраняют одинаковые значения на этом s-кубе. Для ДНФ значению «1» соответствуют прямые значения переменных, значению «0» - их отрицания. Для КНФ значению «0» соответствуют прямые значения переменных, значению «1» - их отрицания. Переменные, не сохраняющие свои значения на s-кубе, в минтерм (макстерм для КНФ) не входят.
Задача минимизации с помощью карт Карно формулируется аналогично задаче минимизации на n-мерном кубе. Данный алгоритм минимизации дает МДНФ для значений функции «1» или МКНФ для значений функции «0».
Использование карт Карно требует более простых построений (наглядных), особенно в случае функций от 4-х переменных, в сравнении с отображением на n-мерном кубе. Для отображения функций 5-ти переменных используются две карты Карно от 4-х переменных, для функций 6-ти переменных используются четыре карты Карно:
При n³5 наглядность карт Карно теряется. Карты Закревского позволяют сохранить наглядность табличного метода при n£8.
Получим МДНФ булевой функции методом карт Карно. Заполняем карты Карно для заданной функции из пяти переменных, что отображают значения Х5 (таблицы 7 и 8).
Исходя из карт Карно получаем:
Получим МКНФ булевой функции методом карт Карно. Заполняем карты Карно для заданной функции из пяти переменных, что отображают значения Х5 (таблицы 9 и 10).
Исходя из карт Карно получаем:
Для реализации выбираем МДНФ и подаем ее в заданном элементном базисе ИЛИ-НЕ.
Для реализации этой функции по приведенному выражению необходимо использовать один логических элемент 2И, два логический элемента 3И, один логических элемент 4И, один логический элемент 4ИЛИ-НЕ.
Представлению функции в виде ДНФ соответствует двухуровневая КС (если считать, что на ее вход могут поступать как прямые так и инверсные входные сигналы), на первом уровне которой элементы И , а их выходы объединяются на втором уровне элементом ИЛИ . Такое построение КС обеспечивает ее максимальное быстродействие, так как ранг схемы минимален. Однако, не всегда возможно на первом уровне и, особенно, на втором выбрать логические элементы с требуемым , т.к. может оказаться, что ЛЭ с таким не выпускаются промышленностью. В этом случае необходимо с помощью нескольких элементов с меньшим получить эквивалент с большим либо, что предпочтительней, преобразовать БФ, перейдя от ДНФ к скобочной форме. Этот переход сопровождается уменьшением логических элементов, требуемого для построения схемы. Осуществить такой переход можно с помощью факторного алгоритма, суть которого рассмотрим на примере.
Выбранную булева функция в виде:
С помощью факторного алгоритма получим скобочную форму для заданной функции. Для этого обозначим все конъюнкции буквами:
и будем рассматривать их как некоторые множества. Находим попарное пересечения множеств:
Полученные пересечения показывают общие части отдельных конъюнкций. Выбираем пересечение, которое имеет наибольшую длину (если такое отсутствует, то выбирают то, которое чаще всего встречается). В данном случае это . Поэтому из конъюнкций А и В и С выносим общую часть . Тогда имеем: