Электроника:Цифровая электроника/Принципы цифровых вычислений/Конечные автоматы

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Перевод: Макаров В. (valemak) Контакты:</br>* Habr: @vakemak</br>* Сайт: www.valemak.com</br>Перевёл статей: 656.
Проверка/Оформление/Редактирование: Мякишев Е.А.


Конечные автоматы[1]

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

В области контрольно-измерительных приборов обратная связь используется для преобразования простой измерительной системы в управляемую:

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

С таблицами поиска, запрограммированными в устройствах памяти, обратная связь от выходных данных к входным адресам создаёт совершенно новый тип устройства – конечный автомат или КА:

Рис. 1. Простейший конечный автомат – это таблицы поиска с обратной связью от выходов к входам.
Рис. 1. Простейший конечный автомат – это таблицы поиска с обратной связью от выходов к входам.

Приведённая на рисунке 1 выше схема иллюстрирует основную идею: данные, хранящиеся по каждому адресу, становятся следующим местом хранения, к которому обращается ПЗУ. Результатом является определённая последовательность двоичных чисел (после последовательности, запрограммированной в ПЗУ) на выходе с течением времени.

Однако, чтобы избежать проблем с синхронизацией сигнала, нам нужно соединить выходные данные обратно с адресными входами через 4-битный триггер D-типа, чтобы последовательность выполнялась шаг за шагом синхронно с управляемым тактовым импульсом:

Рис. 2. Улучшенный конечный автомат.
Рис. 2. Улучшенный конечный автомат.

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

Имея 16 адресуемых ячеек памяти в ПЗУ, этот конечный автомат будет иметь 16 различных стабильных «состояний», в которых он может зафиксироваться. В каждом из этих состояний идентификатор следующего состояния будет запрограммирован в ПЗУ, ожидая, что сигнал следующего тактового импульса будет возвращён в ПЗУ в качестве адреса. Одним из полезных приложений такого конечного автомата может быть генерация произвольной счётной последовательности, такой как код Грея:

Генерация кода Грея с помощью КА
Адрес → Данные / Счётная последовательность / Код Грея
0000 → 0001 / 0 / 0000
0001 → 0011 / 1 / 0001
0010 → 0110 / 2 / 0011
0011 → 0010 / 3 / 0010
0100 → 1100 / 4 / 0110
0101 → 0100 / 5 / 0111
0110 → 0111 / 6 / 0101
0111 → 0101 / 7 / 0100
1000 → 0000 / 8 / 1100
1001 → 1000 / 9 / 1101
1010 → 1011 / 10 / 1111
1011 → 1001 / 11 / 1110
1100 → 1101 / 12 / 1010
1101 → 1111 / 13 / 1011
1110 → 1010 / 14 / 1001
1111 → 1110 / 15 / 1000

Попробуйте следовать последовательности счёта кода Грея, как это сделал бы КА: начиная с 0000, следуйте данным, хранящимся по этому адресу (0001), до следующего адреса и так далее (0011), и так далее (0010), и так далее (0110) и т.д. Результатом для показанной таблицы в программе является то, что последовательность адресации скачет от адреса к адресу, что выглядит случайным образом, но когда вы проверяете каждый доступный адрес, вы обнаружите, что он следует правильному порядку для 4-битного кода Грея.

Когда КА достигает своего последнего запрограммированного состояния (адрес 1000), данные, хранящиеся там, имеют номер 0000, что запускает всю последовательность заново с адреса 0000 синхронно со следующим тактовым импульсом.

Мы могли бы расширить возможности приведённой выше схемы, используя ПЗУ с бо́льшим количеством адресных строк и добавив больше данных для программирования:

Рис. 3. Бо́льшее количеством адресных строк ПЗУ.
Рис. 3. Бо́льшее количеством адресных строк ПЗУ.

Теперь, точно так же, как схема сумматора с таблицей поиска, которую мы превратили в арифметико-логическую единицу (функции +, -, ×, /), используя больше адресных строк в качестве входных данных для «управления функциями», этот счётчик КА можно использовать для генерации более чем одной счётной последовательности: другой последовательности, запрограммированная для четырёх битов обратной связи (от A0 до A3) для каждой из двух комбинаций входных сигналов линии управления функциями (A4 = 0 или 1).

Больше адресных строк в качестве входных данных для «управления функциями»
Адрес → Данные
00000 → 0001
00001 → 0010
00010 → 0011
00011 → 0100
00100 → 0101
00101 → 0110
00110 → 0111
00111 → 1000
01000 → 1001
01001 → 1010
01010 → 1011
01011 → 1100
01100 → 1101
01101 → 1110
01110 → 1111
01111 → 0000
Адрес → Данные
10000 → 0001
10001 → 0011
10010 → 0110
10011 → 0010
10100 → 1100
10101 → 0100
10110 → 0111
10111 → 0101
11000 → 0000
11001 → 1000
11010 → 1011
11011 → 1001
11100 → 1101
11101 → 1111
11110 → 1010
11111 → 1110

Если A4 равен 0, КА считает в двоичном формате; если A4 равен 1, КА считает по коду Грея. В любом случае последовательность подсчёта произвольна: определяется прихотью программиста. Если уж на то пошло, последовательность подсчёта даже не обязательно должна состоять из 16-ти шагов, так как программист может решить, что последовательность будет сводиться до 0000 на любом из шагов вообще. Это полностью гибкое счётное устройство, поведение которого строго определяется программным обеспечением (программированием) в ПЗУ.

Мы можем ещё больше расширить возможности КА, используя микросхему ПЗУ с дополнительными адресными линиями ввода и вывода данных. Возьмём, к примеру, следующую схему:

Рис. 4. ПЗУ с дополнительными адресными линиями ввода и вывода данных.
Рис. 4. ПЗУ с дополнительными адресными линиями ввода и вывода данных.

Здесь выходные данные с D0 по D3 используются исключительно для обратной связи с адресными линиями от A0 до A3. Линии вывода даты с D4 по D7 можно запрограммировать на вывод чего-то другого, кроме значения «состояния» КА. Поскольку четыре бита вывода данных возвращаются к четырём битам адреса, это всё ещё устройство с 16-ю состояниями.

Однако наличие выходных данных, поступающих из других линий вывода данных, даёт программисту больше свободы в настройке функций, чем раньше. Другими словами, это устройство может делать гораздо больше, чем просто считать! Запрограммированный выход этого КА зависит не только от состояния адресных линий обратной связи (от A0 до A3), но и от состояния входных линий (от A4 до A7).

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

Теперь у нас есть устройство, которое лучше соответствует значению слова «программируемый». Данные, записанные в ПЗУ, являются программой в самом прямом смысле: выходы следуют заранее установленному порядку, основанному на входах в устройство и на каком «шаге» находится устройство в своей последовательности.

Это очень близко к действующей конструкции машины Тьюринга, теоретического вычислительного устройства, изобретенного Аланом Тьюрингом. Математически доказано, что оно способно решить любую известную арифметическую задачу при достаточном объёме памяти.

См.также

Внешние ссылки