Проектирование цифровых систем на языках описания аппаратуры/Лекция 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.
Разработаны различные формы задания конечных автоматов. Например, в таблице задан конечный автомат Мили с четырьмя внутренними состояниями
