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

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

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


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

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

Однако есть много приложений, где схемам нужна «память», позволяющая запоминать предыдущие входы и рассчитывать выходы в соответствии с ними. Схема, выход которой зависит не только от текущего ввода, но и от истории ввода, называется схемой последовательности.

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

Итак, давайте предположим, что нам нужно разработать цифровое устройство для игры-викторины, которое работает на тактовом входе и считывает ввод с кнопки, нажатой вручную. Однако мы хотим, чтобы переключатель передавал в схему только один ВЫСОКИЙ импульс. Если мы понажимаем кнопку непосредственно в схеме игрового устройства, будет передано столько ВЫСОКИХ тактов, сколько можно достигнуть нажатием пальца. Движение пальца никогда не будет настолько быстрым, чтобы поспевать за обычной тактовой частотой.

Процедура проектирования имеет определённые шаги, которые необходимо выполнить, чтобы реализовать нашу задумку:

Шаг 1

Первый шаг любого проектирования – ясно и просто определить, что мы, собственно, ждём от нашей схемы:

«

Наша задача – разработать вспомогательную электрическую цепь, которая будет передавать ВЫСОКИЙ импульс длительностью только в один такт при нажатии кнопки ручного управления и не будет передавать другой импульс, пока кнопка не будет отжата и повторно нажата.

»
— Проектировщик схемы

Шаг 2

Следующим шагом является разработка диаграммы состояний.

Это стрелочно-круговая схема, визуально описывающая работу нашей схемы. С математической точки зрения эта диаграмма, описывающая работу нашей схемы последовательности, является конечным автоматом. Обратите внимание, что это конечный автомат Мура.

Его выход является функцией только от его текущего состояния, а не от его входа. Это контрастирует с конечным автоматом Мили, где вход влияет на выход. В этом руководстве будет рассмотрен только конечный автомат Мура.

Диаграмма состояний нашей схемы выглядит следующим образом:

Рис. 1. Диаграмма состояний конечного автомата Мура для нашей задачи.
Рис. 1. Диаграмма состояний конечного автомата Мура для нашей задачи.

Каждый круг представляет собой чётко определённое «состояние», в котором находится наш автомат. В верхней половине круга мы описываем состояние. Описание помогает запомнить, что именно наша схема должна делать в этом состоянии.

  • Первый круг – состояние «ожидания». Это то место, откуда начинается наша схема и где она пока что только ожидает нажатия кнопки.
  • Второй круг – состояние, когда кнопка только что была нажата, и наша схема должна передать ВЫСОКИЙ импульс.
  • Третий круг – состояние, когда наша схема ожидает отпускания кнопки, прежде чем вновь вернуться в состояние «ожидания».

В нижней части круга указано значение на выходе нашей схемы. Если мы хотим, чтобы наша схема передавала ВЫСОКИЙ импульс в определённом состоянии, мы присваиваем этому состоянию 1. В противном случае ставим 0.

Каждая стрелка – это «переход» из одного состояния в другое. Переход происходит один раз за каждый такт. В зависимости от текущего входа мы можем каждый раз переходить в другое состояние. Обратите внимание на число в середине каждой стрелки. Это текущий вход.

Например, когда мы находимся в состоянии «Начальное ожидания» и «считываем» 1, диаграмма указывает, что мы должны перейти в состояние «Активировать импульс». Если мы считываем 0, мы должны оставаться в состоянии «Начальное ожидание».

Итак, что именно делает наша «Машина»? Она запускается из состояния «Начальное ожидание» и ждёт, пока на входе не будет считана 1. Затем она переходит в состояние «Активировать импульс» и передаёт на свой выход ВЫСОКИЙ импульс. Если кнопка всё ещё нажата, схема переходит в третье состояние, «Цикл ожидания».

В этом состоянии автомат ждёт, пока кнопка не будет отпущена (на входе будет 0) при передаче НИЗКОГО уровня на выходе. И потом всё можно начать заново!

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

Шаг 3

Далее мы заменим слова, описывающие разные состояния диаграммы, на двоичные числа. Начнём перечисление с 00, которое присваивается начальному состоянию. Затем мы продолжаем перечисление с любым состоянием, которое нам нравится, пока все состояния не получат свой номер. Результат выглядит примерно так:

Рис. 2. Диаграмма с закодированными состояниями.
Рис. 2. Диаграмма с закодированными состояниями.

Шаг 4

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

Рис. 3. Таблица состояний.
Рис. 3. Таблица состояний.

Количество первых столбцов равно количеству битов самого высокого числа, которое мы присвоили диаграмме состояний. Если бы у нас было 5 состояний, мы бы использовали число до 1002, а это значит, что мы использовали бы 3 столбца. Для нашего примера мы использовали до числа 102, поэтому потребуется всего 2 столбца. Эти столбцы описывают текущее состояние нашей схемы.

Справа от столбцов для текущих состояний размещаем столбцы для входов. Их будет столько же, сколько наших входных переменных. В нашем примере есть только один вход, поэтому только один столбец «Вход».

Далее мы идут столбцы для следующих состояний. Их столько же, сколько столбцов текущего состояния.

Наконец, мы пишем столбцы для выходов. Этих столбцов столько же, сколько наших выходов. Наш пример имеет только один выход, поэтому только один столбец «Выходы». Поскольку мы построили конечный автомат, выход зависит только от текущих входных состояний. По этой причине в столбце «Выходы» есть две 1: чтобы получить выходную логическую функцию, независимую от входа I. Столбцы «Текущее состояние» и «Вход» – это входы нашей таблицы. Заполняем их всеми двоичными числами от 0 до:

2(Количество столбцов текущего состояния + Количество столбцов входа) - 1

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

Каждая строка столбцов «Следующее состояние» заполняется следующим образом. Мы заполняем её состоянием, которого достигаем, когда на диаграмме состояний из той же строки в столбцах «Текущее состояние» следует «Вход» на той же строке. Если необходимо заполнить строку, чей номер текущего состояния не соответствует какому-либо фактическому состоянию на диаграмме состояний, мы отмечаем её как поле безразличия и отмечаем крестиком (×). В конце концов, нам всё равно, куда выйти из состояния, которого не существует. Ведь нас там не будет изначально! Опять же, всё проще, чем может показаться.

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

Таблица состояний заполнена! Она описывает поведение нашей схемы так же полно, как и диаграмма состояний.

Шаг 5а

Следующий шаг – взять эту теоретическую «Машину» и реализовать её в виде схемы. Чаще всего эта реализация включает в себя триггеры. Данное руководство посвящено этому типу реализации и описывает процедуру как для D-триггеров, так и для JK-триггеров. T-триггеры не будут включены, так как они слишком похожи на два предыдущих случая. Выбор триггера является произвольным и обычно определяется стоимостными факторами. Лучший выбор – произвести анализ, на основании которого решить, какой тип триггера даёт минимальное количество логических вентилей и меньшую стоимость.

Сначала мы рассмотрим, как реализовать нашу «Машину» с помощью D-триггера.

Нам понадобится столько D-триггеров, сколько столбцов для состояний, это 2 столбца в нашем примере. Для каждого триггера мы добавим ещё один столбец в нашу таблицу состояний (рисунок 4 ниже) с именем входа триггера, в данном случае они обозначены как «D». Столбец, соответствующий каждому триггеру, описывает, какие входные данные мы должны дать на вход триггеру, чтобы перейти от текущего состояния к следующему состоянию. Для D-триггера это просто: необходимый вход равен следующему состоянию. В строках, содержащих ×, мы также заполняем × в этом столбце.

Рис. 4. Таблица состояний с сигналами D-триггеров.
Рис. 4. Таблица состояний с сигналами D-триггеров.

Шаг 5б

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

Q QСлед. J K
0 0 0 ×
0 1 1 ×
1 0 × 1
1 1 × 0

В соответствии с этой таблицей, если мы хотим перейти из состояния Q в состояние QСлед., нам нужно использовать определённый вход для каждого вывода J или K. Например, чтобы перейти от 0 к 1, нам нужно подать на J значение 1, и нам всё равно, какой вход мы подадим на вывод K.

Рис. 5. Таблица состояний с сигналами на JK-триггере.
Рис. 5. Таблица состояний с сигналами на JK-триггере.

Шаг 6

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

Тем не менее, входные функции для наших D-триггеров следующие:

Рис. 6. Карты Карно для входов D-триггера и производные от неё логические функции.
Рис. 6. Карты Карно для входов D-триггера и производные от неё логические функции.

Если бы мы решили использовать JK-триггер, наши функции были бы следующими:

Рис. 7. Карты Карно для входов JK-триггера и производные от неё логические функции.
Рис. 7. Карты Карно для входов JK-триггера и производные от неё логические функции.

Карта Карно также будет использоваться для определения функции выхода:

Рис. 8. Карта Карно для выходной переменной Y и производная от неё логическая функция.
Рис. 8. Карта Карно для выходной переменной Y и производная от неё логическая функция.

Шаг 7

Наконец-то проектируем схему. Размещаем триггеры и используем логические вентили для формирования вычисленных логических функций. Вентили принимают входные данные с выхода триггеров и входа схемы. Не забудьте подвести тактовый вход к триггерам!

Версия с D-триггером:

Рис. 9. Завершённая схема последовательности (с D-триггером).
Рис. 9. Завершённая схема последовательности (с D-триггером).

Версия JK-триггером:

Рис. 10. Завершённая схема последовательности (с JK-триггером).
Рис. 10. Завершённая схема последовательности (с JK-триггером).

Это оно! Мы успешно спроектировали и построили схему последовательности. Сначала это может показаться сложной задачей, но если попрактиковаться, то процедура станет тривиальной. Схемы последовательностей могут пригодиться в качестве управляющих частей больших схем и могут выполнять любую последовательную логическую задачу, о которой только можем помыслить. Возможности безграничны! (В пределах проектирования печатных плат, во всяком случае.)

Итог

  • Функция логики последовательностей обладает «памятью» и для формирования выхода принимается во внимание предыдущие входные данные.
  • Конечный автомат — это абстрактная математическая модель логической функции последовательности. Он имеет конечные входы, выходы и количество состояний.
  • Конечные автоматы реализуются в реальных схемах с помощью триггеров.
  • Для реализации требуется определённый порядок шагов (алгоритм приведён в данном разделе).

См.также

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