Проектирование цифровых систем на языках описания аппаратуры/Лекция 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.
Иначе говоря, выше представлена таблица задания функций δ , λ, которая называется совмещенной таблицей переходов и выходов.
