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

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

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₀₁ = ₁ + х₂