 |
Минимизация комбинационных логических схем на вентилях
|
|
|
|
Процедура минимизации при проектировании цифровых устройств ставит своей целью упрощение конкретной схемотехнической реализации логического автомата. Для элементной базы логических вентилей более простая переключательная функция автомата однозначно соответствует более простой схемотехнической реализации автомата. Известно несколько методов минимизации автоматов, ориентированных на различный элементный базис: метод склеивания-поглощения, метод построения карт Карно и диаграмм Вейча, скобочные преобразования переключательных функций, метод Квайна-Маккласки и другие.
Рассмотрим минимизацию комбинационных логических схем при помощи скобочных преобразований переключательных функций автомата.
Пример 1. Пусть алгоритм функционирования устройства задан в виде следующей таблицы состояний:
Таблица 6.8.
Алгоритм функционирования устройства
| Х1 | Х2 | Х3 | Y |
1. Выделим в таблице состояний те комбинации входных переменных, при которых входная функция принимает значение, равное логической единице.
2. Для каждой такой строки составим конъюнкцию всех входных переменных.
3. Запишем дизъюнкцию всех найденных конъюнкций:
; (6.19)
; (6.20)
. (6.21)
Можно записать переключательную функцию этого логического автомата, которая в этом случае будет иметь совершенную нормальную дизъюнктивную форму (СНДФ). Сразу же проводим скобочные преобразования этой функции для ее упрощения:
(6.22)
Совершенная нормальная дизъюнктивная форма (СНДФ) переключательной функции – есть функция, в каждую конъюнкцию которой входят все входные переменные со своим прямым или инверсным значением.
|
|
|
Пример 2. Рассмотрим еще один пример минимизации произвольной переключательной функции путем ее скобочных преобразований:
(6.23)
Как видно, результирующее выражение явно проще исходного, поэтому и схемотехническая реализация будет проще, для нее потребуется меньшее число логических вентилей.
6.7.1. Минимизация с помощью карт Карно
Карта Карно – это преобразованная форма таблицы состояний, представляющая собой прямоугольник, в частном случае – квадрат, по строкам и колонкам которого располагают все возможные двоичные комбинации входных переменных, а на пересечении соответствующей строки и колонки указывают значение выходной функции для данной комбинации.
6.7.1.
6.7.2. Правила построения карт Карно
1. Карта заполняется так, чтобы каждая ячейка отличалась от соседней только на одну переменную.
2. Карта может составляться только для одной выходной функции.
3. Число входных переменных не должно превышать четырех – шести, иначе карты Карно также становятся громоздким.
В примере, приведенном ниже, показано для сравнения заполнение таблицы состояний и карты Карно для одного и того же вентиля «И».
Таблица 6.9.
Таблица состояний для вентиля «И»
| Х1 | Х2 | Y |
Таблица 6.10.
Карта Карно для вентиля «И»
| Х1 Х2 | ||
6.7.3. Основные операции при минимизации с
помощью карт Карно
Для минимизации в заполненной карте Карно выделяются контуры, захватывающие единичные квадраты (ячейки).
При проведении контуров придерживаются следующих правил:
1. Контур должен быть прямоугольным.
2. Внутри контура должны быть только ячейки, заполненные единицами (либо только нулями).
3. Число ячеек внутри контура должно быть равно целой степени числа 2 (2, 4, 8 и т. д.).
4. Одни и те же ячейки могут входить в несколько контуров.
5. Самая нижняя и самая верхняя строки карты считаются соседними, то же самое с левым и правым столбцами, т. е. карта Карно в пространстве представляет собой тороидальную поверхность.
|
|
|
6. Число контуров должно быть наименьшим, а сами контуры – как можно большими.
Минитерм – простая конъюнкция, в которую входят все аргументы логической функции.
У логической функции, записанной в карте Карно, представленной ниже, имеется два минитерма – К1 и К2:
Таблица 6.11.
Карта Карно для примера 2
| X1X2 Х3Х4 | 0 0 | 0 1 | 1 0 | 1 1 |
| 0 0 | K1 “1” | K2 “1” | ||
| 0 1 | ||||
| 1 0 | ||||
| 1 1 |
К1: 
; (6.24)
К2: 
. (6.25)
Запишем результирующую переключательную функцию в ее совершенной нормальной дизъюнктивной форме (СНДФ):
. (6.26)
Общие правила упрощения логических функций с помощью карт Карно:
Если в двух, четырех, восьми и т. д. ячейках карты Карно, ограниченных прямоугольным или квадратным контуром, стоят только логические единицы, то можно записывать непосредственно логическое произведение для всей этой группы, причем в это произведение должны входить лишь те переменные, которые остаются неизменными для всех ячеек данной группы.
Пример 3. Для переключательной функции, записанной в своей СНДФ, из карты Карно, приведенной выше, путем скобочных преобразований было получено ее минимизированное выражение (1). Однако, этот же результат можно получить сразу, выделяя единственный контур в карте и записывая для него выражение:
. (6.27)
Пример 4. Минимизация функций двух переменных. Возьмем ту же переключательную функцию, которая использовалась в примере 2, и запишем ее минимизированное выражение, полученное в примере 2:
. (6.28)
Получим то же самое с помощью карты Карно. В заполненной карте Карно выделим контуры (их число минимальное – 2 и они максимально большие). Минимизированную функцию можно записать сразу:
. (6.29)
Таблица 6.12.
Карта Карно для примера 4
| Х1 Х2 | ||
Пример 5. Минимизация функций трех переменных. Пусть задана следующая переключательная функция:
. (6.30)
Теперь можно заполнить карту Карно функции:
|
|
|
Таблица 6.13.
Карта Карно для примера 5
| ВС А | 0 0 | 0 1 | 1 0 | 1 1 |
Выделив в карте Карно два контура, записываем минимизированное выражение для переключательной функции:
. (6.31)
Пример 6. Минимизация логической функции четырех переменных.
Пусть переключательная функция задана в виде следующей своей таблицы состояний:
Таблица 6.14.
Таблица состояний логической
функции четырех переменных
| Х1 | Х2 | Х3 | Х4 | Y |
Заполняем карту Карно функции, причем меняем привычными местами колонки для Х1Х2: 11 и 10. Согласно правилам построения карты Карно это возможно одновременно, в данном случае это позволит выделить большой контур К4, объединив все угловые клетки.
Таблица 6.15.
Карта Карно функции четырёх переменных для примера 6
| Х1Х2 Х3Х4 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 0 1 1 0 1 1 |
Для четырех выделенных контуров записываем минимизированное выражение переключательной функции:
(6.32)
Примечание. Если при минимизации в карте Карно нулей в ячейках карты больше, чем единиц, то целесообразно группировать нули, если они расположены удобней, большими группами. В этом случае выходная функция получается с инверсным значением и для ее окончательной реализации достаточно включить инвертор на выходе логической схемы.
Кроме рассмотренных методов минимизации известен также метод Квайна-Маккласски. Он применяется чаще всего при автоматизированной машинной минимизации переключательных функций.
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.
6.7.
|
|
|
