Задання закону функціонування асинхронного автомата

Основні етапи синтезу скінченних автоматів

Задача синтезу (проектування) скінченних автоматів майже діаметрально протилежна попередній задачі аналізу.

У ряді літературних джерел приводиться послідовність кроків, які поетапно необхідно робити в процесі розробки автомата. Приблизно такі кроки можна описати як етапи проектування:

1. Задається закон функціонування автомата;

2. Мінімізується кількість внутрішніх станів автомата;

3. Кодуються стани автомата;

4. Визначаються функції збудження елементів пам’яті і функції виходів, а також забезпечується їх мінімізація;

5. Складається функціональна схема автомата в вибраному елементному базисі.

Перші три етапи відносяться до абстрактного синтезу автомата, при якому по значеннях вхідних і вихідних сигналів визначаються і кодуються його стани.

При абстрактному синтезі на основі словесного, табличного, за допомогою часових діаграм і інших засобів опису роботи автомату виявляється закон його функціонування і задаються функції переходів і виходів. На цьому етапі забезпечується мінімізація кількості станів і визначається кількість елементів пам’яті, необхідних для побудови автомата.

Решта станів забезпечують процедуру одержання структурних схем автоматів, що задаються кодованими таблицями входів і виходів. Така процедура називається структурним синтезом.

Задача структурного синтезу полягає у виборі типів елементарних автоматів (тригерів) і знаходження такого способу їх з’єднання між собою, який забезпечить функціонування автомата у відповідності до заданих кодованими таблицями переходів і виходів.

Основною задачею цього етапу є синтез комбінаційних схем з урахуванням вибраних тригерів, знаходження мінімальних форм функцій збудження і виходів. Етап закінчується побудовою функціональної схеми автомата.

Задання закону функціонування асинхронного автомата

Початковою інформацією для першого етапу може служити словесний опис алгоритму функціонування автомата або аналіз часових діаграм його роботи. Результатом цього етапу повинно бути отримання формалізованого опису закону функціонування в вигляді таблиць переходів, графів переходів і т. п. Практичний досвід показує, що зручно задавати автомат за допомогою початкових таблиць переходів (ПТП), оскільки їхня структура є найбільш простою.

ПТП характеризується тим, що в кожному її рядку є тільки один стійкий стан, а всі переходи між станами прості.

Розглянемо декілька прикладів складання ПТП, оскільки цей етап є одним з найбільш важливих і складних при проектуванні автоматів.

Необхідно синтезувати автомат (цифровий пристрій), що пропускає імпульси прямокутної форми , якщо немає заборони , і не пропускає, якщо заборона існує . При цьому імпульси не повинні спотворюватись незалежно від моменту появи сигналу заборони .

Такий автомат має назву генератора з забороною. Для більш формального опису можна побудувати часові діаграми, які пояснюють його функціонування. Відповідні діаграми для вхідних і вихідних сигналів приведені на рис. 6.1.

Рис.6.1. Часова діаграма роботи автомата

На основі аналізу зміни вхідних і вихідних сигналів можна вводити стани автомата, які характеризуються станом входу (сигналами і з вхідного алфавіту Х) і станом виходу Y (сигналом у).

Різноманітним комбінаціям вхідних та вихідних сигналів припишемо відповідні номери, які характеризують всі можливі стани автомата. За початковий приймемо стан , який характеризується значеннями вхідних сигналів і значенням вихідного сигналу . Стан є стійким, тобто таким, який не зміниться без дії вхідних сигналів. В таблиці ПТП, що будується, стійкі стани будемо виділяти дужками. Нестійкі стани автомата – це такі, які можуть змінюватися на стійкі без зміни вхідних сигналів. Такі стани в ПТП будемо позначати їх номерами без дужок.

Якщо на автомат, що знаходиться в стійкому стані , діятиме вхідний сигнал , то він перейде в новий, але нестійкий, стан, який потім перейде в стійкий . Нестійкий стан відповідає ситуації, коли в результаті зміни вхідного сигналу Х змінились сигнали збудження тригерів, але ще не змінився вихідний сигнал, тобто у залишився рівним нулю. По закінченні перехідних процесів автомат перейде в стійкий стан , який характеризується вхідними сигналами і вихідним .

Переходу зі стійкого стану (0) в нестійкий 1 в ПТП відповідає переміщення в межах першого рядка з клітки з координатами в клітку з координатами . Вихідний сигнал при цьому залишається незмінним: .

Переходу з нестійкого стану 1 в стійкий стан (1) в ПТП відповідає переміщення в межах одного стовпця з координатами з першого рядка в другий. Вихідний сигнал при цьому змінюється і приймає значення (табл. 6.1).

Таблиця 6.1.

Звідси маємо, що перехід з одного стійкого стану (0) в інший стійкий стан (1) відповідає двом фрагментам переходу: спочатку у межах рядка, а потім у межах стовпця.

З часової діаграми, приведеної на рис. 6.1, видно, що стійкий стан (1) при змінюється на стан (0), а потім під дією сигналу переходить в стан (2), і т.д.

Номери станів на часовій діаграмі зображають так, щоб кожна змінювана ситуація в сигналах X, Y мала свій номер і щоб були враховані всі зовнішні однакові ситуації, які вимагають спеціального запам’ятовування. Наприклад, якщо автомат згенерує третій імпульс, то кожен з трьох імпульсів і кожну з пауз необхідно позначити своїм номером.

Аналіз всієї часової діаграми дозволяє заповнити ПТП (див. табл. 6.2), але не повністю – частина кліток залишається вільними.

Таблиця 6.2.

Наприклад, у першому рядку ПТП залишилась незаповненою клітка з . Оскільки стан є стійким при , то перехід в новий стан, що відповідає , вимагає одночасної зміни обох вхідних сигналів і , що практично неможливо. Оскільки перехід виконати неможливо, в ПТП в відповідній клітці проставляється риска, яка інформує про наявність невизначеного стану. Аналогічно виключаються інші переходи типу , а також .

Розглянемо ще один приклад. Необхідно скласти ПТП для автомата, призначеного для ділення частоти. На виході автомата створюється імпульс, якщо на вхід поступило 3 імпульси (часові діаграми приведені на рис. 6.2).

Таблиця 6.3.

Рис.6.2.

Приклад демонструє випадок, коли деяким ситуаціям, що повторюються, необхідно поставити в відповідність різні стани. Так, стани 0, 2, 4 (як і 1, 3) на часових діаграмах нічим не відрізняються між собою. Але, в той же час, зрозуміло, що для автомата це різні стани, оскільки в кожному з них повинна запам’ятовуватись різна інформація, що мала місце на попередніх інтервалах часу.

Таблиця ПТП автомата, що розглядається, має лише 3 стовбці, і при її заповненні вільні клітки не з’являються (див. табл. 6.3).