50267 (Структурные автоматы), страница 2

5. Построение функциональной схемы автомата.

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

1. 2.1 Кодирование алфавитов автомата

На структурном уровне каждая буква входного алфавита x Х, каждая буква выходного алфавита y Y и каждая буква алфавита состояний а А кодируется двоичными векторами (двоичными наборами), число компонент которых определяется следующим образом:

K_вх >= int(log₂|X|); K_вых >= int(log₂|Y|); K_сост>=int(log₂|A|);

где int - ближайшее большее целое число.

|Х|, |У|, |А| - мощность алфавита входного, выходного и состояний, соответственно. Мощностью алфавита называется количество различных символов входящих в этот алфавит.

Процесс замены буква алфавита (X, У, А) абстрактного автомата двоичными векторами носит название кодирования и описывается таблицами кодирования. Таблица кодирования имеем следующий вид: в левой части перечисляются все символы абстрактного алфавита, а в правой - соответствующие им двоичные векторы.

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

Абстрактный автомат Мили задан таблицей переходов и выходов (табл. 2.). Выполнить кодирование алфавитов автомата.

Таблица 2

А\ Х	x1	x2
a1	a2/y1	a3/y3
a2	a1/y2	a2/y1
a3	a2/y2	a1/y1

Выпишем алфавиты автомата и определим длины векторов кодов алфавитов:

X={x₁,x₂}; K_вх >= int(log₂|2|)=1,

Y={y₁,y₂,y₃}; K_вых >= int(log₂|3|)=2,

A={a1,a2,a3}; K_сост >= int(log₂|3|)=2.

Заполним таблицы кодирования:

Таблица 3

x1	0
x2	1

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

Таблица 6.

А\ X	0	1
00	01/00	10/10
01	00/01	01/00
10	01/01	00/00

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

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

2. 2.2 Выбор элементов памяти автомата

Замена таблицы переходов автомата на структурную таблицу переходов приводит к тому, что функция переходов (а_i,x_j) автомата становится векторной. Иными словами, аргументами такой функции являются все возможные пары двоичных векторов (a_i,x_j), а сама функция принимает значение из множества A двоичных векторов состояний автомата. В соответствии со структурной таблицей переходов автомата его векторная функция переходов каждой паре двоичных векторов ставит в соответствие определенный двоичный вектор a_k, что на абстрактном уровне определяется соотношением а_k = (а_i,х_j). Из этого следует, что структурный автомат должен запоминать двоичный вектор каждого очередного состояния автомата, для чего служат элементы памяти (запоминающие элементы, триггеры).

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

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

Полнота системы выходов означает, что различным состояниям автомата соответствуют различные выходные сигналы. Обычно нулевому состоянию элементарного автомата соответствует нулевой выходной сигнал, единичному - единичный.

Очевидно, что число элементов памяти структурного автомата равно числу компонент вектора его состояний.

2. 2.3 Выбор функционально-полной системы логических элементов

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

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

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

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

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

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

Буквами б₁,... б _ц на рисунках обозначены выходы элементов памяти. Буквами ц₁,…, ц _j обозначены булевы функции возбуждения элементов памяти. Для простоты положим, что каждый элемент памяти структурного автомата имеет один информационный вход. Буквами w₁,...,w_j обозначены выходные каналы автомата, где j - число выходных каналов автомата. Буквами z₁,…,z_m – входные каналы.

1. 2.4 Построение уравнений булевых функций возбуждения и выходов автомата

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

Рисунок 2- Структурная схема автомата Мура

Рисунок 3- Структурная схема автомата Мили

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

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

1. 2.5 Построение функциональной схемы автомата

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

1. Пример канонического метода структурного синтеза

Пусть задан абстрактный автомат Мили таблицей переходов и выходов (табл. 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.)

Выпишем алфавиты автомата и определим длины векторов кодов алфавитов: