Структурные автоматы (стр. 3 из 6)
2.4 Построение уравнений булевых функций возбуждения и выходов автомата
Кодирование и выбор системы элементов однозначно определяют комбинационную часть автомата: вначале строится таблица истинности функций возбуждения элементов памяти автомата, получившая название таблицы функций возбуждения; канонические уравнения функций возбуждения выписываются исходя из построенной таблицы. Полученная аналитическая запись булевой функции возбуждения (для каждого элемента памяти автомата) может быть минимизирована любым из известных методов. Исходными данными для построения таблицы функций возбуждения являются структурная таблица переходов автомата и таблица переходов элемента памяти. Обрамление таблицы функций возбуждения, т.е. идентификация ее строк и столбцов полностью совпадает с обрамлением структурной таблицы переходов синтезируемого автомата. Клетки, расположенные внутри таблицы функций возбуждения, заполняются специальным образом.
Рисунок 2- Структурная схема автомата Мура
Рисунок 3- Структурная схема автомата Мили
Получение канонических уравнений булевых функций выходов структурного автомата проще и может быть сделано непосредственно по структурной таблице выходов автомата. Структурная таблица выходов автомата есть таблица истинности булевых функций выходов автомата. Иными словами, уравнения булевых функций выходов автомата не зависят от типа используемых элементов памяти, однако зависят от их количества.
Если синтезируемый автомат является автоматом Мура, то задача построения уравнений булевых функций возбуждения решается так же. Уравнения булевых функций выходов автомата Мили строятся несколько иначе. Последнее связано с различиями в способах построения структурных таблиц выходов автомата Мили и Мура. После проведения этапа кодирования состояний автомата и кодирования выходных сигналов получаем структурную таблицу выходов автомата, которая является таблицей истинности булевых функций выходов автомата.
2.5 Построение функциональной схемы автомата
На основании полученных выражений для булевых функций возбуждения элементов памяти автомата и булевых функций выходов автомата строятся комбинационная схема функций возбуждения и комбинационная схема формирования выходных сигналов автомата. Элементы памяти подключаются к построенным комбинационным схемам. Функциональная схема автомата Мура отлична только комбинационной схемой формирования выходных сигналов, которая строится на основании уравнений для булевых функций выходов. Отметим, что реализация комбинационных схем может быть выполнена в любом функционально-полном базисе.
3. Пример канонического метода структурного синтеза
Пусть задан абстрактный автомат Мили таблицей переходов и выходов (табл. 7.). Используя логические элементы И, ИЛИ, НЕ и элементарный автомат Мура (элемент памяти), заданный табл. 8.
Таблица 7.
| А\ Х | x1 | x2 | x3 |
| a1 | a2/y3 | a3/y4 | a2/y2 |
| a2 | - | a1/y3 | a3/y1 |
| a3 | a1/y2 | - | a3/y3 |
| А\ Х | x1 | x2 | x3 |
| a1 | a2/y3 | a3/y4 | a2/y2 |
| a2 | - | a1/y3 | a3/y1 |
| a3 | a1/y2 | - | a3/y3 |
Таблица 8
| r1 | r2 | |
| b1 | b1 | b2 |
| b2 | b2 | b1 |
Выполним кодирование алфавитов автомата (табл. 7.)
Выпишем алфавиты автомата и определим длины векторов кодов алфавитов:
Х = {x1, x2, x3}; Kвх >= int(log2|3|)= 2,
У = {y1, y2, y3, y4}; Kвых >= int(log2|3|)= 2,
А = {a1, a2, а3}; Kсост >= int(log2|3|)= 2.
Заполним таблицы кодирования (табл. 9 – 11):
Таблица 9.
| Х | z1 | z2 |
| x1 | 0 | 0 |
| x2 | 0 | 1 |
| x3 | 1 | 0 |
Таблица 10
| У | w1 | w2 |
| y1 | 1 | 0 |
| y2 | 0 | 0 |
| y3 | 1 | 1 |
| y4 | 0 | 1 |
Таблица 11
| А | 1 | 2 |
| a1 | 0 | 0 |
| a2 | 0 | 1 |
| a3 | 1 | 1 |
Каждый разряд вектора кода обозначим символом с соответствующим номером. Входные - z, выходные - w, состояния – а.
Таблица 12
| z1z2 | |||
| 12 | 00 | 01 | 10 |
| 00 | 01/11 | 11/01 | 01/00 |
| 01 | - | 00/11 | 11/10 |
| 11 | 00/00 | - | 11/11 |
В результате получим таблицу переходов и выходов структурного автомата (табл. 12.). Выполним кодирование элементарного автомата Мура (табл. 8.):
- выпишем алфавиты автомата и определим длины векторов кодов алфавитов,
R={r1,r2}; Kвх >= int(log2|2|)=1,
В = {b1, b2}; Kсост >= int(log2|2|)= 1;
-заполним таблицы кодирования:
Структурная таблица переходов элементарного автомата Мура имеет вид (табл. 15.):
Так как абстрактный автомат имеет три состояния, каждое из которых кодируется двумя разрядами, то структурный автомат будет содержать два запоминающих элемента.
Теперь задача сводится к синтезу комбинационной схемы, реализующей канонические уравнения:
w1=l(a1,a2.z1,z2), w2= l(a1, a2, z1, z2) - функции выходов автомата
j1= f(a1,a2.z1,z2), j2= f(a1,a2.z1,z2) - функции возбуждения элементов памяти автомата.
Функции w1, w2 можно получить непосредственно из отмеченной таблицы переходов структурного автомата как дизъюнкцию конъюнкций, соответствующих тем наборам (1,2.z1,z2), на которых эти функции принимают значения 1. Но более удобно пользоваться так называемой таблицей формирования функций возбуждения и функций выходов автомата, в которой в табличной форме задана система булевых функций (табл. 16). Заполним эту таблицу, используя коды соответствующих алфавитов и таблицу переходов и выходов абстрактного автомата. Для заполнения колонок j1, j2 необходимо воспользоваться еще и таблицей элемента памяти (табл. 15).
Для заполнения функций возбуждения элементов памяти рассматривается переход из исходного состояния (12) в состояние перехода (12). За первый разряд 1 отвечает первый элемент памяти (его функция j1), за второй 2 - второй элемент памяти (его функция j2).
В таблице проставляется значение входного сигнала, который обеспечивает соответствующий переход. Количество функций возбуждения элементов памяти автомата зависит от количества разрядов вектора кода состояния и от количества информационных входов самого запоминающего элемента. Рассмотрим, например, что будет со структурным автоматом, если он находится в состоянии 01, и на его вход поступил сигнал 10.
Как видно из таблицы переходов структурный автомат перейдет в состояние 11. Этот переход складывается из двух переходов элементов памяти: 1-й из 0 в 1, 2-й из 1 в 1. По таблице 15 определим входные сигналы элемента памяти, обеспечивающие эти переходы: это 0 и 1., и т.д. В клетку соответствующего перехода запишем вектор функции возбуждения, вызывающий данный переход.
Таблица 16.
| Исходное состояние | Входной сигнал | Состояние перехода | Функции возбуждения эл-в памяти | Выходной сигнал | |||||
| a1 | a2 | z1 | z2 | a1 | a2 | j1 | j2 | w1 | w2 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | ||
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | ||
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | ||
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | ||
По таблице 16 запишем аналитические выражения канонических уравнений:
 Z1Z2 |
Рисунок 4- Структурная схема автомата
Не занимаясь минимизацией канонический уравнений, построим схему электрическую функциональную (рис. 5).