Проектирование цифровых систем на языках описания аппаратуры/Лекция 9
- Заголовок
- Описание конечных автоматов и схем с памятью
- Автор
- Ланкевич Ю.Ю.
- Нижний колонтитул
- Проектирование цифровых систем на языках описания аппаратуры/Лекция 9
- Дополнительный нижний колонтитул
- Ланкевич Ю.Ю., 01:15, 12 октября 2020
Слайд:Конечный автомат
Широкое распространение в практике проектирования дискретных устройств получила модель конечного автомата.</br>
Конечный автомат K определяется как набор
K = (A, Z, W, δ , λ , a1 )
где A = { a1 ,..., aQ } – множество (алфавит) состояний (имеются в виду
внутренние состояния автомата);
Z = { z1 ,..., zN } – множество входных сигналов (входной алфавит);
W = { w1 ,..., wM } – множество выходных сигналов (выходной алфавит);
δ – функция переходов, определяющая состояние автомата в момент времени t+1 в зависимости от состояния автомата и входного сигнала в момент времени t, иначе говоря,
as = δ (am , z),
где am – состояние автомата в момент времени t; z – входной сигнал в момент времени t; as – состояние автомата в момент времени t+1;
λ – функция выходов. Если функция λ по состоянию автомата aq и входному сигналу zn определяет значение выходного сигнала wm
wm = λ (aq , zn )
то конечный автомат называется автоматом Мили , если же
wm = λ (a),
то конечный автомат называется автоматом Мура;
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-код реализует поведение конечного автомата, заданного в таблице. Поведение автомата представляется в виде совокупности двух взаимодействующих процессов.
Процесс NS определяет выходной сигнал w и внутренний сигнал NEXT_state, который является входным для процесса REG. Заметим, однако, что в списке чувствительности процесса REG имеется только сигнал clk, который соответствует моментам времени срабатывания автомата.
Для входных сигналов автомата в пакете vv_vls определяется перечислимый тип
type fsm_in_type is (z1, z2);
для выходных сигналов в том же пакете определяется перечислимый тип
Указан неподдерживаемый язык.
Вы должны указать язык следующим образом: <source lang="html4strict">...</source>
Поддерживаемые языки:
4cs, 6502acme, 6502kickass, 6502tasm, 68000devpac, abap, actionscript, actionscript3, ada, algol68, apache, applescript, apt_sources, arm, asm, asp, asymptote, autoconf, autohotkey, autoit, avisynth, awk, bascomavr, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_loadrunner, c_mac, caddcl, cadlisp, cfdg, cfm, chaiscript, cil, clojure, cmake, cobol, coffeescript, cpp, cpp-qt, csharp, css, cuesheet, d, dcl, dcpu16, dcs, delphi, diff, div, dos, dot, e, ecmascript, eiffel, email, epc, erlang, euphoria, f1, falcon, fo, fortran, freebasic, freeswitch, fsharp, gambas, gdb, genero, genie, gettext, glsl, gml, gnuplot, go, groovy, gwbasic, haskell, haxe, hicest, hq9plus, html4strict, html5, icon, idl, ini, inno, intercal, io, j, java, java5, javascript, jquery, kixtart, klonec, klonecpp, latex, lb, ldif, lisp, llvm, locobasic, logtalk, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, magiksf, make, mapbasic, matlab, mirc, mmix, modula2, modula3, mpasm, mxml, mysql, nagios, netrexx, newlisp, nsis, oberon2, objc, objeck, ocaml, ocaml-brief, octave, oobas, oorexx, oracle11, oracle8, oxygene, oz, parasail, parigp, pascal, pcre, per, perl, perl6, pf, php, php-brief, pic16, pike, pixelbender, pli, plsql, postgresql, povray, powerbuilder, powershell, proftpd, progress, prolog, properties, providex, purebasic, pycon, pys60, python, q, qbasic, rails, rebol, reg, rexx, robots, rpmspec, rsplus, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, spark, sparql, sql, stonescript, systemverilog, tcl, teraterm, text, thinbasic, tsql, typoscript, unicon, upc, urbi, uscript, vala, vb, vbnet, vedit, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xbasic, xml, xorg_conf, xpp, yaml, z80, zxbasic
type fsm_out_type is (w1 , w2 ,w3 ,w4 ,w5);
Для задания состояний автомата в архитектурном теле определяется перечислимый тип t_state. Предполагается, что начальное состояние автомата равно a1. Начальное состояние явно не указывается, так как при инициализации будет взят элемент нижней границы перечислимого типа – это и будет элемент a1.
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;
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;</source>
Многократное изменение синхросигнала 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. Для рассмотренного примера конечного автомата выделение подсхем показано на рисунке.
