ЗМІСТ
Введення
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. Основні поняття. Канонічний метод структурного синтезу автоматів. Теорема Глушкова про структурної повноті
Слідом за етапом абстрактного синтезу автоматів, заканчивающимся мінімізацією числа станів, слід етап структурного синтезу, ланцюгом якого є побудова схеми, що реалізує автомат з логічних елементів заданого типу.
Якщо абстрактний автомат був лише математичною моделлю дискретної системи, то в структурному автоматі враховується структура вхідних і вихідних сигналів автомата, а також його внутрішній устрій на рівні структурних схем. Структурним синтезом займається структурна теорія автоматів, основним завданням якої є знаходження спільних прийомів побудови структурних схем автоматів на основі композиції елементарних автоматів, що належать до заздалегідь заданому кінцевому числу типів.
Під композицією елементарних автоматів в загальному випадку розуміється наступне.
Нехай задані елементарні автомати S 1 , ..., S k . Зробимо об'єднання елементарних автоматів в систему спільно працюючих автоматів. Введемо в розгляд деякий кінцеве безліч вузлів, званих зовнішніми вхідними і зовнішніми вихідними вузлами. Ці вузли відрізняються від вузлів розглянутих елементарних автоматів, які носять назву внутрішніх. Композиція автомата полягає в тому, що в отриманій системі елементарних автоматів S 1 , ..., S k і зовнішніх вузлів проводиться ототожнення деяких вузлів (як зовнішніх, так і внутрішніх). З точки зору спільної роботи системи автоматів сенс операції ототожнення вузлів складається в тому, що елементарний сигнал, що потрапляє на один з вузлів, що входять в безліч ототожнюються між собою вузлів, потрапляє тим самим на всі вузли цієї множини, Після проведених ототожнень вузлів система автоматів перетворюється на так звану схему (мережа) автоматів. Будемо вважати, що автомати, що входять в схему автоматів, працюють спільно, якщо в кожний момент автоматного часу на всі зовнішні вхідні вузли подається набір вхідних сигналів (Структурний вхідний сигнал схеми) і з усіх зовнішніх вихідних вузлів знімається набір вихідних сигналів (структурний вихідний сигнал).
У структурній теорії як вхідні так і вихідні канали вважаються складаються з елементарних вхідних (вихідних) каналів. За всіма елементарним вхідним (вихідним) каналах можуть передаватися тільки елементарні сигнали.
Рисунок 1 - Структурний автомат
Набір можливих значень сигналів, що подаються на один зовнішній вхідний (вихідний) вузол, називається структурним вхідним (вихідним) алфавітом автомата. Алфавіт повинен бути кінцевим.
Вхідний і вихідний сигнали задаються кінцевими впорядкованими наборами елементарних сигналів, називаними векторами, а складові їх елементарні сигнали - компоненти векторів. Число компонентів вектора - це розмірність алфавіту.
Наприклад, X = {x 1 , x 2 , x 3 , x 4 , x < sub> 5 } - вхідний алфавіт абстрактного автомата.
Структурний вхідний алфавіт, розмірність якого дорівнює трьом:
X 1 = 000, x 2 = 001, x 3 = 010, x 4 = 011 , x 5 = 100.
Векторне представлення вхідних і вихідних сигналів називається структурним вхідним вихідним сигналом, відповідно.
Передбачається, що всі входять в композицію автомати мають один і той же структурний алфавіт і працюють в одному і тому ж автоматному часу. В даний час найбільш поширеним структурним алфавітом є двійковий, що пояснюється простотою його представлення в сучасних елементах і приладах. Крім того, для двійкового алфавіту найбільш розроблений апарат булевих функцій, що дозволяє виробляти багато операцій над схемою формально. Тому надалі при вирішенні задач структурного синтезу автоматів буде використовуватися в основному двійковий, структурний алфавіт.
Припустимо, що в кожний момент автоматного часу структурний вихідний сигнал схеми однозначно визначається надійшла до цього часу кінцевою послідовністю структурних вхідних сигналів, початковими станами входять у схему автоматів і зробленими при побудові схеми ототожненнями вузлів. У цьому випадку побудовану схему будемо розглядати як деякий автомат S, а саму схему назвемо структурною схемою цього автомата.
Побудований таким чином автомат S є результат композиції елементарних автоматів S 1 , ..., S k . На відміну від абстрактного C-автомата, що має один вхідний і два вихідних каналу, на які надходять сигнали у вхідному і вихідних алфавітах автомата, структурний автомат має вхідні і вихідні канали, на яких з'являються сигнали в структурному алфавіті автомата. У разі двійкового алфавіту кожен вхідний і вихідні сигнали абстрактного автомата можуть бути закодовані векторами різної довжини відповідно, компоненти яких беруть два значення - нуль і одиницю.
На етапі структурного синтезу попередньо вибираються елементарні автомати, з яких потім шляхом їх композиції будується структурна схема отриманого на етапі абстрактного синтезу автомата Мілі, Мура або C-автомата. Якщо рішення задачі структурного синтезу існує, говорять, що задана система автоматів структурно повна.
В Нині немає скільки-небудь ефективних методів (істотно більше простих, ніж метод перебору всіх варіантів) вирішення основного завдання структурного синтезу при будь-якому наборі структурно повних систем елементарних автоматів. Тому зазвичай застосовується так званий канонічний метод структурного синтезу, при якому використовуються елементарні автомати деякого спеціального виду: автомати з пам'яттю, що мають більше одного стану, і автомати без пам'яті - з одним станом. Автомати першого класу носять назву елементів пам'яті, а автомати другого класу - комбінаційних або логічних елементів.
Теоретичним обгрунтуванням канонічного методу структурного синтезу автоматів є доведена в теорема про структурну повноту (теорема Глушкова):
Усяка система елементарних автоматів, яка містить автомат Мура з нетривіальною пам'яттю, ...
