Автоматів

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

Метод синтезу, в основу якого покладений вказаний принцип, дістав назву канонічного методу структурного синтезу автоматів з пам'яттю. Канонічний метод структурного синтезу оперує з елементарними автоматами, що розділяються на два великих класи. Перший клас складають елементарні автомати з пам’яттю, звані елементами пам'яті. Другий клас складають елементарні комбінаційні автомати - логічні елементи. Для зведення завдання структурного синтезу довільного автомата з пам’яттю до завдання синтезу комбінаційних схем накладають обмеження на тип елементів пам'яті. Результатом роботи методу є рівняння булевих функцій автомата в канонічній формі представлення. Початковим даним для початку роботи методу служить абстрактний цифровий автомат з пам'яттю.

Канонічний метод структурного синтезу дозволяє звести завдання побудови автомата з пам'яттю до завдання синтезу комбінаційних схем (КС). Цей метод заснований на представленні автомата схемами, приведеними на рис. 2.1 (для автомата Мура) і рис. 2.2 (для автомата Мілі). Кожен з автоматів побудований на двох комбінаційних схемах - КС1 і КС2, і двійкових елементах пам'яті, позначених як блок пам’яті. КС2 служить для формування вихідних сигналів

Комбінаційна схема КС1 реалізує переходи автомата з одного стану в інший стан у момент t + 1 дискретного часу під впливом вхідних сигналів x₁,., x_M і a₁,., a_N, що поступили на входи КС1 у момент t. Схема проектується виходячи із закодованої таблиці переходів і підграфу переходів вибраного елементу, пам'яті.

Рисунок 2.1 - Канонічна структура автомата Мура

Рисунок 2.2 - Канонічна структура автомата Мілі

Блок пам'яті є набором тригерів, які зберігають розряди закодованого номера стану. Кількість тригерів залежить від кількості станів, в яких може знаходитися автомат.

Комбінаційна схема КС2 реалізує функцію виходів автомата на основі векторів x і a (для автомата Мілі) або тільки вектору a (для автомата Мура).