Граф-схеми алгоритмів - інформатика, програмування
4. Граф-схеми алгоритмів
ДСА - це орієнтований зв'язний граф, що задає послідовність виконання операцій даного алгоритму і містить ряд операційних і умовних вершин, а також одну початкову і одну кінцеву вершини. Операторної називається вершина, - якої зіставляється одна або кілька мікрооперацій і відзначається відповідними керуючими сигналами У, а умовної - вершина, якої зіставляється деякий логічне умова X.
Будь-яка вершина ГСА, крім вершини «Початок», має по одному входу. Вершина «Початок» входів не має. Вершина «Початок» і будь-яка операторна вершина мають по одному виходу. Вершина «Кінець» виходів не має. Будь-яка умовна вершина має два виходи, позначуваних символами «Так» і «Ні»: Замість цих символів можуть бути використані цифри «1» і «О» відповідно. Зображення вершин «Початок», «Кінець», операторної вершини і умовної вершини ГСА представлено на рис. 2.
Малюнок 2-Графи схеми алгоритмів
ДСА складають так, щоб забезпечити виконання необхідних операцій і перевірку логічних умов відповідно до словесним описом алгоритму.
На підставі переліку микроопераций і реалізують їх функціональних вузлів складається структурна схема ОА. Тут широкими стрілками показані шини, за якими передається інформація, а тонкими - сигнали у, що керують роботою окремих вузлів або передачею інформації по шинам.
ДСА повинна відповідати таким вимогам:
1. Входи і виходи вершин з'єднуються один з одним за допомогою спрямованих завжди від виходу до входу.
2. Кожен вихід з'єднаний тільки з одним входом.
3. Будь-який вхід з'єднується, по крайней мере, з одним виходом.
4. Будь-яка вершина ГСА лежить, по крайней мере, на одному шляху з вершини «Початок» в вершину «Кінець».
5. Один з виходів умовної вершини може з'єднуватися з її входом, що неприпустимо для операторної вершини. Такі умовні вершини іноді називаються поворотними.
6. У кожній умовній вершині записується логічне умова з безлічі логічних умов. Дозволяється в різних умовних вершинах записувати однакові логічні умови.
7. У кожній операторної вершині записується оператор, який представляє собою вихідний сигнал або сукупність вихідних сигналів керуючого автомата. Дозволяється в різних операційних вершинах записувати однакові оператори.
5. Змістовні граф-схеми алгоритмів
Зазвичай при проектуванні різних пристроїв попередньо складається так звана змістовна ДСА, в якій всередині умовних і операторних вершин записані логічні умови і мікрооперації в змістовних термінах.
Як приклад побудуємо змістовну ДСА пристрої, що обчислює функцію знака числа:
Відповідна змістовна ДСА представлена на рис. 3.
Малюнок 3. Змістовна ДСА функції визначення знака числа
6. Синтез керуючого автомата по граф-схемі алгоритму
Кінцевий керуючий автомат, який реалізує микропрограмму роботи дискретного пристрою, прийнято називати мікропрограмним автоматом. Як уже зазначалося, мікропрограма відображається за допомогою ДСА. Розглянемо послідовність етапів синтезу керуючого автомата по його ДСА.
1. Запис словесного алгоритму функціонування операційного автомата (виконуваних операцій) з урахуванням структури операційного автомата.
2. Побудова змістовної ДСА функціонування операційного автомата.
3. Побудова зазначеної ДСА з урахуванням типу автомата.
4. Побудова графа переходів автомата або таблиці переходів.
5. Проведення структурного синтезу автомата по його графу переходів відомими методами, наприклад, за допомогою канонічного методу структурного синтезу.
Побудова зазначеної ДСА проводиться по змістовній ДСА. Для автоматів Мілі і Мура процедура розмітки має відмінності.
6.1 Побудова зазначеної ДСА автомата Мілі
Якщо необхідно побудувати мікропрограмний автомат Мілі, то змістовна ДСА керуючого автомата розмічається відповідно до наступних правил:
2) входи всіх вершин, наступних за операторними, повинні бути відзначені символами а з послідовними індексами;
3) якщо вихід вершини відзначається, то тільки одним символом;
4) входи різних вершин, за винятком вершини «Кінець», відзначаються різними символами;
5) змістовні терміни микроопераций і логічних умов. замінюються їх умовними позначеннями: в кожної операторної вершині послідовно проставляються символи вихідних сигналів, якщо в різних операційних вершинах записані однакові микрооперации, то дозволяється їх відзначати однаковими символами вихідних сигналів; якщо в різних умовних вершинах записані однакові логічні умови, то дозволяється їх відзначати однаковими символами вхідних сигналів.
6.2 Побудова зазначеної ДСА автомата Мура
Якщо необхідно побудувати мікропрограмний автомат Мура, то змістовна ДСА керуючого автомата розмічається відповідно до наступних правил:
1) символом a1 відзначаються вершини «Початок» і «Кінець»;
2) різні операційні вершини відзначаються різними символами;
3) всі операторні вершини повинні бути відзначені.
4) змістовні терміни микроопераций і логічних умов. замінюються їх умовними позначеннями.
Змістовна ДСА (рис. 3.) після розмітки за наведеним алгоритмом представлена на рис. 5.
Після отримання зазначеної ДСА будується граф переходів автомата. Він має стільки різних вершин, скільки різних букв аi з індексами є у зазначеній ДСА. Кожна вершина графа переходів автомата відзначається буквою а з відповідним індексом.
Між двома вершинами графа є дуга, якщо на зазначеній ДСА між вершинами з мітками ai і ak. є шлях. Над дугою ставиться вхідний сигнал, рівний кон'юнкції логічних умов відповідного шляху в зазначеній ДСА. При цьому виконання логічного умови відповідає змінна без заперечення, а невиконання логічного умови - змінна з запереченням на відповідній дузі графа переходів автомата.
Якщо в зазначеній ДСА між згаданими вершинами з мітками ai і аk є кілька шляхів, то в графі переходів автомата на дузі, що зв'язує аi і аk через символ диз'юнкції перераховуються всі кон'юнкції, відповідні наявним шляхам.
Якщо будується граф переходів автомата Мура, то символи микроопераций (вихідні сигнали керуючого автомата) записуються близько відповідних його вершин. Для автомата Мілі символи микроопераций записуються на відповідних дугах при кон'юнкції логічних умов, що описують шлях через операційну вершину з даної мікрооперації.
Якщо в зазначеній ДСА є безумовний перехід між операторними вершинами, тобто шлях, що не проходить ні через які умовні вершини, то на графі переходів автомата йому відповідає дуга, якій приписується вхідний сигнал «1», що показує, що даний перехід в автоматі здійснюється при надходженні чергового синхросигналу.
Надалі синтез проводиться за допомогою описаного раніше методу структурного синтезу. Підкреслимо, що вхідними сигналами синтезованого структурного автомата є кон'юнкції булевих змінних (або диз'юнкції кон'юнкція), кожна з яких відображає шлях через відповідні умовні вершини зазначеної ДСА, а вихідними сигналами - микрооперации, що позначають або вершини, або дуги графа переходів автомата, залежно від його типу. Використовуючи канонічний метод структурного синтезу, можна побудувати функціональну схему автомата.
Інформація про роботу «Мікропрограмні автомати»