Абстрактный конечный автомат
Автоматом называется дискретное устройство способное принимать различное состояние под воздействием входных сигналов, переходить из одного состояния в другое и вырабатывать выходные сигналы.
Наибольшее распространение получили два вида автоматов:
· автомат Мили.
· автомат Мура.
Различие между этими автоматами состоит в том, что выходной сигнал в автомате Мили зависит как от предыдущего состояния, так и от входного воздействия. В то время как в автомате Мура выходной сигнал зависит только от состояния в рассматриваемый момент времени.
Для анализа и синтеза автоматов используются чаще всего таблицы переходов и таблицы выходов, так как по формулам трудно составить алгебру работы, то есть четкое входное воздействие и соответствующий выходной сигнал. Это своего рода таблицы истинности, но несколько своеобразной формы представления.
В синхронном автомате осуществляется синхронизация внешних и внутренних сигналов.
Синтез абстрактного автомата заключается в получении таблицы переходов и таблицы выходов или графа. Далее осуществляется структурный синтез, цель которого состоит в построении схемы, реализующей автомат. В структурной теории автомат представляется как совокупность двух частей: памяти и комбинационной схемы [3].
По заданию необходимо разработать синхронный конечный автомат, заданный таблицей переходов (таблица 5) и таблицей выходов (таблица 6).
Для синтеза схемы применяются D-триггеры и логические элементы базиса И-ИЛИ-НЕ. Синтез производится графическим методом.
Таблица 5
a1 | a2 | |
S0 | S1 | S0 |
S1 | S2 | S1 |
S2 | S0 | S3 |
S3 | S3 | S4 |
S4 | S4 | S2 |
a1 | a2 | |
S0 | ||
S1 | ||
S2 | ||
S3 | ||
S4 |
Исходя из таблицы переходов, в автомат поступает два входных сигнала (а1 и а1). Зашифруем входные сигналы с помощью переменной X, которая может принимать два значения: 1 - соответствует входному сигналу а1, 0 - соответствует входному сигналу а2.
Исходя из таблиц переходов и выходов, автомат имеет 5 внутренних состояний (S0, S1, S2, S3 и S4). Зашифруем эти состояния с помощью переменных b1, b2 и b3, которые могут принимать значения 1 или 0. Обозначим S0 как 000, это означает, что и так далее. Соответствие между внутренними состояниями и переменными b1, b2, b3 приведено в таблице 7.
Исходя из таблицы выходов, автомат имеет два выходных состояния (1 и 0).
Зашифруем выходные сигналы с помощью переменной Y, которая может принимать два значения: 1 - соответствует выходному состоянию 1, 0 - соответствует выходному состоянию 0. Так как в качестве памяти используются D-триггеры, то при переходе из одного внутреннего состояния в другое при изменении переменной bi с 0 на 1 или с 1 на 1 на i-ый вход D-триггера должна подаваться единица. Данное положение отражается на графе автомата.
Таблица 7
b1 | b2 | b3 | |
S0 | |||
S1 | |||
S2 | |||
S3 | |||
S4 |
Представим автомат в виде графа (рисунок 10). Цифры в кружках обозначают внутренние состояния.
Рис. 10. Граф автомата
В результате проведенного кодирования и отметки дуг графа символами Dbi, x, y, определяются функции возбуждения и выходов автомата:
Таким образом, все функции определены. Так как автомат синхронный, то дополнительно вводятся цепи синхронизации. Обозначим синхронизирующий сиграл С(t), тогда полученные функции примут вид:
Входной сигнал также должен быть синхронизирован:
Схема синхронного конечног автомата строится с использованием шин для облегчения построений.
Схема электрическая принципиальная приведена в приложении 3. Для построения дискретного устройства применяются микросхемы транзисторно-транзисторной логики серии К555.
Заключение
Во время работы над проектом были получены навыки синтеза дискретных устройств, таких как генераторы, счетчики, дешифраторы, мультиплексоры, регистры сдвига и делители частоты. Освоены методы минимизации функций алгебры логики. Разработан абстрактный автомат.
При выполнении данного курсового проекта особое внимание уделялось правильному обозначению элементов - использовался ГОСТ. Был проведен подбор радио электрических и электронных компонент в соответствии с поставленными задачами.
Список литературы
1. Электронные устройства железнодорожной автоматики, телемеханики и связи. Под ред. А.В. Шилейко. М.: Транспорт, 1989.-327 с.
2. Электротехника и электроника. Под ред. Проф. В.Г. Герасимова. М.: Энергоиздат, 1998. - 432 с.
. Интегральная схемотехника. Мулярчик С.Г. Мн.: Изд-во БГУ, 1983-189 с.
. Методические указания для выполнения курсового проекта «Синтез дискретных устройств». К.А. Бочков, T. В. Кострома, А.Н. Семенюта. Гомель изд-во БелГУТа 1991.