- •Описание фал в виде последовательности десятичных или двоичных чисел. Описание фал в виде кубических комплексов
- •Теорема поглощения и теорема склеивания – основные теоремы минимизации фал
- •3. Минимизация фал методом Квайна.
- •4 Минимизация фал методом кубических форм.
- •Минимизация фал методом карт Карно (Вейча)
- •4.Пример для четырех переменных
Лекция №6
Минимизация комбинационных логических устройств
Описание ФАЛ в виде последовательности десятичных или двоичных чисел. Описание ФАЛ в виде кубических комплексов
Теорема поглощения и теорема склеивания – основные теоремы минимизации ФАЛ
Минимизация ФАЛ методом Квайна
Минимизация ФАЛ методом кубических форм
Минимизация ФАЛ методом карт Карно (Вейча)
Описание фал в виде последовательности десятичных или двоичных чисел. Описание фал в виде кубических комплексов
ФАЛ КЛС.
ФАЛ, выраженные в СДНФ и СКНФ, описывают алгоритм работы КЛС, которые могут быть созданы на любой базисной комбинации элементарных логических элементов.
Как правило, КЛС, созданные с использованием СДНФ и СКНФ, обладают аппаратной избыточностью.
Поэтому при проектировании КЛС с целью минимизации (упрощения) логических функций используют методов:
А) метод Квайна;
Б) метод кубических форм;
В) метод карт Карно (картВейча) ;
Г) метод Мак-Класки - специальный алгоритмически метод минимизации на ЭВМ.
Способы описания ФАЛ:
а) словесное описание;
Таблица 1 |
|||
X2 |
X1 |
X0 |
y |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
в) в виде алгебраического выражения:
ДНФ, КНФ, СДНФ,СКНФ;
г) описание в виде последовательности
десятичных или двоичных чисел:
y(x3,x2,x1,x0)=Σ(4,5,6,9)=V(4,5,6,9)=
V(0100,0101,0110,1001);
y=(x3,x2,x1,x0)=П(2,3,7,5)=∩(2,3,7,5);
д) представление в виде кубических комплексов:
0-кубы (нулевые кубы) |
1-кубы (единичные кубы) |
2-кубы (двоичные кубы) |
y(x2,x1,x0)= Σ(3,4,5,6,7)=V(011,100,101,110,111);
Кубы, отличающиеся только одной переменной, называются соседними.
Ранг куба определяется числом несовпадающих переменных координат – числом прочерков.
1.4 Нулевой кубический комплекс K0 - множество “0”кубов:
К0= Σ(011,100,101,110,111)
1.5 Единичный кубический комплекс К1- множество единичных кубов:
К1= Σ(-11,10-,1-0,11-,1-1):
1.6 Двоичный кубический комплекс К2- множество двоичных кубов:
К2= Σ(1- -)
1.7. Кубический комплекс К(Z) образуется сложением кубических комплексов К0,К1,…,Кn-1
Кубический комплекс К(Z) для нашего примера:
K(Z)=(011,100,101,110,111,-11,11-,1-1,10-,1-0,1- -)
1.8 Покрытием П(Z) называют подмножество кубов из комплекса К(Z) разных рангов.
1.9 Цена любого n-куба ранга r, входящего в П(Z),равна:
Цk=(n-r)k
n-число переменных куба; r-ранг куба.
1.10 Цена покрытия П(Z) равна:
Теорема поглощения и теорема склеивания – основные теоремы минимизации фал
2.1.Теорема поглощения:
(x0x1+x1)=(x0+1)x1=x1; (KX0+K)=K,
(x1+x0)x1=x1x1+x0x1=x1x0+x1=x1; (K+X0)K=K.
2.2. Теорема склеивания:
; ;
; ,
Действительно:
3. Минимизация фал методом Квайна.
3.1 Минимизируемая функция представляется в СДНФ и к ней применяются все возможные операции неполного склеивания:
1)
а затем поглощения:
2) K+KX0=K(1+ X0)=K, где
3.2 Эта пара операций может применяться многократно:
y= (x2,x1,x0)= Σ(3,4,5,6,7)=V(011,100,101,110,111)
+ + ;