Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 64
Текст из файла (страница 64)
2 ДРугими словами, минимальная сумма содержит наименьшее возможное чне ло термов-произведений (равное числу вентилей на первом уровне и числу вхо дов вентилей на втором уровне) и, кроме этого, наименьшее возможное число 4.3. Синтез комбинационных схем 27З литералов (равное числу входов вентилей на первом уровне). Таким образом, среди трех вариантов схем для обнаружения простых чисел, только схема, приведенная парне.
4.30 является реализацией минимальной суммы. Следующее определение точно устанавливает смысл слов «влечет за собой», когда мы говорим о логических функциях: ° Логическая функция Р(Хь, ..,Х,) влечет за собой (!тр!!ез) логическую функцюо Е(Хь..., Х„), если для каждой комбинации переменных, такой что Р = 1, имеет место также Е= 1. Иначе это можно выразить так: если Р влечет за собой Е, то Е равно! для каждой комбинации переменных, для которой Р = 1, и, может быть, еще при каких-нибудь комбинациях. Такую связь между Р и Е можно символически записать в виде Р =» Е. Об этой связи между Р и Е можно сказать также, что «Е включает в себя (!пс!иа!вв) р» или что «Е покрывает (согвгв) Р». «Простая импликапта(рг!те !тр!!сап!) логической функции Е(Хь ..., Х„) — это нормальный терм-произведение Р(Хь...,Х„), который влечет за собой Е, причем такой, что если любую переменную удалить из Р, то получающийся при этом терм-произведение уже не влечет за собой Е.
На языке карты Карно простая импликанта функции Е представляет собой обведенный набор клеток, содержащих 1, удовлетворяющий нашим правилам объединения, такой, что если мы попытаемся его расширить (покрыть вдвое большее число клеток), то в него обязательно попадет, по крайней мере, один О. Теперь пришел черед самого важного; речь идет о теореме, которая устанавливает предел того, сколько труда нужно затратить на поиск минимальной суммы логической функции: Теорема а простых имиликантах.
Минимальная сумма является суммой простых нмплнкант. Это означает, что при поиске минимальной суммы не нужно рассматривать термы-произведения, не являющиеся просты ми импликантами. Эта теорема легко доказывается от противного. Предположим, что терм-произведение Р в «минимальной» сумме к«является простой имплнкантой.
Тогда, по определению простой импликанты, нз Р можно удалить какой-то литерал, если только Р не является единицей, н получить новый терм-произведение Р', который все еще влечет за собой Е. Если мы заменим Р на Р» в сумме, относительно которой мы предположили, что она минимальна, то получающаяся в результате этого сумма будет понрежнему равна Е, но будет содержать на один литерал меньше. Поэтому исходная сумма, фигурировавшая в нашем предположении, вовсе не была минимальной. Рассмотрим в качестве другого примера минимизации функцию 4-х переменных, приведенную на рис.4.31. В данном случае имеется две простые импликанты, н совершенно очевидно, что нх обе необходимо включить в минимальную сумму, чтобы покрыть все клетки таблицы, содержащие 1.
Мы не приводим принципиаль"ую схему, поскольку теперь вы уже сами знаете, как это сделать. 224 Глава 4. Принципы проекпероваиин комбинационных логических схем (Ь) ЧЧ ЧЧ. Х (а) ЧЧ о я ы в 1 ] 01 10 Х г " ГНЧ,Х,Ч,2(а,т 12,13,14,1Б) Х гнХ 2+ЧЧ'Х Рис.4 31. Е=Х „„(5,7, 12,!3, 14, 15):(а) карта Карно;(Ь) простыеимпликанты Сумма всех простых имплнкант называется поеной суммой (соар1еге яие). Хотя полная сумма всегда указывает допустимый способ реализации логической функции, она не всегда является минимальной.
Рассмотрим, например, логическую функцию, представленную парис.4.32. У нее пять простых импликант, но минимальная сумма включает только три из них. Спрашивается, как можно систематически определять, какие нмпликанты следует брать, а какие — отбрасывать? Нужны еще два определения: ° Особенная клетка, содержащая 1 (йи(1пйи 1яйей 1-се11), — это такая клетка, которая соответствует комбинации переменных, покрываемой только одной простой импликантой. ° Существенная простая ичпяиканта (еяяепйа1 ргппе )трйсап1) логической функции — это простая импликанта, покрывающая одну особенную клетку, содержащую 1, или большее их число. (а) О з с В 1 1 (Ь) ЧЧ 7 01 зО Х Я = Еч,хчл(1,3,4,в,а,1 1,12,1З,!4,!5) ЧЧ Х Х Г = Х Ч' + Х" Е + ЧЧ.
Х Рис. 4.32. Р = ачч „,,т(1, 3, 4, 5, 9, 11, 12, 13, 14, 15); (а) каРта Каоно; (Ь) пРостые имплнканты и особенные клетки, содержащие 1 Поскольку существенная простая импликанта является единственной простойй им ил икантой, покрывающей одну из клеток, содержащих 1, она доллсна входить в: 4 3. Синтез комбинационных схем 276 любую минимальную сумму данной логической функции. Таким образом, первый шаг в процедуре выбора простых импликант совсем прост: мы устанавливаем, какие из клеток, содержашнх 1, являются особенными, берем соответствуюшие нм простые импликанты и включаем их в качестве существенных простых импликант в минимальную сумму. После этого остается лишь определить, как покрыть остаюшиеся клетки, содержащие 1, — если таковые имеются, — не покрытые существенными простыми импликантами. В примере на рис.4.32 три особенные юзетки, содержащие 1, заштрихованы, а соответствующие нм существенные простые импликанты обведены более жирными линиями.
В этом примере все клетки, содержащие 1, покрываются существенными простыми нмпликаитамн, так что больше делать ничего не нужно. Аналогично обстоит дело в примере на рнс, 4,33, где все простые импликанты являются существенными и поэтому все они включаются в минимальную сумму. ((з) у2~, ОЕ О1 11 1О уу.х !а! ! Х 7 ] 01 !о Х Р = Хуу х у,г(2,3,4,5,б,7,11,13,15) чч' у Р = МГ У + а' Х + Х г ь У г Рис. 4.33. Е = Цуухуг(2, 3, 4 5 6, 7, 11, 13, 15): (а) карта Карно; (Ь) простые импликанты и особенные клетки, содержащие 1 Логическая функция, у которой не все клетки, содержащие 1, покрываются существенными простыми импликантами, приведена на рис. 4.34.
Исключая сушественные простые нмпликанты и покрываемые ими клетки, содержащие 1, мы получаем редуцированную карту, в которой имеется лишь одна клетка, содержашая 1, которую покрывают две простые импликанты. В данном случае осуществить выбор между ними легко: мы берем терм-произведение Ч/'. Е, так как в нем меньше переменных и поэтому соответствующая ему логическая схема с меньшим числом входов дешевле. В более сложных случаях нам понадобится еще одно определение: О двух простых импликантах Р и О, относяшихся к редуцированной карте, говорят, что Р перекрываеш (есйрзез) О (пишется: Р ...
О), если Р покрывает по меньшей мере все клетки, содержашие 1, покрываемые О. Если стоимость Р не больше, чем стоимость О, и если Р перекрывает О, то исключение О из дальнейшего рассмотрения не может помешать нам найти минимальную сумму: другими словами, простая имплнканта Р, по крайней мере, так же хороша, как и простая им ил иканта О.
276 Глава 4. Принципы проектировании к4)ыбинационных лопОЧЕСКИх схвм (Ь) )Н ах Ч2~, ОО О! 11 10 (а) ъч 4 ~ П 4 ! (с) их и чх~ Оо о) и !о ч( ч 1 ] ] [" -х чх х х Г = ЧГ. Г + И"Х ч О). Х Ч . ЧГ.2 х !и х ч Е Ънх чх(0,1,2,6АО,Ч,1К15) Рис.4.34. г = 2 шхуна(0, 1, 2, 3, 4, 5, 7, 14, 15); (а) карта Карно; (Ь) простые импли- канты и особенные клетки, содержащие 1; (с) редуцированная карта после ис- ключения существенных простых импликант и покрываемых ими клеток, со- держащих 1 Пример перекрытия представлен на рис. 4.35. После исключения существенных простых имплнкант у нас остаются две клетки, содержащих 1, каждая из которых покрывается двумя простыми импликантами. Однако простая импликанта Х У 2 перекрывает две другие простые имплнканты, иэгорые, таким образом, можно исключить из рассмотрения. В данном случае две клетки, содержащие 1, покрываются единственной простой импликантой Х ч' Е, которая является существенной простой импликантой второго порядка (весси((агу еввепба! рг)те )трйсапг) и которая должна быть включена в минимальную сумму.
(с) (а) ч( (Ь) чу~ ОО 01 11 !О Г; о! Х.Ч 2 1 — 1 и ч. х Г = Ьнх ч 2(2,6.7.0.15,15) 56ж ч"г+чч ч т+х ч г Рис.4.35. г = ~ хчт(2, 6, 7, 9, 13, 15): (а) каРта КаРно; (Ь) пРостые импликанты и особенные кнеп(и, содержащие 1; (с) редуцированная карта после исключений существенных простых импликант и покрываемых ими клеток, содержаизих 1 На рис. 4.36 показан более трудный случай: здесь у логической функции нет существенных простых импликант. Для этой функции методом проб и ошибок можно найти две различные минимальные суммы.
Возможен другой систематический подход к данной проблеме, который называется метадаи ветвления (ЬгапсЫпя течйас(). Начиная с любой клетки, содержа-ч щей 1, мы произвольно выбираем покрывающую ее простую импликанту и вклк)-„ чаем ее в наше рассмотрение, как если бы она была существенной, Это упрощает остающуюся часть задачи, которую можно решить обычным способом нахожде. „ ния гипотетической минимальной суммы. Этот процесс повторяется, начиная с 4.3. Синтез комбинационных схем 2 г г каждой другой простой имплнканты, покрывающей начальную клетку, содержащуюю 1; результатом каждый раз будет новая гипотетическая минимальная сумма. На этом пути можно споткнуться, и тогда метод ветвления необходимо применять рекурсивно. В конце концов мы сравниваем все полученные таким образом гипотетические минимальные суммы и выбираем одну из них, которая является минимальной на самом деле.
(Ь) ЧЧ ОО (а) ЪЧ ОО 01 [ 10 (г() 00 (с) ЧЧ' У' 2 Х' У' 2 01 ЧЧ Х'2 У.д 1О ЧЧ У.7 'Х 2 РпХ.У 2+Чу Х' 2+ЧУ'.У' 2 Р = ЧЧ" Х 2 + ЧЧ У 2 + Х' У' 2 рнс.4.36.г=Х хуг(1,5,7,9,11,15):(а)картаКарно;(Ь)простыенмплнканты; (с) минимальная сумма; (О) другая минимальная сумма 4.3.6. Упрощение произведений сумм На основании принципа двойственности можно минимизировать выражения вида кпроизведение сумм», рассматривая нули на карте Карно. Каждый О на карте соответствует макстерму в каноническом произведении логической функции, Все, что было изложено в предыдущем разделе, можно переформулировать в плане двойственности, включая правила составления термов-сумм, соответствующих обведенным наборам нулей, в результате чего находится лгинимаеьпое произведение (тт(та( ргог(исг). Если, однако, нам известно, как находить минимальные суммы, то отыскание минимального произведения для данной логической функции, к счастью, оказывается более легким.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
