Загальні відомості про цифрові автомати

Вичерпне визначення поняття "цифровий автомат" дав автор цього терміну В.М.Глушков[[i]]: "Електронні цифрові машини з програмним керу­ванням являють собою приклад одного з найпоширеніших сьогодні типів перетворювачів дискретної інформації, названих дискретними або цифровими автоматами. Тому задача синтезу схем електронних цифрових ма­шин з програмним керуванням входить як частковий випадок в більш загальну задачу синтезу схем цифрових автоматів". Отже, будь-який елемент, вузол, пристрій чи навіть ЕОМ, незалежно від складності їх функціонування, є перетворювачами цифрової інформації – цифровими автоматами.

У загальному випадку на вхід цифрового автомата надходить множи­на двійкових змінних X₀, X₁, … X_N-1, а з виходу знімається множина двійкових функцій Y₀, Y₁, … Y_N-1. Відмінна особли­вість цифрових автоматів полягає в тому, що цей функціональний зв'я­зок визначається також дискретною множиною внутрішніх станів, причо­му перехід з одного стану в інший здійснюється стрибкоподібно. Ре­альні цифрові автомати можуть мати лише скінченну множину внутріш­ніх станів, а тому - скінченне число станів, входів та виходів. Че­рез це цифрові автомати називають ще скінченними.

Вихідні сигнали цифрового автомата залежать як від вхідних сигналів, що діють у даний (фіксований) момент часу, так і від передісторії, тобто від тих сигналів, які надійшли на його входи ра­ніше і зафіксувались в елементах пам’яті – запам’ятовувачах Отже, роботу автомата слід розглядати щодо конкретного інтервалу часу T -такту. Такт - це скінченний відрізок часу, який необхідний для пере­дачі одного з розрядів двійкового числа /біта/ - у разі послідовно­го коду, або всього двійкового коду (слова) одночасно - при паралель­ному коді. Залежно від того, чим визначається такт Т , розрізня­ють асинхронні та синхронні автомати. В асинхронних цифрових автома­тах Т ¹ cоnst і зміна вхідних сигналів зразу викликає певну зміну вихідних сигналів, у синхронних Т=const і тому зміна вхідних сигналів викликає певну зміну вихідних тільки після подачі синхронізуючих (тактових) імпульсів, які керують роботою автомата.

Для опису законів функціонування цифрових автоматів зручно ко­ристуватись абстрактним часом, що набуває цілих невід’ємних значень (t=0,1,2,...), а не тактом Т. Наприклад, позначимо такти роботи автомата як t і t + 1 . Алгебраїчний вираз, який розкриває функці­ональний зв’язок цифрового автомата між вихідним сигналом у такті t + 1 і множиною вхідних сигналів та станів у попередньому такті t називається функцією переходу d.

Найпростішою математичною моделлю цифрового автомата з одним вхо­дом X і одним виходом є абстрактний автомат, що заданий су­купністю таких величин:

скінченою множиною вхідних сигналів (вхідний алфавіт) автомата

;

скінченою множиною вихідних сигналів /вихідний алфавіт/ автомата

;

довільною множиною станів /алфавіт станів/ автомата

а також початковим станом автомата , функцією переходу автомата з одного стану в інший та функцією виходу ав­томата .