Курсова робота Структурні автомати
1. Основні поняття. Канонічний спосіб структурного синтезу автоматів. Теорема Глушкова про структурну повноту
2. Основні етапи канонічного методу структурного синтезу
2.1 Кодування алфавітів автомата
2.2 Вибір елементів пам'яті автомата
2.3 Вибір функціонально-повної системи логічних елементів
2.4 Побудова рівнянь булевих функцій збудження та виходів автомата
2.5 Побудова функціональної схеми автомата
3. Приклад канонічного методу структурного синтезу
4. Елементи пам'яті
4.1 Елементи пам'яті з одним інформаційним входом
4.2 Елементи пам'яті із двома інформаційними входами
4.3 Матриця переходів елемента пам'яті
5. Кодування станів та виходів автомата та складність
6. Забезпечення стійкості функціонування цифрових автоматів. Перегони в автоматах
6.1 Методи усунення гонок в автоматах
Тема курсової роботи "Структурні автомати" з дисципліни "Прикладна теорія управління автоматами".
- Основні поняття структурних автоматів;
- канонічний метод структурного синтезу автоматів;
- теорему Глушкова про структурну повноту;
- Основні етапи канонічного методу структурного синтезу;
- Приклади канонічного методу структурного синтезу;
- кодування станів та виходів автомата та складність комбінаційних схем;
- Забезпечення стійкості функціонування цифрових автоматів;
- перегони в автоматах;
- методи усунення гонок в автоматах та ін.
1.Основні поняття. Канонічний спосіб структурного синтезу автоматів. Теорема Глушкова про структурну повноту
Після етапом абстрактного синтезу автоматів,закінчується мінімізацією числа станів, слідує етап структурного синтезу, ланцюгом якого є побудова схеми, що реалізує автомат з логічних елементів заданого типу.
Якщо абстрактний автомат був лише математичною моделлю дискретної системи, то структурному автоматі враховується структура вхідних і вихідних сигналів автомата, і навіть його внутрішній пристрій лише на рівні структурних схем. Структурним синтезом займається структурна теорія автоматів, основним завданням якої є знаходження загальних прийомів побудови структурних схем автоматів на основі композиції елементарних автоматів, що належать до заданого кінцевого числа типів.
Під композицією елементарних автоматів у випадку розуміється таке.
Нехай задані елементарні автомати S1. Sk. Зробимо об'єднання елементарних автоматів у систему спільно діючих автоматів. Введемо на розгляд деяке кінцеве безліч вузлів, званих зовнішніми вхідними та зовнішніми вихідними вузлами. Ці вузли відрізняються від вузлів аналізованих елементарних автоматів, які звуться внутрішніх. Композиція автомата у тому, що у отриманої системі елементарних автоматів S1 . Sk та зовнішніх вузлів здійснюється ототожнення деяких вузлів (як зовнішніх, так і внутрішніх). З точки зору спільної роботи системи автоматів сенс операції ототожнення вузлів полягає в тому, що елементарний сигнал, що потрапляє на один з вузлів, що входять в безліч вузлів, що ототожнюються між собою, потрапляє тим самим на всі вузли цієї множини. так звану схему (мережа) автоматів. Вважатимемо, що автомати, що входять до схеми автоматів, працюють спільно, якщо в кожен момент автоматного часу навсі зовнішні вхідні вузли подається набір вхідних сигналів (структурний вхідний сигнал схеми) і всіх зовнішніх вихідних вузлів знімається набір вихідних сигналів (структурний вихідний сигнал).
У структурної теорії як вхідні, так і вихідні канали вважаються які з елементарних вхідних (вихідних) каналів. По всіх елементарних вхідних каналах можуть передаватися тільки елементарні сигнали.
Малюнок 1- Структурний автомат
Набір можливих значень сигналів, що подаються на один зовнішній вхідний (вихідний) вузол називається структурним вхідним (вихідним) алфавітом автомата. Алфавіт має бути кінцевим.
Вхідний і вихідний сигнали задаються кінцевими впорядкованими наборами елементарних сигналів, званими векторами, а елементарні сигнали, що їх складають, - компоненти векторів. Число компонент вектора - це розмірність алфавіту.
Наприклад, X=1 x2 x3 x4 x5 > - Вхідний алфавіт абстрактного автомата.
Структурний вхідний алфавіт, розмірність якого дорівнює трьом:
Векторне уявлення вхідних та вихідних сигналів називається структурним вхідним вихідним сигналом, відповідно.
Передбачається, що всі автомати, що входять до композиції, мають один і той же структурний алфавіт і працюють в тому самому автоматному часі. В даний час найбільш поширеним структурним алфавітом є двійковий, що пояснюється простотою його подання у сучасних елементах та приладах. Крім того, для двійкового алфавіту найбільш розроблений апарат булевих функцій, що дозволяє робити багато операцій над схемою формально. Тому надалі при вирішенні завдань структурного синтезу автоматів використовуватиметься переважно двійковий, структурний алфавіт.
Припустимо, що коженмомент автоматного часу структурний вихідний сигнал схеми однозначно визначається кінцевою послідовністю структурних вхідних сигналів, що надійшла до цього часу, початковими станами входять в схему автоматів і зробленими при побудові схеми ототожненнями вузлів. У цьому випадку побудовану схему розглядатимемо як деякий автомат S, а саму схему назвемо структурною схемою цього автомата.
Побудований таким чином автомат S є результатом композиції елементарних автоматів S1. Sk. На відміну від абстрактного C-автомата, що має один вхідний і два вихідних канали, на які надходять сигнали у вхідному та вихідних алфавітах автомата, структурний автомат має вхідні та вихідні канали, на яких з'являються сигнали в структурному алфавіті автомата. У разі двійкового алфавіту кожен вхідний та вихідні сигнали абстрактного автомата можуть бути закодовані векторами різної довжини відповідно, компоненти яких приймають два значення – нуль та одиницю.
На етапі структурного синтезу попередньо вибираються елементарні автомати, з яких потім їх композиції будується структурна схема отриманого на етапі абстрактного синтезу автомата Милі, Мура або C-автомата. Якщо розв'язання задачі структурного синтезу існує, то кажуть, що задана система автоматів структурно повна.
Нині немає скільки-небудь ефективних методів (істотно простіших, ніж метод перебору всіх варіантів) вирішення основного завдання структурного синтезу за будь-якого набору структурно повних систем елементарних автоматів. Тому зазвичай застосовується так званий канонічний метод структурного синтезу, при якому використовуються елементарні автомати деякого спеціального виду: автомати з пам'яттю, що мають більше одного стану, та автоматибез пам'яті – з одним станом. Автомати першого класу звуться елементів пам'яті, а автомати другого класу - комбінаційних чи логічних елементів.
Теоретичним обґрунтуванням канонічного методу структурного синтезу автоматів є доведена теорема про структурну повноту (теорема Глушкова):
Будь-яка система елементарних автоматів, що містить автомат Мура з нетривіальною пам'яттю, що має повну систему переходів і повну систему виходів, і якусь функціонально повну систему логічних елементів, є структурно повною.
Існує загальний конструктивний прийом (канонічний метод структурного синтезу), що дозволяє в даному випадку звести завдання структурного синтезу довільних автоматів до синтезу комбінаційних схем.
Результатом канонічного методу структурного синтезу є система логічних рівнянь, що виражає залежність вихідних сигналів автомата (функції виходів автомата) і сигналів, що подаються на входи елементів, що запам'ятовують, від сигналів, що приходять на вхід всього автомата в цілому, і сигналів, що знімаються з виходу елементів пам'яті (функції збудження елементів пам'яті автомата). Ці рівняння називаються канонічними.
Для правильної роботи схем, очевидно, не можна дозволяти, щоб сигнали на вході елементів, що запам'ятовують, безпосередньо брали участь в освіті вихідних сигналів, які по ланцюгах зворотного зв'язку подавалися в той же момент часу на ці входи. У зв'язку з цим елементами, що запам'ятовують, повинні бути не автомати Милі, а автомати Мура (див. рівняння функціонування цих автоматів).
Таким чином, структурно повна система елементарних автоматів повинна містити хоча б один автомат Мура. У той же час для синтезу будь-яких автоматів із мінімальним числомелементів пам'яті необхідно як такі елементи вибирати автомати Мура, мають повну систему переходів і повну систему виходів - звані повні автомати.
Розглянемо повноту автоматів пам'яті з прикладу автомата Мура. (табл. 1.) Повнота системи переходів означає, що з будь-якої пари станів (am ,…,аs ) автомата знайдеться вхідний сигнал, переводящий перший елемент цієї пари am у другий - as т. е. у такому автоматі у кожному стовпці таблиці переходів повинні зустрічатися всі стани автомата. Повнота системи виходів автомата Мура у тому, що кожному стану автомата поставлено відповідність свій особливий вихідний сигнал, відмінний від вихідних сигналів інших станів.
Вочевидь, що у такому автоматі число вихідних сигналів дорівнює числу станів автомата. Разом з попереднім твердженням це призводить до того, що в автоматі Мура з повною системою виходів можна ототожнити стан автомата з його вихідними сигналами. У зв'язку з цим в автоматах пам'яті ми будемо використовувати одні й самі позначення і для станів, і для вихідних сигналів, тобто зазначена таблиця переходів в автоматах Мура з повною системою виходів перетворюється просто на таблицю переходів. Автомат Мура у табл. 1. задовольняє умовам повноти системи переходів та виходів.
Наявність функціонально повної системи логічних елементів дозволяє реалізувати бульову функцію будь-якого ступеня складності.
Після вибору елементів пам'яті таКодування станів синтезу структурного автомата зводиться до синтезу комбінаційної схеми, що реалізує канонічні рівняння.
Автомат пам'яті також можна розглядати на абстрактному та структурному рівнях. Абстрактний автомат пам'яті має один вхідний та один вихідний канали. При переході від абстрактного автомата до структурного автомата вхідні та вихідні сигнали мають бути закодовані відповідними двійковими наборами.
2.Основні етапи канонічного методу структурного синтезу
У канонічному методі структурного синтезу можна виділити кілька основних етапів:
1. Кодування алфавітів автомата.
2. Вибір елементів пам'яті.
3. Вибір функціонально повної системи логічних елементів.
4. Запис та мінімізація канонічних рівнянь.
5. Побудова функціональної схеми автомата.
Вихідними даними для початку роботи даного методу є абстрактний цифровий автомат із пам'яттю, заданий таблицею переходів та виходів. Розглянемо докладніше кожен із етапів канонічного методу.
2.1 Кодування алфавітів автомата
На структурному рівні кожна буква вхідного алфавіту xХ, кожна буква вихідного алфавіту yY та кожна буква алфавіту станів аА кодується двійковими векторами (двійковими наборами), число компонент яких визначається таким чином:
де int - найближче ціле число.
Х, У, А - потужність алфавіту вхідного, вихідного та станів, відповідно. Потужністю алфавіту називається кількість різних символів, що входять до цього алфавіту.
Процес заміни букви алфавіту (X, У, А) абстрактного автомата двійковими векторами носить назву кодування та описується таблицями кодування. Таблиця кодування маємо такий вигляд: у лівій частиніперераховуються всі символи абстрактного алфавіту, а правій - відповідні їм двійкові вектори.
Абстрактний автомат Милі заданий таблицею переходів та виходів (табл. 2.). Виконати кодування алфавітів автомата.
| А\ Х | x1 | x2 |
| a1 | a2 /y1 | a3 /y3 |
| a2 | a1 /y2 | a2 /y1 |
| a3 | a2 /y2 | a1 /y1 |
Випишемо алфавіти автомата та визначимо довжини векторів кодів алфавітів:
Заповнимо таблиці кодування:
| x1 | 0 |
| x2 | 1 |
Результуюча таблиця - структурна таблиця переходів та виходів автомата (табл. 6.) Отриманням структурної таблиці переходів-виходів автомата закінчується етап кодування.