(Новая страница: «{{Панель управления/Электроника}} {{Перевод от valemak}} {{Myagkij-редактор}} =Конечные автоматы<ref>[https://www.allaboutcircuits.com/textbook/digital/chpt-16/finite-state-machine/ www.allaboutcircuits.com - Finite-state Machine]</ref>= Обратная связь – весьма увлекательный инженерный принцип. Она может превратить довольн...»)
Обратная связь – весьма увлекательный инженерный принцип. Она может превратить довольно простое устройство или процесс во что-то принципиально более сложное. Мы видели эффекты обратной связи, преднамеренно интегрированные в схемы, с некоторыми довольно поразительными эффектами:
[[Обратная связь]] – весьма увлекательный инженерный принцип. Она может превратить довольно простое устройство или процесс во что-то принципиально более сложное. Мы видели эффекты обратной связи, преднамеренно интегрированные в схемы, с некоторыми довольно поразительными эффектами:
*Компаратор + отрицательная обратная связь → усилитель с регулируемым усилением.
В области контрольно-измерительных приборов обратная связь используется для преобразования простой измерительной системы в управляемую:
В области контрольно-измерительных приборов обратная связь используется для преобразования простой измерительной системы в управляемую:
*Система измерения + отрицательная обратная связь → система управления с обратной связью.
* [[Система измерения]] + [[отрицательная обратная связь]] → [[система управления с обратной связью]].
Обратная связь, как положительная, так и отрицательная, имеет тенденцию добавлять совершенно новую динамику в работу устройства или системы. Иногда эта новая динамика находит полезное применение, а иногда она просто интересна.
[[Обратная связь]], как положительная, так и отрицательная, имеет тенденцию добавлять совершенно новую динамику в работу устройства или системы. Иногда эта новая динамика находит полезное применение, а иногда она просто интересна.
С таблицами поиска, запрограммированными в устройствах памяти, обратная связь от выходных данных к входным адресам создаёт совершенно новый тип устройства – конечный автомат или КА:
С таблицами поиска, запрограммированными в устройствах памяти, обратная связь от выходных данных к входным адресам создаёт совершенно новый тип устройства – [[конечный автомат]] или КА:
[[File:IV-16_3_1.png|400px|center|thumb|'''Рис. 1.''' Простейший конечный автомат – это таблицы поиска с обратной связью от выходов к входам.|alt=Рис. 1. Простейший конечный автомат – это таблицы поиска с обратной связью от выходов к входам.]]
[[File:IV-16_3_1.png|400px|center|thumb|'''Рис. 1.''' Простейший [[конечный автомат]] – это таблицы поиска с обратной связью от выходов к входам.|alt=Рис. 1. Простейший конечный автомат – это таблицы поиска с обратной связью от выходов к входам.]]
Приведённая на рисунке 1 выше схема иллюстрирует основную идею: данные, хранящиеся по каждому адресу, становятся следующим местом хранения, к которому обращается ПЗУ. Результатом является определённая последовательность двоичных чисел (после последовательности, запрограммированной в ПЗУ) на выходе с течением времени.
Приведённая на рисунке 1 выше схема иллюстрирует основную идею: данные, хранящиеся по каждому адресу, становятся следующим местом хранения, к которому обращается [[ПЗУ]]. Результатом является определённая последовательность двоичных чисел (после последовательности, запрограммированной в [[ПЗУ]]) на выходе с течением времени.
Однако, чтобы избежать проблем с синхронизацией сигнала, нам нужно соединить выходные данные обратно с адресными входами через 4-битный триггер D-типа, чтобы последовательность выполнялась шаг за шагом синхронно с управляемым тактовым импульсом:
Однако, чтобы избежать проблем с синхронизацией сигнала, нам нужно соединить выходные данные обратно с адресными входами через [[4-битный триггер D-типа]], чтобы последовательность выполнялась шаг за шагом синхронно с управляемым тактовым импульсом:
Аналогией работы такого устройства может быть серия почтовых ящиков, каждый из которых имеет идентификационный номер на двери (адрес) и каждый содержит лист бумаги с адресом другого абонентского ящика (данные). Человек, открыв первый абонентский ящик, найдёт в нем адрес следующего абонентского ящика, который нужно открыть.
Аналогией работы такого устройства может быть серия почтовых ящиков, каждый из которых имеет идентификационный номер на двери (адрес) и каждый содержит лист бумаги с адресом другого абонентского ящика (данные). Человек, открыв первый абонентский ящик, найдёт в нем адрес следующего абонентского ящика, который нужно открыть.
Сохраняя определённый шаблон адресов в абонентских ящиках, мы можем диктовать последовательность открытия каждого ящика и, следовательно, последовательность чтения листов бумаги.
Сохраняя определённый шаблон адресов в абонентских ящиках, мы можем диктовать последовательность открытия каждого ящика и, следовательно, последовательность чтения листов бумаги.
Имея 16 адресуемых ячеек памяти в ПЗУ, этот конечный автомат будет иметь 16 различных стабильных «состояний», в которых он может зафиксироваться. В каждом из этих состояний идентификатор следующего состояния будет запрограммирован в ПЗУ, ожидая, что сигнал следующего тактового импульса будет возвращён в ПЗУ в качестве адреса.
Имея 16 адресуемых ячеек памяти в [[ПЗУ]], этот конечный автомат будет иметь 16 различных стабильных «состояний», в которых он может зафиксироваться. В каждом из этих состояний идентификатор следующего состояния будет запрограммирован в [[ПЗУ]], ожидая, что сигнал следующего тактового импульса будет возвращён в [[ПЗУ]] в качестве адреса.
Одним из полезных приложений такого конечного автомата может быть генерация произвольной счётной последовательности, такой как код Грея:
Одним из полезных приложений такого конечного автомата может быть генерация произвольной счётной последовательности, такой как код Грея:
Строка 43:
Строка 43:
Когда КА достигает своего последнего запрограммированного состояния (адрес 1000), данные, хранящиеся там, имеют номер 0000, что запускает всю последовательность заново с адреса 0000 синхронно со следующим тактовым импульсом.
Когда КА достигает своего последнего запрограммированного состояния (адрес 1000), данные, хранящиеся там, имеют номер 0000, что запускает всю последовательность заново с адреса 0000 синхронно со следующим тактовым импульсом.
Мы могли бы расширить возможности приведённой выше схемы, используя ПЗУ с бо́льшим количеством адресных строк и добавив больше данных для программирования:
Мы могли бы расширить возможности приведённой выше схемы, используя [[ПЗУ]] с бо́льшим количеством адресных строк и добавив больше данных для программирования:
[[File:IV-16_3_3.png|400px|center|thumb|'''Рис. 3.''' Бо́льшее количеством адресных строк ПЗУ.|alt=Рис. 3. Бо́льшее количеством адресных строк ПЗУ.]]
[[File:IV-16_3_3.png|400px|center|thumb|'''Рис. 3.''' Бо́льшее количеством адресных строк [[ПЗУ]].|alt=Рис. 3. Бо́льшее количеством адресных строк ПЗУ.]]
Теперь, точно так же, как схема сумматора с таблицей поиска, которую мы превратили в арифметико-логическую единицу (функции +, -, ×, /), используя больше адресных строк в качестве входных данных для «управления функциями», этот счётчик КА можно использовать для генерации более чем одной счётной последовательности: другой последовательности, запрограммированная для четырёх битов обратной связи (от A<sub>0</sub> до A<sub>3</sub>) для каждой из двух комбинаций входных сигналов линии управления функциями (A<sub>4</sub> = 0 или 1).
Теперь, точно так же, как схема сумматора с таблицей поиска, которую мы превратили в арифметико-логическую единицу (функции +, -, ×, /), используя больше адресных строк в качестве входных данных для «управления функциями», этот счётчик КА можно использовать для генерации более чем одной счётной последовательности: другой последовательности, запрограммированная для четырёх битов обратной связи (от A<sub>0</sub> до A<sub>3</sub>) для каждой из двух комбинаций входных сигналов линии управления функциями (A<sub>4</sub> = 0 или 1).
Строка 55:
Строка 55:
|}
|}
Если A<sub>4</sub> равен 0, КА считает в двоичном формате; если A<sub>4</sub> равен 1, КА считает по коду Грея. В любом случае последовательность подсчёта произвольна: определяется прихотью программиста. Если уж на то пошло, последовательность подсчёта даже не обязательно должна состоять из 16-ти шагов, так как программист может решить, что последовательность будет сводиться до 0000 на любом из шагов вообще. Это полностью гибкое счётное устройство, поведение которого строго определяется программным обеспечением (программированием) в ПЗУ.
Если A<sub>4</sub> равен 0, КА считает в двоичном формате; если A<sub>4</sub> равен 1, КА считает по коду Грея. В любом случае последовательность подсчёта произвольна: определяется прихотью программиста. Если уж на то пошло, последовательность подсчёта даже не обязательно должна состоять из 16-ти шагов, так как программист может решить, что последовательность будет сводиться до 0000 на любом из шагов вообще. Это полностью гибкое счётное устройство, поведение которого строго определяется программным обеспечением (программированием) в [[ПЗУ]].
Мы можем ещё больше расширить возможности КА, используя микросхему ПЗУ с дополнительными адресными линиями ввода и вывода данных. Возьмём, к примеру, следующую схему:
Мы можем ещё больше расширить возможности КА, используя микросхему [[ПЗУ]] с дополнительными адресными линиями ввода и вывода данных. Возьмём, к примеру, следующую схему:
[[File:IV-16_3_4.png|400px|center|thumb|'''Рис. 4.''' ПЗУ с дополнительными адресными линиями ввода и вывода данных.|alt=Рис. 4. ПЗУ с дополнительными адресными линиями ввода и вывода данных.]]
[[File:IV-16_3_4.png|400px|center|thumb|'''Рис. 4.''' [[ПЗУ]] с дополнительными адресными линиями ввода и вывода данных.|alt=Рис. 4. ПЗУ с дополнительными адресными линиями ввода и вывода данных.]]
Здесь выходные данные с D<sub>0</sub> по D<sub>3</sub> используются исключительно для обратной связи с адресными линиями от A<sub>0</sub> до A<sub>3</sub>. Линии вывода даты с D<sub>4</sub> по D<sub>7</sub> можно запрограммировать на вывод чего-то другого, кроме значения «состояния» КА. Поскольку четыре бита вывода данных возвращаются к четырём битам адреса, это всё ещё устройство с 16-ю состояниями.
Здесь выходные данные с D<sub>0</sub> по D<sub>3</sub> используются исключительно для обратной связи с адресными линиями от A<sub>0</sub> до A<sub>3</sub>. Линии вывода даты с D<sub>4</sub> по D<sub>7</sub> можно запрограммировать на вывод чего-то другого, кроме значения «состояния» КА. Поскольку четыре бита вывода данных возвращаются к четырём битам адреса, это всё ещё устройство с 16-ю состояниями.
Строка 65:
Строка 65:
Однако наличие выходных данных, поступающих из других линий вывода данных, даёт программисту больше свободы в настройке функций, чем раньше. Другими словами, это устройство может делать гораздо больше, чем просто считать! Запрограммированный выход этого КА зависит не только от состояния адресных линий обратной связи (от A<sub>0</sub> до A<sub>3</sub>), но и от состояния входных линий (от A<sub>4</sub> до A<sub>7</sub>).
Однако наличие выходных данных, поступающих из других линий вывода данных, даёт программисту больше свободы в настройке функций, чем раньше. Другими словами, это устройство может делать гораздо больше, чем просто считать! Запрограммированный выход этого КА зависит не только от состояния адресных линий обратной связи (от A<sub>0</sub> до A<sub>3</sub>), но и от состояния входных линий (от A<sub>4</sub> до A<sub>7</sub>).
Вход тактового сигнала триггера D-типа также не обязательно должен поступать от генератора импульсов. Чтобы сделать ещё более интересно, триггер/флоп можно было бы синхронизировать по какому-то внешнему событию, чтобы КА переходил в следующее состояние только тогда, когда ему об этом сообщает входной сигнал.
Вход тактового сигнала [[триггера D-типа]] также не обязательно должен поступать от генератора импульсов. Чтобы сделать ещё более интересно, [[триггер]]/флоп можно было бы синхронизировать по какому-то внешнему событию, чтобы КА переходил в следующее состояние только тогда, когда ему об этом сообщает входной сигнал.
Теперь у нас есть устройство, которое лучше соответствует значению слова «программируемый». Данные, записанные в ПЗУ, являются программой в самом прямом смысле: выходы следуют заранее установленному порядку, основанному на входах в устройство и на каком «шаге» находится устройство в своей последовательности.
Теперь у нас есть устройство, которое лучше соответствует значению слова «программируемый». Данные, записанные в [[ПЗУ]], являются программой в самом прямом смысле: выходы следуют заранее установленному порядку, основанному на входах в устройство и на каком «шаге» находится устройство в своей последовательности.
Это очень близко к действующей конструкции машины Тьюринга, теоретического вычислительного устройства, изобретенного Аланом Тьюрингом. Математически доказано, что оно способно решить любую известную арифметическую задачу при достаточном объёме памяти.
Это очень близко к действующей конструкции машины Тьюринга, теоретического вычислительного устройства, изобретенного Аланом Тьюрингом. Математически доказано, что оно способно решить любую известную арифметическую задачу при достаточном объёме памяти.
Обратная связь – весьма увлекательный инженерный принцип. Она может превратить довольно простое устройство или процесс во что-то принципиально более сложное. Мы видели эффекты обратной связи, преднамеренно интегрированные в схемы, с некоторыми довольно поразительными эффектами:
Обратная связь, как положительная, так и отрицательная, имеет тенденцию добавлять совершенно новую динамику в работу устройства или системы. Иногда эта новая динамика находит полезное применение, а иногда она просто интересна.
С таблицами поиска, запрограммированными в устройствах памяти, обратная связь от выходных данных к входным адресам создаёт совершенно новый тип устройства – конечный автомат или КА:
Приведённая на рисунке 1 выше схема иллюстрирует основную идею: данные, хранящиеся по каждому адресу, становятся следующим местом хранения, к которому обращается ПЗУ. Результатом является определённая последовательность двоичных чисел (после последовательности, запрограммированной в ПЗУ) на выходе с течением времени.
Однако, чтобы избежать проблем с синхронизацией сигнала, нам нужно соединить выходные данные обратно с адресными входами через 4-битный триггер D-типа, чтобы последовательность выполнялась шаг за шагом синхронно с управляемым тактовым импульсом:
Аналогией работы такого устройства может быть серия почтовых ящиков, каждый из которых имеет идентификационный номер на двери (адрес) и каждый содержит лист бумаги с адресом другого абонентского ящика (данные). Человек, открыв первый абонентский ящик, найдёт в нем адрес следующего абонентского ящика, который нужно открыть.
Сохраняя определённый шаблон адресов в абонентских ящиках, мы можем диктовать последовательность открытия каждого ящика и, следовательно, последовательность чтения листов бумаги.
Имея 16 адресуемых ячеек памяти в ПЗУ, этот конечный автомат будет иметь 16 различных стабильных «состояний», в которых он может зафиксироваться. В каждом из этих состояний идентификатор следующего состояния будет запрограммирован в ПЗУ, ожидая, что сигнал следующего тактового импульса будет возвращён в ПЗУ в качестве адреса.
Одним из полезных приложений такого конечного автомата может быть генерация произвольной счётной последовательности, такой как код Грея:
Попробуйте следовать последовательности счёта кода Грея, как это сделал бы КА: начиная с 0000, следуйте данным, хранящимся по этому адресу (0001), до следующего адреса и так далее (0011), и так далее (0010), и так далее (0110) и т.д. Результатом для показанной таблицы в программе является то, что последовательность адресации скачет от адреса к адресу, что выглядит случайным образом, но когда вы проверяете каждый доступный адрес, вы обнаружите, что он следует правильному порядку для 4-битного кода Грея.
Когда КА достигает своего последнего запрограммированного состояния (адрес 1000), данные, хранящиеся там, имеют номер 0000, что запускает всю последовательность заново с адреса 0000 синхронно со следующим тактовым импульсом.
Мы могли бы расширить возможности приведённой выше схемы, используя ПЗУ с бо́льшим количеством адресных строк и добавив больше данных для программирования:
Теперь, точно так же, как схема сумматора с таблицей поиска, которую мы превратили в арифметико-логическую единицу (функции +, -, ×, /), используя больше адресных строк в качестве входных данных для «управления функциями», этот счётчик КА можно использовать для генерации более чем одной счётной последовательности: другой последовательности, запрограммированная для четырёх битов обратной связи (от A0 до A3) для каждой из двух комбинаций входных сигналов линии управления функциями (A4 = 0 или 1).
Больше адресных строк в качестве входных данных для «управления функциями»
Если A4 равен 0, КА считает в двоичном формате; если A4 равен 1, КА считает по коду Грея. В любом случае последовательность подсчёта произвольна: определяется прихотью программиста. Если уж на то пошло, последовательность подсчёта даже не обязательно должна состоять из 16-ти шагов, так как программист может решить, что последовательность будет сводиться до 0000 на любом из шагов вообще. Это полностью гибкое счётное устройство, поведение которого строго определяется программным обеспечением (программированием) в ПЗУ.
Мы можем ещё больше расширить возможности КА, используя микросхему ПЗУ с дополнительными адресными линиями ввода и вывода данных. Возьмём, к примеру, следующую схему:
Здесь выходные данные с D0 по D3 используются исключительно для обратной связи с адресными линиями от A0 до A3. Линии вывода даты с D4 по D7 можно запрограммировать на вывод чего-то другого, кроме значения «состояния» КА. Поскольку четыре бита вывода данных возвращаются к четырём битам адреса, это всё ещё устройство с 16-ю состояниями.
Однако наличие выходных данных, поступающих из других линий вывода данных, даёт программисту больше свободы в настройке функций, чем раньше. Другими словами, это устройство может делать гораздо больше, чем просто считать! Запрограммированный выход этого КА зависит не только от состояния адресных линий обратной связи (от A0 до A3), но и от состояния входных линий (от A4 до A7).
Вход тактового сигнала триггера D-типа также не обязательно должен поступать от генератора импульсов. Чтобы сделать ещё более интересно, триггер/флоп можно было бы синхронизировать по какому-то внешнему событию, чтобы КА переходил в следующее состояние только тогда, когда ему об этом сообщает входной сигнал.
Теперь у нас есть устройство, которое лучше соответствует значению слова «программируемый». Данные, записанные в ПЗУ, являются программой в самом прямом смысле: выходы следуют заранее установленному порядку, основанному на входах в устройство и на каком «шаге» находится устройство в своей последовательности.
Это очень близко к действующей конструкции машины Тьюринга, теоретического вычислительного устройства, изобретенного Аланом Тьюрингом. Математически доказано, что оно способно решить любую известную арифметическую задачу при достаточном объёме памяти.