Мінімізація кількості внутрішніх станів

повністю визначених автоматів

Розглянемо метод мінімізації повністю визначених автоматів, запропонований Ауфенкампом і Хоном.

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

Для користування методом введемо декілька означень.

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

Об'єднання всіх 1-еквівалентних станів абстрактного автомата утворює 1-клас еквівалентності.

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

Об'єднання всіх 2-еквівалентних станів утворює 2-клас еквівалентності.

По індукції можна розповсюдити визначення до i-еквівалентних станів та i-класів еквівалентності.

Якщо для деякого i розбиття станів автомата на (i+1) - класи співпадає з розбиттям на i-класи, то воно є розбиттям і на -класи еквівалентності.

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

Все вищевикладене безпосередньо застосовується для мінімізації автомата Мілі. При мінімізації повністю визначених автоматів Мура вводиться поняття 0-еквівалентності станів і розбиття безлічі станів на 0-еквівалентні класи: до такого класу відносяться однаково відмічені стани автомата Мура.

Якщо два 0-еквівалентні стани будь-яким вхідним сигналом переводиться в два 0-еквівалентні стани, то вони називаються 1-еквівалентними. Всі подальші класи еквівалентності станів для автомата Мура визначаються аналогічно приведеному для автоматів Мілі.

Структурний синтез цифрових автоматів

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

На відміну від абстрактного автомата, що має один вхід і один вихід, на які поступають сигнали, у вхідному і вихідному W={W1,..,WG} алфавітах, структурний автомат має L вхідних х1,х2,..,хL і N вихідних y1,y2,…,yN каналів, на кожному з яких присутній сигнал структурного алфавіту.

Рисунок 1.3 – Абастактний (а) і структурний (б) автомати

Як правило, в якості структурного використовується двійковий алфавіт.

В цьому випадку кожному вхідному сигналу ZF абстрактного автомата відповідає деякий двійковий вектор (lf1,lf2,..,lfL), де lfL{0,1}.

Очевидно, що для представлення (кодування) вхідних сигналів Z1,..,ZF абстрактного автомата різними двійковими векторами повинна бути виконана умова L ] log2F [, аналогічно N ] log2G [.

Наприклад, Z={Z1,Z2,Z3,Z4} W={W1,W2,W3}.

Тоді Llog24=2, Nlog23=2.

Закодувати вхідні і вихідні сигнали можна,наприклад, так:

Z1 = 00; W1 = 00;

Z2 = 01; W2 = 01;

Z3 = 10; W3 = 11.

Z4 = 11.

Отже, структурний автомат з двома входами x1 і x2 і двома виходами y1 і y2 може бути представлений у вигляді:

Рисунок 1.4 – Структурний автомат

Задача синтезу структури автомата

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

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

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

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

Для правильної роботи схем сигнали на вході елементів, що запам'ятовують, не повинні безпосередньо брати участь в утворенні вихідних сигналів, які по ланцюгах зворотного зв'язку подавалися б в той же самий момент часу на ці входи. Елементами, що запам'ятовують, повинні бути не автомати Мілі, а автомати Мура. Таким чином, структурно повна система елементарних автоматів повинна містити хоча б один автомат Мура. В той же час, для синтезу автоматів з мінімальним числом елементів пам'яті, необхідно як такі елементи вибирати автомати Мура, що мають повну систему переходів і повну систему виходів – повні автомати.

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

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

Рисунок 1.5 – Структурна схема цифрового автомата

Канонічний метод структурного синтезу