Способи опису роботи автоматів

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

Розглянемо спочатку опис роботи автомата з використанням таблиць переходів та виходів. Стовбці (рядки) цих таблиць позначають символами з множини Q, а рядки (стовбці) – символами з множини Х.

Кількість рядків таблиці переходів визначається кількістю комбінацій вхідних сигналів ρ, а кількість стовбців – відповідно, кількість станів М автомата.

У табл. 5.2 зображена таблиця автомата з , .

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

Таблиця 5.2. Таблиця 5.3.

Таблиця 5.4.

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

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

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

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

Як приклад, розглянемо більш детально автомати, що описуються табл. 5.2 – табл. 5.4.

При двійкових вхідних сигналах входи автоматів , , можуть бути задані вхідними логічними змінними та , тобто з множини . В алфавіті Х матимемо різних слова, а саме: , , , . Звідси витікає, що – це заборонене слово для автоматів, що розглядаються. Але така заборона може існувати не для всіх станів автомата, а тільки для деяких. Наочний приклад такого автомата приводиться в [Борисенко О.А.], що заданий таблицею переходів табл. 5.5. З таблиці витікає, що при стані Q₀ на вхід автомата не повинен надходити сигнал , оскільки перехід у такому випадку не визначений.

Таблиця 5.5.

Можна прийняти, що X₁ = x = 1, а і, відповідно, лише значення X₁ = 1 може змінювати стан автомата. З табл. 5.5 однозначно визначається і послідовність зміни станів автомата при дії X₁ : . Для цього необхідно задати послідовність X₁ , X₁ , X₁ . З цього витікає, що автомат закінчує свою роботу переходом до початкового стану. Якщо функція λ = 1, то виходи автомата Мілі одночасно визначатимуться значеннями його внутрішніх станів. В тому випадку, коли X₁ є тактовим сигналом, що діє лише на тригери, а стани автомата змінюються упорядковано в зростаючому або спадаючому напрямку, автомат називається лічильним автоматом, або лічильником.

Більш наочним є спосіб опису автоматів з допомогою графів, подібно до того, як описувалася робота тригерів. Різниця полягає в тому, що автомат може мати суттєво більшу кількість станів. На рис. 5.2 показані граф-схеми автоматів Мілі і Мура, які задані табл. 5.2 – 5.3 (рис.5.2.а), табл.5.4 (рис.5.2, б).

Рис.5.2. Граф-схеми автоматів Мілі (а) і Мура (б)

Граф-схеми широко використовуються як при аналізі, так і при синтезі автоматів, а також при переході від словесного до формалізованого їх опису.

За допомогою таблиць переходів і виходів, як і за допомогою граф-схеми завжди можна знайти вихідну реакцію автомата на будь-яке вхідне слово, що належить множині Х.

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

Таблиця 5.6.

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

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

На рис. 5.3 приводиться приклад дерева переходів, що відповідає табл. 5.2.

Рис.5.3. Дерево переходів