Синтез комбинаторных систем.

Комбинаторной системой называется автомат выполняющий преобразование х в у, где

x = { x₁, x₂, …, x_n } – множество входных булевых переменных

y = { y₁, y₂, …, y_n } – множество выходных булевых функций

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

x₁ x_n

КС

у₁ у_n

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

Алгоритм синтеза логических функций с малым числом переменных в заданном базисе :

1. Функция записывается в сов. норм. дизъюнктивной форме по заданной таблице истинности

2. Находится мин. форма, любым способом.

3. Операции дизъюнкции, конъюкции и отрицания варажаются через функции базиса.

4. Записывается выражение функции в элементах базиса и строится схема.

Пример.

Функция задана таблицой истинности :

x1	x2	x3	f

Минимизируем графическим методом :

111 110

_{011 010}

f ( x₁, x₂, x₃ ) = x₂x₃ + ₁x₂ + _{2 3}

_{101 100}

001 000

Реализуем функцию в базисе В₆ = { у₆, у₇ }

у₆(x₁, x₂) = x₁ Å x₂

y₇(x₁, x₂) = x₁ x₂

^{x1 x1}

^x2 _у6 ^{x2 1} _у9

Выразим в заданном базисе функцию отрицания у₆(x, 1) =

Выразим функцию конъюкции у₆ (y₇(y₆, 1), у₆(x₂, 1),1) = x₁x₂

Запишем выражение искомой функции

f ( x₁, x₂, x₃ ) = y₇ [у₆ (y₇(y₆(x₂, 1), y₆(x₃, 1)),1),y₆(y₇(x₂,x₃),1), y₆(y₇(x₁, y₆(x₂,1)),1)];

Построим схему данной функции :

_{1 1}

_{x2 11}

^{1 1} _{f ( x1, x2, x3 )}

_{x3 1}

¹

₁

_x2 ¹

^x3 ₁

¹

_x2 ^{1 1}

x3

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

Для синтеза схем с большим числом переменных существуют более эффективные методы. Один из них :

МЕТОД КАСКАДОВ.

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

f(x₁, … , x_n) = _i f(x₁, …, x_i-1,Æ,x_i+1, …, x_n)+f (x₁, …,x_i-1,1,x_i+1,…, x_n ) =

= _i f ( Æ ) + x_i f( 1 )

Эту функцию можно реализовать следующей схемой :

_f1

^&

_xi

_{1 f}

_&

^f0

Это устройство – каскадный элемент, который на схемах обозначают в следующем виде :

_{f1 &}

₁

_{x1 & f}

_f0

С помощью данного каскада получено представление от n аргументов, через остат-ные функции f₀ и f₁ для функций от n-1 аргумент, с помощью искл. х_i перемен.

На втором шаге каскада реализуется искл. следующая перемен. И далее поступая также мы получим остат – ные функции.

Это – каскадный метод – при этом каждый каскад соответствует исключению некоторой переменной. Для одной и той же функции можно получить несколько реализаций. Число реализаций равно :

N ( N - 1)( N – 2) - … = n!

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

Поэтому для метода должна быть найдена эффективная стратегия. Это позволяет сделать аппарат произв – ных от булевых функций. Пр – ная от функции n-аргументов.

=f (x₁,…, x_i-1,Æ,x_i+1,…, x_n)Åf (x₁, …, x_i-1,1,x_i+1, …, x_n)

Пример :

Найти пр-ную от функции двух переменных

f (x₁,x₂) = x₁ + x₂

= x₂ Å (1 + x₂) = ₂

Повторные пр-ные определяются следующим образом :

= ( ) и т. д.

Пр-ная от булевой функции определяет условия при которых функция зависит от х_i

f (x₁,…, x_i-1,Æ,x_i+1,…, x_n) ¹ f (x₁, …, x_i-1,1,x_i+1, …, x_n) т.е. при изменении х_i меняется значение функции. ( функция зависит от перем.)

Если пр-ная равна 0, то функция от х_i не зависит, т.е. при изменении х_i значение функции не меняется.

Рассмотрим пример:

f (x₁, x₂, x₃, x₄) = x₁x₂x₃ + ₁х₄ + x₂x₃ + x_{1 3}x₄

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

= ( ₁х₄ +х₁х₄) Å (х₁х₂ + ₁х₄ +х₂) = х₄ Å ( х₂+ ₁х₄) =

= х_{4 2 1}х₄ + ₄ ( х₂+ ₁х₄ ) = х_{4 2} (х₁+ ₄) + ₄х₂ = ₄х₂ + х_{4 2}х₁

Ответом на поставленную задачу будут значения х₁, х₂ , х₄ при которых

= 1.

Составим соответствующую таблицу:

х1	х2	х4

х1	х2	х4

На этих наборах функция зависит от переменной х₃.

Первый шаг каскадной реализации.

_{х1 & & 1}

^х4

_&

_f0

f₀ ( x₁,x₃,x₄ ) = ₁ + _{3 4} + x₃x₄ = ₁ +

Введем определение :

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

Запишем утверждение :

Чем больше состояний имеет функция, прикоторых она зависит от x_i, тем сильнее она зависит от этой переменной.

Для примера выясним от какой переменной функция зависит сильнее.

f ( x₁, x₂, x₃,x₄ ) = x₁x₂x₃ + ₁x₄ + x₂x₃ + x_{1 3}x₄

W ( ) = 3

= ( x₄ +x₂x₃ ) Å (x₂x₃ + ₃x₄ )

х1	х2	х4

W ( ) = 1

= ( ₁x₄ + x_{1 3}x₄ ) Å ( x₁x₃ + ₁x₄ + x₃ + x_{1 3}x₄ ) =(x_{4 1} + x_{4 3}) Å ( x₃ + x₄ )

х1	х2	х4

W ( ) = 3

=(x₁x₂x₃ + x₂x₃)Å(x₁x₂x₃ + ₁ + x₂x₃ + x_{1 3}) = x₂x₃Å(x₂ + ₁ + ₃ )

х1	х2	х4

W ( ) = 5

Оказалось, что сильнее всего функция зависит от переменной х₄. При этом видно, что чем сильнее зав-ть функции, тем меньше сложность ост-ной функции при ее искл-нии.

Для функции заданной таблично удобно использовать следующий метод определения веса производной:

Рассмотрим на примере :

Функция от четырех переменных задана таблицей истинности :

х1	х2	x3	x4	f

Для заданной функции определить веса производных по х₁, х₂, х₃, х₄.

x2	x3	x4			d

Cтолбцы 1 и 0 заполняются следующим образом :

Вместо искл. переменной в каждый набор подставляются значения 1 или 0 и выписывают соотв. стб. знач. Функции из исходной таблицы.

Столбец d получается сложением по mod 2 соотв. знач. стб. 1 и 0.

W₁ = 5

x₂ :

x1	x3	x4			d

W₂ = 3

x₃ :

x1	x2	x4			d

W₃ = 3

x₄ :

x1	x2	x3			d

W₄ = 5

Анализ производных показал, что для данного примера первыми исключ-ми переменными будут х₁ и х₄.

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

f ( x₁, x₂, x₃, x₄, x₅ ) = x_{1 2}x₃ + _{1 3}x₄ + x₁x_{3 5} + x₁x₂x₄ + ₂x₃x₅ + _{3 4}x₅

Для данного примера на картах Карно определим веса производных и первую искл. переменную. Затем на картах Карно определим вторую исключаемую переменную и т.д., а затем по полученным данным построим принц. Схему функции.

X₁X₂ x₃X₄X_{5 001 011 010 110 111 101 100}

W₁ = 7 ; W₂ = 5 ; W₃ = 9 ; W₄ = 5 ; W₅ = 7 ;

Первая искл. переменная х₃

Рассмотрим карту Карно для остальных функций : f ( 1 ) f ( 0 )

X₁X₂ X₄X_{5 00 01 11 10}

f (0) 00

W₁ = 2 ; W₂ = 2 ; W₄ = 4 ; W₅ = 4 ;

X₁X₂ X₄X_{5 00 01 11 10}

f (1) 00

W₁ = 5 ; W₂ = 3 ; W₄ = 1 ; W₅ = 3 ; Искл. х₁

Второй искл. переменной - х₄ или х₅.

Получим f (1,0) f (1,1).

x₂ x₄ x_{5 00 01 11 10}

0
1

f₁₁ = ₂ + ₅ + x₄ = + x₄

x₂ x₄ x_{5 00 01 11 10}

0
1

f₁₀ = ₂ x₅

Функции f(0,0) и f(0,1) получ. искл. х₄.

f₀₀ = х₅ f₀₁ = ₁ + х₂

По имеющимся данным строим принц. схему каск. метода :

^{f 00}

^{& 1}

₁ ^x4 _{f 0 & 1}

^& f 01

_{f 10 x3 f}

^{x4 & & 1} _{f 1} ^&

^{x5 x1}

^&

^{x4 &} _{f 11}

f₀₀ = х₅ f₀₁ = ₁ + х₂