Проектирование цифровых систем на языках описания аппаратуры/Лекция 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.
Слайд:Пример автомата Мили
Функционирование автомата происходит следующим образом: в дискретные моменты времени 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. Для рассмотренного примера конечного автомата выделение подсхем показано на рисунке.
