Проектирование цифровых систем на языках описания аппаратуры/Лекция 9
- Заголовок
- Описание конечных автоматов и схем с памятью
- Автор
- Ланкевич Ю.Ю.
- Нижний колонтитул
- Проектирование цифровых систем на языках описания аппаратуры/Лекция 9
- Дополнительный нижний колонтитул
- Ланкевич Ю.Ю., 01:15, 12 октября 2020
Содержание |
Слайд:Определение конечного автомата
- Абстра́ктный автома́т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.
Ограничение числа состояний абстрактного автомата определило такое понятие как конечный автомат. Конечный автомат K определяется как набор
- A = { a1 ,..., aQ } – множество (алфавит) состояний (имеются в виду внутренние состояния автомата);
- Z = { z1 ,..., zN } – множество входных сигналов (входной алфавит);
- W = { w1 ,..., wM } – множество выходных сигналов (выходной алфавит);
- δ – функция переходов, определяющая состояние автомата в момент времени t+1 в зависимости от состояния автомата и входного сигнала в момент времени t, иначе говоря,
- am – состояние автомата в момент времени t;
- z – входной сигнал в момент времени t;
- as – состояние автомата в момент времени t+1;
- λ – функция выходов.
Слайд:Автомат Мили и автомат Мура
Если функция λ по состоянию автомата aq и входному сигналу zn определяет значение выходного сигнала wm
то конечный автомат называется автоматом Мили , если же
то конечный автомат называется автоматом Мура;
- a1 – начальное состояние автомата в момент времени t =0, a1∈A.
Слайд:Пример автомата Мили
- Следующее состояние = F (текущее состояние, вход)
- Выход = G (текущее состояние, вход)
Функционирование автомата происходит следующим образом: в дискретные моменты времени t = 0, 1, 2, 3,... на вход устройства поступает входной сигнал – один из элементов множества Z,
а на выходе появляется выходной сигнал – один из элементов множества W, в этот же момент времени t автомат из состояния am переходит в состояние as, в котором он будет находиться в момент времени t+1.
Разработаны различные формы задания конечных автоматов. Например, в таблице задан конечный автомат Мили с четырьмя внутренними состояниями
| Входные сигналы | Состояния | |||
|---|---|---|---|---|
| a1 | a2 | a3 | a4 | |
| z1 | a2/w1 | a2/w1 | a1/w2 | a1/w4 |
| z2 | a4/w5 | a3/w3 | a4/w4 | a3/w5 |
Алфавит состояний A = {a1, a2, a3, a4}, q = 1,...,4. Входной алфавит Z образуют сигналы z1, z2, т.е. Z = {z1 , z2 }, n = 1,2.
Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1,w2,w3,w4,w5}, m = 1,...,5. На пересечении строки zn и столбца aq в таблице находится состояние as ,
в которое должен перейти автомат из состояния aq под воздействием сигнала zn.
После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn.
Иначе говоря, выше представлена таблица задания функций δ , λ, которая называется совмещенной таблицей переходов и выходов.
Автомат может быть задан ориентированным графом, в котором вершинам соответствуют абстрактные внутренние состояния автомата, а дуги соответствуют переходам между состояниями.
Такой граф носит название графа автомата. Для автомата, заданного в таблице, граф автомата имеет следующий вид.
Легко видеть, что совмещенная таблица переходов и выходов автомата и граф автомата являются эквивалентными формами задания поведения конечного автомата Мили.
Слайд:Пример VHDL модели автомата Мили
Следующий VHDL-код реализует поведение конечного автомата, заданного в таблице. Поведение автомата представляется в виде совокупности двух взаимодействующих процессов.
Процесс NS определяет выходной сигнал w и внутренний сигнал NEXT_state, который является входным для процесса REG. Заметим, однако, что в списке чувствительности процесса REG имеется только сигнал clk, который соответствует моментам времени срабатывания автомата.
Для задания состояний автомата в архитектурном теле определяется перечислимый тип t_state. Предполагается, что начальное состояние автомата равно a1.
Начальное состояние явно не указывается, так как при инициализации будет взят элемент нижней границы перечислимого типа – это и будет элемент a1.
Library work; use work.vv_vls.all; entity FSM_A is port ( z : in fsm_in_type; clk : in bit; w : out fsm_out_type); end FSM_A; architecture rtl_a of fsm_a is type T_state is (a1,a2,a3,a4); signal NEXT_state : T_state; signal state : T_state; begin NS : process (state, z) begin case state is when a1 => if (z=z1) then NEXT_state <= a2; w <= w1; elsif (z=z2) then NEXT_state <= a4; w <= w5; end if; when a2 => if (z=z1) then NEXT_state <= a2; w <= w1; elsif (z=z2) then NEXT_state <= a3; w <= w3; end if; when a3 => if (z=z1) then NEXT_state <= a1; w <= w2; elsif (z=z2) then NEXT_state <= a4; w <= w4; end if; when a4 => if (z=z1) then NEXT_state <= a1; w <= w4; elsif (z=z2) then NEXT_state <= a3; w <= w5; end if; end case; end process; REG : process(clk) begin if clk = '1' then state <= NEXT_state; end if; end process; end rtl_a;
Слайд:Пример VHDL модели автомата Мили
Для входных сигналов автомата в пакете vv_vls определяется перечислимый тип
type fsm_in_type is (z1, z2);
для выходных сигналов в том же пакете определяется перечислимый тип
type fsm_out_type is (w1 , w2 ,w3 ,w4 ,w5);package vv_vls is type fsm_in_type is (z1, z2); type fsm_out_type is (w1, w2, w3, w4, w5); end vvv; package body vvv is end vvv;
Многократное изменение синхросигнала clk можно более компактно описать в виде процесса generator. Переменная number задает число тактов. В данном случае число тактов равно 5.
generator : process variable number : integer := 5; begin for i in 1 to number loop clk <= transport '1'; wait for 25 ns; clk <= transport '0'; wait for 25 ns; end loop; end process;
При описании схем с памятью выделяют комбинационную часть автомата и память. Описание поведения выполняют в виде совокупности двух взаимодействующих процессов – процесса NS и детализированного процесса REG. Для рассмотренного примера конечного автомата выделение подсхем показано на рисунке.
