3 X6

Xz

Рис. 1.3

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

если 1-клеток, входящих только в один т-куб, нет, то следует рассмотреть несколько вариантов минимизации.

Диаграммы Вейча для числа переменных гг>4 составляются из идентичных (в смысле обозначения сторон первичными термами

дсрр) диаграмм Вейча для четырех переменных. На рис. 1.3 представлены диаграммы Вейча для п - Ъ и 6. Две диаграммы Вейча для четырех переменных будем называть соседними, если оии имеют общую грань. Клетки, расположенные в одинаковых местах соседних диаграмм Вейча для четырех переменных, являются соседними, так как им соответствуют соседние минтермы. Так, например, клетки с номерами О и 16; 5 и 21 и т.п. (рис. 1.3, а), О и 16; О и 32; 5 и 21; 5 и 37 и т.п. (рис. 1.3, в) являются соседними, но клетки О и 48; 5 и 53; 16 и 32 и т.п. (см. рис. 1.3, в) не являются соседними, так как они расположены не в соседних диаграммах Вейча для четырех переменных.

Легко убедиться в том, что т-кубы, расположенные в одинаковых местах двух соседних диаграмм Вейча для четырех переменных, образуют (m-fl)-ky6. С учетом этого МДНФ функции ((у), представленной на рис. 1.3,6, имеет вид \{)=х%Х1\/ХгхС\/ХьК\1

\/xbxixi.

В диаграммах Вейча для шести переменных т-кубы, располо-

Рис. 1.4

женные р одинаковых местах всех четырех диаграмм Вейча для четырех переменных, образуют (п+2)-куб. Поэтому МДНФ функции, представленной на рис. 1.3, г, имеет вид (v) =Х1;сг\/хъХ*Х\\/

\/XatXiVx5XA.

Минимизация неполностью определенных функций. Основная

задача минимизации неполностью определенных функций заключается в отыскании оптимального варианта ее доопределения, позволяющего получить минимальную из всех возможных ДНФ или КНФ. Если значения функции не заданы в т точках, то ее можно доопределить 2"" способами. Поэтому минимизация неполностью опреде" ленной функции состоит в выборе одной из 2"" полностью определенных функций, которая имеет минимальную ДНФ или КНФ. СДНФ неполностью определенной функции /(v) можно представить в виде

/(v)= VKi fv) УФ V /C,v(v),

где v=(Xn, Xi); (s -номера тех точек области определения, в которых функция /(vi) = l, а tV -номера тех точек области определения, в которых функция f(v) имеет неопределенное значение, т.е.

Пусть задана СДНФ неполностью определенной функции четырех переменных: ха, хз, Хг, хг. /(v) =KoVK4V7V8V®(iV5V VeVKsVia), где y((=/Ci(v), Составим для этой функции диаграмму Вейча (рис. 1.4). Для этого в клетки с номерами ( = 0, 4, 7 и 8 следует занести значения функции, равные 1, а в клетки с номерами 1=1, 5, 6, 9 и 12 - неопределенные значения Ф. С помощью диаграммы Вейча легко найти все минимальные покрытия, полагая либо Ф=0, либо Ф=1. На рис. 1.4 представлены два варианта доопре-деления функции v), к от орые дают минимальные ДНФ, f(v) = =х,Хз\/Х!Х1, /(v) =Х4ХзУхзХ2 (Ф = 0, если символ Ф не вощел ни в один т-куб, и Ф=1, если он вощел хотя бы в один т-куб).

Аналогично этому можно найти и МКНФ данной неполностью определенной функции, произведя оптимальным способом доопределение инверсной функции: /(v) =Х4Хз\/зХ2, /(v) = (x4v3) {Хз\/ VA). Для данной функции имеется только один способ доопределения, дающий минимальную КНФ.

1.4. Комбинационные схемы

Логическая схема, выходные сигналы г, которой описываются системой переключательных функций

2q = fq{Xn.....(1.56)

лэ и

- Хг-

Рис. 1.6

Xi Xf.

Рис. 1.7

где дср -входные сигналы логической схемы, р=9=1...*, называется КС. Из системы (1.56) следует, что КС реализует однозначное соответствие между значениями входных и выходных сигналов. При синтезе КС, имеющих несколько выходов г,, независимая минимизация каждой функции /«(ДСп, ...,*i), как правило, ие дает оптимального результата в смысле суммарного числа первичных термов, требуемых для представления функций.

Совместная минимизация функций. МДНФ функций /i(v) и /2(v), заданных диаграммами Вейча на рис. 1.5,

\ib) Xixy хХ2\ и{)=-ЧЧУ ЧЧ- (1-57)

На рис. 1.6, а показана КС, реализующая эти функции. Из рис. 1.5 следует, что функции /i(v) и /2(v) можно представить также в форме (не МДНФ):

/i (V) = Хз V *4 Ж.Ч-а; ]Л)=ЧЧЧ ЧХ%Ч- (1-58) Контерм XiXsXi входит в обе функции, а для его реализации требуется только один логический элемент (ЛЭ) И. Для реализации функций в форме (1.58) требуется семь первичных термов, а в форме (1.57) - восемь первичных термов. На рис. 1.6,6 показана КС, реализованная в соответствии с (1.58). Сложность реализации КС можно оценивать также по суммарному числу входов используемых ЛЭ.

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

Порядок КС. Максимальное число последовательно вьшолняемых логических операций для реализации функции /(х„, xi) называется порядком переключательной функции. Функции, представлен-