38. Синтез комбинационных автоматов в заданном базисе

Синтез комбинационных автоматов.

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

Синтез переключательной схемы.

Пусть задана переключательная функция Получим переключательную схему (рис. 57).

Рис. 57. Переключательная схема,

реализующая функцию

На рис. 57 верхняя и нижняя горизонтальные линии обозначают, например, полюсы источника питания, а буква F – некоторый элемент, срабатывающий в случае равенства функции логический единице, т.е. в случае наличия цепи к верхнему полюсу. Символами переменных х₁,х₂,х₃ могут обозначаться, например, контакты некоторых датчиков, а F – обмотка реле, контакт которого включает некоторый исполнительный орган (вентилятор, сирену, нагреватель и др. элементы автоматики). Соответствующая релейно-контактная схема изображена на рис. 58.

Часто датчики подключаются не непосредственно в цепи реализации переключательных функций, а через реле-повторители (рис. 59).

Рис. 58. Релейно-контактная схема

реализации логической функции

Рис. 59. Релейно-контактная схема реализации переключательной функции с реле-повторителями сигналов датчиков

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

Синтез в базисе И, ИЛИ, НЕ.

Наиболее просто это сделать, если задать базис И, ИЛИ, НЕ. Предполагается, что переключательная функция представлена в ДНФ.

Пусть, например, задана следующая переключательная функция: z(аbсdx₂x₁)=

Получим схему в базисе И, ИЛИ, НЕ (рис. 60).

Рис. 60. Схема в базисе И, ИЛИ, НЕ без ограничения числа входов

функциональных элементов

Схема рис. 60 изображена в предположении, что число входов элементов не ограничено.

Если же должны использоваться только двухвходовые элементы, т.е. все операции бинарные (кроме инверсии), то схема будет выглядеть так, как изображено на рис. 61.

Рис. 61. Схема с учетом наличия только двухвходовых элементов И, ИЛИ

Синтез методом каскадов.

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

f(x₁,...,x_i,...,x_n)=x_if(x₁,...,1,...,x_n)Ú_if(x₁,...,0,...,x_n)=x_if(1)Ú_if(0).

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

Реализуем вышерассмотренную функцию z(аbсdx₂x₁) методом каскадов с использованием блоков исключения переменной вида x_if(1)Ú _if(0), которые легко реализуются в базисе И, ИЛИ, НЕ.

Очевидно, что:

z(аbсdx₂x₁)=,

т.е. ,, которые реализуются на двухвходовых элементах И, ИЛИ. Проводить дальнейшее разложение нет необходимости. Соответствующая схема комбинационного автомата изображена на рис. 62.

Рис. 62. Схема, построенная по методу каскадов

Интересно, что схема на рис. 62, построенная по методу каскадов, проще в смысле числа элементов – для ее построения необходимо 11 элементов (9 двухвходовых и 2 инвертора). Сравните ее со схемой на рис. 61, для построения которой потребовалось 13 элементов (11 двухвходовых и 2 инвертора).

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

=f(x₁,x₂,...,x_i-1,1,x_i+1,...,x_n)Åf(x₁,x₂,...,x_i-1,0,x_i+1,...,x_n),

где Å – сумма по модулю 2 [9].

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

Например, в импликативном базисе {®,0}:

=(а®(b®0))®0.

Синтез в базисах И-НЕ, ИЛИ-НЕ.

Наиболее часто используются базисы, состоящие из одной функции: И-НЕ, ИЛИ-НЕ.

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

f(аbсd)===– это представление в базисе И-НЕ.

–это представление в базисе ИЛИ-НЕ.

Соответствующие схемы представлены на рис. 63.

Рис. 63. Реализация логической функции f(аbсd)=

в базисе 2И-НЕ (а) и 2ИЛИ-НЕ (б),

т.е. для двухвходовых элементов И-НЕ, ИЛИ-НЕ

В случае превышения ограничения по числу входов элементов следует еще раз применить закон Де Моргана, например:

т.е. получили только одноместные и двухместные операции И-НЕ.

Синтез в базисе Жегалкина.

Полиномом Жегалкина называется представление логической функции в базисе {Å,И,НЕ} (имеется соответствующая алгебра Жегалкина). В данном представлении инверсия реализуется как сумма по модулю 2 с константой 1.

Для представления ДНФ в виде полинома Жегалкина необходимо выразить дизъюнкцию через конъюнкцию и инверсию.

Например:

хÚy==(хÅ1)(yÅ1)Å1=

=xyÅxÅyÅ1Å1=xyÅxÅy.

(1Å1=0).

Пример. Представить в виде полинома Жегалкина логическую функцию xÚyÚz.

xÚyÚz==(хÅ1)(yÅ1)(zÅ1)Å1=(xyÅxÅyÅ1)(zÅ1)Å1=

=xyzÅxzÅyzÅxyÅxÅyÅ1Å1=xyzÅxzÅyzÅxyÅxÅy.

Для преобразования полинома Жегалкина используются обычные приемы элементарной алгебры (исключение составляет равносильность аÅа=0).

Полином Жегалкина может быть получен по таблице истинности путем суммирования по модулю 2 конъюнкций переменных без инверсии x_i или инверсных переменных (x_jÅ1) соответствующих рабочих наборов.

Например, получим полином Жегалкина для функции f, таблица истинности которой имеет вид табл. 54.

Таблица 54

Таблица истинности

Тогда получим:

f=(xÅ1)(yÅ1)zÅ(xÅ1)y(zÅ1)Åx(yÅ1)(zÅ1)Åxyz=

=(xyÅxÅyÅ1)zÅ(xzÅxÅzÅ1)yÅx(yzÅyÅzÅ1)Åxyz=

=xÅyÅz,

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