Ограничения на глубину связи в схеме

 

Формализуем понятие глубины связей в схемах следующим образом. Рассмотрим схемы, не имеющие обратных связей. Элементы таких схем можно однозначно разбить на группы, называемые рангами или ярусами, по следующему правилу. К нулевому ярусу (рангу) относим входные полюса схемы. Элементы, входы которых связаны только с входными полюсами, отнесем к первому ярусу. В общем, к элементу
i-го яруса отнесем все элементы, входы которых связаны только с выходами элементов (i --1)-го и, может быть, элементов нижних ярусов. Если выход элемента i-го уровня связан с входом элемента j-го уровня, то длину этой связи оценим числом (i - j), названным глубиной связи. Если на схему задано ограничение на глубину связи, это означает, что рассматриваются только такие схемы, в которых глубина связи не превосходит заданной величины l.

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

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

Вслед за Постом, определим булеву функцию как a-функцию, если f(x,x,x,...x) = x, b-функцию, если f(x,x,...,x)=1, g - функцию, если f(x,x,...,x) = 0 и как d- функцию, если f(x,x,...,x) = `x , где `x -инверсия х.

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

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

Следующие утверждения будут нам необходимы при доказательстве:

У1. Если функция самодвойственная, то она или a- или d-функция. Утверждение следует из того, что f(0,0,...,0)  ¹ f(1,1,...,1).

У2. Линейная функция есть a- или d-функция тогда и только тогда, когда она самодвойственная, b- или c-функция тогда и только тогда, когда она несамодвойственная. Утверждение следует из определения линейной функции и того, что в первом случае сумма будет содержать нечетное число сомножителей, во втором случае – четное.

У3. Если b- или c-функция отлична от константы, то она немонотонна. Утверждение следует из того, что эта функция будет иметь одинаковые значения на нулевом и единичном наборах, которые сравнимы со всеми наборами и являются, соответственно, максимальным и минимальным.

У4. d-функция является немонотонной и не сохраняет константы.

У5. Из линейной функции заменой некоторых переменных на константу 0 можно получить переменную (a-функцию). Из нелинейной функции для получения a-функции необходимо иметь обе константы.

Доказательство проведем в несколько этапов. Вначале покажем, что если базис содержит более двух элементов, то среди его функций обязательно есть a-функция, то есть он полон при l = 1. Затем более подробно разберем двухэлементные базисы, не содержащие a-функций. В конце доказательства рассмотрим одноэлементные
базисы.

 Пусть базис j = {j i | i=1,к} и к > 2. Покажем, что он содержит a -функцию.

Разделим базисы на две группы в зависимости от того, какова в нем нелинейная функция (обозначим ее как j₁):

а. j₁ является самодвойственной;

б. j₁ – функция несамодвойственная.

Случай а. По свойству 1 функция j₁ или a- или b-функция. Если это-
d-функция, то она немонотонная, не сохраняет константы, и в базис достаточно добавить несамодвойственную функцию, то есть базис будет иметь только две функции.

Случай б. Если j₁ d-функция, то она по свойству У4 одна является полным базисом. Если j₁ b- или c-функция, то по свойству У3 она немонотонна и не сохраняет одну константу. В этом случае в базис нужно добавить только функцию, не сохраняющую вторую константу.

Утверждение 1 доказано. Рассмотрим теперь базисы, содержащие ровно две функции и не содержащие a-функций. Обозначим их как
j={j₁, j₂}.

 Снова разделим рассмотрение на два случая: а) функция j₁ –несамодвойственная и линейная, j₂ - функция самодвойственная и нелинейная. Случай б) функция j₁ – несамодвойственная и нелинейная,
j₂ - не сохраняет константу.

Случай а). По свойству У2 функция j₂ является d-функцией, значит на втором уровне можно получить инверсии переменных. Функция j₁ является a- или c-функцией, значит на втором уровне можно получить одну из констант. На третьем уровне с помощью этих функций получаем переменные и обе константы (вторую – через инверсию первой). С помощью констант из линейной функции можно получить на четвертом и всех последующих уровнях a-функцию (повторитель), чем и обеспечивается полнота базиса для этого случая.

Случай б.

 функция j₁ – несамодвойственная, нелинейная и не d-функция (иначе она одна – базис). Значит это b- или c-функция. Если при этом j₂ есть
b- или c-функция , то на втором уровне можно получить только такие функции, которые имеют значения на нулевом наборе такие же, как и на единичном. Значит, на следующих уровнях из них не удастся получить a- или d-функции и полнота обеспечена не будет.

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

И, наконец, если функция j₂ есть константа, то она есть на первом уровне вместе с переменными. С ее помощью из функции j₁ можно получить на втором уровне инверсии переменных и обе константы, которые обеспечат полноту.

Для одноэлементного базиса, реализующего только d-функцию, на первом ( и всех нечетных ) уровне можно реализовать только
d-функции, на втором (и всех четных) уровне реализуются только
a-функции. В этом базисе при l=1 никогда не реализуются
b- и d -функции. Значит, полнота обеспечена быть не может.

При l=2  функциональная полнота обеспечивается для любого функционально полного в смысле Поста базиса.

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

Здесь любая схема будет иметь l = 1, и для получения схем с глубиной связи, равной двум, нужно решетку дополнить диагональными связями,

например, как это показано на рис. 3.5

.

 

 

Методы синтеза схем

Рассмотрим два подхода к синтезу схем – декомпозицию и факторизацию.

Метод факторизации

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

Рассмотрим применение метода для классического базиса, состоящего из элементов {2-И, 2-ИЛИ, НЕ}, и для монофункциональных базисов {И-НЕ} или {ИЛИ-НЕ.}

Метод декомпозиции

Метод декомпозиции ещё называют методом от выходов к входам. Он состоит из последовательности шагов:

1. Определяется множество функций, называемых множеством непостроенных функций (обозначим как Fн). Вначале Fн=F.

2. Выбирается функция fÎFн и она удаляется из Fн. Выбирается элемент gÎY. Предполагается, что f реализуется на выходе
элемента g.

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

4. Эти функции, за исключением входных переменных, вносятся в множество Fн.

Шаги 2 -4 повторяются до тех пор, пока множество Fн не станет пустым. Для того чтобы получить решение, любая из функций образующего списка для f должна быть проще функции f. Самыми простыми считаются входные переменные, для других функций каждый метод предлагает своё понятие простоты.

Рассмотрим работу метода на примере реализации функции сложения по модулю два от двух переменных в одноэлементном базисе, состоящем из элемента 2-И-НЕ.

Запишем таблицу для элемента базиса (табл. 3.4) и перепишем её в виде табл.3.5, где символом x обозначено значение «что угодно». Например, 2-я строка таблицы означает, что если на первом входе элемента – нулевое значение, то независимо от значения на втором входе значение на выходе элемента равно единице.

Запишем функцию в векторном виде как f = (aÅb) = <0110>.

При построении образующего списка будем исходить из того, что для реализации на выходе элемента 0 необходимо на оба входа
подать 1, для реализации 1 необходимо на один вход подать 0, на другой – что угодно. Образующий список для f в этом случае будет иметь вид {<1x01>,<10x1>}.

Таблица 3.4
a	b	j
0	0	1
0	1	1
1	0	1
1	1	0
Таблица 3.5
a	b	j
0	x	1
x	0	1
1	1	0

Будем оценивать сложность функции числом неопределённых значений в ней. Будем при этом исходить из того, что чем больше неопределённость функции, тем легче доопределить её до переменной. Из этой оценки следует, что вариант образующего списка {<1001>,<1хx1>} нас не устраивает, так как в этом варианте первая функция списка имеет ту же сложность, что и исходная.

Представим всё решение в виде рис. 3.6. На выходе 2-го элемента верхняя функция дополняется до переменной b=<0011>, нижняя функция элемента 3 – до функции а=<0101>. На входе 5-го элемента нижняя функция дополняется до b, верхняя функция 4-го элемента – до а.

Результирующая схема приведена на рис.3.7.

К методу декомпозиции можно отнести и метод каскадов Поварова, основанного на разложении К. Шеннона. Функция представляется как f(x1,x2,…,xn) = x×f(x=1) Ú`x×f(x=0), конструкция из элемента дизъюнкции и 2-х элементов конъюнкции образует каскад, на входе которого функции не зависят от переменной х и в этом смысле более просты, чем исходная функция.

В этом методе результат неоднозначен и зависит от порядка выбора переменных, по которым проводится разложение. Если функцию можно представить как сложение по модулю два переменной и некоторой функции f” от остальных переменных, то f” = f(x = 1) =`f(x = 0).

Пример. Построим схему для функции от 4 переменных, представленную в виде вектора

f(a, b, c, d) = <0110100101000101>

Начнём разложение с разложения по a. Получим
f1 = f(a = 0) = <01101001>, f2 = f(a = 1) = <01000101>.

Разложим f1 по переменной b, получим

f11 = f1(b = 0) = <0110>, f12 = f1(b = 1) = <1001>.

Замечаем, что f11 =`f12 = `c×dÚ c×`d.

Эта функция не минимизируется, реализуем её в базисе

{2-И, 2-ИЛИ, НЕ}.

Разложим f2 по переменной b, получим:

f21=f2(b=0)=<0100>, f22=f2(b=1)=<0101

Замечаем, что f22=переменной d, f21 =(`c×d).

Окончательно решение примет вид как на рис. 3.8.

 

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: