Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 63
Текст из файла (страница 63)
В этой книге мы будем применять двойную разметку строк и столбцов карты, несмотря на ее избьпочность. Рассмотрим, например, карту для случая 4-х переменных на рнс. 4.26(с). Столбцы помечены четырьмя возможными комбинациями(Я( и Х: )л)Х = 00, О1, 11 и 10. Аналогично, строки помечены комбинациями'Я. Эти метки снабжают нас всей необходимой информацией. Однако мы будем также расставлять квадратные скобки, чтобы каждой из четырех переменных поставить в соответствие определенные области на карте. Каждая область, отмеченная скобкой, — это часть карты, в пределах которой указанная переменная равна 1. Очевидно, что скобки несут ту же самую информационную нагрузку, что и метки, которыми помечены строки и столбцы.
Когда карта рисуется от руки, гораздо легче нарисовать скобки, нежели выписывать все метки. Однако мы сохраним на картах Карно, предназначенных лля учебных целей, также и метки в качестве дополнительного средства, облегчающего понимание. В любом случае, вы безусловно должны размечать строки и столбцы в надлежащем порядке, чтобы сохранить соответствие между клетками карты н номерами строк в таблице истинности, указанное парис.4.26. Чтобы представить логическую функцию в виде карты Карно, мы просто переносим единицы и нули из таблицы истинности или ее эквивалента в соответствующие клетки карты.
На рис. 4.27(а) и (Ь) приведены таблица истинности н карта Карно для логической функции, которую мы рассматривал и в параграфе 4 2 (продолжаем долбить одно и то же). В дальнейшем, чтобы не рябило в глазах, мы будем заносить в карту только единицы или нули, но не те и другие одновременно. 4 3.
Синтез комбинационных схем 269 »э я г' хт ~ о х т х а г а о г о о а у а г, о г, |г (Ъ) о о о о о с о г о о о о о о 1 1 ! хг У 'г.г (с) (а) рнс 4-27 Р = Ххтг(1, 2, б, 7): (а) таблица истинности; (Ъ) карта Карно; (с) объединение соседних клеток, содержащих 1 4.3.5. Минимизация сумм произведений Г = . ~аХ У'.2+Х У.Е + (Х 2) .
г" + (Х 2) г' +Х 2. Вспоминая о том, что таблицу следует представлять себе «свернутой», мы видим, что клетки 1 и 5 на рис.4.27(Ъ) также являются смежными и их можно объединитгк Е =Х' У' Е+Х У' 2+ = Х' (У' 2)+Х (У' 2)+" =У' Е+.... Вы, наверное, уже успели удивиться «странному» порядку, в котором следуют строки и столбцы в карте Карно. Для установления этого порядка имеется очень веская причина: каждой клетке соответствует такая комбинация переменных, которая отличается от комбинаций, соответствующих клеткам, находящимся в непосредственном соседстве с данной клеткой, лишь значением одной переменной. Например, 5-я и 13-я клетки в карте для случая 4 х переменных различаются только значением Чг.
В случае 3-х н 4-х переменных чуть менее очевидными соседями являются соответствующие клетки в крайнем левом и крайнем правом столбцах и в верхней и нижней строках; например,! 2-я и 14-я клетки в случае 4-х переменных являются смежными, поскольку они различаются только значением у. Каждая комбинация переменных с единичным значением функции в таблице истинности соответствует минтерму в канонической сумме данной логической функции. Поскольку пара соседних клеток карты Карно, содержащих 1, указывает на наличие минтермов, различающихся значением только одной переменной, эту пару минтермоа можно объединить в один терм-произведение на основании обобщения теоремы Т!0: гепп т'+ гепп 1' = зепи. Таким образом, картой Карно можно воспользоваться для упрощения канонической суммы логической функции.
Рассмотрим, например, клетки 5 и 7 на рнс. 4.27(Ъ) н их вклад в каноническую сумму этой функции: 270 Глава 4. Принципы проектирования комбинационных логических схем В общем случае логическую функцию можно упростить, объединяя пары соседних клеток, содержащих 1, (пары минтермов) везде, где только это возможно, и выписывая сумму термов-произведений, покрывающую все клетки, содержащие 1. На рис.
4.27(с) представлен результат для логической функции, рассматривае мой в нашем примере. Мы обвели пары единиц, чтобы указать, что соответствую щие минтермы объединяются в один терм-произведение. Схема И-ИЛИ, реализующаяэтуфункцию,приведенанарис.4.28. Х Рис. 4.28. Минимизированная схема И-ИЛИ В отношении многих логических функций процедуру объединения клеток можно распространить на случай, когда один терм-произведение получается в резул ьтате объединения не двух клеток, а большего их числа.
Рассмотрим, например, каноническую сумму логической функции Е = Хх тз(0, 1, 4, 5, б). Выполняя итеративно те же алгебраические преобразования, что и в предыдущих примерах, можно четыре из пяти минтермов объединить в один: г = Х' У' Е'+Х' У' 2+Х У' Е'+Х У' 2+Х У Е =[(Х' У') Л'+(Х' У') 2[+[(Х.У').Е'+(Х У') Е[+Х У Е' =Х' У'+Х У'+Х У Е' = [Х' (У') +Х (У'Ц+Х У Е' = У'+Х У Е'. В общем случае объединение 2' клеток, содержащих 1, приводит к образованию терма-произведения с и — (литералами, где и — число переменных у данной функции. Вот точное математическое правило для определения того, как именно можно объединять клетки, содержащие 1, образуя соответствующий терм-произведение: Набор из 2' клеток, содержащих 1, можно объединить, если существует 1'таких переменных рассматриваемой логической функции, что в пределах данного набора перебираются все 2' возможных комбинаций зтих переменных, тогд~ как остальные и — ! переменных во всех клетках набора имеют одни и те же значения.
Соответствующий терм-произведение содержит и — ~ литерале~ причем та или иная переменная вхолит в него в виде дополнения, если оиа имеет значение 0 во всех обьединяемых клетках, и- непосредственно, если ее значение равно!. 4.3. Синтез коаябинациоиных схем 271 Графически это означает, что можно обводить прямоугольные»аборы единиц (гесьяляи(аг з«м оГ)з), содержащихся в 2' клетках («прямоугольные» как в буквальном, так и в переносном смысле этого слова), распространив определение «прямоугольный» на случаи, когда необходимо принимать во внимание свернутость карты по краям. Литералы, которые войдут в соответствующие термы-произведения, можно непосредственно определить по карте; вопрос о каждой из переменных решается по одному из следующих правил: ° Если обведенная область покрывает толью ту часть карты, где переменная равна О, то эта переменная входит в терм-произведение в виде дополнения, ° Если обведенная область покрывает только ту часть карты, где переменная равна 1, то эта переменная входит в терм-произведение непосредственно.
° Если в обведенную область попадают участки карты, где переменная равна О, а также участки карты, где переменная равна! „то эта переменная отсутствует в терме-произведении. Сумма произведений для нашей функции должна состоять из термов-произведе- ний (обведенных наборов клеток, содержащих 1), которые покрывают все единицы на карте и не содержат нулей. Х Х. 2' 0 Х 2~Оп д 1 з 1 (а) (с) У рис. 429. г = Ех тг(0, 1, 4, 5, б).
(а) первоначальная карта Карно; (Ь) карта Карно с обведенными термами-произведениями; (с) схема И-ИЛИ В самом последнем нашем примере логическая функция имела вид: г = 2х тх(О, 1 4, 5, б); карта Карно для нее представлена на рис.4.29(а) и (Ь). Мы обвели два набора единиц: один из них охватывает четыре клетки н соответствует терму-произведению у, а другой состоит из двух единиц н эквивалентен терму-произведению Х 2'.
Обратите внимание на то, что во второй терм-произведение входит на олин литерал меньше, чем в соответствующий терм-произведение в нашем алгебРаическом решении (Х.у 2'). Включив клетку 6 в наибольший возможный набор единиц. мы нашли более экономичную реализацию данной логической функции, 272 Глава 4. Принципы проектирования коыбинацмоииьпс лопоческнх схеы поскольку 2-в ходовой вентиль И, скорее всего, будет стоить дешевле, чем 3-входа вой вентиль. То, что два разных терма-произведения покрывают теперь одну и 1У же клетку, содержащую 1 (4-ю клетку), никак не отражается на логической фут, ции, так как при логическом сложении 1 ь 1 = 1, а не 2! Соответствующая двухуро невая схема И-ИЛИ показана парис.4.29(с).
Другим примером может служить минимизация схемы устройства лля обна ружения простых чисел, привеленная ранее на рис. 4.! 8; результат минимизаци „ представлен на рнс. 4.30. (Ь) 213 ой! ЙЗ г — -1 М!Мо~ 00 01 11 10 00 ЙЗ'М! 'Мо йо М,.йо 122' ЙЗ' М! 2!2 К = ЙЗ ™О + ЙЗ™2 ™1 + М2 ™! ™О О Й2™1' МО МЗ к = 2!о т т до(1,2,зжт, »,1 з) (с) М! Й, Мо рис. 4. 30. устройство для обнаружения простых чисел: (а) исходная карта Кар- но; (Ь) обведенные наборы единиц и соответствующие им термы-произведе- ния; (с) минимизированная схема Теперь нам понадобится еше несколько определений, чтобы внести ясность в то, что мы делаем: Чинимальвал сумма (тт!та)зит) логической функции р(Х1,, Х )-это такое выражение для г вида «сумма произведенийгч что не существует представлений Е в виде суммы произведений с меньшим числом терман-произведений а в любое другое выражение вида «сумма произведений» с тем же самым чис лом терман входит, по меньшей мере, столько же литералов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
