2.1.2. ВЫБОР МИНИМАЛЬНОГО ПОКРЫВАЮЩЕГО МНОЖЕСТВА ПРОСТЫХ МНОГОВЫХОДОВЫХ ИМПЛИКАНТ

Выбор минимального покрывающего множества простых многовыходовых импликант можно сформулировать в виде задачи покрытия таблицы простых импликант. Каждой строке в этой таблице соответствует простая многовыходовая импликанта, а каждому столбцу - каждая точка 1 каждой функции fj. Если столбец / представляет точку 1 f, то элемент в строке ( столбца / равен 1, если точка 1, представленная столбцом /, покрыта простой многовыходовой импликантой, представленной строкой г. Как и в случае минимизации одной функции, стоимость, ассоциируемая с простой импликантой, зависит от цели оптимизации. Если такой целью является минимизация общего числа логических элементов, то стоимость, связанная с простой Импликантой Pj, содержащей литерал, равна 1, если > 1, и О, если qi= I. Если целью оптимизации является минимиза-

на рис. 2.5,6. Результирующие простые импликанты равны х^з для fz, Х1Х2 для fi-fz и Xi-Xs для fz- Однако 1X2 есть также простая многовыходовая импликанта и самих функций /1 и fz.

Указанный выше недостаток этой процедуры связан с потерей информации, имеющей место при использовании метода кодирования функциональных идентификаторов. Например, строке, представляющей собой точку 1 функций fi и fz, мы присваиваем идентификатор П. Однако такое присвоение не учитывает того, что рассматриваемая строка представляет и точки 1 функций fl и fz, взятых индивидуально. Указанную трудность можно преодолеть, повторяя эту строку со всеми возможными функциональными идентификаторами. Тогда для только что упомянутого примера для одной и той же входной комбинации необходимы три строки с функциональными идентификаторами 01, 10 и 11. Однако с увеличением числа строк эта модификация, вероятно, становится слишком громоздкой.

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

и XiXzXi для fl, XzXi, Х1Х2Х3 и XiX3Xi для f2 и Х2Х3Х4 для fi-f2

(рис. 2.3). Произведение fi-f2 функций fi и f2 равно 1 в точках, где fl и f2 равны 1, fi-fz = О в точках, где либо fi, либо f2 равна О, и fi-f2 - не определено в точках, в которых ни fi, ни /г не равна О и fl и/или f2 не определены.

Рис. 2.6. Множество функций (а); таблица покрытия (б); упрощенная таблица покрытия (е); минимальная реализация И-ИЛИ (г).

ЦИЯ общего числа входов логических элементов, то импликанта Pi с Qi литералами является простой многовыходовой импликантой множества k функций, стоимость этой импликанты равна Qi -f k при <?г > 1 VI k при qi = 1.

Как отмечено выше, простая многовыходовая импликанта Pi для подмножества F cz F может также быть простой многовыходовой импликантой для F с F\ В этом случае простая импликанта Pi должна быть включена в простую импликанту, покрывающую таблицу более одного раза: один раз для каждого произведения функций, покрытых Р,-. Например, если Pi - простая импликанта fi-fj, а также функции fi (но не fj), то в таблице простых импликант появятся две строки, соответствующие Pi. С этими строками связаны две различные стоимости. Для Рг, рассматриваемой в качестве простой импликанты произведения fi-f2, стоимость минимизации числа входов логических элементов равна <?г + 2, где (7i -число литерал в Р,-, и трактуется как покрытие соответствующих точек 1 функций ft и fj. Стоимость, связанная с Pi как простой импликантой только функции fi, равна -}- 1 и трактуется как покрытие только соответствующих точек 1 функции fj. В ряде случаев таблица простых многовыходовых импликант поддается упрощению с помощью соотношений доминирования, аналогичных рассмотренным для случая индивидуальных функций. Кроме того, упрощение получается в случае, если одна и та же импликанта появляется Б таблице несколько раз. Предположим, что Pj появ-

Простые импликанты, покрывающие таблицу, приведены на рис. 2.6, б. Заметим, что импликантам 2X3X4 и 2X3X4 соответствуют по две строки.

Импликанта Х2Х3Х4 существенна для покрытия точек 1 функции /2. Выберем строку 2 и уменьшим стоимость строки 3 до 1. Аналогично выберем строку 4 для покрытия точек 1 функции и уменьшим стоимость строки 5 до I. В полученной в результате таблице на рис. 2.6, в минимальное покрытие состоит из простых импликант: Х2Х3Х4 и Х2Х3Х4. Поэтому эти термы делятся соответственно между fi и fg и fi и /з, как показано на рис. 2.6, г.

Как показано в случае одной функции, множества минимальных покрытий для множества функции F = {fi, /2, . , f,} иногда могут быть получены из карт Карнау отдельных функций и карт произведений всех подмножеств этих функций. Это делается путем выбора существенных или хороших простых многовыходовых импликант. Простая многовыходовая импликанта называется существенной в отношении 1-точки функции fi е F, если она единственная простая многовыходовая импликанта, покрывающая точку т, функции fi.

Простая многовыходовая импликанта называется хорошей в отношении 1-точки т,- функции /, е F, если для любой другой простой многовыходовой импликанты Pj, покрывающей mj функции /а, 1) Р,- покрывает все ранее непокрытые точки 1 всех функций в F, которые покрыты Pj, и 2) стоимость Р,- стоимости Pj.

ляется как простая импликанта ft и fj-fj и что для покрытия всех точек 1 функции fi надо выбрать одну из этих строк. Мы можем выбрать Р,- как простую импликанту fi и упростить таблицу. При этом стоимость строки, соответствующей Pi как простой многовыходовой импликанте fi-fj, снижается до 1, так как распределение терма, уже выбранного для реализации, требует только одного дополнительного входа. Если в конечном счете эта строка выбирается как часть минимального покрытия, то это заменяет использование Р,- в качестве простой импликанты только fi. В действительности мы выбираем Pi, реализуемую логическим элементом И, но откладываем решение о том, будет ли Рг использована только как простая импликанта Д- или простая импликанта fi и f,.

Пример 2.3. Для множества функций {fi, fz, Ы, показанного на рис. 2.6, а, существует следующее множество простых много-выходовых импликант:

XzXsXiifi /2), XXsXiifs), XXsXiifl fs)-

Рис. 2.7. Карты Карнау fi, /г. fi /2-

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

Пример 2.4. Для множества функций F = \f\, fz) карты Карнау отдельных функций и их произведения приведены на рис. 2.7. Видно, что, во-первых, простая импликанта XzXi существенна

Применять это правило нужно с осторожностью, так как стоимость ранее выбранной простой импликанты, покрывающей точку tUj функции fh, равна 1. После выбора простой многовыходовой импликанты, покрывающей точки 1 множества функций F, все точки 1 всех fi е f, покрытые этой импликантой, заменяются неопределенными элементами.

1 Щ

ДЛЯ покрытия точки 1 trig функции fi. Анэлогично простая импликанта xixx существенна для покрытия точки 1 mi2, функции /г- Выбирая эти простые импликанты и заменяя покрытые ими точки 1 на неопределенные, получим карты, приведенные на рис. 2.8. Стоимости этих простых импликант уменьшаются

Рис. 2.8. Карта Кариау после выбора существенных простых импликант

ДО I. Простая импликанта xiXgXg - хорошая простая импликанта для покрытия точки Inij функций /г и fi. Поэтому выбираем ее и распределяем между обеими функциями. Ранее выбранная простая импликанта Х1Х2Х4 - хорошая в отношении mi2 и Ши функции /1 и используется для покрытия этих точек. Минимальная двухступенчатая реализация этих функций имеет вид

fl == XsXi + Х1Х2Х3 + X1X2X4, /2 XjXgX -j- Х1Х2Х4.

Подчеркнутые снизу термы принадлежат обеим функциям, и общее число входов логических элементов равно 13,

2.2. МНОГОСТУПЕНЧАТЫЕ КОМБИНАЦИОННЫЕ ЦЕПИ

До сих пор мы ограничивались рассмотрением двухступенчатых цепей. Однако на практике существует много причин, заставляющих нас обращаться к цепям с большим количеством ступеней. Связь между стоимостью аппаратуры и быстродействием (т. е. числом ступеней) можно уяснить из рассмотрения реализации функции проверки на честность f (хьХг,..., x ) = Xi ф ф © ... фх . Эта функция равна 1 тогда и только тогда, когда

©

©

l*ji©a:z©.

ц

©

Р

Рис. 2.9. Дерево схемы проверки на четность (а); цепь проверки на четность

на два входа (б).

нечетное число входных переменных равно 1. Для двухступенчатой реализации требуется 2 - логических элементов И на п входов каждый и один логический элемент ИЛИ на 2 ~ входов. Кроме того, в случае одноканальных входов необходимо п инверторов для образования дополнительных входов. Общее число ступеней в этом случае будет равно трем.

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

Реализация имеет Uog2 1 ступеней проверки на четность на два входа, где [х] представляет собой наименьшее целое число, большее или равное х. При реализации каждой цепи проверки на четность на два входа трехступенчатой цепью (включая инверторы), как показано на рис. 2.9,6, суммарное число ступеней в цепи равно STlogsttl. Цепь содержит 3{п-1) логических элементов на два входа и 2{п - 1) инверторов.

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

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

X,.

[У

Рис. 2.10. Двухступенчатая реализация (а); факторная реализация (б).

гического элемента обычно ограничены определенными максимальными значениями. Чтобы удовлетворить этим ограничениям, часто необходимо реализовать цепи с числом ступеней, большим двух. Процедура, используемая для создания таких цепей, называется разложением на множители. Рассмотрим функцию F == xiXzXsXi + XiXzXaXi. Оба терма имеют общий множитель Х1Х2 и, следовательно, могут быть переписаны как XiX2{x3Xi4- ХъХ^). Соответствующие реализации показаны на рис. 2.10. В результате разложения на множители коэффициент разветвления по входу снизился с четырех до двух, а число ступеней логики увеличилось с двух до трех (соответственно увеличив запаздывание).

Любая произвольная комбинационная цепь может быть непосредственно преобразована в эквивалентную логическую цепь, удовлетворяющую ограничениям коэффициентов разветвления по входу и выходу. Например, логический элемент И на и входов реализуется древовидной цепью, построенной на логических элементах И на два входа (аналогично схеме на рис. 2.9). Чис-

) Коэффициент разветвления по входу логического элемента G представляет собой число входов этого элемента, коэффициент разветвления по выходу элемента G - число элементов, присоединяемых к выходу элемента С

2.3. ДЕКОМПОЗИЦИЯ КОМБИНАЦИОННЫХ ФУНКЦИЙ

Функция f{xi, Х2, .... Хп) называется разложимой, если она может быть реализована в виде совокупности функций, каждая из которых имеет менее п переменных, т.е. f{xi, xz, ..., Хп) =

1 х„.

Рис. 2.11. Декомпозиционная реали-

ЗаПИЯ функции f (Хи Х2.....Хп).

Рис. 2.12. Декомпозиционная реализация функции Х1Х2 + (Х2 -\- Xs) Xi -(-+ XiXi.

= P(gu §2, . gk), ЧТО показано на рис. 2.11. Например, функция f(xi, Xz, Хг, х^ -XiXz-\- (x2-f X3)X4 + 3ci3c4 может быть разложена, как показано на рис. 2.12.

Декомпозиция комбинационных функций [1,3] может быть дизъюнктивной и нондизъюнктивной (содержать отрицание дизъюнкции). При дизъюнктивной декомпозиции внешние входные переменные для подфункции gi являются независимыми входными переменными для любой подфункции g-,-. Пусть X = = { 1. Xz, Хп]-множество входных переменных. Тогда если (х) f{gi(Ai), gziAz), gk{Ak)), где Л Az, ..., Л, -множества входных переменных, таких, что Af (] Aj = Ф для лю-

ЛО ступеней дерева равно flogs п\. Аналогично коэффициент разветвления по выходу п реализуется деревом с [logzn] ступенями, где каждый логический элемент в схеме имеет один вход и коэффициент разветвления по выходу, равный 2.

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

бого и /, и LJ Лг = л, и л и ... и = X, то декомпозиция

дизъюнктивна. Если для некоторых /, /, 1 i, j п, А^ПАф Ф Ф, то декомпозиция нондизъюнктивна.

2.3.!. ПРОСТЫЕ ДИЗЪЮНКТИВНЫЕ ДЕКОМПОЗИЦИИ

Простая дизъюнктивная декомпозиция имеет только одну подфункцию gx и /(х) = /(л'1, л'2. .... А' ) =/(§1(Л,), Лг), где Л, ПЛ2 = Ф, Л, иЛ2 = Л'.

Пример 2.5. Пусть f{x) = f(Xi, х^, Хъ, х^) =XiXiXb-{- ХзХ^. Ион-дизъюнктивная декомпозиция /(х) показана на рис. 2.13, а.

[К

{у

>1

Рис. 2.13. Нондизъюнктивная декомпозиция /(х) (а); простая дизъюнктивная

декомпозиция / (х) (б).

а простая дизъюнктивная, где Л, = {л; Хг, х^, Лг - {хз}, ,(Л,) =XiX2 + Jf4, f(gi(i), Az) =X3-gi{Xi, xz, X4), -на рис. 2.13,6.

Чтобы определить свойства комбинационных функций, которые позволяют получать простые дизъюнктивные декомпозиции в виде F{g{A{), Лг), рассмотрим карту Карнау функции f (рис. 2.14,а), где строки соответствуют переменным множества Лг, а столбцы - переменным множества Ль Для Л] = = [хи Xz, Хз} и Лг = {Х4, Xg} карта имеет вид, показанный на рис. 2.14,6. Построенная таким образом карта Карнау называется картой декомпозиции для множеств переменных (Л Лг).

Если Ах имеет q входных переменных (обозначенных как \Ax\=q), а Az - r входных переменных (Л2 = /), то = = п = г -\- q. Каждая строка карты декомпозиции представляет 2 точки п-куба, а каждый столбец -множество 2 точек. Множество точек, представленное любой строкой, имеет то же значение множества переменных Az, и множество точек, представленное любым столбцом, имеет то же значение множества переменных Ах. Предположим теперь, что функция f(x), имеющая простую дизъюнктивную декомпозицию, нанесена на карту декомпозиции для множества переменных (Ль Az). Необходи-