4 Моделювання мікропрограмного автомата
ЛАБОРАТОРНА РОБОТА № 4
Мета роботи. Вивчити структурно-функціональну організацію операційного пристрою, формальну модель абстрактного автомата. Навчитися моделювати мікропрограмний автомат Мура. Освоїти інструменти проектування і відлагодження кінцевих автоматів САПР Aldec Active-HDL.
4.1 Мікропрограмний автомат
Операційний пристрій представляє собою композицію двох блоків: керуючого автомата (КА) і операційного автомата (ОА) [1,2,8]. Структурно-функціональна організація операційного пристрою показана на рис.4.1. Операційний автомат виконує перетворення даних – операції. Дані надходять на входи h1..hF. Результат перетворення в ОА формується на виходах b1..bG. Керуючий автомат виробляє розподілену за часом послідовність керуючих сигналів – мікрокоманд, під впливом яких ОА виконує перетворення даних (операції).
Рисунок 4.1 – Операційний пристрій
Керуючий автомат операційного пристрою є мікропрограмним автоматом (МПА). Тобто він працює відповідно до мікропрограми.
Мікрооперацією (МО) називається елементарний неподільний акт обробки даних, що відбувається протягом одного такту автоматного часу. На рис.4.1 видно, що мікрооперації формуються вектором сигналів Y = {y1,.,yN}. Функціональне призначення МПА – це формування послідовності мікрооперацій відповідно до виконання мікропрограми (згідно алгоритму роботи операційного пристрою). Мікрокомандою (МК) називається сукупність мікрооперацій, що виконуються одночасно.
Для керування послідовністю формування мікрокоманд використовуються логічні умови X={x1..,xL}. Логічні умови (ЛУ) можуть бути сформовані як в ОА, так і поступати ззовні. Значення ЛУ перевіряються на кожному такті автоматного часу, внаслідок чого МПА формує відповідну функцію переходу.
Алгоритм роботи МПА задається у вигляді граф-схеми алгоритму (ГСА). ГСА – це орієнтований граф, що складається з вершин чотирьох типів: початкової, кінцевої, операторної і умовної (рис. 4.2,а).
За допомогою ГСА, приведеної на рис.4.2,б, заданий алгоритм роботи МПА S1. Вона містить початкову, кінцеву вершини, 7 операторних і 6 умовних вершин.
а – типи вершин ГСА; б – граф схема алгоритму автомата S1
Рисунок 4.2 – Граф-схема алгоритму
4.2 Абстрактний автомат
Абстрактний автомат S призначений для роботи в дискретному часі і задається за допомогою шестикомпонентного кортежу S = {А, Z, W, δ, λ, a1}, де
А = {a1,..,aM} – алфавіт станів автомата;
Z = {z1,..,zF} – множина вхідних сигналів (вхідний алфавіт);
W = {w1,..,wG} – множина вихідних сигналів (вихідний алфавіт);
δ – функція переходів, що визначає стан автомата у момент часу t+1 залежно від його стану у момент часу t;
λ – функція виходів, що формує вихідне слово у момент часу t+1 залежно від його стану у момент часу t;
a1 – початковий стан автомата.
Абстрактні автомати прийнято поділяти на два великі класи: автомати Мілі і автомати Мура [8-10]. В автоматі Мілі функція виходів λ ставить у відповідність парі "стан – вхідний сигнал" (am, zf) вихідний сигнал wg, тобто wg= λ (am, zf). В автоматі Мура функція λ в якості аргументу використовує тільки стан am, тобто wg= λ (am).
Кінцевим автоматом називають автомат з визначеною кількістю станів. У загальному випадку функції δ і λ кінцевого автомата прийнято задавати за допомогою таблиць переходів і виходів. Автомат Мілі задають суміщеною таблицею переходів і виходів (табл.4.1), автомат Мура – відзначеною таблицею переходів (табл.4.2). Вони компактно описують графи переходів МПА [11]. На рис.4.3 зображені графи переходів автоматів S2 і S3, що задані табл.4.1 – 4.2.
Таблиця 4.1 – Суміщена таблиця переходів Таблиця 4.2 – Відзначена таблиця переходів
та виходів (автомат Мілі) (автомат Мура)
|
|
a1 |
a2 |
a3 |
a4 |
|
|
a1(w3) |
a2(w2) |
a3(w3) |
a4(w1) |
|
z1 |
a2(w1) |
a2(w1) |
a1(w2) |
a1(w4) |
|
z1 |
a1 |
a3 |
a1 |
a4 |
|
z2 |
a4(w5) |
a3(w3) |
a4(w4) |
a3(w5) |
|
z2 |
a2 |
a4 |
a4 |
a1 |
а – автомат Мілі S2; б – автомат Мура S3
Рисунок 4.3 – Графи переходів
Приклад П4.1 – Формування послідовності вихідних сигналів
Якщо на вхід автоматів S2 і S3 подавати послідовність z1 z2 z1 z1 z2 z1 z2 z2, то на виході автоматів Мілі і Мура буде формуватися послідовність вихідних сигналів, що відповідає графам переходів Г(S2) і Г(S3) (табл.4.3).
У момент часу t=0, коли автомат знаходиться в початковому стані a1, автомат Мілі не формує вихідне слово. В загальному випадку можна сказати, що реакція автомата Мілі відома у момент переходу, тоді як в автоматі Мура вихідне слово відповідає поточному стану. Цей факт необхідно враховувати, наприклад, під час перетворення автомата Мура в автомат Мілі.
Таблиця 4.3 – Формування вихідних слів
|
Час |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Вхід |
|
z1 |
z2 |
z1 |
z1 |
z2 |
z1 |
z2 |
z2 |
|
S3 |
a1 (w3) |
a1 (w3) |
a2 (w2) |
a3 (w3) |
a1 (w3) |
a2 (w2) |
a3 (w3) |
a4 (w1) |
a1 (w3) |
|
S2 |
a1 (–) |
a2 (w1) |
a3 (w3) |
a1 (w2) |
a2 (w1) |
a3 (w3) |
a1 (w2) |
a4 (w5) |
a3 (w5) |