- •1. СТАНОВЛЕНИЕ ТЕОРИИ АВТОМАТОВ
- •1.1. Взаимосвязь теории автоматов и других
- •1.2. Подходы к определению конечного автомата
- •1.3. Сущность метода "черного ящика"
- •1.4. Основные задачи теории автоматов
- •2. ФОРМАЛЬНАЯ КЛАССИФИКАЦИЯ АБСТРАКТНЫХ АВТОМАТОВ И ИХ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
- •2.1. Словесные определения автоматов
- •2.2. Формальное определение абстрактного автомата
- •2.3. Формальная классификация автоматов
- •2.4. Математические модели автоматов
- •2.4.1. Модель Мили
- •2.4.2. Модель Мура
- •2.4.3. Модель совмещенного автомата (С-автомата)
- •2.4.4. Модель микропрограммного автомата
- •3. СТРУКТУРНЫЕ МОДЕЛИ ПЕРВОГО УРОВНЯ АБСТРАКТНЫХ АВТОМАТОВ
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3. Структурная модель С-автомата
- •3.4. Структурная модель микропрограммного автомата
- •4. СПОСОБЫ ЗАДАНИЯ АБСТРАКТНЫХ И СТРУКТУРНЫХ АВТОМАТОВ
- •4.1. Начальные языки
- •4.1.1. Язык регулярных выражений алгебры событий
- •4.1.2. Язык логических схем
- •4.1.3. Язык граф – схем алгоритмов
- •4.2. Автоматные языки
- •4.2.1. Таблицы переходов и выходов
- •4.2.2. Матрицы переходов и выходов
- •4.2.3. Граф автомата
- •4.3.2. Язык временных диаграмм
- •5. Минимизация абстрактных автоматов
- •6. МАТЕМАТИЧЕСКИЕ ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •6.1. Формальное определение алгебры логики
- •6.2. Аксиомы, теоремы и законы алгебры логики
- •6.2.1. Аксиомы алгебры логики
- •6.2.2. Теоремы алгебры логики
- •6.2.3. Законы алгебры логики
- •6.3. Основные понятия и определения
- •6.4. Формы представления логических функций
- •6.4.1. Словесная форма представления логических функций
- •6.4.2. Табличная форма представления логических функций
- •6.4.3. Аналитическая форма представления логических функций
- •7. Минимизация логических функций
- •7.1. Методы минимизации логических функций на основе прямых аналитических преобразований СДНФ
- •7.2. Метод испытания импликант
- •7.3. Визуальные методы минимизации логических функций
- •7.3.2. Метод минимизации частично определенных логических функций с помощью карт Карно
- •7.4. Машинно-ориентированные методы минимизации логических функций
- •7.5. Групповая минимизация системы логических функций
- •8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ
- •9. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ
- •9.1. Программируемые логические матрицы
- •10. КОНЕЧНЫЕ ФУНКЦИОНАЛЬНЫЕ ПРЕОБРАЗОВАТЕЛИ
- •11. СИНТЕЗ И АНАЛИЗ ТИПОВЫХ КОМБИНАЦИОННЫХ АВТОМАТОВ
- •11.1. Шифратор (coder) и его синтез
- •11.2. Дешифратор и его синтез
- •11.3. Мультиплексор и его синтез
- •11.4. Синтез демультиплексора (распределителя)
- •12. Элементарные автоматы с памятью и их синтез
- •12.1. Понятие функционально полной системы элементарных автоматов
- •12.2. Разновидности триггеров
- •12.3. Обобщённая характеристика триггеров
- •12.4. Синтез однотактного асинхронного RS-триггера
- •12.4.1. Синхронный однотактный RS-триггер
- •12.5. Синхронный однотактный D-триггер
- •12.6.1. Принцип построения двухтактного триггера
- •12.6.2. Однотактный Т-триггер
- •12.6.3. Двухтактные Т-триггеры
- •12.7. Двухтактный JK-триггер
- •12.8. Двухтактные RS-триггеры и D-триггеры
- •Рис. 12.28. Синхронный двухтактный RS-триггер
- •Рис. 12.30. УГО синхронного двухтактного RS-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
на введении такого понятия как цена схемы – Ц. Цену схемы можно рассчитать по следующей формуле:
n |
|
Ц = ∑K ji , |
(7.11) |
i, j =1
где K ji - количество входов у j-ого элемента, i-количество
элементов.
Оценим полученную минимизированную ДНФ логической функции (7.10) по формуле (7.11). Элементов “И” в выражении присутствует 5 (два элемента по 2 входа, три элемента по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 вх о- дов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:
Ц=2*2+3*3+1*5+4*1=22 входа
Затем оценим СДНФ функции R(a,b,c,d), воспользовавшись картой Карно (рис. 7.5). Потребуется элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:
Ц=11*4+1*11+4*1=59 входов
7.4. Машинно-ориентированные методы минимизации логических функций
Для минимизации логических функций, зависящих от большого числа переменных, применяют машинные методы минимизации. Самым распространенным методом является метод Квайна-Мак-Класки. Он базируется на кубическом представлении логических функций в сочетании с методом Квайна, однако, исходная логическая функция не требует обязательного представления ее в СДНФ. Достоинствами этого метода являются:
106
•использование числового представления логических функций и реализация алгоритма минимизации на ЭВМ;
•в этом методе практически отсутствуют ограничения на число логических переменных, от которых зависит минимизируемая функция.
Метод Квайна-Мак-Класки базируется на следующих основных этапах:
1.Нахождение простых импликант (из кубического представления функции).
2.Построение таблицы покрытий матрицы Квайна.
3.Отыскание минимального покрытия логической
функции.
4.Получение минимальной формы логической функ-
ции.
Более подробно этот материал изложен в [24], [25].
7.5.Групповая минимизация системы логических функций
Минимизация в широком смысле слова — такое преобразование логических выражений, которое упрощает их в смысле некоторого критерия. Целью минимизации одиночных логических функций является сокращение ранга и числа элементарных конъюнкций входящих в исходную ДНФ логической функции. В результате минимизации по таким критериям могут быть получены кратчайшие и/или минимальные тупиковые дизъюнктивные нормальные формы, обеспечивающие минимальную структурную сложность при реализации логической функции в элементных базисах И, ИЛИ, НЕ; И -НЕ; ИЛИНЕ и прочее.
Минимизация одиночных логических функций может быть осуществлена методом Квайна, методом Квайна – МакКласски, методами Закревского, а также с помощью карт Карно и т.п.
При минимизации системы логических функций, зависящих от одних и тех же логических аргументов, используют методы функциональной декомпозиции системы логических
107
функций. Суть такой минимизации заключается в представлении исходной системы логических функций в виде тождественной системы из функционально связанных логических функций, каждая из которых зависит от меньшего числа аргументов и одновременно является сложным аргументом для последующей логической функции. Такие методы минимизации очень сложны для ручной реализации и не всегда возможны.
При реализации системы логических функций наиболее эффективен метод группой минимизации, который легко реализуется и состоит в следующем: в системе логических уравнений отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы одинаковых элементарных конъюнкций вводится фиктивная переменная с каким-либо индексом (например, Z1, … ZS). Далее все исходные логические уравнения переписываются в терминах фиктивных переменных. Затем на логической схеме реализуют элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями, содержащими фиктивные переменные.
Рассмотрим метод групповой минимизации системы логических функций на примере.
Пусть система логических функций задана таблицей истинности (табл. 7.4).
Таблица 7.4
x |
y |
z |
f1 (x, y, z) |
f2 (x, y, z) |
f3 (x, y, z) |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
|
|
|
108 |
|
Представим систему логических функций в виде СДНФ
(7.12).
f1 |
СДНФ (x, y, z) = |
|
|
|
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x |
|
y |
|
z |
x |
|
yz + xyz + x yz |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
СДНФ (x, y, z) = x yz + x yz + xyz + xyz |
(7.12) |
|||||||||||||||||||||||||||
f2 |
||||||||||||||||||||||||||||
f3 |
СДНФ (x, y, z) = |
|
|
|
|
|
|
|
|
|
||||||||||||||||||
x |
yz + x yz + x yz |
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для каждой группы одинаковых элементарных конъюнкций вводим фиктивные переменные:
b1 = |
x |
|
y |
|
z |
|
b4 = x |
|
|
|
|||||||||
|
|
|
y |
|
z |
||||||||||||||
b2 |
= |
|
|
|
|
|
|
b5 |
= xyz |
||||||||||
x |
yz |
||||||||||||||||||
b3 |
= |
|
|
b6 |
= x |
|
|
||||||||||||
xyz |
yz |
Перепишем все исходные логические уравнения (7.12) в терминах фиктивных переменных, получим (7.13):
f СДНФ (x, y, z) = b |
+b |
+b |
+b |
|
|
1 |
1 |
2 |
3 |
4 |
|
f2 |
СДНФ (x, y, z) = b1 +b2 |
+b3 |
+b5 |
(7.13) |
|
f3 |
СДНФ (x, y, z) = b2 |
+b4 |
+b6 |
|
|
|
|
|
|
|
|
Реализуем элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями (7.13) на логической схеме (рис. 7.7):
109