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

Структурним синтезом займається структурна теорія автоматів.

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

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

Завдання, які вирішує теорія структурного синтезу

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

Теорема про структурну повноту

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

Повнота переходів та виходів

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

Повнота виходів автомата означає, що у кожному стані автомат видає вихідний сигналвихідний сигнал, відмінний від сигналів що видаються в інших станах.

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

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

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

Див. також

Джерела

1. Лекція В. Д. Ромакіна -«Елементарні автомати з одним інформаційним входом» -ЧНУ ім П.Могили — 2013р — с.1.^{[неавторитетне джерело]}