Разделы
Публикации
Популярные
Новые
Главная » Теория переключательных цепей

1 2 3 4 5 6 ... 58

1

0 111

1 1 1

2 v 1 1 IV

3 1 1 1 V

Рис 1.9. Табличный способ нахождения простых импликант.

На рис. 1.9, представленном в виде таблицы, эти точки сгруппированы в соответствии с числом входов, которые равны 1. Множества Si и Sz образуются комбинациями в множествах Si и S2, и Ss и S3 точек, отличающихся только на одну переменную (первая строка Si образуется из первых строк Si и S2 и т. д.).

В таблице приведены все возможные комбинации точек. Импликанты {X1X2X3, X1X3, Х1Х2, Х2Х3] являются простыми, так как они не объединялись ни с какими другими импликантами (отмечены отсутствием знака V ) и ни одна из них не имеет неопределенной метки.

Другой метод получения простых импликант, удобный для функций с малым числом переменных, основан на использовании карт Карнау [9]. Карта Карнау для п переменных служит эффективным средством иллюстративного представления п-куба. Она содержит 2 ячеек, каждая из которых соответствует одной из 2 возможных комбинаций значений п двоичных переменных. Карта строится так, что ее соседние ячейки (как по вертикали, так и по горизонтали) отличаются только на одну переменную.

4. Термы, не участвовавшие в процедуре (определяемые по отсутствию знака V ). являются простыми импликантами при условии, что они не содержат литерал, соответствующих неопределенной метке.

Пример 1.3. Пусть f есть функция входных переменных х\, Х2, хъ с точками 1{(0, О, 1), (О, 1, 0), (1, О, 0), (О, 1, 1)} и неопределенной точкой {(1, 1, 1)}.



Карты Карнау для функций трех, четырех и пяти переменных приведены соответственно на рис. 1.10, fi, б, е. Отметим, что для каждой функции может быть построено несколько различных карт. В этих картах все ячейки в столбцах (или строках), обозначенных через Xi, представляют входные комбинации с Xi=\,a ячейки в необозначенных столбцах (строках)-комбинации с Хг - 0. Кроме того, столбцы и строки могут быть обозначены значениями подмножества определяющих их переменных. Например, столбцы карты на рис. 1.10, g определяются значениями переменных Xi и Х2 а могут быть обозначены слева направо как 00, 01, И и 10. На рис. 1.10,6 показаны две карты Карнау для функции четырех переменных. Входная комбинация, представленная каждой ячейкой карты, определяется проверкой обозначений соответствующих столбца и строки. Например, ячейка с на рис. 1.10,6 соответствует входной комбинации 0010, так как она принадлежит только строке Хз и не лежит внутри ни одного из столбцов Xl я Х2 и ни одной из строк Xi. Отметим, что для 1 i п, где п - число переменных в карте, ровно половина ячеек каждой карты соответствует Хг - I, а другая половина соответствует Xi = 0.

Каждой точке п-куба соответствует ровно п точек, отличающихся от рассматриваемой только одной переменной. Из карт, приведенных на рис. 1.10, видно, что каждая ячейка может иметь не более четырех смежных ячеек. Поэтому для представления точек, отличающихся только на одну переменную, необходимо использовать и более удаленные (не смежные) ячейки. Для получения с помощью карт Карнау простых импликант нужно визуальным осмотром выделить точки, отличающиеся одной переменной. Например, точки g и с на рис. 1.10,6 отличаются только переменной Хз. В этой карте первый и четвертый столбцы, а также верхняя и нижняя строки могут рассматриваться как смежные. Целесообразность использования карт Карнау ограничена кругом задач с малым числом переменных из-за неспособности человека представлять большие кубы в таком виде, чтобы без труда визуальным осмотром находить смежные входные комбинации.

Комбинационная функция может быть представлена на карте Карнау только в виде 1-точек и неопределенных точек. Подразумевается, что необозначенные ячейки соответствуют 0-точ-кам. При таком подходе карту Карнау функции, заданной в табличной форме на рис. 1.9, можно представить в виде, изображенном на рис. 1.11.

Импликанты функции образуются комбинированием 1-точек и неопределенных точек, которые отличаются только одной входной переменной. На карте Карнау такие термы представляются множеством смежных 1-точек (или неопределенных



г, 12

00 01 и 1С

с

а

к


Рис Ho. Карты Карнау дая трех (а), четырех (б) и пяти переменных (в).



точек). Карты строятся так, что точки, симметричные относительно оси, разделяющей области Xi= I и = О, отличаются только переменной Xi и считаются смежными. Следовательно, точки G и с на рис. 1.10,6 смежные, так как они симметричны относительно оси Хз, делящей области Хз = 1 и Хз = 0. Эти точки образуют простой куб XiX2Xi. Аналогично точки d и е на рис. 1.10, е- смежные, так как они симметричны относительно оси Xi. Точки f п g, а также } и k на рис. 1.10,6 симметричны относительно

Рнс. 1.11. Представление функции картой Карнау.

Рис. 1.12. Карта Карнау с отмеченными простыми импли-кантами.

ОСИ Хз, а пары f, g и j, k - относительно оси Х2. Эти четыре точки образуют 2-куб, представляющий импликанту 1X4. Аналогичным образом точки [g, h, i, /} представляют импликанту х\Хз. Обладая небольшим опытом, можно без труда визуально идентифицировать -кубы. Вообще й-кубы могут характеризоваться их симметрией относительно /г-осей карты. Определение простых импликант функции заключается в нахождении всех fe-кубов, которые не содержатся в кубах более высокого порядка.

Пример 1.4. Простые импликанты для карты Карнау, приведенной на рис. 1.12, равны

Х2ХзХ^ Х[Х2Хз, Х\ХзХ^, Х\Х2Х^, 23-4, 1-24 13

Заметим, что импликанты х\Х2Хз и xixi не являются простыми, так как образуемые ими простые кубы содержатся в 2-кубе х\Хз.

После нахождения простых импликант задача получения двухступенчатой реализации вида И-ИЛИ минимальной стоимости сводится к так называемой задаче покрытия простыми импликантами, заключающейся в выборе простых импликант минимальной стоимости, покрывающих 1-точки. Зависимость между простыми импликантами и 1-точками может быть представлена таблицей простых импликант, в которой строки соответствуют простым импликантам, столбцы-1-точкам реализуе-



МОЙ функции, а элементы, записанные в ячейках на пересечении i-й строки и /-Г0 столбца, равны 1 только тогда, когда простая импликанта, соответствующая строке i, покрывает 1-точку, соответствующую столбцу /.

Для функции, рассмотренной в примере 1.3, таблица простых импликант приведена на рис. 1.13.

Задача покрытия состоит в выборе множества строк минимальной стоимости, таких, что для каждого столбца по меньшей мере одна из строк в этом множестве содержит 1 в столбце Cj.

Каждой простой импликанте (строке) соответствует своя стоимость, отражающая стоимость аппаратуры, необходимой для реализации данного терма функции. Выше было указано на

Минтермы /и, nij / 3

1 lP,U,x,


Рис. 1 13. Таблица покрытия простых импликант.

Рис. 1.14. Упрощенная таблица покрытия.

два типа функций стоимости: одна функция зависит от числа логических элементов в цепи, а другая - от общего числа входов логических элементов. Способы использования этих или других функций стоимости рассматриваются ниже.

Для упрощения таблицы простых импликант так, чтобы любое покрытие минимальной стоимости этой таблицы являлось также покрытием минимальной стоимости исходной таблицы, используются следующие правила.

1. Существенно простые импликанты. Простая импликанта комбинационной функции f называется существенной в отношении 1-точки nij, если она покрывает только эту точку. Существенно простая импликанта соответствует строке Pj, в которой стоит только элемент столбца Cj. Любое минимальное покрытие таблицы должно содержать Р,. Таким образом, строка Pj должна быть выбрана так, чтобы элемент покрывающего множества, строка Pj и все столбцы, покрытые Pj, могли быть исключены из таблицы.

В таблице, изображенной на рис. 1.13, для случая Рд = xiX2 существенно простой импликантой для точки 1 является /Пг. *даляя Рз и столбцы, покрытые Рз, получим таблицу, изображенную на рис. 1.14. Простая импликанта Pi=zXiX2Xs является



с. С,

Рис. 1.15 Таблица покрытия.

самостоятельно). Таким образом, мы можем исключить Pj из таблицы, поскольку покрытие минимальной стоимости для упрощенной таблицы будет покрытием минимальной стоимости для оригинальной таблицы.

3. Доминирующий столбец. Столбец Q доминирует над столбцом Cj, если каждая простая импликанта, покрывающая Q, покрывает также Q (т. е. С{ содержит единицы во всех строках, в которых стоят единицы в столбце Cj). Таким образом, любая простая импликанта, покрывающая Q, покрывает также и С,-. Поэтому мы можем исключить Q из таблицы, так как любое покрывающее множество для упрощенной таблицы будет одновременно покрывать С,.

Правила упрощения таблиц можно применять повторно до тех пор, пока дальнейшее упрощение окажется невозможным. В качестве примера рассмотрим таблицу, изображенную на рис. 1.15; предположим, что

С(Р,)=-С(Р2)=С(Рз)=С(Р4).

Строка Рг доминирует над Pi, поэтому Pj можно исключить из таблицы, которая в результате такого упрощения примет вид, показанный на рис. 1.16. В этой таблице простая импликанта Рг существенна в отношении столбца Сг, что позволяет исключить строку Pg и все покрывающие ее столбцы. Результирующая

существенно простой в отношении точки trii, а Р2 = х^х^ - в отношении точки nti- Таким образом, покрывающее множество имеет вид {х\Х2, Х1Х2Х3, xix}. Однако правило 1 не позволяет упростить таблицу, изображенную на рис. 1.15.

2. Доминирующая строка. Пусть С (Р^) - стоимость простой импликанты Р^. Строка Р, является доминирующей по отношению к строке Pj, если С(Рг) C(Pj) и Pi покрывает все точки 1, покрытые Pj (т. е. строка Р, содержит единицы во всех столбцах, в которых стоят единицы в строке Pj). Если строка Pj доминирует над Pj, то существует покрытие минимальной стоимости, не содержащее Pj (доказательство предлагается выполнить



Рис. 1.16. Таблица после исключения Р,.

Рис. 1.17. Таблица после исключения и столбца, покрытого Рг-

любое покрытие содержит по крайней мере один элемент из R, строки Pi и исключении как этой строки, так и покрытых ей столбцов. Решения, найденные после упрощения полученных таким образом таблиц, являются субоптимальными (оптимальными относительно строки Pi). Лучшее из всех субоптимальных решений считают оптимальным. Рассмотренная процедура иллюстрируется следующим примером.

Пример 1.5. Пусть стоимости всех простых импликант таблицы, приведенной на рис. 1.18, равны. Столбцы Сз и С5 можно исключить, так как они являются доминирующими по отношению к соответствующим столбцам Ci и С7. Хотя дальнейшее упрощение таблицы с помощью правил упрощения невозможно, анализ столбца Ci показывает, что любое покрытие должно содержать Pi и/или Рз - единственные строки, покрывающие этот столбец. Проанализируем эти две возможности с помощью процедуры ветвления вокруг этого столбца. Если выбрать Рь то после исключения всех покрытых Pi столбцов таблица приобре-1ает вид, показанный на рис. 1.19, а. Таблица, упрощенная в результате выбора Рз, приведена на рис. 1.19,6. Теперь обе таб- ицы можно преобразовать с помощью правил упрощения. Минимальные покрытия, полученные, в результате процедуры вет ьления, соответственно равны {Pi, Р5] {Р3, Ре, Pi}, {Р3, Ре, Р.)

таблица показана на рис. 1.17. Учитывая, что Р4 доминирует над Рз и наоборот, минимальными покрывающими множествами для таблицы, показанной на рис. 1.15, являются {Рг, Рз} и

Однако прийти непосредственно к получению покрытия минимальной стоимости с помощью рассмотренных выше правил упрощения не всегда удается. Оригинальная или упрощенная таблицы могут не содержать существенные строки и доминирующие строки и столбцы. Такие таблицы иногда называют циклическими. В этих случаях для получения минимальных покрытий используется процедура ветвления. Она состоит в последовательном выборе из подмножества строк R, для которых



ИЛИ {Рз, Рь Pi). Так как стоимость первого покрытия {Pi, Р5} меньше, чем второго, то оно и является минимальным покрытием для рассматриваемой таблицы (рис. 1.18).

Процедура ветвления может быть выполнена вокруг любого столбца. Однако с вычислительной точки зрения наиболее удоб-

Рис. 1.18. Циклическая таблица.

но использовать столбец с минимальным числом единиц. Для получения минимального покрытия может потребоваться несколько ветвлений. Отметим, что для упрощения таблиц простых импликант существуют и более сложные правила [5].

а о

Рис. 1.19. Таблица, получающаяся при выборе Pi (а); таблица, получающаяся при выборе Рз (б).

Для решения задач покрытия небольших таблиц простых импликант удобен метод, предложенный Петриком [15]. Он основан на том, что каждая точка 1 комбинационной функции может быть покрыта любой импликантой, имеющей в этом столбце единицу. Определим булеву переменную pi так, что Pi=\, если простая импликанта Pj есть терм покрывающего множества, и р, = О Б противном случае. Тогда условием того, что столбец Cj



где все операции - булевы. Если выражение слева от знака равенства записано в форме суммы произведений, то каждый член представляет собой множество простых импликант, покрывающих все 1-точки.

Стоимость каждого множества равна сумме стоимостей входящих в него отдельных простых импликант. Если стоимость всех простых импликант одинакова, то минимальное покрытие характеризуется терм-произведением с минимальным числом литералов. Иначе говоря, минимальное покрытие определяется терм-произведением минимальной стоимости.

Для таблицы, изображенной на рис. 1.18, покрывающие множества описываются выражением

(Pl + Рз) (Pl + Р2 + Рб) (Pl + Рз) (Р2 + Рз + Рб) (Р4 + Р5 + Рб) X X (Pl + Pi) (Р4 + Р5 + Рб) =

= PiPs + P1P2P4 + Р1Р2Р6 + Р2Р3Р4 + РзР4Рб + Р1Р3Р4 + PiPsPe,

и минимальное покрытие равно {pi, р^}.

Задача покрытия может быть также сформулирована как линейная задача целочисленного программирования). Пусть переменная Xi=l, если строка i является частью покрывающего множества, и = О в противном случае. Минимизируемая

1) Определение линейной задачи целочисленного программирования дано в приложении. - -

2 Зак, 841

покрыт какой-либо простой импликантой, является булево выражение У, Рг=1, где /j - множество строк, покрывающих

столбец Cj, а операция сложения - булева (ИЛИ). Например, столбец Ci таблицы, показанной на рис. 1.18, будет покрыт, если (Р1 + Рз)= 1- Аналогично для покрытия столбца Сг необходимо выполнение условия (pi -j-pz-j-ре)= 1. Множество простых импликант, покрывающее оба этих столбца, должно удовлетворять условию

(Pl + Рз) (Pl + Р2 + Рб) = 1

Так как все Pi представляют собой булевы переменные, это условие может быть записано в виде

Р1 + Р2Рз + РзРб==1-

В общем виде условие покрытия всех столбцов таблицы, содержащей т столбцов, формулируется следующим образом:



целевая функция равна X CjX/, где Cj - стоимость строки i, а

i = l

ограничения определяются столбцами таблицы. Для каждого /

п

имеем X AifXi 1, где Afj = 1, если строка i покрывает стол-

бец

, и Ац = О в противном случае. При использовании для получения минимальных покрытий карт Карнау в ряде случаев удается воспользоваться концепциями существенности и доминирования непосредственно на основе визуального анализа карты. При этом легче всего найти существенные простые импликанты, так как они покрывают 1-точки, не покрытые ни одной из других простых импликант. Так как эти точки не нужно покрывать другими простыми импликантами, их на карте можно заменить неопределенными.

Концепция доминирующей строки используется для нахождения хороших простых импликант. Простая импликанта называется хорошей, если она покрывает некоторую 1-точку и доминирует над всеми другими простыми импликантами, покрывающими эту точку. Это означает, что если Pj - простая импликанта, покрывающая определенную 1-точку т^, то Pj есть хорошая импликанта по отношению к nth тогда и только тогда, когда для любой другой простой импликанты Pj, покрывающей т^. Pi покрывает все не покрытые предварительно 1-точки, покрытые Pj и C(Pj): (з). т. е. если Pj и Pj - соответственно кубы fej-ro и fej-TO порядков, ki kj.

Таким образом, хорошая простая импликанта соответствует в таблице простых импликант строке, которая становится существенной после вычеркивания строк, над которыми она доминирует. Хорошая простая импликанта является составной частью минимальной реализации вида И-ИЛИ. Из сказанного следует, что Б ряде случаев карта Карнау может с успехом использоваться как для определения простых импликант, так и для получения минимальных реализаций вида И-ИЛИ. Иногда наряду с картами Карнау нужно использовать и процедуру ветвления.

Пример 1.6. Для комбинационной функции, заданной картой Карнау, показанной на рис. 1.20, Х3Х4 - существенно простая импликанта для 1-точек 0100 и 1000 (но не для 0000 или 1100). В результате замены всех 1-точек, покрытых этой импликантой, неопределенными точками получаем хорошую импликанту .1X2X4 для 1-точки 0001 и хорошую импликанту Х1Х2Х3 для 1-точки 1110. Так как теперь все точки этого типа покрыты, то минимальная реализация в виде суммы произведений имеет вид ХзХ4-\-х1х2х4-\--f X1X2XS.

Мы показали, как получить минимальную реализацию функции / Б виде суммы произведений. Минимальную реализацию

и



1 2 3 4 5 6 ... 58
© 2004-2024 AVTK.RU. Поддержка сайта: +7 495 7950139 в тональном режиме 271761
Копирование материалов разрешено при условии активной ссылки.
Яндекс.Метрика