Описание цифровых автоматов на VHDL
Немного теории
Цифровой автомат (ЦА) — это устройство, которое осуществляет прием, хранение и преобразование дискретной информации по некоторому алгоритму и может находиться в одном из нескольких устойчивых состояний [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-вариант лежит тут.
