До сих пор мы находили решения проблем логической редукции на основе Суммы-Произведений (СуП). Для каждого из этих решений СуП также существует эквивалентное решение на основе Произведения-Сумм (ПрС), которое может оказаться более полезным в зависимости от нюансов решаемой задачи.
Перед тем, как приступить к работе над решением в духе «произведение сумм», нужно ввести новую терминологию. Приведённая ниже процедура сопоставления членов Произведения-Сумм не нова для этой главы.
Сейчас требуется просто задать формальную процедуру, определяющую минтерм, чтобы затем перейти к новой процедуре, определяющей макстерм.
Рис. 1. Функция от произведения трёх переменных (или их дополнений) является сама себе минтермом.
Минтерм
Минтерм – это логическое выражение, выход которого будет равен 1 для какой-то одной ячейки, и 0 для всех остальных ячеек, если данную функцию представить в виде карты Карно или таблицы истинности. Если минтерм имеет одну единицу, то остальные ячейки заполняются нулями, количество единиц в ячейках таким образом будет минимально возможным.
В левой части рисунка 1 выше показан минтерм ABC, это единственный член выходной логической функции, на карте Карно представлен как единичная единица в одной из ячеек, в остальных случаях ячейки заполнены нулями. Ранее мы не проставляли нули на наших картах Карно, так как их принято опускать, если в них нет особой необходимости (но при этом всегда подразумевалось, что пустые ячейки заполнены именно нулями). Ещё один минтерм A'BC' показан в правой части рисунка 1 выше.
Важно отметить, что адрес ячейки напрямую соответствует отображаемому минтерму. То есть ячейка 111 соответствует минтерму ABC в левой части рисунка 1 выше.
В правой части рисунка 1 выше видим, что минтерм A'BC' соответствует непосредственно ячейке 010. У логического выражения или карты может быть несколько минтермов.
Ссылаясь на приведённый выше рисунок 1, давайте подытожим процедуру размещения минтерма на K-карте:
Определяем минтерм (член логического выражения, содержащего все переменные или их дополнения), который необходимо сопоставить.
Записываем соответствующее минтерму двоичное числовое значение.
Используем двоичное значение в качестве адреса, чтобы проставить 1 на K-карте.
Повторяем шаги для остальных минтермов (членов в Сумме-Произведений).
Рис. 2. Логическое выражение содержит два минтерма, отображаем их на карте Карно.
Логическое выражение чаще всего состоит из нескольких минтермов, соответствующих нескольким ячейкам на карте Карно, как показано на рисунке 2 выше. В данном случае это те минтермы, которые мы рассмотрели по-отдельности на предыдущем рисунке 1.
Для справки мы рассмотрим тот факт, что двоичные адреса ячеек с единицами на K-карте преобразуются непосредственно в члены Суммы-Произведений.
Под «непосредственно» подразумевается, что 0 соответствует дополнению к переменной, а 1 соответствует прямому значению переменной. Пример: 010 преобразуется напрямую в A'BC'.
В этом примере не было упрощения. Тем не менее, получен результат в виде Суммы-Произведений из минтермов.
С учётом приведённого рисунка 2 выше, подытожим процедуру написания сокращённого логического уравнения для Суммы-Произведений на основе K-карты:
Формируем самые большие группы из единиц, охватывающие все минтермы. Количества ячеек в группах должны быть степенями двойки, формы групп - прямоугольниками.
Записываем двоичное числовое значение для каждой группы.
Преобразовываем двоичное значение в член Суммы-Произведений.
Повторяем шаги для всех групп. Каждая группа даёт член Суммы-Произведений.
Пока ничего особенного, тут прописан формальный порядок работы с минтермами. Это послужит образцом для работы с макстермами.
А сейчас мы кавалерийским наскоком разберёмся с логической функцией, которая равна 0 в одной из ячеек на карте Карно и 1 во всех остальных ячейках.
Рис. 3. Функция от суммы трёх переменных (или их дополнений) является сама себе макстермом.
Макстерм
Макстерм – это логическое выражение, выход которого будет равен 0 для какой-то одной ячейки, и 1 для всех остальных ячеек, если данную функцию представить в виде карты Карно или таблицы истинности. На рисунке 3 выше показан макстерм (A + B + C), являющийся единственным членом в Произведении-Сумм, отображённый как 0 на карте Карно, все остальные ячейки заполнены единицами.
Раз макстерм имеет единственный 0 на карте Карно, а все оставшиеся ячейки заполнены единицы, он, по всей видимости, покрывает максимальную область единицами.
Это то, чем схожи минтерм и макстерм, а теперь рассмотрим то, что делает макстерм особенным. На карте Карно макстерм равен 0, а не 1. Макстерм – это логическая сумма, (A + B + C) в нашем примере, а не логическое произведение. Также выглядит странным, что (A + B + C) отображается в ячейку с адресом 000.
Для уравнения Вых. = (A + B + C) = 0 все три переменные (A, B, C) по отдельности должны быть равны 0. Только (0 + 0 + 0) будет равно 0. Таким образом, мы помещаем наш единственный 0 для макстерма (A + B + C) в ячейку A, B, C = 000 на K-карте, где все входы равны 0.
Это единственный случай, который даст нам 0 для нашего макстерма. Все остальные ячейки содержат единицы, потому что любые входные значения, отличные от (0, 0, 0) для (A + B + C), дают 1.
С учётом приведённого рисунка 3 выше, процедура размещения макстерма на K-карте следующая:
Определяем суммирующий член, который нужно сопоставить с картой Карно.
Запишем соответствующее двоичное числовое значение для этого члена.
Сформируем дополнение для этого двоичного значения.
Используем дополнение в качестве адреса ячейки, в которую ставим 0 на K-карте.
Повторяем эти действия для других макстермов (суммирующих множителей в Произведении-Сумм).
Рис. 4. В данном случае Произведение-Сумм состоит из одного множителя, являющегося макстермом.
Другой макстерм (A' + B' + C') показан на рисунке 4 выше, ему соответствует число 000. Дополнение к этому числу – 111. Помещаем 0 для макстерма (A' + B' + C') в ячейку с адресом (1, 1, 1) на K-карте, как показано на рисунке 4 выше.
Почему (A' + B' + C') помещает 0 именно в ячейку с адресом 111? Когда (A' + B' + C') равно (1' + 1'+ 1'), инвертирование всех единиц даёт (0 + 0 + 0), что соответствует единственному условие, при котором данное выражение даст 0. Все единицы дополняются до нулей, что в итоге даёт 0 для функции ИЛИ.
Рис. 5. Логическое выражения с двумя макстермами.
Выражение или карта логического Произведения-Сумм может иметь более одного макстерма, как показано на рисунке 5 выше. Макстерм (А + В + С) дает число 111, которая дополняется до 000, в результате чего 0 для этого макстерма следует поместить в ячейку (0, 0, 0). Макстерм (А + В + С') даёт числовое значение 110, которое дополняется до 001, в результате чего 0 для этого макстерма следует поместить в ячейку (0, 0, 1).
Теперь, когда у нас есть настроенная К-карта, нас теперь заботит, как написать упрощённое Произведения-Сумм. Сгруппируем нули. В данном случае это будет единая группа из двух нулей. Запишем двоичное значение, соответствующее сумме-члену, равному (0, 0, ×).
И A, и B равны 0 для всех ячеек этой группы. Но, C одновременно принимает и 0, и 1. Поэтому мы пишем «×» в качестве держателя места для переменной C. Сформируем дополнение (1, 1, ×). Напишем сумму-член (A + B), отбрасывая C и ×, которые занимали свои позиции в записи.
В общем, «произведение сумм» будет давать больше сумм. Хотя здесь у нас достаточно простой пример.
Рис. 6. Упрощение Произведения-Сумм с помощью макстермов.
Резюмируем порядок действий для написания логической редукции Произведения-Сумм на K-карте:
Формируем как можно бо́льшие группы из нулей, охватывающих все макстермы. Количества ячеек в группах должны быть степенями двойки, формы групп - прямоугольниками.
Записываем двоичное числовое значение для группы.
Дополняем двоичное числовое значение для группы.
Преобразуйте значение дополнения в множитель упрощённого Произведения-Сумм.
Повторяем шаги для всех групп. Каждая группа даёт сумму, являющуюся сомножителем в упрощённом Произведении-Сумм.
Примеры
Пример 1: Упростим приведённое на рисунке 7 ниже логическое выражение Произведения-Сумм, предоставив результат в виде ПрС.
Рис. 7. Это выражение нужно упростить до ПрС, разобрав его на макстермы.
Решение: Перенесём семь макстермов на карту Карно в виде нулей (рисунок 8 ниже). Не забываем сформировать дополнения для входных переменных при определении правильного местоположения ячейки.
Рис. 8. Каждый макстерм представляем в виде нуля на карте Карно.
Тут нули сопоставлены так, что они отображаются слева-направо сверху-вниз на карте. Для трёх последних макстермов приведены линии выноски, указывающие ячейки с нулями для этих макстермов.
После того, как нули размещены в соответствующих ячейках, группируем их, как показано на рисунке 9 ниже. Как помните, группы большего размера дадут сумму с меньшим количеством входов. Меньшее количество групп приведёт к меньшему количеству сумм в результате.
Рис. 9. Оптимально распределяем нули по трём группам.
У нас есть три группы, поэтому мы ожидаем, что в нашем ПрС-результате выше будет три суммы-члена для итогового Произведения-Сумм. Группа из 4-х ячеек даёт сумму с двумя переменными. Две группы по 2 ячейки дают нам две суммы с тремя переменными.
На рисунке 9 выше подробно показано, как мы получили эти суммы. Для каждой группы записан двоичный адрес входа, для которого находится дополнение, в результате чего оно преобразуется в член логический суммы. Конечный результат – произведение трёх сумм.
Пример 2: Упростим приведённое на рисунке 7 ниже логическое выражение произведения сумм, предоставив результат в виде СуП.
Рис. 10. Это выражение нужно упростить до СуП, разобрав его на макстермы.
Решение: в целом, действуем аналогично предыдущему примеру. За исключением того, что в итоге формируем Сумму-Произведений, а не Произведение-Суммы. На карте Карно проставляем нули для макстермов, как показано в левой части рисунка 11 ниже.
Рис. 11. Для макстермов проставляем нули (слева), оставшиеся пустые клетки заполняем единицами (справа).
Затем заполняем единицами пустые ячейки. В предыдущем примере в пустых ячейках тоже подразумевались единицы, просто в том случае их показывать не было надобности.
Рис. 12. Так как нам в итоге нужно СуП, а не ПрС, группируем единицы, а не нули.
Формируйте группы из единиц так, чтобы охватить их все. Затем записываем упрощённый результат в виде Суммы-Произведений, как в предыдущем разделе этой главы. Кстати, текущий случай идентичен как примеру 1 выше, так и случаю, приведённому на рисунке 9 в предыдущем разделе.
Рис. 13. Сравнение результатов для примера 1 и примера 2. Хотя в одном случае это ПрС, а в другом СуП, эти решения эквивалентны, поскольку входные условия те же самые.
На рисунке 13 выше для сравнения показано решение «Произведение-Сумм» из предыдущего примера и решение «Сумма-Произведений» из текущей задачи.
Какое решение проще? ПрС использует 3 вентиля ИЛИ и 1 вентиль И, в то время как СуП использует 3 вентиля И и 1 вентиль ИЛИ. Таким образом и там и там по четыре вентиля.
Присмотревшись, посчитаем количество входов в вентилях. ПрС использует 8 входов; СуП использует 7 входов. По определению решения с минимальной стоимостью решение СуП проще.
Это технически правильный ответ, но в реальном мире решения принимается исходя из других соображений.
Лучшее решение зависит от сложности и используемого семейства логических схем. СуП обычно лучше для ТТЛ-логики, поскольку вентили И-НЕ являются основным строительным блоком, хорошо работающим с реализациями СуП.
С другой стороны, ПрС предпочтителен для КМОП-логики, поскольку будет доступен широкий выбор вентилей ИЛИ-НЕ всех размеров.
Рис. 14. Реализации обоих решений.
Вентильные схемы для обоих случаев показаны на рисунке 14 выше: Произведение-Сумм (ПрС) слева и Сумма-Произведений (СуП) справа.
Версию справа, являющейся примером Суммы-Произведений рассмотрим более подробно:
Рис. 15. В Сумме-Произведений заменим И на И-НЕ, ИЛИ на ИЛИ-НЕ.
Прежде всего, логические элементы И заменим на И-НЕ, а логические элементы ИЛИ на выходе заменены логическим элементом И-НЕ. Чтобы доказать эквивалентность замены, передвинем инвертирующие пузырьки с выходов 3-х вентилей И-НЕ на вход конечной И-НЕ:
Рис. 16. Косметические преобразования над правой частью предыдущего рисунка 15: пузырьки инверторов с выхода трёх начальных И-НЕ смещены на вход конечного И-НЕ.
В правой части рисунка 16 выше видим, что выходной элемент И-НЕ с инвертированными входами логически эквивалентен элементу ИЛИ согласно закону де Моргана и двойному отрицанию.
Этот трюк полезен при построении цифровой логики в лабораторных условиях, так как логические элементы И-НЕ семейства ТТЛ более доступны в самых разных конфигурациях, чем другие типы вентилей.
Процедура построения логики И-НЕ/И-НЕ вместо логики И/ИЛИ следующая:
При отрисовке монтажной схемы СуП замените все вентили (как И, так и ИЛИ) на вентили И-НЕ.
Неиспользуемые входы свяжите с «высоким» логическим уровнем.
В случае устранения неполадок внутренние узлы на первом уровне выходов вентилей И-НЕ не соответствуют логическим уровням схемы И-ИЛИ, а инвертируются. Используйте логическую схему И-НЕ/И-НЕ. Ведь входы и конечный результат будут идентичны.
Обозначьте корпуса как U1, U2 и т.д.
Присвойте упорядоченные номера входным и выходным контактам всех вентилей.
Пример 3: Вернёмся к задаче из прошлой лекции (см. в ней рисунок 8), связанной с минимизацией СуП. Создадим решение на основе ПрС. Сравните новое решение с предыдущим.
Рис. 17. См. рисунок 8 предыдущего раздела. Решаем на этот раз с помощью ПрС.
Решение: На рисунке 17 вверху слева видим исходную задачу, начинающуюся с 9-членного логического неупрощённого выражения. В прошлый раз мы сформировали четыре группы по 4 ячейки, получить итоговый СуП с 4-мя произведениями, см. нижнюю левую часть рисунка 17.
В средней части рисунка 17 выше заполняем пустые места подразумеваемыми нулями. Единицы сотрём, чтобы было более наглядно (но предполагается, что эти единицы остаются в этих клетках). Нули образуют две 4-ячеечные группы. Группа, окаймлённая сплошной синей линией – это (A' + B), а отмеченная красным пунктиром – это (C' + D). Это даёт две суммы, являющихся сомножителями в Произведении-Сумм. В правой части рисунка 17 выше записываем результат: Вых. = (A' + B)(C' + D).
Если сравнить предыдущее упрощение СуП (левая часть рисунка 17) и упрощение ПрС (правая часть рисунка 17), то видно, что Произведение-Сумм является менее затратным решением. СуП использует всего 5 вентилей, а ПрС только 3.
Это ПрС-решение даже при использовании ТТЛ-логики выглядит привлекательнее ввиду своей простоты. Потребуются вентили И и ИЛИ с двумя входами, а не с четырьмя как в СуП.
Рис. 18. Для решения в духе ПрС потребуются более простые компоненты и в меньшем количестве, чем в случае СуП.
Вентильные схемы и СуП и ПрС показаны на рисунке 18 выше для сравнения.
С учётом схемы расположения для логических вентилей интегральных схем семейства ТТЛ на рисунке 19 ниже, разметим диаграмму макстерма с правой части рисунка 18 выше обозначениями цепей (U1-a, U1-b, U2-a и т.д.) и номерами контактов.
Рис. 19. Реализуем вентильную схему с помощью стандартных интегральных схем.
Каждый корпус интегральной схемы, который мы будем использовать, получит обозначение схемы: U1, U2, U3. Чтобы различать отдельные вентили внутри корпуса, обозначим как a, b, c, d и т.д.
Инверторный корпус 7404 – это U1. Отдельные инверторы в нём – это U1-a, U1-b, U1-c и т.д. Обозначение U2 назначим модели 7432 с четырьмя вентилями ИЛИ. Обозначение U3 назначим модели 7408 с четырьмя вентилями И.
Чтобы можно было ссылаться на номера выводов на диаграммах с рисунка 19 выше, назначим номера выводов всем входам и выходам вентиля (см. схему на рисунке 20 ниже).
Теперь можем построить эту схему в лабораторных условиях. Или могли бы разработать для него печатную плату. Печатная плата содержит «проводку» из медной фольги, поддерживаемую непроводящей подложкой из фенола или эпоксидного стекловолокна.
Печатные платы используются для массового производства электронных схем. Заземлите входы неиспользуемых вентилей.
Рис. 20. При реализации на вентильной схеме покажем обозначения интегральных схем и их входов.
На этом рисунке показана разметка схемы ПрС-решения обозначениями цепей и номерами контактов. Это будет похоже на то, что мы только что сделали.
Рис. 21. В наличии есть вентиль И-НЕ с 4-мя входами, но нам нужен 4-входный ИЛИ.
Мы можем найти 2-входные логические элементы И, 7408, в предыдущем примере. Однако у нас возникли проблемы с поиском логического элемента ИЛИ с 4-мя входами в нашем каталоге ТТЛ.
Единственный тип логического элемента с 4-мя входами – вентиль И-НЕ 7420, показанный в правой части рисунка 21 выше.
Мы можем превратить вентиль И-НЕ с 4-мя входами в вентиль ИЛИ с 4-мя входами, инвертировав входы в вентиль И-НЕ, как показано на рисунке 22 ниже. Таким образом, можно использовать вентиль И-НЕ с 4-мя входами 7420 в качестве логического элемента ИЛИ, инвертировав входы.
Рис. 22. Вентиль И-НЕ превращаем в вентиль ИЛИ.
Однако мы не будем использовать дискретные инверторы для того, чтобы обратить входы 4-входном вентиле И-НЕ 7420, а будем управлять им с помощью 2-входного вентиля И-НЕ, используемого вместо вентилей И, которые требуются в СуП-решении для минтермов.
Инверсия на выходе вентилей И-НЕ с 2 входами обеспечивает инверсию вентилей ИЛИ с 4-мя входами.
Рис. 23. Итоговая реализация с использованием доступных вентилей.
Результат показан на рисунке 23 выше. Это единственный практический способ создать его с помощью логических элементов ТТЛ, используя логику И-НЕ/И-НЕ, заменяющую логику И/ИЛИ.
