Конечный автомат

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

• Компаратор + отрицательная обратная связь —————-> усилитель с регулируемым усилением.
• Компаратор + положительная обратная связь —————-> компаратор с гистерезисом
• Комбинационная логика + положительная обратная связь-> мультивибратор

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

• Система измерения + отрицательная обратная связь —-> система управления с обратной связью

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

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

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

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

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

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

Имея 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 10 10 1101 -------> 1111 13 1011 1110 -------> 1010 14 1001 1111 -------> 1110 15 1000 

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

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

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

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

 Адрес -----> Адрес данных -----> Данные 00000 -------> 0001 10000 -------> 0001 00001 -------> 0010 10001 -------> 0011 00010 -------> 0011 10010 -------> 0110 00011 -------> 0100 10011 -------> 0010 00100 -------> 0101 10100 -------> 1100 00101 -------> 0110 10101 -------> 0100 00110 -------> 0111 10110 -------> 0111 00111 -------> 1000 10111 -------> 0101 01000 -------> 1001 11000 -------> 0000 01001 -------> 1010 11001 -------> 1000 01010 -------> 1011 11010 -------> 1011 01011 -------> 1100 11011 -------> 1001 01100 -------> 1101 11100 -------> 1101 01101 -------> 1110 11101 -------> 1111 01110 -------> 1111 11110 -------> 1010 01111 -------> 0000 11111 -------> 1110 

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

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

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

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

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

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

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