Элементы теории конечных автоматов
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Автомат называется Комбинационным, если выходной сигнал зависит только от входного сигнала. Функция его переходов в комбинационном автомате вырождена, а функция выходов имеет вид:

 

Автомат называется Логическим, если его входной алфавит состоит из логических слов длиной , а выходной алфавит состоит из логических слов длиной .

Функция выходов логического автомата является системой логических функций от Переменных.

Для задания структурных схем таких автоматов используют элементарные схемы, называемые Вентилями. Некоторые элементарные булевы функции представлены в таблице 7.1.

Таблица 7.1.

Название и изображение вентиля

Булево выражение

Схемы в базисе «И-НЕ»

«И»

«ИЛИ»

«ИЛИ-НЕ»

Исключающее «ИЛИ»

В схемах символ означает отрицание. Из таблицы видно, что любую логическую функцию выходов можно сформировать из элементов, реализующих «И» и «НЕ». Точно так же можно реализовать схемы в базисе «ИЛИ» - «НЕ» или «ИЛИ», «И» и «НЕ».

Если рассмотреть функции четырех переменных, то можно использовать параллельно по два двухвходовых элемента. Так, реализацию функции можно представить в базисе «И» - «НЕ» в виде, как представлено на рис. 7.21.

Рис. 7.21. Реализация функции в базисе «И» - «НЕ»

Рисунки с изображениями вентелей называются логическими диаграммами. Комбинационная схема не обладает запоминающими свойствами. Значения на ее выходах постоянно определяются значениями на входах в текущий момент времени.

Если автомат не может быть представленным как комбинационный, то он носит название Последовательностного.

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

Рассмотрим простейший из возможных случаев, когда множество входных и выходных сигналов и состояния состоят из одного единственного элемента:

Предположим также, что функция выхода имеет простейший вид, а именно Таким образом, функция перехода Являются рекуррентной функцией только двух аргументов - И Если интерпретировать Как независимый второй аргумент, то на возможных четырех наборах можно, как мы уже знаем, набрать 16 различных функций. В теории автоматов прикладной интерес представляют только четыре из них (см. табл. 2.3) - . (табл. 7.2).

Таблица 7.2. Таблицы переходов одновходных триггеров

0

0

0

1

0

1

0

1

0

1

1

0

1

0

1

0

1

0

1

1

1

0

0

1

Очевидно, что функция есть инверсия , а является инверсией Из таблицы видно, что Соответствует автомату, который имеет лишь одну переменную состояния, который принимает значение 0 или 1 в соответствии с законом, указанным в таблице. Такой автомат в технике называют D-триггером (delаy – задержка, trigger – спусковой крючок). Аналогично, функции Или являются таблицей переходов автомата с одной переменной, который называется Т-триггером (toggle - крутиться).

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

для D – триггера

для Т – триггера

Вспоминая, что функция выхода для триггера равна Можно видеть, что для D – триггера значения выхода триггера будут задерживаться (запаздывать) на один такт относительно состояния, а значения выхода для Т – триггера при постоянном входе будут постоянно меняться.

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

Которая содержит три аргумента. Таких логических функций всего 64, но только некоторые из них нашли применение в технике.

Рассмотрим первый из них – RS – триггер, для которого множество входных сигналов состоит из двух элементов А состояния определяются как переменная q. Аналитическая форма функции переходов имеет вид:

А таблица истинности для состояний такова:

 

1

0

0

0

0

2

0

0

1

1

3

0

1

0

1

4

0

1

1

1

5

1

0

0

0

6

1

0

1

0

7

1

1

0

---

8

1

1

1

---

Видно, что только в строках 3-6 происходит изменение состояния триггера. В связи с этим входы триггера называют установочными: Устанавливают триггер в 1, Устанавливает в 0. Естественно поэтому одновременная подача двух установочных входных сигналов запрещена.

Другой триггер для двух входных сигналов - это JK – триггер. (Резкий толчок, Убивать). Можно считать, что Триггер – это обобщение Триггера, а его входы И Являются аналогами входов И . Это видно из таблицы переходов:

 

1

0

0

0

0

2

0

0

1

1

3

0

1

0

0

4

0

1

1

0

5

1

0

0

1

6

1

0

1

1

7

1

1

0

1

8

1

1

1

0

Принципиальное отличие в том, что одновременно можно на вход подавать сигналы «1». В этом случае триггер изменит свое состояние на противоположное. Таким образом, установка в состояние «1» происходит с помощью сигнала (строки 5 и 7), а в состояние «0» - с помощью сигнала (строки 4 и 8).

Все триггеры могут быть представлены в виде схем, например, в базисе «И-НЕ» рис. 7.22 – 7.24.

Рис. 7.22. Схема реализации Т – триггера в базисе «И-НЕ».

Рис. 7.23. Схема реализации Триггера в базисе «И-НЕ»

Рис.7.24. Схема реализации Триггера с помощью Триггера

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

Добавить комментарий


Защитный код
Обновить