ПТЦА - Прикладна теорія цифрових автоматів

1. Методи аналізу і синтезу комбінаційних схем.

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

Для з'ясування, що ж таке комбінаційна схема, розглянемо схему S, що має m входів і n виходів (рис. 1). На її входи можуть бути подані набори значень вхідних змінних X _i {0,1}, , А на виходах формуються вихідні змінні Y _j Î {0,1}, .

Схема S називається комбінаційної, якщо кожну з n функцій її виходів Y _1, Y _2,..., Y _n можна представити як булеву функцію вхідних змінних X _1, X _2,..., X _m.

Комбінаційна схема описується за допомогою системи рівнянь (1), де F _i - булева функція.

Як випливає з визначення комбінаційної схеми, значення вихідних змінних Y _j в довільний момент часу однозначно визначаються значеннями вхідних змінних X _i.

Структурно комбінаційна схема може бути представлена ​​як сукупність елементарних логічних схем - логічних елементів (ЛЕ). ЛЕ виконують над вхідними змінними елементарні логічні операції типу І-НЕ, І, АБО, АБО-НЕ і т.д. Число входів логічного елемента відповідає числу аргументів відтворюється їм булевої функції. Графічне зображення комбінаційної схеми, при якому показані зв'язки між різними елементами, а самі елементи представлені умовними позначеннями, називається функціональною схемою.

В ході розробки комбінаційних схем доводиться вирішувати завдання аналізу і синтезу.

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

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

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

1.1. Канонічний метод синтезу комбінаційних схем.

Як зазначалося вище, комбінаційна схема (КС) може мати кілька виходів. При канонічному методі передбачається, що кожна вихідна функція реалізується своєї схемою, сукупність яких і дає необхідну КС. Тому синтез складної КС з n виходами замінюється синтезом n схем з одним виходом.

Згідно з канонічним методу синтез КС включає в себе ряд етапів.

1. Що підлягає реалізації булева функція (або її заперечення) представляється у вигляді СДНФ.

2. З використанням методів мінімізації визначається мінімальна ДНФ (МДНФ) або мінімальна КНФ (МКНФ). З отриманих двох мінімальних форм вибирається більш проста.

3. Булеву функцію у мінімальній формі відповідно до п.2 представляють в заданому (або обраному розробником) базисі.

4. За поданням функції в заданому базисі будують комбінаційну схему.

Необхідно відзначити, що підлягає реалізації булева функція F (X _1, X _2,..., X _m) може бути задана не на всіх можливих наборах аргументів X _1, X _2,..., X _m. На тих наборах, де функція невизначена, її доопределяют так, щоб в результаті мінімізації отримати більш просту МДНФ або МКНФ. При цьому спроститься і сама КС. Крім того, досить часто з метою отримання ще більш простого представлення функції МДНФ, отримана в п.2, представляється в так званій скобочной формі, тобто виносяться за дужки загальні частини импликант МДНФ.

Розглянемо канонічний метод синтезу на прикладі побудови схеми повного однорозрядного довічного суматора.

Як відомо з курсу машинної арифметики, повний однорозрядних суматор - це пристрій, який здійснює складання по mod 2 відповідних розрядів (X1, X2) двійкових чисел з урахуванням перенесення (Р _m) в даний розряд з сусіднього молодшого розряду суми. Суматор виробляє цифру результату (S) в даному розряді і перенесення (Р _с) в сусідній старший розряд суми. Таблиця істинності такого суматора (тобто уявлення булевої функції, яку він реалізує, у вигляді СДНФ) представлена ​​нижче.

Необхідно отримати булеві функції S = F ₁ (X _1, X _2, Р _m) і Р _з = F ₂ (X _1, X _2, Р _m). Карти Карно для цих функцій наведено нижче (рис.2).

Як випливає з наведених карт, МДНФ відповідних функцій має вигляд:

P _c = X ₁ X ₂ + X ₁ P _m + X ₂ P _m

Отримана система булевих функцій представлена ​​в базисі І, АБО, НЕ. Відповідна їй КС наведена на малюнку 4.

Отриману комбінаційну схему можна спростити, винісши за дужки загальні частини в виразах для S і Р _c, проте істотного результату це не дасть (бажано самостійно в цьому переконатися).

Значно спростити схему можна, якщо скористатися іншим базисом, наприклад логічним елементом "Що виключає АБО". В цьому випадку вираз для S можна записати S = (X ₁ + X ₂ + Р _m) mod2 = X ₁ Å X ₂ Å Р _m. Тоді схема для S матиме вигляд (рис.3).

Іноді для синтезу КС з декількома виходами може використовуватися наступний прийом. Будемо вважати, що при синтезі схеми суматора функція S є функцією чотирьох змінних: S = f (X _1, X _2, Р _m, Р _с). Таблиця істинності для цього випадку приймає вид зображений в таблиці 2.

Невизначені значення для S відповідають наборам, які ніколи не можуть бути в реальній схемі. Карта Карно для функції S = f (X _1, X _2, P _m, P _c) представлена на рис.5.

В результаті мінімізації, виходить:

Порівнюючи вирази (2) і (3), відзначаємо, що функція S = f (X _1, X _2, P _m, P _c) простіше, ніж функція S = f ₁ (X _1, X _2, P _m). Схему, відповідну (3), пропонується побудувати самостійно.

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

1.2. Характеристики комбінаційних схем.

Складність схеми оцінюється кількістю обладнання, що становить схему. При розробці схем на основі конкретної елементної бази кількість обладнання зазвичай вимірюється числом корпусів (модулів) інтегральних мікросхем, використовуваних в схемі. У теоретичних розробках орієнтуються на довільну елементну базу і тому для оцінки витрат обладнання використовується оцінка складності схем по Квайну.

Складність (ціна) за Квайну визначається сумарним числом входів логічних елементів в складі схеми.

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

- складність схеми легко обчислюється по булевих функцій, на основі яких будується схема: для ДНФ складність схеми дорівнює сумі кількості букв, (букві зі знаком заперечення відповідає ціна 2), і кількості знаків диз'юнкції, збільшеного на 1 для кожного диз'юнктивного вираження.

- всі класичні методи мінімізації булевих функцій забезпечують мінімальність схеми саме в сенсі ціни по Квайну.

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

Швидкодія комбінаційної схеми оцінюється максимальною затримкою сигналу при проходженні його від входу схеми до виходу, тобто визначається проміжком часу від моменту надходження вхідних сигналів до моменту встановлення відповідних значень вихідних. Затримка сигналу кратна числу елементів, через які проходить сигнал від входу до виходу схеми. Тому швидкодія схеми характеризується значенням r t, де t - затримка сигналу на одному елементі. Значення r визначається кількістю рівнів комбінаційної схеми, яка розраховується наступним чином. Входів КС приписується рівень нульової. Логічні елементи, пов'язані тільки з входами схеми відносяться до рівня ПЕРШОМУ. Елемент відноситься до рівня k, якщо він пов'язаний з входів з елементами рівнів k -1, k -2, і т.д. Максимальний рівень елементів r визначає кількість рівнів КС, зване рангом схеми. Приклад визначення рангу r схеми наведено на малюнку 6.

Як відомо, будь-яка булева функція може бути представлена ​​в ДНФ, якій відповідає дворівнева комбінаційна схема. Отже, швидкодія будь КС в принципі можна довести до 2t.

Мінімізація булевої функції з метою зменшення складності схем зазвичай призводить до необхідності подання функцій в скобочной формі, якій відповідають схеми з r> 2. Тобто, зменшення витрат обладнання в загальному випадку призводить до зниження швидкодії схем.

1.3. Системи (серії) логічних елементів і їх

Основні характеристики.

При побудові КС пристроїв обчислювальної техніки використовуються різні логічні елементи, які повинні узгоджуватися з вхідним і вихідним сигналами, напрузі харчування і т.д. Для цієї мети логічні елементи об'єднують в серії.

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

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

Конструктивно логічні елементи являють собою мікромініатюрізованние інтегральні електронні схеми (мікросхеми), сформовані в кристалі кремнію за допомогою спеціальних технологічних процесів.

У більшості сучасних серій елементів є мікросхеми малого ступеня інтеграції (ІС до 100 елементів на кристал), середнього ступеня (СІС - до 1000 елементів на кристал), значною мірою інтеграції (ВІС - до 10000 елементів на кристал) і надвеликої ступеня інтеграції (НВІС - більше 10000 елементів на кристал). Логічні елементи у вигляді ІС реалізують сукупність простих логічних операцій: І, АБО, І-АБО, І-НЕ, АБО-НЕ і т.д. Логічні елементи на СІС і БІС реалізують вузли ЕОМ, на НВІС - мікроЕОМ.

Основними параметрами серії логічних елементів є:

- живлять напруги і сигнали для подання логічного 0 і логічної 1;

- коефіцієнти об'єднання по входу;

- здатність навантаження (коефіцієнт розгалуження по виходу);

- стійкість;

- розсіює потужність;

- швидкодія.

Серія елементів характеризується кількістю використовуваних живлячих напруг і їх номінальними значеннями. Зазвичай логічного 0 відповідає низький рівень напруги, а логічної 1 - високий. Для найбільш часто використовуваних серій напруга живлення складає +5, рівень логічної одиниці 2,4-5В, рівень логічного 0 - 0-0,4В.

Коефіцієнт об'єднання по входу (К _об) визначає максимально можливе число входів логічного елемента, іншими словами, функцію скількох змінних може реалізувати цей елемент. Зазвичай До _про приймає значення від 2 до 4, рідше До _об = 8. Збільшення числа входів пов'язане з ускладненням схеми елементів і призводить до погіршення інших параметрів - завадостійкості, швидкодії і т.д.

Коефіцієнт розгалуження по виходу (К _раз) показує на скільки логічних входів може бути одночасно навантажений вихід даного логічного елементу. Зазвичай До _раз для найбільш часто використовуваних серій дорівнює 10. Іноді замість До _раз задається гранично допустиме значення вихідного струму логічного елемента в стані 0 або 1.

Перешкодостійкість - це здатність елемента правильно функціонувати при наявності перешкод. Вона визначається максимально допустимою напругою завади, при якому не відбувається збій в його роботі. Зазвичай це напруга порядку 0,6-0,9 В.

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

Найбільш часто вживані типи інтегральних мікросхем - це потенційні елементи транзисторних-транзисторної логіки (ТТЛ) - серії К155, К555, К531, К1533 і т.д., транзисторної логіки з емітерний зв'язками (Естлі) - це серії К500, К1500, елементи на КМОП транзисторах - серії К176, К561, К564 і т.д.

При синтезі КС на реальних логічних елементах необхідно обов'язково враховувати обмеження на К _об і К _раз.

1.4. СИНТЕЗ КС З УРАХУВАННЯМ ОБМЕЖЕНЬ НА .

При побудові КС може виявитися, що вихід k - го логічного елемента навантажений входів інших ЛЕ (рис.7а). Це означає, що k - тий логічний елемент перевантажений і необхідно вжити заходів, що усувають зазначене явище. Існують два способи забезпечення заданого :

· Використання додаткових розв'язують підсилювачів;

· Дублювання перевантаженого елемента.

Схема з використанням додаткових розв'язують підсилювачів представлена ​​на ріс.7.б. Кількість p додаткових підсилювачів, необхідних для забезпечення заданого , Визначається за формулою:

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

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

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

1.5. СИНТЕЗ КС З УРАХУВАННЯМ ОБМЕЖЕННЯ НА .

Поданням функції у вигляді ДНФ відповідає дворівнева КС (якщо вважати, що на її вхід можуть надходити як прямі так і інверсні вхідні сигнали), на першому рівні якої елементи І, а їх виходи об'єднуються на другому рівні елементом АБО. Така побудова КС забезпечує її максимальну швидкодію, так як ранг схеми мінімальний. Однак, не завжди можливо на першому рівні і, особливо, на другому вибрати логічні елементи з необхідним , Тому що може виявитися, що ЛЕ з таким не випускаються промисловістю. В цьому випадку необхідно за допомогою декількох елементів з меншим отримати еквівалент з великим або, що краще, перетворити БФ, перейшовши від ДНФ до скобочной формі. Цей перехід супроводжується зменшенням логічних елементів, необхідного для побудови схеми. Здійснити такий перехід можна за допомогою факторного алгоритму, суть якого розглянемо на прикладі.

Нехай задана деяка булева функція у вигляді

Для реалізації цієї функції за наведеним висловом необхідно використовувати 3 логічних елемента 4И, один логічний елемент 5І, один логічний елемент 4ІЛІ.

За допомогою факторного алгоритму отримаємо дужкову форму для заданої функції. Для цього позначимо все кон'юнкції буквами:

і будемо розглядати їх як деякі множини. Знаходимо попарні перетину множин:

, , , , , .

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

.

Позначимо F = і знаходимо перетину:

, , .

Отже, для вихідної функції маємо:

.

позначимо ,

перетин . Отже, остаточно маємо:

Для реалізації функції за останнім висловом необхідно 5 елементів 2И, 1 елемент 3І, 3 елементи 2ИЛИ (рис.8).

Як видно з отриманої схеми для її реалізації необхідні елементи з = 2 або 3 (на відміну від вихідної з = 4 або 5). Однак ранг схеми збільшився до 7, що призводить до збільшення затримки спрацьовування схеми.

1.6. Аналіз комбінаційних схем.

Завдання аналізу КС виникають при необхідності перевірити правильність синтезу (на етапі проектування) або визначити БФ, реалізовану КС (при аналізі або ремонті схем). Всі існуючі методи аналізу діляться на прямі і непрямі.

В результаті аналізу КС прямим методом виходить безліч наборів вхідних змінних, що забезпечують задане значення на виході, що дозволяє записати в алгебраїчному вигляді БФ, реалізовану схемою. До прямих методів відноситься метод p- алгоритму.

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

Всі згадані методи аналізу є машінoоріентірованнимі, що дозволяє виконати аналіз схеми на ЕОМ.

Для всіх методів аналізу необхідно описати схему у вигляді схемного списку, в який включається в загальному випадку такі дані: номер ЛЕ в схемі; логічна функція, що реалізується ЛЕ; вхідні змінні для даного ЛЕ. Наприклад, схема представлена ​​на рис.9, може бути описана наступним списком:

1.7. Аналіз комбінаційних схем методом p -алгоритми.

При цьому методі, як згадувалося вище, шукаються набори вхідних змінних, що забезпечують задане значення на виході КС. Набори, що забезпечують на виході КС логічну 1, утворюють так зване єдине покриття . Аналогічно, вхідні набори, що забезпечують на виході КС логічний 0, утворюють нульове покриття . Розглянемо покриття і для найпростішого логічного елемента 2І, що виконує функцію Y = X ₁ X _2. Таблиця істинності для цієї функції:

Табл.3 Таблиця істинності функції Y = X ₁ X ₂

Як видно з наведеної таблиці тільки при єдиному наборі X ₁ = 1 і X ₂ = 1 на виході ЛЕ буде 1, тобто одиничне покриття включає тільки один набір = {1 + 1}. На виході ЛЕ буде 0 при трьох наборах, що утворюють нульове покриття:

Це покриття можна спростити, помітивши, що перший набір склеюється з другим і третім, тобто

Т.ч. для ЛЕ 2І можна сказати, що 1 на його виході буде тільки при обох одиницях на входах, а для забезпечення 0 на виході досить подати хоча б на один вхід 0. Міркуючи аналогічно, отримаємо таблицю покриттів і для основних ЛЕ, представлених нижче в табл. 4.

Таблиця 4.

ЛЕ YYYYYYY

НЕ 2И 2И - НЕ 2ИЛИ 2ИЛИ-НЕ ІБК. АБО 3І - НЕ

XX ₁ X ₂ X ₁ X ₂ X ₁ X ₂ X ₁ X ₂ X ₁ X ₂ X ₁ X ₂ X ₃

1 0 X 1 1 0 0 1 X 0 0 1 1 1

X 0 X 1 + 1 1

0 1 1 0 X 1 X 0 0 0 1 0 XX

X 0 X 1 1 0 X 0 X

XX 0

При аналізі схеми методом p - алгоритму, задавшись певним значенням на виході, замінюють його відповідним покриттям елемента, що формує вихідний сигнал. В результаті цього визначається, які повинні бути сигнали на виходах елементів, підключених до вихідного ЛЕ. У свою чергу, сигнали на виходах цих елементів можна замінити відповідними покриттями, тобто визначити значення вихідних сигналів для інших ЛЕ і т.д. Цей процес триває до тих пір, поки не вийдуть покриття, що складаються тільки з вхідних змінних, які називаються опорними. Сукупність таких покриттів і дає відповідне покриття схеми.

Приклад аналізу КС (рис 9.) методом p - алгоритму представлений в табл. 5. В останній колонці цієї таблиці наведено оператор підстановки, в результаті роботи якого сигнал на виході ЛЕ замінюється відповідним покриттям. Необхідно звернути увагу, що всі значення змінних, записані в одному рядку, повинні одночасно бути в наявності для забезпечення заданого значення вихідного сигналу. по-

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

На підставі отриманого одиничного покриття можна записати БФ, реалізовану схемою:

Таблиця 5 Аналіз схеми методом p - алгоритму.

а) Отримання першого покриття

б) Отримання нульового покриття

Надалі можна порівняти отриману БФ з тієї, по якій будувалася схема і перевірити правильність її побудови.При аналізі схеми може виявитися, що деяка змінна, яка отримала на одному з попередніх кроків деякі значення на даному етапі повинна прийняти протилежне значення. Виникла суперечність говорить про те, що даний шлях є тупиковим і його необхідно виключити з подальшого розгляду. Якщо ні при одній комбінації вхідних змінних не забезпечується значення 1 (0) на виході, то це означає, що схема реалізує константу 0 (1) відповідно.

1. 8 Аналіз КС методом синхронного моделювання.

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

Розглянемо метод синхронного моделювання на прикладі схеми (рис.9).

На першому етапі схему розбиваємо на рівні і записуємо в порядку зростання рівня рівняння, що описують функціонування ЛЕ:

Проаналізуємо схему при подачі на вхід набору X ₁ = 0, Х ₂ = 0, Х ₃ = 0, Х ₄ = 1, Х ₅ = 1. Для цього вирішуємо записані рівняння в порядку зростання рівняння. маємо:

;

;

;

.

Отже, при подачі на вхід набору {00011}, на виході буде Y = 1. Аналогічно можна промоделювати роботу схеми при подачі на вхід будь-якого іншого набору.

1.9 Аналіз КС методом асинхронного моделювання.

Реальний ЛЕ перемикається за якийсь кінцевий час, залежне від технології виготовлення, умов експлуатації, ємностей навантаження і т.д. Проходження сигналу послідовно через кілька ЛЕ буде призводити до накопичення часу затримки і виникнення зсуву в часі вихідного сигналу по відношенню до вхідного. Наявність затримки і породжується нею тимчасового зсуву сигналів може призводити до появи на виході окремих ЛЕ і всієї схеми в цілому короткочасних сигналів, не передбачених БФ, що реалізується схемою. Як ілюстрацію, розглянемо схему рис.11, а.

Мал. 11 а)

Мал. 11. Статичний ризик збою.

а) - схема, б) - тимчасові діаграми.

t _1-час затримки інвертора

t _2-час затримки елемента 2И

Дана схема реалізує функцію , Тобто константу 0 незалежно від вхідного сигналу X. Однак в перехідному процесі в результаті затримки спрацьовування ЛЕ можлива ситуація, коли на обох входах елемента 2И будуть логічні одиниці, що може привести до появи на виході схеми логічної 1 (див. рис.11 б). Розглянутий випадок можливий при затримці спрацьовування другого елемента більше, ніж першого. Таке явище називається ризиком збою. Розрізняють статистичний і динамічний ризики збою.

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

При динамічному ризик збою до і після перехідного процесу стану вихідного сигналу протилежні, але в перехідному процесі вихідний сигнал кілька разів змінює своє значення. Динамічний ризик збою можливий в схемі (рис.12 а) при зміні набору (Х ₁ = 0, Х ₂ = 1, Х ₃ = 1) на набір (Х ₁ = 1, Х ₂ = 0, Х ₃ = 0) і ілюструється діаграмами (рис.12 б).

В даному прикладі динамічний ризик збою на виході КС супроводжується статичним на виході елемента 1. Як видно з тимчасових діаграм ризик збою має місце при наявності певного часового зсуву між сигналами, які надходять на вхід ЛЕ. Небажані сигнали на виході можуть бути і відсутніми при іншому співвідношенні часових сигналів, однак принципова можливість їх появи є фактором знижує надійність роботи схеми. Тому дуже важливо вміти виявляти і усувати такі явища.

Для аналізу процесу перемикання КС при зміні вхідних наборів і виявлення ризиків збою використовується метод асинхронного моделювання. При цьому методі вважається, що кожен елемент перемикається з однаковою затримкою. Аналіз включає такі етапи:

1. Кожна елементу схеми присвоюється рівень, причому рівень 1 мають елементи, всі входи яких є незалежними входами схеми.

2.Запісиваются рівняння, що описують кожен ЛЕ в порядку убування рівня.

3. Для початкового вхідного набору А (X _1, X _2,..., X _n) визначається значення сигналів на виходах всіх ЛЕ схеми. Нехай цей набір А замінюється набором В (X _1, X _2,..., X _n).

4.Помечаются ті рівняння, в правій частині яких хоча б одна з змінних змінила своє значення.

5.Решаются помічені рівняння в порядку їх запису в схемі. Після рішення рівняння вважається непоміченими.

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

Аналіз схеми (рис.13) методом асинхронного моделювання наведено нижче. Для даної схеми вхідний набір А (1011110) замінюється набором В (1101011).

Мал. 13. Комбінаційна схема для методу асинхронного моделювання.

Рівняння, що описують ЛЕ:

Табл. 6 Таблиця моделювання схеми

Виходи Такти моделювання Прим.

0 1 2 3

e ₆ 1 0 1 0 дин.

e ₅ 0 1 0 0 стат.

e ₄ 0 0 0 0

e ₃ 1 0 0 0

e ₂ 1 0 0 0

e ₁ 0 1 0 1

Як випливає з результатів моделювання, при зміні набору А набором В на виході елемента 4 має місце статичний ризик збою, а на виході схеми - динамічний ризик збою.

Радикальним способом усунення ризиків збою є введення стробирования для зняття вихідного сигналу КС. Стробірующій імпульс подається після закінчення перехідного процесу в КС (тобто коли на виході КС вже встановилося необхідне значення вихідного сигналу), що виключає вплив можливих збоїв на вироблюваний схемою сигнал.

ОСНОВНІ ПОНЯТТЯ І ВИЗНАЧЕННЯ ТЕОРІЇ абстр K тних АВТОМАТІВ.

Ознайомившись в курсах "Програмування" і "Машинна арифметика" з принципами роботи ЕОМ, можна вказати на дві основні особливості таких обчислювальних машин: оперування даними, представленими в цифровій формі і автоматична робота по заздалегідь складеній програмі. Ці особливості показують, що будь-яка ЕЦОМ є цифровим автоматом (ЦА). Поняття ЦА служить узагальненням для всіх видів пристроїв обробки цифрової інформації, що мають програмне керування.

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

Математичною моделлю ЦА (а в загальному випадку будь-якого дискретного пристрою) є так званий абстрактний автомат, певний як 6-компонентний кортеж: S = (A, Z, W, d, l, а ₁₎ у якого:

1.A = {a _1, a _2,..., a _m} - безліч станів (внутрішній алфавіт)

2. Z = {z _1, z _2,..., z _f} - безліч вхідних сигналів (вхідний алфавіт)

3. W = {w _1, w _2,..., w _g} - безліч вихідних сигналів (вихідний алфавіт)

4. d: A · Z®A - функція переходів, що реалізує відображення _{D d} Í А · Z в А. Іншими словами функція d деяким парам стан - вхідний сигнал (а _m, z _f) ставить у відповідність стану автомата а _s = d (a _m, z _f), a _s Î A.

5. l: A · Z®W - функція виходів, що реалізує відображення D _l Í А · Z на W. Функція l деяким парам стан - вхідний сигнал (а _m, z _f) ставить у відповідність вихідні сигнали автомата Wg = l (а _m, z _f), Wg Î W.

6. a _i Î A - початковий стан автомата.

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

Абстрактний автомат (рис.14) має один вхід і один вихід. Автомат працює в дискретному часі, що приймає цілі невід'ємні значення t = 0,1,2, ... У кожен момент t дискретного часу автомат знаходиться в деякому стані a (t) з безлічі станів автомата, причому в початковий момент t = 0 він завжди знаходиться в початковому стані a (0) = a1. У момент t, будучи в стані a (t), автомат здатний сприйняти на вході букву вхідного алфавіту z (t) Î Z. Відповідно до функцією виходів він видасть в той же момент часу t букву вихідного алфавіту W (t) = l ( a (t), z (t)) і відповідно до функції переходів перейде в наступний стан a (t + 1) = d [a (t), z (t)], a (t) Î A, w (t ) Î W.

Сенс поняття абстрактного автомата полягає в тому, що він реалізує деяке відображення безлічі слів вхідного алфавіту Z в безліч слів вихідного алфавіту W. Тобто якщо на вхід автомата, встановленого в початковий стан a1, подавати буква за буквою деяку послідовність літер вхідного алфавіту z (0), z (1), ... - вхідний слово, то на виході автомата будуть послідовно з'являтися літери вихідного алфавіту w (0 ), w (1), ... - вихідна слово. Т.ч. вихідна слово = j (вхідний слово), де j - відображення, здійснюване абстрактним автоматом.

На рівні абстрактної теорії поняття "робота автомата" розуміється як перетворення вхідних слів у вихідні. Можна сказати, що в абстрактному автоматі відволікаємося від його структури - вмісту прямокутника (рис. 14), розглядаючи його як "чорний ящик", тобто основна увага приділяємо поведінки автомата щодо зовнішнього середовища.

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

На практиці найбільшого поширення набули два класи автоматів - автомати Мілі (Mealy) і Мура (Moore).

Закон функціонування автомата Мілі задається рівняннями:

a (t + 1) = d (a (t), z (t)); w (t) = l (a (t), z (t)), t = 0,1,2, ...

Закон функціонування автомата Мура задається рівняннями:

a (t + 1) = d (a (t), z (t)); w (t) = l (a (t)), t = 0,1,2, ...

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

Крім автоматів Мілі і Мура іноді виявляється зручним користуватися суміщеної моделлю автомата, так званим С- автоматом.

Під абстрактним С- автоматом будемо розуміти математичну модель дискретного пристрою, яка визначається восьмікомпонентним вектором S = (A, Z, W, U, d, l _1, l _2, а _1), у якого:

1. A = {a _1, a _2,..., a _m} - безліч станів;

2. Z = {z _1, z _2,..., z _f} - вхідний алфавіт;

3. W = {w _1, w _2,..., w _g} - вихідний алфавіт типу 1;

4. U = {u _1, u _2,..., u _h} - вихідний алфавіт типу 2;

5. d: A · Z ® A - функція переходів, що реалізує відображення _{D d} Í А · Z в А;

6. l _1: A · Z ® W - функція виходів, що реалізує відображення D _{l 1} Í А · Z в W;

7. l _2: A ® U - функція виходів, що реалізує відображення D _{l 2} Í А в U;

8. а ₁ Î А - початковий стан автомата.

Абстрактний С- автомат можна представити у вигляді пристрою з одним входом, на який надходять сигнали з вхідного алфавіту Z, і двома виходами, на яких з'являються сигнали з алфавітів W і U. Відмінність С - автомата від моделей Милі і Мура полягає в тому, що він одночасно реалізує дві функції виходів l ₁ і l _2, кожна з яких характерна для цих моделей окремо. Закон функціонування С- автомата можна описати наступними рівняннями:

а (t + 1) = d (a (t), z (t)); w (t) = l ₁ (a (t), z (t)); u (t) = l ₂ (a (t)); t = 0, 1, 2, ...

Вихідний сигнал U _h = l ₂ (a _m) видається весь час, поки автомат знаходиться в стані a _m. Вихідний сигнал Wg = l ₁ (a _m, z _f) видається під час дії вхідного сигналу Z _f при знаходженні автомата в стані a _m.

Розглянуті вище абстрактні автомати можна розділити на:

1) повністю визначені і часткові;

2) детерміновані і імовірнісні;

3) синхронні і асинхронні;

Повністю певним називається абстрактний цифровий автомат, у якого функція переходів і функція виходів визначені для всіх пар (a _i, z _j).

Частковим називається абстрактний автомат, у якого функція переходів або функція виходів, або обидві ці функції визначені не для всіх пар (a _i, z _j).

До детермінованим відносяться автомати, у яких виконана умова однозначності переходів: автомат, що знаходиться в деякому стані a _i, під дією будь-якого вхідного сигналу z _j не може перейти більш, ніж в один стан.

В іншому випадку це буде імовірнісний автомат, в якому при заданому стані a _i і заданому вхідному сигналі z _j можливий перехід із заданою вірогідністю в різні стани.

Для визначення синхронних і асинхронних автоматів вводиться поняття стійкого стану. Стан a _s автомата називається стійким, якщо для будь-якого стану a _i і вхідного сигналу z _j таких, що d (a _i, z _j) = a _s має місце d (a _s, z _j) = a _s, тобто стан стійко, якщо потрапивши в цей стан під дією деякого сигналу zj, автомат вийде з нього тільки під дією іншого сигналу z _k, відмінного від z _j.

Автомат, у якого все стану стійкі - асинхронний.

Автомат називається синхронним, якщо він не є асинхронним.

Абстрактний автомат називається кінцевим, якщо кінцеві множини А = {a _1, a _2,..., a _m}, Z = {z _1, z _2,..., z _f}, W = {w _1, w ₂, ..., w _g}. Автомат носить назву инициального, якщо в ньому виділено початковий стан a _1.

СПОСОБИ ОПИСУ І ЗАВДАННЯ АВТОМАТІВ.

Для того, щоб задати автомат, необхідно описати всі компоненти кортежу S = (A, Z, W, d, l, а _1). Безлічі А, Z, W описуються і задаються простим перерахуванням своїх елементів. Серед різноманіття різних способів завдань функцій d і l (отже і всього автомата в цілому) найбільшого поширення набули табличний і графічний.

При табличному способі завдання автомат Мілі описується за допомогою двох таблиць. Одна з них (таблиця переходів) задає функцію d, тобто a (t +1) = d (a (t), z (t)) (табл.7), друга (таблиця виходів) - функцію l, тобто W (t) = l (a (t), z (t)) (табл. 8).

Кожному стовпцю з наведених таблиць поставлено у відповідність один стан з безлічі А, кожному рядку - один вхідний сигнал з безлічі Z. На перетині шпальти a _m і рядки z _f в табл.7 записується стан a _s, в яке повинен перейти автомат зі стану a _m під дією вхідного сигналу Z _f, тобто a _s = d (a _m, z _f). На перетині шпальти a _m і рядки z _f в табл.8 записується вихідний сигнал Wg, що видається автоматом в стані a _m під час вступу на вхід сигналу z _f, тобто Wg = l (a _m, z _f).

Для наведених таблиць безлічі, що утворюють автомат A = {a _1, a _2, a _3, a _4}, Z = {z _1, z _2}, W = {w _1, w _2, w _3, w _4, w ₅ }. Автомат Мілі може бути заданий однієї суміщеної таблицею переходів і виходів (табл.9), в якій кожен елемент a _s / w _g записаний на перетині шпальти a _m і рядки z _f, визначається наступним чином:

a _s = d (a _m, z _f); w _f = l (a _m, z _f).

Автомат Мура задається однієї зазначеної таблицею переходів (табл.10), в якій кожному колонку приписані не тільки стан a _m, але ще і вихідний сигнал Wg, відповідний цього стану, де Wg = l (a _m).

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

Для завдання С - автоматів також використовується табличний метод. В цьому випадку таблиця переходів (табл.11) аналогічна таблиці переходів автомата Мілі, а в таблиці виходів кожне стан відзначено відповідним вихідним сигналом u _i вихідного алфавіту типу 2 (табл.12)

При графічному способі автомат задається у вигляді орієнтованого графа, вершини якого відповідають станам, а дуги - переходам між ними. Дуга, спрямована з вершини a _m, задає перехід в автоматі зі стану a _m в стан a _s. На початку цієї дуги записується вхідний сигнал Z _f ÎZ, що викликає даний перехід a _s = d (a _m, z _f). Для графа автомата Мілі вихідний сигнал w _g ÎW, що формується на переході, записується в кінці дуги, а для автомата Мура - поруч з вершиною a _m, зазначеної станом a _m, в якому він формується. Якщо перехід в автоматі зі стану a _m в стан a _s виробляється під дією декількох вхідних сигналів, то дузі графа, спрямованої з a _m в a _s, приписуються всі ці вхідні і відповідні вихідні сигнали. Граф С- автомата містить вихідні сигнали двох типів і вони позначаються на графі як на графах відповідних автоматів. Графи автоматів, заданих своїми таблицями переходів і виходів
(Табл. 7¸12) представлені на малюнках 15,16,17.

ЗВ'ЯЗОК МІЖ МОДЕЛЯМИ милі І МУРА.

Розглянемо деякий автомат Мілі, заданий таблицями переходів і виходів. Таблиця переходів а) і виходів б) автомата Мілі

Подамо на вхід автомата, встановленого в стан а _1, вхідний слово x = z ₁ z ₂ z ₂ z ₁ z ₂ z _2. Так як d (а _1, z ₁₎ = a _2, l (a _1, z ₁₎ = W _2, то під впливом вхідного сигналу z ₁ автомат перейде в стан а ₂ і видасть на переході вихідний сигнал W _2. Потім, перебуваючи в стані а ₂ під впливом сигналу Z ₂ перейде в стан а ₁ = d (а _2, z ₂₎ і видасть сигнал W ₁ = l (a _2, z ₂₎ і т.д. У табл. 13 приведена послідовність станів, які автомат проходить, сприймаючи вхідний слово x, і вихідні сигнали, що виробляються на цих переходах.

Назвемо вихідне слово w = l (a _1, x) реакцією автомата Мілі в стані а ₁ на вхідний слово x.

У нашому випадку w = w ₂ w ₁ w ₂ w ₂ w ₁ w ₂

Як видно, з наведеного прикладу, у відповідь на вхідний слово довжини k автомат Мілі видасть послідовність станів довжини k +1 і вихідне слово довжини k.

У загальному вигляді поведінку автомата Мілі, встановленого в стан a _m, можна описати наступним чином (табл. 14).

Аналогічно можна описати поведінку автомата Мура, що знаходиться в стані a _1, при приході вхідного слова

x = Z _i1, Z _i2,. . . , Z _ik, враховуючи, що W (t) = l (a (t)):

Очевидно, що для автомата Мура вихідний сигнал W _{i 1} = l (a _m) в момент часу i ₁ не залежить від вхідного сигналу Z _{i 1} і визначається тільки станом a _m. Отже, сигнал W _{i 1} ніяк не пов'язаний з вхідним словом x.

У зв'язку з цим під реакцією автомата Мура, встановленого в стан a _m, на вхідний слово x = Z _{i 1,} Z _{i 2,.} . . , Z _ik будемо розуміти вихідний слово тієї ж довжини w = l (a _m, x) = W _{i 2} W _{i 3}... W _{ik +1,} зрушене по відношенню до x на один такт.

Розглянемо приклад. Нехай заданий автомат Мура:

Подамо на вхід цього автомата ту ж послідовність, що і для автомата Мілі: x = z ₁ z ₂ z ₂ z ₁ z ₂ z _2. Послідовність зміни станів і вироблюваних вихідних сигналів представлена ​​в таблиці:

Порівнюючи реакції автомата Мілі (табл. 13) і автомата Мура (табл.15), відзначаємо, що ці реакції на одне і те ж слово x збігаються. Отже автомати Мілі і Мура реалізують один і той же перетворення слів вхідного алфавіту. Такі автомати називаються еквівалентними. Суворе визначення еквівалентності наступне:

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

Для кожного автомата Мілі може бути побудований еквівалентний йому автомат Мура і навпаки.

Перехід від автомата Мура до еквівалентного йому автомата Мілі тривіальний і легко здійснюється при графічному способі задання автомата. Для отримання графа автомата Мілі необхідно вихідний сигнал Wg, записаний поруч з вершиною a _s вихідного автомата Мура, перенести на всі дуги, що входять в цю вершину. На рис. 18 наведено граф автомата Мілі, еквівалентного автомата Мура (рис. 16)

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

Перехід від автомата Мілі до еквівалентного йому автомата Мура складніший. Це пов'язано з тим, що в автоматі Мура в кожному стані виробляється тільки один вихідний сигнал. Як і в попередньому випадку, перехід найбільш наочно робити при графічному способі задання автомата. У цьому випадку кожне стан a _i вихідного автомата Мілі породжує стільки станів автомата Мура, скільки різних вихідних сигналів виробляється в вихідному автоматі при попаданні в стан a _i. Розглянемо перехід від автомата Мілі Sa до автомата Мура S _b на прикладі автомата (рис. 15).

Як випливає з рис. 15 для автомата Sa при попаданні в стан а ₁ виробляються вихідні сигнали W _2, W _4, W _5, при попаданні в а ₂ - W _1, W _2, a ₃ - W _2, a ₄ - W _3. Кожній парі стан a _i - вихідний сигнал Wj, який виробляється при попаданні в цей стан, поставимо у відповідність стан b _k еквівалентного автомата Мура S _b з тим же вихідним сигналом Wj: b ₁ = (a _1, W _2), b ₂ = (a _1, W _4), b ₃ = (a _1, W _5), b ₄ = (a _2, W _1), b ₅ = (a _2, W _2), b ₆ = (a _3, W ₂), b ₇ = (a _4, W _3), тобто кожне стан a _i автомата Мілі породжує деякий безліч A _i станів еквівалентного автомата Мура: A ₁ = {b _1, b _2, b _3}, A ₂ = {b _4, b _5}, A ₃ = {b _6}, A ₄ = {b _7}. Як видно, в еквівалентному автоматі Мура кількість станів 7. Для побудови графа S _b чинимо так. Оскільки в автоматі S _a є перехід зі стану а ₁ в стан а ₂ під дією сигналу z ₁ з видачею W _1, то з безлічі станів A ₁ = {b _1, b _2, b _3}, породжуваних станом а ₁ автомата S _a в автоматі S _b повинен бути перехід в стан (a _3, W ₂₎ = b ₆ під дією сигналу Z ₂ і т.д. Граф еквівалентного автомата Мура представлений на рис.19.

Якщо від автомата Мура S _b, еквівалентного автомата Милі Sa (рис. 19) знову перейти до автомата Мілі, то отримаємо автомат Мілі S ₁ (рис. 20)

Внаслідок транзитивності відносини еквівалентності два автомата Мілі S ₁ і Sa також будуть еквівалентними, але у останнього будуть на 3 стану більше. Т.ч., еквівалентні між собою автомати можуть мати різне число станів, в зв'язку з чим виникає задача знаходження мінімального (тобто з мінімальним числом станів) автомата в класі еквівалентних між собою автоматів.

МІНІМІЗАЦІЯ ЧИСЛА ВНУТРІШНІХ СТАНІВ ПОВНІСТЮ ПРОДАЖУ ТА АВТОМАТІВ.

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

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

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

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

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

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

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

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

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

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

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

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

Розглянемо приклад мінімізації автомата Мілі, заданого таблицями переходів і виходів:

З таблиці виходів отримуємо розбиття на 1-класи еквівалентності p _1, об'єднуючи в еквівалентні класи Bi стану з однаковими стовпцями:

p ₁ = {B _1, B _2}; B ₂ = {a _1, a _2, a _5, a _6}; B ₂ = {a _3, a _4}

Для отримання 2-еквівалентних станів будуємо таблицю 1-розбиття (табл.17), замінюючи в таблиці переходів стану a ₁ відповідними класами еквівалентності B1 або B2.

З отриманої таблиці 1-розбиття отримуємо 2-класи еквівалентності C _i і розбиття p ₂ = {C _1, C _2, C _3}, де З ₁ = {a _1, a _1}, C ₂ = {a _5, a ₆ }, C ₃ = {a _3, a _4}. Порівнюючи p ₂ і p _1, відзначаємо, що ці розбиття відрізняються один від одного. Тому аналогічно будуємо таблицю 2-розбиття (табл. 18), знову замінюючи в таблиці переходів стану a _i відповідними класами еквівалентності C _i.

З отриманої таблиці 2-розбиття отримуємо 3-класи еквівалентності D _i і розбиття p ₃ = {D _1, D _2, D _3}, де D ₁ = {a _1, a _2}, D ₂ = {a _5, a ₆ }, D ₃ = {a _3, a _4}.

Порівнюючи p ₃ і p _2, помічаємо, що D ₁ = C _1, D ₂ = C _2, D ₃ = C _3, p ₃ = p _3. Отже отримали розбиття на ¥ - еквівалентні класи. Оскільки всього три таких класу, то мінімальний автомат буде містити всього три стану. Вибираємо з кожного класу D _i по одному стану і отримуємо безліч станів A 'мінімального автомата. Нехай, наприклад, A '= {a _1, a _4, a _5}. Для отримання мінімального автомата з первинних таблиць переходів і виходів (табл. 16) викреслюємо стовпці, що відповідають "зайвим станів" a _2, a _3, a _6. В результаті виходить мінімальний автомат Мілі, еквівалентний вихідному автомату (табл. 19).

Мінімізацією числа внутрішніх станів автомата закінчується етап абстрактного синтезу.

Структурний синтез ЦА.

Завдання синтезу ЦА.

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

Елементарні цифрові автомати з пам'яттю

(тригерні пристрої) і їх властивості.

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

На відміну від абстрактного автомата, що має один вхід і один вихід, на які надходять сигнали у вхідному і виходять в вихідному W = {W _1,.., W _G} алфавітах, структурний автомат має L вхідних каналів х _1, х _2,.., х _L і N вихідних y _1, y _2,..., y _N на кожному з яких присутній сигнал структурного алфавіту.

Зазвичай в якості структурного використовується двійковий алфавіт.

У цьому випадку кожному вхідному сигналу Z _F абстрактного автомата відповідає деякий двійковий вектор (l _{f 1,} l _{f 2,}.., l _{f L),} де l _{f L} Î {0,1}.

Очевидно, що для подання (кодування) вхідних сигналів Z _1,.., Z _F абстрактного автомата різними двійковими векторами повинна бути виконана умова

L ] Log ₂ F [,

аналогічно

N ] Log ₂ G [

Наприклад, Z = {Z _1, Z _2, Z _3, Z _4} W = {W _1, W _2, W _3}.

тоді L log ₂ 4 = 2 N log ₂ 3 = 2

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

Z ₁ = 00 W ₁ = 00

Z ₂ = 01 W ₂ = 01

Z ₃ = 10 W ₃ = 11

Z ₄ = 11

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

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

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

Теоретичним обґрунтуванням канонічного методу структурного синтезу автоматів служить теорема про структурну повноті:

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

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

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

Канонічний метод структурного синтезу передбачає подання структурної схеми автомата у вигляді двох частин: пам'яті і комбінаційної схеми.

Пам'ять складається з елементарних автоматів Мура П _1,...., П _Z,...., П _R. Після вибору елементів пам'яті кожне стан синтезованого автомата А кодується набором їхніх статків. Якщо все автомати П ₁..., П _R однакові, що в загальному випадку необов'язково, то їх число

де M - число станів синтезованого автомата А, а b - число станів елементарного автомата пам'яті. Зазвичай для елементарного автомата b = 2, тоді .

Наприклад, перехід автомата А, що має 5 елементів пам'яті, алфавіт станів яких - двійковий, з одного стану (A _m) = 01011 в інше (A ₃₎ = 11000, полягає в зміні станів відповідних автоматів пам'яті: перший елемент пам'яті переходить з 0 в 1, другий - з 1 в 1, третій з 0 в 0, четвертий - з 1 в 0, п'ятий - з 1 в 0.

Переходи автоматів пам'яті, відповідні переходам в автоматі А, відбуваються під дією сигналів збудження пам'яті, що надходять з виходукомбінаційної схеми на вхід пам'яті автомата. Так на малюнку X = (X _1, X _2,.., X _L) і Y = (Y _1, Y _2,..., Y _N) - векторні структурні вхідний і вихідний сигнали автомата, U = (U _1, U _2,..., U _T) - векторна функція збудження пам'яті і Q = (Q _1,..., Q _T) - вектор вихідного сигналу зворотного зв'язку від елементів пам'яті автомата.

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

Повнота переходів очевидна з таблиці (в кожному стовпці їхні капітали зустрічаються). При розгляді автомата на абстрактному рівні його можна представити у вигляді рис.22 а.

При переході від абстрактного автомата до структурному, вхідні і вихідні сигнали повинні бути закодовані наборами сигналів структурного алфавіту (вхідного або вихідного відповідно). При довічним структурному алфавіті автомат П _z матиме два вхідних і два вихідних каналу.

Отже, самі компоненти U _z і Q _z при Z = 1, ..., R векторів сигналів збудження пам'яті U і сигналів зворотного зв'язку від пам'яті Q також можуть бути представлені у вигляді векторів:

U _z = (U _Z1, U _Z2,..., U _{Z K)} і Q _Z = (Q _{Z 1,} Q _{Z 2,}..., Q _{Z R).}

Якщо не обумовлено, то використовується двійковий структурний алфавіт як для вхідних і вихідних каналів синтезованого автомата, так і для вхідних і вихідних каналів автоматів пам'яті. Алфавіт станів автоматів пам'яті також зазвичай двійковий.

При побудові функцій збудження пам'яті автомата використовують функцію входів елемента пам'яті m (b _i, b _j), яка ставить у відповідність кожній парі станів (b _i, b _j) сигнал, який повинен бути поданий на вхід цього автомата для перекладу його зі стану b _i в стан b _j. Функцію входів зручно задавати у вигляді таблиці. Для елемента пам'яті (функція переходів якого наведена раніше) функція входів має вигляд:

Якщо вхідні сигнали елемента пам'яті q _1,..., q _p закодовані наборами (U _{Z 1,}..., U _{Z K)} сигналів на його вхідних каналах, то елементами таблиці, яка задає функцію входів замість q _i будуть відповідні набори. Так, якщо q ₁ = 00, q ₂ = 01, q ₃ = 10, то відповідна f входів матиме вигляд ріс.23a.

Елементарні цифрові автомати - елементи пам'яті.

Як елементи пам'яті структурного автомата зазвичай використовуються тригери.

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

Зазвичай в тригерах виділяють два види вхідних сигналів (і відповідно входів): інформаційні та синхросигнали.

Інформаційні сигнали визначають новий стан тригера і присутні в будь-яких триггерах. За типом інформаційних сигналів здійснюється класифікація тригерів: D, T, RS, JK, RST, DV і т.д.

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

На синхровхід тригера надходять тактирующие імпульси задає, синхронизирующего роботу ЦА. Період проходження імпульсів відповідає одному такту автоматного часу ЦА.

Розглянемо основні типи тригерів, які використовуються для синтезу ЦА: D, T, RS, JK.

D -тригер - елемент затримки - має один інформаційний вхід D і один вихід Q і здійснює затримку надійшов на його вхід сигналу на один такт.

Умовне позначення і таблиця переходів D -тригер представлена на рис. .

З наведеної таблиці переходів для даного тригера Q ^{t + 1} = f (Q ^t, D ^t) можна отримати таблицю функцій його входів D ^t = j (Q ^t, Q ^{t + 1).}

Як видно з таблиці, стан, в яке переходить тригер (середній стовпець), збігається з котрі вступили на його вхід сигналом D (t) (правий стовпець). У зв'язку з цим таблиця функцій збудження пам'яті синтезованого автомата з використанням D -тригер буде повністю збігатися з кодованої таблицею переходів цього автомата. Промисловість випускає D -тригер в інтегральному виконанні. наприклад,

K155TM2 (рис. 25) .Таких тригерів два в одному корпусі. Вхід З -вхід синхронізації, Q, `Q - виходи, Q - прямий, - інверсний. R, S - входи установки в 0 і 1 відповідно. При подачі на вхід R і S логічного нуля тригер встановлюється в відповідні стану незалежно від сигналу на входах D і C.

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

Умовне позначення і таблиця переходів T- тригера представлена на рис 26.

Таблиця функцій входів тригера ^{T t} = f (Q ^t, Q ^{t + 1)} представлена в таблиці.

На підставі цієї таблиці можна отримувати функцію збудження елементів пам'яті при синтезі автомата на базі T -тригер. Наприклад, якщо автомат перейшов зі стану a _i = 010 в стан a _j = 110, то для забезпечення цього переходу функції порушення повинні бути:

для першоготригера при переході з 0 в 1 T ₁ = 1,

для другого тригера при переході з 1 в 1 T ₂ = 0,

для третього тригера при переході з 0 в 0 T ₃ = 0 і т.д.

У чистому вигляді промисловість не випускає T -тригер.

RS -тригер - тригер з роздільними входами.

Даний тригер має два вхідних каналу R і S і один вихідний Q. Вхід S (set) називається входом установки в одиницю, вхід R (reset) - входом установки в нуль. Умовне позначення і таблиця переходів RS -тригер представлена на рис. 27.

У таблиці переходів при подачі комбінації S = R = 1 стан переходу Q ^{t + 1} не визначене і ця комбінація сигналів є забороненою для RS -тригер.

Таблицю переходів можна більш компактно зобразити у вигляді (див. Табл. 21б) Аналізуючи табл.21 б, в відзначаємо що, наприклад, перехід тригера з 0 в 0требует подачі комбінації R = 0, S = 0 або R = 1, S = 0 , тобто можна сказати що цей перехід буде при R = X (байдуже стан), S = 0.

Аналогічно розмірковуючи по відношенню до інших переходах отримаємо наступну таблицю функцій входів.

На підставі таблиці можна отримати функцію збудження пам'яті автомата при синтезі на базі RS -тригер. Наприклад, якщо автомат переходить зі стану a _i = 010 в стан a _j = 110, то для забезпечення такого переходу функції порушення повинні бути:

для першоготригера при переході з 0 в 1 R ₁ = 0, S ₁ = 1;

для другого тригера при переході з 1 в 1 R ₂ = 0, S ₂ = X;

для третього тригера при переході з 0 в 0 R ₃ = X, S ₃ = 0.

Аналогічно для будь-якого іншого переходу автомата.

У чистому вигляді синхронний RS - тригер, який використовується для синтезу ЦА, промисловістю не випускається.

JK- тригер - має два інформаційних входи J і K і один вихід Q. Вхід J - вхід установки в 1, вхід K - вхід установки в 0, тобто ці входи аналогічні відповідних входів RS -тригер: J - відповідає S, K - відповідає R. Однак, на відміну від RS -тригер, вхідні комбінація J = 1, K = 1 не є забороненою. Умовне позначення і таблиця переходів JK -тригер представлені на рис.28. і в табл. 22.

Як випливає з таблиць переходів, для комбінацій вхідних сигналів JK = 00¸10 тригер веде себе як RS -тригер, а при комбінації JK = 11 - як T -тригер.

Аналізуючи таблицю переходів (табл. 22 а), відзначаємо, що перехід тригера, наприклад, з 0 в 1 вимагає подачі вхідних сигналів J = 1, K = 0 або J = 1, K = 1, тобто J = 1, K = Х (байдуже значення). Аналогічно розмірковуючи по відношенню до інших переходах, отримаємо наступну таблицю функцій входів JK -тригер.

На підставі останньої таблиці можна отримати функцію збудження елементів пам'яті при синтезі автомата на JK -тригер. Наприклад, при переході автомата зі стану a _i = 010 в стан a _j = 110, функції збудження повинні бути:

для першоготригера при переході з 0 в 1 J 1 = 1, K 1 = X;

для другого тригера при переході з 1 в 1 J 2 = X, K 2 = 0;

для третього тригера при переході з 0 в 0 J 3 = 0, K 3 = X.

Приклад канонічного методу структурного синтезу автомата.

Виконаємо структурний синтез часткового автомата А, заданого своїми таблицями переходів і виходів (табл. 23 і 24.).

Синтез виконуватимемо в наступному порядку:

1. Виберемо в якості елементів пам'яті D -тригер, функція входів якого представлена в таблиці стор. 33.

2. Закодируем вхідні, вихідні сигнали і внутрішні стани автомата. Кількість вхідних абстрактних сигналів F = 3, отже кількість вхідних структурних сигналів L =] log ₂ F [=] log ₂ 3 [= 2, тобто х _1, х _2.

Кількість вихідних абстрактних сигналів G = 4, отже кількість вихідних структурних сигналів N =] log ₂ G [=] log ₂ 4 [= 2, тобто у _1, у _2. Кількість внутрішніх станів абстрактного автомата M = 4, отже кількість двійкових елементів пам'яті (тригерів) R =] log ₂ M [=] log ₂ 4 [= 2.

Отже, структура ЦА з урахуванням того, що вихідний автомат є автоматом Мілі, як елементи пам'яті використовується D -тригер, може бути представлена у вигляді (рис. 29):

Кодування вхідних, вихідних сигналів і внутрішніх станів представлена ​​в таблицях:

Кодування, в загальному випадку, здійснюється довільно. Тому, наприклад, кожному з сигналів Z _i можна поставити у відповідність будь-яку двухразрядного комбінацію х _1, х _2. Необхідно тільки, щоб різні вихідні сигнали Z _i кодувалися різними комбінаціями х _1, х _2. Аналогічно для W _i і a _i.

3. Отримаємо кодовані таблиці переходів і виходів структурного автомата. Для цього в таблицях переходів і виходів вихідного абстрактного автомата замість Z _i, W _i, a _i cтав відповідні коди. Отримаємо таблиці:

В кодованої таблиці переходів задані функції

В кодованої таблиці виходів задані функції:

4. При канонічному методі синтез зводиться до отримання функцій:

і подальшому побудові комбінаційних схем, що реалізують цю систему булевих функцій.

Функції у ₁ і у ₂ можуть бути безпосередньо отримані з таблиці виходів, наприклад, у вигляді:

Однак вираження для у ₁ і у ₂ можна істотно спростити в результаті мінімізації, наприклад, за допомогою карт Карно:

В результаті мінімізації маємо:

Для отримання виразів для D ₁ і D ₂ необхідно отримати таблиці функцій збудження.Для чого в загальному випадку необхідно скористатися таблицею переходів і функціями входів елементів пам'яті. Знаючи код вихідного стану автомата і код

стану переходу на підставі таблиці входів тригера отримуємо потрібну установку функції збудження, що забезпечує заданий перехід. Однак для D -тригер, як зазначалося раніше, таблиця переходів збігається з таблицею функції збудження. Тоді або безпосередньо з цієї таблиці, або в результаті мінімізації одержуємо необхідні значення D _i. Зазвичай використовується мінімізація за допомогою карт Карно:

В результаті мінімізації одержуємо:

5. На підставі отриманих в результаті синтезу булевих виразів ((*), (**)), будуємо функціональну схему автомата. Для цього рівняння ((*), (**)) представимо у вигляді:

Функціональна схема автомата представлена на сторінці 41:

Додатково на функціональній схемі показаний сигнал , Який встановлює автомат в початковий стан (в даному випадку 00).

Особливості синтезу автоматів на базі T, RS, JK тригерів.

Необхідно відзначити, що синтез на базі зазначених типів тригерів здійснюється аналогічно виконаному синтезу на базі D -тригер. Зокрема, п. 1¸3 (див. Попередній параграф) абсолютно аналогічні. Крім того, як випливає з п.4 (див. Попередній параграф) вихідні сигнали залежать від типу тригерів, тому вираз для y _i будуть однаковими для будь-якого типу тригерів. Однак функції збудження будуть різні для різних типів тригерів і виходять на підставі таблиці переходів вихідного автомата і функції входів обраного тригера. Без особливих пояснень нижче наведені таблиці функцій входів, функцій збуджень і карти Карно для мінімізації функцій збудження при використанні для синтезу автомата попереднього параграфа T -, RS -, JK -тригер.

T -тригер.

RS - тригер.

JK - тригер.

Функціональні схеми автоматів з різними типами тригерів пропонується побудувати самостійно.

Кодування внутрішніх станів ЦА.

Гонки в автоматі.

Кодування полягає в зіставленні кожному стану автомата набору (коду) станів елементів пам'яті. При цьому набори для всіх станів повинні мати однакову довжину, а різним станам автомата повинні відповідати різні набори. Якщо елементи пам'яті виконавчі, то їх число .

Перехід автомата з одного стану в інший здійснюється за рахунок зміни станів елементів пам'яті. Якщо автомат переходить зі стану з кодом 010 в стан з кодом 100, то це означає, що тригер V ₁ переходить зі стану 0 в стан 1, V ₂ - з 1 в 0, V ₃ - зберігає свій стан.

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

Якщо при переході автомата з одного стану в інший повинні змінити свої статки відразу кілька запам'ятовуючих елементів, то між ними починаються змагання. Той елемент, який виграє ці змагання, тобто змінить свій стан раніше, ніж інші елементи, може через ланцюг зворотного зв'язку змінювати сигнали на входах деяких запам'ятовуючих елементів до того, як інші, які беруть участь в змаганнях елементи, змінять свої статки. Це може привести до переходу автомата в стан, не передбачене його графом. Тому в процесі переходу зі стану a _m в стан a _s під дією вхідного сигналу Z _f автомат може виявитися в стані a _k або a _l: (рис.36.).

Якщо потім при тому ж вхідному сигналі Z _f автомат з а _k і а _l перейде в а _s, то такі змагання є допустимими або некритичними.

Якщо ж в цьому автоматі є перехід, наприклад, з а _k в а _j ¹ а _s під дією того ж сигналу Z _f, то автомат може перейти в а _j, а не в а _s і правильність його роботи буде порушена (мал.37 .).

Такі змагання називаються критичними змаганнями або гонками і необхідно вживати заходів для їх усунення.

Усунути гонки можна апаратними засобами або використовуючи спеціальні методи кодування. Один із способів ліквідації гонок складається в Тактирование вхідних сигналів автомата імпульсами певної тривалості. Передбачається, що крім вхідних каналів х _1,..., х _l є ще канал З від генератора синхроімпульсів, за яким надходить сигнал С = 1 в момент приходу імпульсу і С = 0 при його відсутності. У зв'язку з цим вхідним сигналом на переході (a _m, a _s) буде не Z _f, а CZ _f. Тоді, якщо тривалість імпульсу t _c менше найкоротшого шляху проходження тактірованного сигналу зворотного зв'язку по комбінаційної схемою, то до моменту переходу в проміжний стан a _k сигнал C = 0, CZ _f = 0, що виключає гонки. Канал С - це фактично синхровхід тригера. Недолік методу - в труднощі підбору необхідної тривалості імпульсу, тому що вона залежить від багатьох факторів, які чинять спротив суворому обліку.

Інший спосіб ліквідації гонок полягає у введенні подвійний пам'яті. У цьому випадку кожен елемент пам'яті дублюється, причому перепис з першого елемента пам'яті в другій відбувається в момент С = 0 (мал.38.).

Сигнали зворотного зв'язку для отримання функцій збудження і функцій виходів автомата знімаються з виходу другого тригера. Таким чином змагання можуть виникнути тільки між першими тригерами, сигнали ОС (виходи друге тригерів) не можуть змінитися до тих пір, поки С не стане рівним 0. Але тоді CZ _f = 0, перший тригер перестане сприймати інформацію, і перегонів не буде.

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

Сусіднє кодування не завжди можливо. Граф автомата, що допускає сусіднє кодування, повинен задовольняти ряду вимог, а саме:

1) в графі автомата не повинно бути циклів з непарним числом вершин;

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

Під станами другого порядку розуміються такі два стану, шлях між якими по графу автомата складається з двох ребер (незалежно від орієнтації). Приклади графів автоматів допускають і не допускають сусіднє кодування представлені на рис.39. і 39б. відповідно.

При сусідньому кодуванні зазвичай користуються карткою Карно. В цьому випадку стану, пов'язані дугою, мають у своєму розпорядженні на сусідніх клітинах карти (рис.40.).

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

Кодування станів і складність комбінаційної схеми автомата.

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

1) алгоритм кодування для D -тригер;

2) евристичний алгоритм кодування.

Алгоритм кодування для D -тригер.

Згідно розглянутого алгоритму при кодуванні необхідно виконати наступне:

1. Кожному стану автомата а _m (m = 1,2, ..., M) ставиться у відповідність ціле число N _m, яка дорівнює кількості переходів в стан а _m (N _m дорівнює числу появ а _m в полі таблиці переходів або числу дуг , що входять в а _m при графічному способі задання автомата).

2. Числа N _1, N _2,..., N _m упорядковуються по спадаючій.

3. Стан а _s з найбільшим N _s кодується кодом: , Де R-кількість елементів пам'яті.

4. Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1: 00 ... 01, 00 ... 10, ..., 01 ... 00, 10 ... 00.

5. Для решти станів знову в порядку списку п.2. використовують коди з двома одиницями, потім з трьома і так далі поки не будуть закодовані їхні капітали.

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

Зокрема, для автомата, заданого своїми таблицями переходів і виходів (див. Нижче) при кодуванні на базі D -тригер.

a ₁ ~ N ₁ = 3 N ₃ a ₃ = 000

a ₂ ~ N ₂ = 4 N ₂ a ₂ = 001

a ₃ ~ N ₃ = 5 N ₁ a ₁ = 010

a ₄ ~ N ₄ = 5 N ₄ a ₄ = 100

a ₅ ~ N ₅ = 1 N ₅ a ₅ = 011

Аналогічно кодування внутрішніх станів для D -тригер можна кодувати вихідні сигнали для будь-якого типу тригерів, тобто чим частіше виробляється даний вихідний сигнал w _i, тим менше одиниць в його коді. Так для автомата (рис.41.) Маємо:

w ₁ ~ N ₁ = 6 N ₁ w ₁ = 00

w ₂ ~ N ₂ = 5 N ₂ w ₂ = 01

w ₃ ~ N ₃ = 2 N ₃ w ₃ = 10

w ₄ ~ N ₄ = 2 N ₄ w ₄ = 11

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

Евристичний алгоритм кодування.

Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK -тригер. Для даних типів тригерів (на відміну від D -тригер!) На кожному переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа перемикань тригерів призводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно призводить до спрощення комбінаційної схеми автомата.

Введемо деякі визначення.

Нехай Г (S) - неорієнтований граф переходів автомата S. Вершини графа ототожнюються з станами автомата. Вершини i і j з'єднані ребром, якщо є перехід з а _i і а _j або навпаки.

Позначимо q (i, j) число всіляких переходів автомата з а _i в а _j. Кожному ребру (i, j) графа Г (S) поставимо у відповідність вага ребра р (i, j) = q (i, j) + q (j, i).

Введемо функцію w (i, j) = р (i, j) × d (i, j), де d (i, j) - число компонентів, якими коди станів а _i в а _j відрізняються один від одного (тобто . кодова відстань між кодами а _i в а _j).

Функція w (i, j) має простий фізичний зміст. Перход автомата з а _i в а _j (або навпаки) супроводжується перемиканням стількох тригерів, скількома компонентами відрізняються коди цих станів, тобто їх число дорівнює w (i, j). Отже, при переході автомата по всіх ребрах, що з'єднує станам а _i і а _j (їх число p (i, j)!) Всього переключиться кількість тригерів, рівне p (i, j) × d (i, j) = w (i , j).

Але тоді функція показує, скільки всього перемикається тригерів при проходженні автомата по всіх можливих переходах. Функція w показує, скільки всього одиниць у функції збудження, тобто дозволяє оцінювати складність комбінаційної схеми автомата. W можна розглядати як якусь цільову функцію, мінімум якої визначить таке кодування, при якому комбінаційна схема найбільш проста. До речі, міінмальное кодове відстань між різними станами дорівнює 1 і якщо вдається закодувати їхні капітали сусіднім кодуванням, то очевидно, що w буде мінімально можливим і рівним , Тобто сумарному числу переходів для автомата.

З виразу для w слід, що перехід з а _i в а _i, для якого d (i, i) = 0, не впливає на w (що цілком очевидно, якщо врахувати, що на цьому переході жоден тригер перемикається).

Розглянемо застосування евристичного алгоритму на конкретному прикладі автомата, заданого таблицями переходів і виходів (рис.41.). Для цього автомата можна побудувати орієнтований граф (без урахування петель), представлений на ріс.42. На кожному ребрі вказано його вага.

Евристичний алгоритм складається з наступних кроків.

1. Будуємо матрицю , Що складається з усіх пар номерів (i, j), для яких р (i, j) ¹ 0 (тобто в автоматі є перехід з а _i в а _j або навпаки) і i Для кожної пари в матриці вказуємо її вага р (i, j), що співпадає з вагою ребра з'єднує а _i і а _j.

2. Впорядкуємо рядки матриці , Для чого побудуємо матрицю наступним чином. У перший рядок матриці помістимо пару (a, b) з найбільшим вагою р (a, b). У нашому випадку (a, b) = (2,3), р (2,3) = 3. З усіх пар, що мають загальний компонент з парою (a, b) вибирається пара (g, d) з найбільшим вагою і заноситься у другому рядку матриці . Ясно, що {a, b} × {g, d} ¹0. Потім з усіх пар, що мають загальний компонент хоча б з однією з внесених вже в матрицю пар вибирається пара з найбільшою вагою і заноситься в матрицю і т.д .. У випадку рівності ваг пар обчислюються суми ваг компонентів пар (вагою р (a) компонента a називається число появ a в матриці ) І в матрицю заноситься пара з найбільшою сумою ваг. В даному автоматі на друге місце слідом за парою (2,3) претендують пари: (1,2) з р (1,2) = 2; (3,4) з р (3,4) = 2, (3,5) з р (3,5) = 2.

Для визначення того, яка пара займе друге місце в матриці знаходимо ваги компонентів пар:

р (1) = 3 р (2) = 3 р (1) + р (2) = 6

р (3) = 4 р (4) = 2 р (3) + р (4) = 6

р (3) = 4 р (5) = 2 р (3) + р (5) = 6

В даному випадку для всіх пар збігаються і їх ваги і ваги їх компонентів. Тому на друге місце матриці може бути поставлена ​​будь-яка з пар (1,2), (3,4), (3,5). Але тоді на 3-му і 4-му будуть інші дві. Виконавши упорядкування всіх пар, отримаємо матрицю у вигляді:

3. Визначаємо розрядність коду для кодування станів автомата (кількість елементів пам'яті - тригерів). Всього станів M = 5. тоді

R =] log ₂ M [=] log ₂ 5 [= 3.

Закодируем стану з першого рядка матриці наступним чином: K ₂ = K (а ₂₎ = 000; K ₃ = K (а ₃₎ = 001.

Для зручності кодування будемо ілюструвати цей процес картою Карно:

4. Викреслимо з матриці перший рядок, відповідну закодованим станам а ₂ і а _3. отримаємо матрицю .

5. В силу упорядкування п.2 в першому рядку закодований рівно один елемент. Виберемо з першого рядка незакодований елемент і позначимо його g. (В нашому випадку g = 1).

6. Будуємо матрицю , Вибравши з рядки, що містять g.

Нехай B _g = {g _1,..., g _F} - безліч елементів з матриці , Які вже закодовані. Їх коди До _{g 1,}..., K _{g F} відповідно. У нашому випадку:

B _g = B ₃ = {2,3} K ₂ = 000 K ₃ = 001.

7. Для кожного K _{g f} (f = 1, ..., F) знайдемо - безліч кодів, сусідніх з і ще не зайнятих для кодування станів автомата. (Для сусідніх кодів кодова відстань d = 1).

K ₂ = 000 = {100, 010}

K ₃ = 001 = {011, 101}.

побудуємо безліч

Якщо виявляється, що , То будуємо нове безліч , де - безліч кодів, у яких кодова відстань до коду дорівнює 2 і т.д ..

8. Для кожного коду з безлічі D _g знаходимо кодова відстань до коду .

K ₂ = 000 K ₃ = 001

d (100, 000) = 1 d (100, 001) = 2

d (010, 000) = 1 d (010, 001) = 2

d (011, 000) = 2 d (011, 001) = 1

d (101, 000) = 2 d (100, 001) = 1

9. Знаходимо значення функції w для кожного коду з безлічі D _g.

10. З безлічі D _g вибираємо код K _g, у якого вийшло мінімальне значення w в п.9. Вибираємо код для стану a ₁ До ₁ = 100.

11. З матриці викреслюємо рядки, в яких обидва елементи вже закодовані, в результаті чого отримаємо нову матрицю . Якщо в новій матриці не залишилося жодного рядка, то кодування закінчено. В іншому випадку повертаємося до п.5. У нашому випадку маємо:

До ₂ = 000 = {010}

K ₃ = 001 = {011, 101}

K ₂ = 000 K ₃ = 001

d (010, 000) = 1 d (010, 001) = 2

d (011, 000) = 2 d (011, 001) = 1

d (101, 000) = 2 d (101, 001) = 1

Вибираємо До ₄ = 101.

До ₁ = 100 = {110}

K ₂ = 000 = {010}

До ₃ = 001 = {011}

До ₁ = 100 K ₂ = 000 K ₃ = 001

d (110, 100) = 1 d (110, 000) = 2 d (110, 001) = 3

d (010, 100) = 2 d (010, 000) = 1 d (010, 001) = 2

d (011, 100) = 3 d (011, 000) = 2 d (011, 001) = 1

Вибираємо До ₅ = 011.

Оскільки їхні капітали автомата закодовані, то робота алгоритму закінчується. Загальна кількість перемикань тригерів:

Мінімально можлива кількість перемикань (якби стану були закодовані сусіднім кодуванням)

Коефіцієнт ефективності кодування:

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

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

Керуючі і операторні автомати.

Принцип мікропрограмного управління.

ЕОМ переробляє інформацію, виконуючи над нею якісь операції. Для виконання операцій над інформацією використовуються операційні пристрої - процесори, канали введення-виведення, пристрої управління зовнішніми пристроями і т.д. Функцією операційного пристрою є виконання заданої множини операцій F = {f _1,..., f _G} над вхідними словами D = {d _1,..., d _H} c метою обчислення слів R = {r _1,... , r _Q}, які представляють результати операцій R = f _g (D), де g = 1,2, ..., G.

Функціональна і структурна організація операційних пристроїв базується на принципі мікропрограмного управління, який полягає в наступному:

1. Будь-яка операція f _g (g = 1, ..., G), що реалізується пристроєм, розглядається як складна дія, яка поділяється на послідовність елементарних дій над словами інформації. Ці елементарні дії називаються мікрооперацій.

2. Для управління порядком проходження мікрооперацій використовуються логічні умови, які в залежності від значень слів, перетворюються мікрооперацій, приймають значення "брехня" або "істина" (1 або 0).

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

4. Мікропрограма використовується як форма представлення функції пристрою, на основі якої визначається структура і порядок функціонування пристрою в часі.

Т.ч. з принципу мікропрограмного управління слід, що структура і порядок функціонування операційних пристроїв зумовлюється алгоритмом виконання операції F = {f _1,..., f _G}.

До елементарним діям над словами інформації Мікрооперацій відносяться: передача інформації з одного регістру в інший, взяття зворотного коду, зсув і т.д.

Поняття операційного і керуючих автоматів.

Як показав академік В.М. Глушков в будь-якому пристрої обробки цифрової інформації можна виділити два основні блоки - операційний автомат (ОА) і керуючий автомат (УА).

Операційний автомат (ОА) служить для зберігання слів інформації, виконання набору мікрооперацій і обчислення значень логічних умов, тобто операційний автомат є структурою, організованою для виконання дій над інформацією. Микрооперации, що виконуються ОА, задаються безліччю керуючих сигналів Y = {y _1,...., y _M}, з кожним з яких ототожнюється певна мікрооперація.

Значення логічних умов, що обчислюються в операційному автоматі, відображаються безліччю осведомітельних сигналів X = {x _1,..., x _L}, кожен з яких ототожнюється з певним логічним умовою.

Керуючий автомат (УА) генерує послідовність керуючих сигналів, визначену прошивки і відповідну значенням логічним умов. Інакше кажучи, керуючий автомат задає порядок виконання дій в ОА, що випливає з алгоритму виконання операцій. Найменування операції, яку необхідно виконати в пристрої, визначається кодом g операції, що надходять в УА ззовні. По відношенню до УА сигнали g _1,..., g _h, за допомогою яких кодується найменування операції і осведомітельних сигнали x _1,..., x _L, що формуються в операційному автоматі, грають однакову роль: вони впливають на порядок вироблення керуючих сигналів Y . Тому сигнали g _1,..., g _h і x _1,..., x _L відносяться до одного класу - до класу осведомітельних сигналів, що надходять на вхід УА.

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

Операційний і керуючий автомати можуть бути визначені своїми функціями - переліком виконуваних ними дій.

Функція ОА визначається наступною сукупністю відомостей:

1) безліччю вхідних слів D = {d _1,..., d _H}, що вводяться в автомат в якості операндів;

2) безліччю вихідних слів R = {r _1,..., r _Q}, що представляють результати операцій;

3) безліччю внутрішніх слів S = {s _1,..., s _N}, використовуваних для представлення інформації в процесі виконання операцій. Можна вважати, що вхідні і вихідні слова збігаються з певними внутрішніми D ÍS, RÍS.

4) безліччю мікрооперацій Y = {y _m}, що реалізують перетворення S = j _m (s) над словами інформації, де j _m - обчислюється функція;

5) безліччю логічних умов X = {x _i}, де x _i = y _i (s _i) і y _i - булева функція;

To функція ОА задана, якщо задані (визначені) безлічі D, R, S, Y, X. Час не є аргументом функції ОА. Функція встановлює перелік дій-микроопераций і логічних умов, які може виконувати автомат, але ніяк не визначає порядок проходження цих дій у часі. Тобто функція ОА характеризує засоби, які можуть бути використані для обчислень, але не сам обчислювальний процес.

Порядок виконання дій у часі визначається в формі функцій керуючого автомата.

Функція керуючого автомата - це операційна схема алгоритму (прошивки), функціональними операторами якої є символи у _1,..., у _m, ототожнюються з мікрооперацій, і в якості логічних умов використовуються булеві змінні х _1,..., х _L. Операційна схема алгоритму найбільш часто представляється у вигляді граф-схеми алгоритму (ГСА). ДСА визначає обчислювальний процес послідовно в часі, встановлюючи порядок перевірки логічних умов х ₁ - х _L і порядок проходження мікрооперацій у ₁ - у _m.

СПОСОБИ ОПИСУ алгоритмів та вбудоване

Найбільш наочно зображати мікропрограми та алгоритми у вигляді орієнтованого графа, т.зв. граф схеми алгоритму (ГСА). Крім наочності це дає можливість використовувати для аналізу та перетворення мікропрограм ефективні методи теорії графів. При графічному описі окремі функції алгоритмів (мікрооперації) відображаються у вигляді умовних графічних зображень, т.зв. вершин. В ДСА зазвичай використовують вершини наступних типів:

- вершина «початок» має один вихід, входів не має. Позначає початок прошивки.

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

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

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

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

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

Сама мікропрограма і її граф повинні бути коректні, тобто відповідати таким умовам:

1. У графі повинна бути тільки одна початкова і одна кінцева вершина.

2. У будь-яку вершину графа повинен вести принаймні один шлях з початкової вершини.

3. З кожного виходу будь-якої вершини графа повинен існувати по

Принаймні один шлях в кінцеву вершину.

4. При всіх можливих значеннях логічних умов і використовуваних слів повинен існувати шлях з початкової вершини в кінцеву.

Приклад ДСА представлений на малюнку:

ДСА на рис.43 називається змістовною, тому що всередині вершин записані в явному вигляді мікрооперації і логічні умови. Якщо ж кожну микрооперацию позначити символами Yi, a логічні умови через Xi, то вийде так звана кодованих ДСА (ріс.44). Для правильного сприйняття прошивки, заданої у вигляді кодованої ДСА, необхідно знати відповідності між Yi, Xi і змістом відповідних мікрооперацій і логічних умов.

Для запису микроопераций всередині вершин використовується так званий Ф-мова. Детально з зтим мовою можна ознайомитися в наступних курсах «Схемотехніка ЕОМ», «Теорія і проектування ЕОМ». Тут же ми розглянемо тільки основні положення цієї мови.

У цій мові існують виконавчі константи і змінні: 0010 - константа, A (1: 4) - чотирирозрядний слово - чотирирозрядний двійковий змінна. Наприклад, A (1: 4) = 1010 означає, що в першому розряді слова A буде 1, у другому - 0 і т.д. A (2: 3) - частина слова A, розміщена в другому і третьому розрядах.

Найбільш вживані операції Ф-мови:

присвоювання - A (0: 3): = 1000, B (1: 4): = A (5: 8) і т.д.

інвертування - A (0: 3): = ^ B (1: 4)

конкатенації - С (0: 6): = A (0: 3). B (1: 3)

Приклад 1. A (0: 3): = 1100 B (1: 4): = A (0: 3) ® B (1: 4): = 1100

2. B (1: 4): = 0101 A (0: 3): = ^ B (1: 4) ® A (0: 3): = 1010

3. A (0: 3): = 1101 B (1: 3): = 110 C (0: 6): = A (0: 3). B (1: 3) ® C (0: 6): = 1101110

Запис виду A (2) означає, що тут розглядається другий розряд слова A, тобто це біт, записаний у другому розряді слова A.

При виконанні операцій присвоювання необхідно дотримуватися рівність розрядів в словах зліва і праворуч від знака присвоювання. Операції додавання, логічного додавання і т.д. в Ф-мові записуються звичайним способом через оператор присвоювання:

C (0: n): = A (0: n) + B (0: n)

D (0: n): = A (0: n) vB (0: n) і т.д.

ОПЕРАЦІЙНІ ЕЛЕМЕНТИ

Згідно принципу мікропрограмного управління, будь-яка складна операція розпадається на ряд мікрооперацій, які виконуються ОА. Різні микрооперации виконуються елементарними ОА - так званими операційними елементами (ОЕ), які є складовими частинами основного ОА.

Під операційним елементом розуміють пристрій, що реалізує одну з наступних функцій або їх довільну комбінацію:

· Зберігання слова інформації С;

· Виконання деяких мікрооперацій, в результаті яких обчислюється нове значення слова С;

· Обчислення логічного умови, що залежить від слова С;

Т.ч. функція ОЕ визначена, якщо задані:

· Опис зберігається або обчислюється слова;

· Опис безлічі мікрооперацій, виконуваних цим елементом;

· Опис обчислюваних цим елементом логічних умов.

Для побудови ОА ОЕ з'єднуються між собою за допомогою ланцюгів передачі слів інформації від виходів одних елементів до входів інших.

Залежно від виконуваних мікрооперацій ОЕ діляться на різновиди: шина, регістр, лічильник, суматор, схема порівняння, дешифратор, шифратор і т.д.

Шина - це сукупність ланцюгів, призначених для передачі слова інформації. Умовне позначення шини представлено на рис.45.

Шини, зображені на рис.45 називаються некерованими шинами.

Керовані шини представлені на ріс.46.

Під дією керуючого сигналу у керована шина виконує мікрооперації: у = 0: B (0: 3): = 0, y = 1: B (0: 3): = A (0: 3)

Тобто при y = 1 здійснюється операція передачі. Розрядність шини може бути довільна, але зазвичай це 8, 12, 16, 24, 32 і т.д.

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

· Установка регістра в 0 (скидання);

· Прийом слова з іншого регістра, шини і т.д .;

· Передача слова на інший регістр, шину і т.д .;

· Перетворення кодів збережених слів в інверсні коди;

· Зрушення зберігається слова вліво або вправо на необхідне число розрядів.

Регістр, що виконує такі мікрооперації, називається багатофункціональним. Оскільки регістр призначений для зберігання інформації, то він містить елементи пам'яті, в якості яких використовуються тригери. Кількість тригерів визначає розрядність регістра. Будемо позначати регістр у вигляді прямокутника із зазначенням розрядності (ріс.47).

Регістр може складатися з окремих подрегістров, що мають самостійне значення (рис.48.). На рис.48 представлений регістр, який зберігає число у формі з плаваючою комою. У цьому регістрі три подрегістра: для зберігання знака Рг (0), характеристики Рг (1: 7), мантиси Рг (8:31) числа.

Регістр може виконувати ряд мікрооперацій, наприклад:

Регістр, який виконує микрооперацию у4 (зрушення вправо) або У5 (зрушення вліво) називаються регістром зсуву.

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

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

Умовне позначення комбінаційного суматора представлено на ріс.50.

Накопичують називається суматор, який здійснює складання слів A і B при подачі їх на суматор одного за іншим. В накапливающем сумматоре имеется дополнительный регистр для хранения результата.

Структура и условное обозначение накапливающего сумматора представлены на рис. 51.

Счетчик - операционный элемент, который реализует микрооперацию счета. Микрооперация счета состоит в изменении состояния счетчика (значения хранимого слова) на 1. Кроме того счетчик может выполнить и такие микрооперации: установка в 0 и прием произвольного числа.

Тобто полный набор возможных микроопераций для счетчика:

Счетчик, выполняющий микрооперацию у ₁ называется суммирующим, микрооперацию у ₂ - вычитающим, обе микрооперации - реверсивный.

Дешифратор - операционный элемент, выполняющий функцию преобразования некоторого n-разрядного двоичного кода в унитарный код «один из N». Если N=2 ⁿ - то такой дешифратор называется полным, если N<2 ⁿ - то частичным. Таблица истинности простейшего полного дешифратора (n=2) и его условное обозначение приведены в табл. 25. и на рис. 53.

Промышленность может выпускать дешифраторы с инверсными выходами. Для такого дешифратора таблица истинности и условное обозначение имеют вид (табл. 26., рис. 54.)

СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ ПО ГРАФ-СХЕМЕ АЛГОРИТМА

Граф-схема алгоритма есть форма представления микропрограммы, которую должно выполнить операционное устройство (ОУ). При построении операционного устройства, как состоящего из операционного (ОА) и управляющего (УА) автоматов, необходимо уметь выделить функции ОА и УА из ГСА. Обычно микропрограмма представляется в виде содержательной ГСА. В этом случае для задания функций ОА необходимо перечислить все выполняемые микрооперации и все проверяемые логические условия данной микропрограммы, а также описать разрядность слов, обрабатываемых операционным устройством. На основании этих данных можно построить ОА методами, которые будут изложены в курсе «Схемотехника ЭВМ». Для инициализации выполнения той или иной микрооперации на ОА должны поступать в нужный согласно ГСА момент времени управляющие сигналы Yi. Обычно при проектировании ОУ принимают определенный способ кодирования микроопераций (чаще всего кодом, содержащим столько разрядов, сколько всего различных микроопераций) и для разработки ОА считают, что УА выдает код микроопераций, которые должны выполниться в данный момент времени.

Для УА важна последовательность выдачи соответствующих кодов микроопераций в зависимости от логических условий, вырабатываемых ОА и анализируемых УА в нужные моменты времени. Если принят способ кодирования микроопераций, то функции УА задаются кодированной ГСА. Поэтому для различных содержательных ГСА , имеющих одинаковую кодированную ГСА, ОА будут различны, но УА будет одним и тем же.

В дальнейшем будем рассматривать синтез только УА и только кодированной ГСА.

Конечный автомат, интерпретирующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Одну и ту же ГСА можно интерпретировать как автоматом Мили, так и автоматом Мура.

Абстрактный синтез микропрограммного автомата по ГСА осуществляется в два этапа:

1. Получение отмеченной ГСА.

2. Построение графа автомата или таблиц переходов и выходов.

СИНТЕЗ АВТОМАТА МИЛИ

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечают символами a ₁, a ₂,.. по следующим правилам:

1) символом а ₁ отмечают вход вершины, следующей за начальной, а также вход конечной вершины;

2) входы всех вершин следующих за операторными, должны быть отмечены;

3) входы различных вершин, за исключением конечной, отмечаются различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов а ₁,...,a _m. Результатом первого этапа является отмеченная ГСА, которая служит основой для второго этапа - перехода к графу или таблицам переходов-выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.

На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы переходов-выходов. Для этого полагают, что в автомате будет столько состояний сколько символов a _i понадобилось при отметке ГСА.

На плоскости рисунка отмечаем все состояния автомата a _i. Для каждого из состояний a _i определяем по отмеченной ГСА все пути, ведущие в другие состояния и проходящие обязательно только через одну операторную вершину . Например, из состояния а ₁ (рис.55.) есть переход в состояние a ₂ (путь проходит через операторную вершину y ₁ y ₂) и в состояние a ₄ (путь проходит через вершину y ₃ y ₄). Перехода из a ₁ в a ₃ нет, так как на этом пути нет ни одной операторной вершины. Будем считать, что автомат осуществляет переход, например, из a ₁ в a ₂ при условии x ₁ = 0 или x ₁ (см.ГСА, рис.55. ) и вырабатывает на этом переходе выходные сигналы у ₁ у ₂ (то, что записано в проходимой операторной вершине ГСА, рис.55.). Значение условий х ₂, х ₃, х ₄ на этом переходе не оказывает влияния на автомат.

Исключение составляет только путь, ведущий в конечную вершину, он может не содержать ни одной операторной вершины (например, переход из а ₆ в а ₁), т.е. не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг, которым приписываем условия перехода и выходной сигнал, вырабатываемый на этом переходе. Получим граф автомата (рис.55. ).

На этом графе переходам типа а ₃ ®a ₄, a ₅ ® a ₁ приписывается условие перехода 1, т.к. эти переходы являются безусловными и выполняются всегда, когда автомат попадает в состояние а ₃ (или а ₅). На основании отмеченной ГСА или графа автомата можно построить таблицу переходов-выходов. Для микропрограммных автоматов таблица переходов-выходов строится в виде списка и различаются прямая и обратная таблицы. Для данного автомата прямая таблица представлена в табл. 27., обратная - в табл. 28.

Табл. 27.Прямая таблица переходов- Табл. 28.Обратная таблица перехо-

выходов автомата Мили дов - выходов автомата Мили

В приведенных таблицах a _m - исходное состояние, a _S - состояние перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния am в состояние as, Y - выходной сигнал, вырабатываемый автоматом при переходе из a _m в a _S.

СИНТЕЗ АВТОМАТА МУРА.

Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:

1) символом а ₁ отмечается начальная и конечная вершины;

2) различные операторные вершины отмечаются различными символами;

3) все операторные вершины должны быть отмечены;

Пример ГСА, отмеченной для автомата Мура, представлен на рис. 56.

Граф автомата Мура, соответствующий отмеченной ГСА (рис. ), представлен на рис. . Построение его аналогично построению графа для автомата Мили.

Таблицы переходов-выходов автомата Мура представлены в табл. 29 (прямая) и табл. 30 (обратная). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется и выходной сигнал записывается в столбце, где указывается исходное состояние a _m или состояния перехода a _S.

Табл. 29.Прямая таблица переходов Табл. 30.Обратная таблица переходов

автомата Мура. автомата Мура.

Получением графа или таблиц переходов-выходов заканчивается этап абстрактного синтеза микропрограммного автомата. Как и для конечных автоматов, на этапе абстрактного синтеза можно выполнить минимизацию количества внутренних состояний автомата.

СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ

Структурный синтез микропрограммных автоматов после получения графа или таблицы переходов-выходов в принципе аналогичен каноническому методу синтеза цифровых автоматов, рассмотренному ранее. Однако существуют и определенные особенности в первую очередь связанные с тем, что для реальных автоматов количество элементов памяти и входных сигналов может достигать десяти и более. Функции возбуждения и выходных сигналов трудно поддаются минимизации да и практически минимизация не дает существенного упрощения этих функций при большом количестве переменных. Поэтому минимизация практически не используется при синтезе микропрограммных автоматов.

При выполнении структурного синтеза строят так называемые структурные таблицы переходов и выходов, которые также могут быть как прямыми так и обратными.

Рассмотрим этапы структурного синтеза на конкретных примерах.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МИЛИ

Выполним структурный синтез микропрограммного автомата Мили, заданного своей таблицей переходов-выходов (табл. 27 или табл. 28). В качестве примера синтез будем выполнять по прямой таблице (табл. 27).

1. В исходном автомате количество состояний М=6, следовательно, число элементов памяти

m = ] log 2 M [ = ] log 2 6 [ = 3.

Пусть для синтеза используются JK триггеры.

2. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис.57.) и по возможности метод соседнего кодирования. Рекомендуется самостоятельно закодировать состояние с помощью эвристического алгоритма.

3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл. 31). В данной таблице в столбцах k(a _m) и k(a _s) указывается код исходного состояния и состояния перехода соответственно. В столбце функций возбуждения ФВ указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности. Предлагается самостоятельно построить структурную таблицу переходов с указанием всех значений функций возбуждения (в том числе и неопределенных), выполнить минимизацию и сравнить результаты с приведенными ниже.

Табл. 31. Структурная таблица переходов-выходов автомата Мили.

4. Для получения функций возбуждения поступаем следующим образом. Выражение для каждой функции получается в виде логической суммы произведений вида a _i X, где a _i - исходное состояние, X-условие перехода. Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:

J ₁ = a ₂ x ₃ + a ₄ x ₂ K ₁ = a ₃ + a ₅

J ₂ = a ₁ x ₁ K ₂ = a ₅ + a ₆ x ₄

J ₃ = a ₁ x ₁ + a ₂ x ₃ x ₂ K ₃ = a ₄ x ₂ + a ₆ x ₄ + a ₆ x ₄ = a ₆ + a ₄ x ₂

5. Для получения функций выходов поступаем аналогично:

y ₁ = a ₁ x ₁ + a ₂ x ₃ x ₂ + a ₄ x ₂ + a ₆ x ₄

y ₂ = a ₁ x ₁ + a ₂ x ₃ x ₂ + a ₂ x ₃ + a ₄ x ₂ + a ₅ + a ₆ x ₄

y ₃ = a ₂ x ₃ + a ₃ + a ₁ x ₁

y ₄ = a ₁ x ₁ + a ₂ x ₃ x ₂ + a ₃ + a ₄ x ₂

6. Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить a _i его значениями через Q ₁ Q ₂ Q ₃ либо получить сигнал, соответствующий a _i. Обычно используют второй способ и для получения сигнала a _i применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q ₁ Q ₂ Q ₃. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:

A = a ₂ x ₃ x ₂ +J ₂; J ₁ = D + B ; y ₁ = A + B + E ;

B = a ₄ x ₂; K ₁ = a ₃ + a ₅; y ₂ = A + D + C + a ₅ + E ;

C = a ₄ x ₂; J ₂ = a ₁ x ₁; y ₃ = D + F + a ₃;

D = a ₂ x ₃; K ₂ = a ₅ + a ₆ x ₄; y ₄ = a ₃ + B + J ₃;

E = a ₁ x ₁; K ₃ = a ₆ + C ;

F = a ₁ x ₁ J ₃ = F+a ₂ x ₃ x ₂

Функциональная схема автомата, построенная на основании полученных уравнений, представлена на рис. 58.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МУРА

Выполним структурный синтез микропрограммного автомата Мура, заданного своей таблицей переходов-выходов (табл.29 или табл. 30). В качестве примера синтез будем выполнять по обратной таблице (табл. 32).

1. В исходном автомате количество состояний М=7, следовательно число элементов памяти

m = ] log 2 M [ = ] log 2 7 [ = 3

Пусть для синтеза используется D-триггеры.

2. Кодируем внутренние состояния автомата, используя алгоритм кодирования для D-триггеров. Количество переходов в данное состояние легко определяется из обратной таблицы: a ₁ ~ 2, a ₂ ~ 3, a ₃ ~ 2, a ₄ ~ 1, a ₅ ~ 1, a ₆ ~ 1, a ₇ ~ 2.

Поэтому коды состояний следующие:

a ₂ -000, a ₁ -001, a ₃ -010, a ₇ -100, a ₄ -011, a ₅ -101, a ₆ -110.

3. Строим структурную таблицу переходов - выходов автомата Мура.

Табл. 32. Структурная таблица переходов - выходов автомата Мура.

Построение таблицы выполняется аналогично автомату Мили.

4. Выражения для функций возбуждения получаются в виде суммы произведений a _i х, где a _i -исходное состояние, х - условие перехода.

D ₁ = a ₂ x ₃ + a ₂ x ₃ x ₂ + a ₃ x ₂ + a ₅

D ₂ = a ₁ x ₁ + a ₄ + a ₃ x ₂ + a ₂ x ₃ x ₂

D ₃ = a ₆ x ₄ + a ₇ + a ₃ x ₂ + a ₂ x ₃

или

A = a ₃ x ₂

B = a ₂ x ₃ x ₂

D ₁ = a ₂ x ₃ + B + a ₃ x ₂ + a ₅

D ₂ = a ₁ x ₁ + a ₄ + A + B

D ₃ = a ₆ x ₄ + a ₇ + A + a ₂ x ₃

5. Выражения для выходных сигналов автомата Мура получаем, исходя из того, что эти сигналы определяются только внутренним состоянием автомата.

y ₁ = a ₂ + a ₄

y ₂ = a ₂ + a ₅ + a ₇

y ₃ = a ₃ + a ₅

y ₄ = a ₃ + a ₄ + a ₆

6. Для построения функциональной схемы автомата как и в предыдущем случае используем дешифратор состояний. Схема представлена на рис. 61 .

ЗАМЕЧАНИЯ.

1. При синтезе микропрограммных автоматов изложенным методом получаемые выражения для функций возбуждения не всегда являются минимальными и в некоторых случаях могут быть упрощены. В частности, можно доопределить функции возбуждения на некоторых наборах единичным значением (а не нулевым, как было ранее) и выполнить все операции склеивания. Например, в синтезированном ранее автомате Мили таким образом можно получить значение k ₁ =1. Рекомендуется в этом убедиться самостоятельно.

Для упрощения схем автоматов можно также предварительно упростить ГСА, уменьшив количество вершин или узлов методами, изложенными в / /.

Автомат Мили в течении такта сохраняет свое состояние и лишь в конце его переходит в новое. Пока автомат находится в данном состоянии Ai он вырабатывает выходные сигналы y=f(Ai,x), где х - сигналы, подаваемые на вход автомата в течение данного такта. В связи с этим автомат Мили может интерпретировать микропрограмму корректно только в том случае, если для любого перехода выполняется условие независимости логических условий от результатов выполнения микроопераций на данном переходе.

Условие независимости нарушается, если на некотором переходе из а _m в а _s под действием сигнала х с выработкой у _i наблюдается функциональная зависимость х = f ( у _i). В таком случае выполнение микрооперации у _i может привести к изменению значения х и автомат, находясь в состоянии а _m, и, реагируя на набор входных сигналов, сформирует набор выходных сигналов, не соответствующий микропрограмме. Чтобы избежать этого, можно использовать следующие способы:

1) запомнить значение сигналов х на промежуток времени, равный длительности такта;

2) ввести в автомат дополнительные состояния;

3) реализовать автомат по схеме Мура.

Запоминание значений сигналов х в течение такта осуществляется операционным автоматом с помощью дополнительных элементов памяти – триггеров. Интерпретация микропрограммы автоматом Мура рассматривалась ранее. Введение дополнительных состояний иллюстрируется рис. 59 .

В исходном автомате (рис. 59.а) есть переходы из а _i в а _j под действием сигналов х и х с выработкой y ₁ и y ₂ соответственно и имеет место х = f ( y ₁, y ₂). Действительно, введение вспомогательных состояний а _k и а _l позволяет устранить возможную ошибку в выдаче выходных сигналов. На переходах а _i а _k или а _i а _l выходные сигналы не вырабатываются. Переходы а _i а _k или а _i а _l являются безусловными с выработкой y ₁ или y ₂ соответственно. В таком случае изменение значения х, в результате выполнения микроопераций y ₁ или y _2, не повлияет на выходной сигнал, вырабатываемый автоматом, так как на переходах а _i а _k или а _i а _l выходной сигнал уже не зависит от х.

Синтез управляющего автомата Мура
на базе регистра сдвига.

Кроме рассмотренного ранее канонического метода, существуют и другие методы синтеза управляющих автоматов, среди которых наиболее широко используется синтез на базе регистра сдвига. Этот метод позволяет при построении схемы отказаться от дешифратора, т.к. состояния кодируются унитарным кодом. В автомате количество элементов памяти выбирается равным количеству внутренних состояний. В каждый момент времени только один триггер находится в 1, остальные в 0. Обычно при синтезе на базе регистра сдвига используются D -триггеры. Очень эффективен данный метод для так называемых линейных микропрограмм, т.е. микропрограмм без ветвлений (отсутствует логические условия). Рассмотрим пример синтеза управляющего автомата Мура данным методом. Пусть закодированная ГСА микропрограммы имеет вид рис. 60. Разметив данную ГСА для автомата Мура, получаем семь состояний. Следовательно число триггеров m =7. Выполним синтез с использованием D -триггеров. Закодируем состояния унитарным кодом: a ₁ =1000000, a ₂ =0100000,..., a ₇ =0000001. Обратная структурная таблица переходов-выходов для данного автомата представлена в таблице.