Немного теории
Цифровой автомат (ЦА) — это устройство, которое осуществляет прием, хранение и преобразование дискретной информации по некоторому алгоритму и может находиться в одном из нескольких устойчивых состояний [7].
Рисунок 1 — Граф цифрового автомата
Если выходной сигнал цифрового автомата зависит лишь от текущего состояния, то такой автомат называется автоматом Мура, если же выходной сигнал зависит от текущего состояния и входных сигналов, то такой цифровой автомат носит название автомата Мили.
Цифровой автомат может быть описан с помощью таких представлений:
— в виде ориентированного графа,
— с помощью переходов и выходов.
Представление цифрового автомата в виде ориентированного графа показано на рис. 1. Здесь в кругах — вершинах графа — показаны состояния цифрового автомата, переходы между состояниями показаны дугами между вершинами, а переход в то же самое состояние — петлей.
Возле дуг и петель показаны значения входных сигналов, при которых происходит этот переход. Например, (a OR b) обозначает, что этот переход произойдет при a = 1 или b = 1.
Выходные сигналы для автомата Мура показаны около вершин графа, а для цифрового автомата Мили — на дугах возле входных сигналов. Т.о. на рис. 1 показан цифровой автомат Мура.
Представление цифрового автомата с помощью таблиц предполагает наличие двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов связывает между собой текущее состояние, входные сигналы и будущее состояние цифрового автомата. Таблица переходов ЦА, описанного графом на рис. 1, показана в табл. 1.
Таблица 1 — Таблица переходов цифрового автомата
| Текущее состояние | Следующее состояние | Условие перехода |
| S0 | S0 | a=0 ИЛИ c=0 |
| S0 | S1 | a=1 |
| S1 | S1 | a=1 ИЛИ b=1 |
| S1 | S0 | a=0 И b=0 |
| S0 | S2 | c=1 |
| S2 | S2 | c=1 ИЛИ b=1 |
| S2 | S0 | c=0 И b=0 |
Таблица выходов — показывает соответствие текущего состояния цифрового автомата и его выходных сигналов (табл. 2).
Таблица 2 — Таблица выходов цифрового автомата}
| Текущее состояние | Выход |
| S0 | 00 |
| S1 | 01 |
| S2 | 10 |
При реализации цифрового автомата мы будем придерживаться принципа разделения на комбинационную и последовательностную части схемы. При такой интерпретации цифровой автомат будет представлен тремя блоками (рисунок 2):
— комбинационный блок логики переходов;
— регистр для хранения состояний ЦА;
— комбинационный блок формирования выходных сигналов — разные для ЦА Мили и Мура.
Рисунок 2 — Схематическое изображение цифрового автомата с асинхронными выходами
Схема логики переходов на свой вход получает код текущего состояния цифрового автомата (present_st) и внешние сигналы (input_signal). Выходом этого блока будет код следующего состояния (next_st).
В регистр состояний входит три сигнала: тактовый (clk), сброса (reset) и код следующего состояния (next_st). Тактовый сигнал и сигнал сброса предназначены для управления триггерами, которые хранят состояние цифрового автомата. По переднему фронту тактового сигнала производится запись следующего состояния (next_st) в триггеры. Результаты записи в триггеры появляется на выходе регистра состояния в виде сигнала текущего состояния ЦА (present_st).
Блок формирования выходных сигналов в зависимости от состояния ЦА (и входных сигналов для автомата Мили) формирует асинхронные выходные сигналы. Для получения синхронных выходных сигналов в этот блок дополнительно встраивают регистр.
Использование VHDL для описания цифровых автоматов
Для описания состояний цифрового автомата необходимо использовать перечислимый тип. Для этого описывается тип (state_type), значениями которого являются состояния цифрового автомата. Потом описывается сигнал (state) этого перечислимого типа, в котором и будет храниться текущее состояние автомата.
TYPE state_type IS (init, state1, state2, ...);
SIGNAL state: state_type;
При реализации будет получена схема из нескольких триггеров. В зависимости от метода кодирования состояний количество триггеров может изменяться, что влияет на быстродействие и размер схемы. Более подробно о методах кодирования мы поговорим чуть позже.
Для описания работы цифрового автомата и создания комбинационных схем логики переходов и выходов необходимо использовать соответствующие таблицы и помощью оператора case проанализировать значения сигнала present_st.
Процесс, который описывает комбинационную часть для вычисления логики переходов цифрового автомата, может быть описан с помощью такого шаблона:
PROCESS (present_st, input_signal)
BEGIN
CASE present_st IS
WHEN state1 =>
IF input_signal = '1'
THEN next_st <= state1;
ELSE next_st <= state2;
END IF;
WHEN state2 =>
IF input_signal = '1'
THEN next_st <= state2;
ELSE next_st <= state3;
END IF;
...
END CASE;
END PROCESS;
Для описания логики выходных сигналов возможно использование оператора процесса или оператора параллельного условного присваивания.
Процесс, который описывает комбинационную часть для вычисления выходных сигналов цифрового автомата Мура, может быть описан с помощью такого шаблона:
PROCESS (present_st)
BEGIN
CASE present_st IS
WHEN state1 =>
output <= "000";
WHEN state2 =>
output <= "001";
...
END CASE;
END PROCESS;
Здесь в списке инициализации процесса используется только текущее состояние цифрового автомата present_st, значения которого анализируются с помощью оператора case.
Для автомата Мили этот же процесс будет выглядеть таким образом:
PROCESS (present_st, input_signal)
BEGIN
CASE present_st IS
WHEN state1 =>
IF input_signal = '1'
THEN output <= "000";
ELSE output <= "001";
END IF;
WHEN state2 =>
IF input_signal = '1'
THEN output <= "011";
ELSE OUTPUT <= "010";
END IF;
...
END CASE;
END PROCESS;
Этот процесс для инициализации использует текущее состояние ЦА (present_st) и входной сигнал (input_signal) так как изменения любого из этих сигналов должно запускать выполнение процесса.
Для получения синхронных выходных сигналов необходимо использовать процесс, у которого в списке инициализации находится только тактовый сигнал clk. Анализ текущего состояния так же как и в предыдущем случае производится с помощью оператора case.
PROCESS (clk)
BEGIN
IF (rising_edge(clk)) THEN
CASE present_st IS
WHEN state1 =>
output <= "000";
WHEN state2 =>
output <= "001";
...
END CASE;
END IF;
END PROCESS;
Формирование выходных сигналов с помощью параллельного условного присваивания не требует оператора процесса. В этом случае можно использовать такую конструкцию:
output <= "000" WHEN present_st = state1 ELSE
"001" WHEN present_st = state2 ELSE
...
"100";
При описании последовательностной части цифрового автомата в списке инициализаторов процесса должны содержатся сигналы clk и reset. При поступлении сигнала сброса reset цифровой автомат переходит в начальное состояние init, из которого начинается работа всего автомата. Передний фронт сигнала clk приводит к записи в триггеры ЦА его нового текущего состояния, т.е. сигнал next_st переписывается в сигнал present_st.
Фактически последовательностная часть представляет собой регистр со сбросом:
PROCESS (clk, reset)
BEGIN
IF reset = '1'
THEN present_st <= Init;
ELSIF (rising_edge(clk))
THEN present_st <= next_st;
END IF;
END PROCESS;
Сигнал сброса может быть синхронным или асинхронным. Выше в листинге описан вариант асинхронного сброса.
При использовании асинхронного сигнала сброса мы всегда знаем в каком состоянии будет находиться цифровой автомат при включении питания, т.е. до поступления тактового сигнала и начала нормальной работы системы. В этом случае нет необходимости декодировать неиспользуемые состояния цифрового автомата, что позволяет уменьшить схему логики переходов.
Использование синхронного сигнала сброса не позволяет определить в каком состоянии окажется автомат при включении питания. Возможно, что он <<залипнет>> в одном из неописанных состояний. Т.о. при описании цифрового автомата необходимо описать все2^n комбинаций состояний триггеров вне зависимости от того являются они рабочими состояниями цифрового автомата или нет. Здесь n — количество триггеров, применяемых для кодирования цифрового автомата. Это, в свою очередь приведет, к увеличению схемы логики переходов.
Для того, чтобы избежать <<залипания>> ЦА в неописанных состояниях необходимо явно прописывать действия в таких ситуациях с помощью конструкции when… others. Например, возможно использование такого процесса для описания синхронного сброса и действий в неиспользуемых состояниях.
PROCESS (clk)
BEGIN
IF (rising_edge(clk)) THEN
IF reset = '1'
THEN state <= init;
ELSE
CASE state IS
WHEN state1 =>
IF input_signal = '1'
THEN state <= state1;
ELSE
state <= state2;
END IF;
WHEN state2 =>
IF input_signal = '1'
THEN state <= state2;
ELSE
state <= state3;
END IF;
...
WHEN OTHERS =>
state <= init;
END CASE;
END IF;
END IF;
END PROCESS;
Три, два, один
Цифровой автомат можно описать с помощью одного, двух или трех операторов процесса. Эти варианты рассмотрим на примере цифрового автомата управления светофором.
Этот цифровой автомат имеет пять состояний: начальное (Init), красный ( R ), зеленый (G) и два желтых — один для перехода из красного к зеленому (RG), а второй — из зеленого к красному (GR). В том случае, когда вход cnt равняется нулю, никаких переходов не происходит, когда вход cnt равняется единице — происходит переход в следующее состояние. Граф цифрового автомата изображен на рис. 3.
Рисунок 3 — Граф цифрового автомата светофора
Этот же автомат может быть представлен с помощью таблицы переходов и таблицы выходов. Выходной сигнал представлен трехбитным вектором, в котором старший бит отвечает за красный, второй – за желтый и младший – за зеленый.
Таблица 3 — Таблица переходов
| present_ st | next_st | Условие перехода |
| Init | Init | cnt = 0 |
| Init | R | cnt = 1 |
| R | R | cnt = 0 |
| R | RG | cnt = 1 |
| RG | RG | cnt = 0 |
| RG | G | cnt = 1 |
| G | G | cnt = 0 |
| G | GR | cnt = 1 |
| GR | GR | cnt = 0 |
| GR | R | cnt = 1 |
Таблица 4 — Таблица выходов
| present_st | output |
| Init | 000 |
| R | 100 |
| RG | 010 |
| G | 001 |
| GR | 010 |
Для описания состояний ЦА необходимо описать перечислимый тип, в котором будут перечислены все состояния. В приведенном примере вводится тип state_type, который содержит пять значений: Init, R, RG, G, GR. Для работы конкретного экземпляра цифрового автомата нужно описать сигналы этого типа. В примере это сигналы next_st, present_st для хранения последующего и текущего состояний автомата соответственно. При выполнении процессов этот сигнал будет принимать значение текущего состояния цифрового автомата.
Теперь рассмотрим описание этого цифрового автомата с помощью трех процессов (рисунок 4), каждый из которых описывает отдельную часть цифрового автомата:
— комбинационная часть для логики переходов;
— комбинационная часть для выходных сигналов;
— последовательностная часть только для записи состояний цифрового автомата.
Рисунок 4 — Цифровой автомат с тремя процессами
Такой вариант описания цифрового автомата дает возможность разработчику отделять логику переходов от логики формирования выходящих сигналов и осуществлять синхронную запись состояния автомата в регистр хранения состояния. А это, в свою очередь, позволяет более просто описывать и отлаживать синхронный цифровой автомат.
Сама программа представляет собой комбинацию трех процессов, описанных выше.
Описание цифрового автомата с помощью трех процессов
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
ENTITY traffic IS
PORT(clk : IN std_logic;
cnt : IN std_logic;
reset : IN std_logic;
output : OUT std_logic_vector(2 downto 0)
);
END ENTITY;
ARCHITECTURE rtl OF traffic IS
TYPE state_type IS (Init, R, RG, G, GR);
SIGNAL next_st, present_st: state_type;
BEGIN
state_proc:
PROCESS (present_st, cnt)
BEGIN
CASE present_st IS
WHEN Init =>
IF cnt = '1'
THEN next_st <= R;
ELSE
next_st <= Init;
END IF;
WHEN R =>
if cnt = '1'
THEN next_st <= RG;
ELSE
next_st <= R;
END IF;
WHEN RG =>
IF cnt = '1'
THEN next_st <= G;
ELSE
next_st <= RG;
END IF;
WHEN G =>
IF cnt = '1'
THEN NEXT_st <= GR;
ELSE
next_st <= G;
END IF;
WHEN GR =>
IF CNT = '1'
THEN next_st <= R;
ELSE
next_st <= GR;
END IF;
WHEN OTHERS =>
next_st <= Init;
END CASE;
END PROCESS;
next_st_proc:
PROCESS (clk, reset)
BEGIN
IF reset = '1'
THEN present_st <= Init;
ELSIF (rising_edge(clk))
THEN present_st <= next_st;
END IF;
END PROCESS;
out_proc:
PROCESS (present_st)
BEGIN
CASE present_st IS
WHEN Init =>
output <= "000";
WHEN R =>
output <= "100";
WHEN RG =>
output <= "010";
WHEN G =>
output <= "001";
WHEN GR =>
output <= "010";
END CASE;
END PROCESS;
END rtl;
Результирующий граф ЦА, полученный при компиляции в пакете Quartus II показан на рисунке 5 (меню Tools — Netlist Viewers — State Machine Viewer).
Рисунок 5 — Цифровой автомат с тремя процессами. Результат компиляции
Результат синтеза программы, приведенной в листинге выше, показан на рис. 6 (меню Tools — Netlist Viewers — Technology Map Viewer). Для облегчения понимания на рисунке элементы ввода-вывода обозначены как IO, триггеры как FF, а логические элементы — LE. Как видно в результате синтеза получится схема из 5 триггеров для хранения состояний цифрового автомата (в случае метода кодирования One Hot) и двух логических элементов для реализации схемы переходов и формирования выходных сигналов.
Рисунок 6 — Цифровой автомат с тремя процессами. Technology Map Viewer
Описание с помощью двух процессов (рис. 6) предполагает, что блок логики переходов и регистр состояний объединяются в один процесс, в котором с помощью оператора case производится выбор будущего значения состояния цифрового автомата. Поскольку нет необходимости разделять сигналы текущего и будущего состояний, то эти два сигнала заменены на один, state, в котором и хранится состояние цифрового автомата.
В листинге ниже показан пример описания ЦА с асинхронным сбросом. В результате компиляции будет получен такой же результат как и в предыдущем случае — рис.7.
Рисунок 7 — Цифровой автомат с двумя процессами
Описание ЦА с помощью двух процессов. Асинхронный сброс
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
ENTITY traffic IS
PORT(clk : IN std_logic;
cnt : IN std_logic;
reset : IN std_logic;
output : OUT std_logic_vector(2 downto 0)
);
END ENTITY;
ARCHITECTURE rtl OF traffic IS
TYPE state_type IS (Init, R, RG, G, GR);
SIGNAL state: state_type;
BEGIN
state_proc:
PROCESS (clk, reset)
BEGIN
IF reset = '1'
THEN state <= Init;
ELSIF (rising_edge(clk)) THEN
CASE state IS
WHEN Init =>
IF cnt = '1'
THEN state <= R;
ELSE
state <= Init;
END IF;
WHEN R =>
IF cnt = '1'
THEN state <= RG;
ELSE
state <= R;
END IF;
WHEN RG =>
IF cnt = '1'
THEN state <= G;
ELSE
state <= RG;
END IF;
WHEN G =>
IF cnt = '1'
THEN state <= GR;
ELSE
state <= G;
END IF;
WHEN GR =>
IF cnt = '1'
THEN state <= R;
ELSE
state <= GR;
END IF;
END CASE;
END IF;
END PROCESS;
out_proc:
PROCESS (state)
BEGIN
CASE state IS
WHEN Init =>
output <= "000";
WHEN R =>
output <= "100";
WHEN RG =>
output <= "010";
WHEN G =>
output <= "001";
WHEN GR =>
output <= "010";
END CASE;
END PROCESS;
END rtl;
Цифровой автомат с синхронным сбросом, описанный двумя процессами показан ниже. Результаты синтеза из Technology Map Viewer показаны на рис. 8, из которого видно, что размер комбинационной части значительно автомата увеличился по сравнению с автоматом с асинхронным сбросом.
Описание ЦА с помощью двух процессов. Синхронный сброс
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
ENTITY traffic IS
PORT(clk : IN std_logic;
cnt : IN std_logic;
reset : IN std_logic;
output : OUT std_logic_vector(2 downto 0)
);
END ENTITY;
ARCHITECTURE rtl OF traffic IS
TYPE state_type IS (Init, R, RG, G, GR);
SIGNAL state: state_type;
BEGIN
state_proc:
PROCESS (clk)
BEGIN
IF (rising_edge(clk)) THEN
IF reset = '1'
THEN state <= Init;
ELSE
CASE state IS
WHEN Init =>
IF cnt = '1'
THEN state <= R;
ELSE
state <= Init;
END IF;
WHEN R =>
IF cnt = '1'
THEN state <= RG;
ELSE
state <= R;
END IF;
WHEN RG =>
IF cnt = '1'
THEN state <= G;
ELSE
state <= RG;
END IF;
WHEN G =>
IF cnt = '1'
THEN state <= GR;
ELSE
state <= G;
END IF;
WHEN GR =>
IF CNT = '1'
THEN state <= R;
ELSE
state <= GR;
END IF;
END CASE;
END IF;
END IF;
END PROCESS;
out_proc:
PROCESS (state)
BEGIN
CASE state is
WHEN Init =>
output <= "000";
WHEN R =>
output <= "100";
WHEN RG =>
output <= "010";
WHEN G =>
output <= "001";
WHEN GR =>
output <= "010";
END CASE;
END PROCESS;
END rtl;
Рисунок 8 — Результат синтеза цифрового автомата с синхронным сбросом
Описание цифрового автомата с помощью одного процесса предполагает, что вся логика находится в одном процессе. Некоторые авторы [5] считают, что использование одного процесса для описания цифрового автомата является более простым и позволяет более просто описывать и отлаживать цифровой автомат. Данное утверждение справедливо для небольших цифровых автоматов. При увеличении количества состояний и использовании одного процесса ухудшается читабельность кода. Потому как еще древние римляне при описании цифровых автоматов пользовались правилом «Разделяй и властвуй».
Еще одним аргументом, который приводится в пользу использования одного процесса при описании цифрового автомата, является то, что этот вариант предполагает использование синхронных выходных сигналов. Это условие не является обязательным для всех ЦА и может быть легко достижимо, что было показано выше при обсуждении логики формирования выходных сигналов.
И все же, для завершения образа, приведем пример описания цифрового автомата с асинхронным сбросом с помощью одного процесса.
Описание ЦА одним процессом
LIBRARY IEEE;
USE ieee.std_logic_1164.ALL;
ENTITY traffic IS
PORT(clk : IN std_logic;
cnt : IN std_logic;
reset : IN std_logic;
output : OUT std_logic_vector(2 downto 0)
);
END ENTITY;
ARCHITECTURE rtl OF traffic IS
TYPE state_type IS (Init, R, RG, G, GR);
SIGNAL state: state_type;
BEGIN
PROCESS (clk, reset)
BEGIN
IF reset = '1'
THEN state <= Init;
ELSIF (rising_edge(clk)) THEN
CASE state IS
WHEN Init =>
IF cnt = '1'
THEN state <= R;
ELSE
state <= Init;
END IF;
output <= "000";
WHEN R =>
IF cnt = '1'
THEN state <= RG;
ELSE
state <= R;
END IF;
output <= "100";
WHEN RG =>
IF cnt = '1'
THEN state <= G;
ELSE
state <= RG;
END IF;
output <= "010";
WHEN G =>
IF cnt = '1'
THEN state <= GR;
ELSE
state <= G;
END IF;
output <= "001";
WHEN GR =>
IF cnt = '1'
THEN state <= R;
ELSE
state <= GR;
END IF;
OUTPUT <= "010";
END CASE;
END IF;
END PROCESS;
END rtl;
Результат компиляции программы показан на рисунке \ref{FSM_1process_TMView}. Очевидно, что результат оказался таким же как и при описании с помощью двух процессов с единственным отличием – добавились триггеры для выходного регистра.
Рисунок 9 — Цифровой автомат с одним процессом
Подведем небольшие итоги наших изысканий.
Первое, и самое важное. Цифровой автомат существует! Мы его видели на картинке 5.
Второе. Описания с помощью двух и трех процессов дают одинаковый результат и выбор метода описания зависит от предпочтений разработчика.
Третье. Нужно очень внимательно относиться к начальному сбросу автомата и описанию неиспользуемых состояний.
Четвертое. Описание с помощью одного процесса приводит к появлению регистров для выходных сигналов цифрового автомата.
Список литературы.
1. Altera. Quartus II Handbook Version 10.0 Volume 1: Design and Synthesis Vol. 1, 2010 — 1820 p.
2. B. Cohen. VHDL Coding style and Metodologies. Kluwer Academic Publishers.2002 — 454 p.
3. D. L. Perry. VHDL programming by example. New York: McGraw-Hill, 2002.- 476 p.
4. D. J. Smith. HDL chip design: a practical guide for designing, synthesizing, and simulating ASICs and FPGAs using VHDL or Verilog. Madison, AL: Doone Publications, 1996. — 448 p.
5. A. Taylor. How to Implement State Machines in Your FPGA. Xcell, 81(4), p. 52–57.
6. Xilinx. VHDL Reference Guide. XST User Guide.
7. К. Г. Самофалов. Прикладная теория цифровых автоматов. М.:, 1987. 375 с.
P.S. PDF-вариант лежит тут.
