Синтез керуючих автоматів ВСТУП Принцип мікропрограмного керування припускає, що цифровий пристрій складається з двох частин: операційний автомат (ОА) і керуючий автомат (КА). ОА виконує найпростіші операції (мікрооперації) типу зсув, алгебраїчне додавання, кон’юнкція, диз’юнкція і т.п. КА формує послідовність керуючих символів в ОА, під впливом яких ОА реалізує більш складні алгоритми. Такі послідовності операцій називаються мікропрограмами та, звичайно, записуються у вигляді граф-схеми алгоритму. КА розділяються на дві великі групи: автомати з жорсткою логікою та автомати з програмованою логікою. У свою чергу автомати з жорсткою логікою підрозділяються на автомати, виконані за схемою Мілі (КА Мілі) і за схемою Мура (КА Мура), автомати з програмованою логікою – на автомати з примусовою адресацією та з природною адресацією. В автоматах з жорсткою логікою схема автомата однозначно інтерпретує граф-схему мікропрограми. В автоматах із програмованою логікою граф-схема інтерпретується у вигляді програми, що зберігається в пам’яті автомата. 1. СИНТЕЗ ОПЕРАЦІЙНОГО АВТОМАТА 1.1 Аналіз вхідних даних Загальна формула для обчислювання результату S має такий вигляд: Формулі , та згідно з варіантом завдання: Загальний алгоритм для обчислювання формули S приведений на рисунку 1.1. Для обчислювання формули S використовується ІМp-модель (IndividualMutualwithParallelpart - IMp). Рис. 1.1 – Загальний алгоритм для обчислювання формули S Схему взаємодії операційного та керуючої частин у цифровому просторі зображено на рисунку 1.2. Рис. 1.2 – Структура цифрового пристрою Структурна схема ІМp - моделі зображена на рисунку 1.3 Рис. 1.3 – Структура операційного пристрою Пам’ять автомата складається з регістрів загального призначення R1, ... , Rn . Локальні шини А1 , А2 , A3 призначені для прийому інформації з пам’яті та передачі її на комбінаційні схеми (КС). В даному випадку використовуються КС двох типів: одномісні та двомісні. Рис. 1.4 – Приклад комбінаційних схем Однак, у даному ОА використовуються лише деякі з них. 1.2 Розробка функціонального алгоритму Функціональна і структурна організація операційних пристроїв (ОУ) базується на принципі мікро програмного керування, сформульованому в 1951 році М. Уилксом. Відповідно до цього принципу будь-яка машинна операція розділяється на послідовність елементарних дій по обробці інформації – мікро операцій (МО). Порядок проходження мікро операцій визначається спеціальними логічними умовами (ЛУ), що у залежності від значень оброблюваної інформації приймають значення "істина" (1) або "неправда" (0). Алгоритм операцій в ОУ, записаний у термінах мікро операцій і логічних умов, що відбиває порядок проходження мікро операцій у часі, називається мікропрограмою. Функція УА – це оперативна схема алгоритму, операторами якої є символи , що ототожнюються з МО, виконуваними ОА, як логічні умови використовуються булеві перемінні . Найбільше часто операторна схема алгоритму представляється у виді граф-схеми алгоритму (ГСА). Граф-схема алгоритму. Орієнтований зв'язаний граф – граф, що містить одну початкову вершину, одну кінцеву вершину, довільну безліч умовних і операторних вершин. Будова ІМр автомата дозволяє паралельно виконувати одномісну та двумісну операції, тобто можливо виконувати за одне завантаження автомату завантаження двох операнд. Наприклад, у п’ятій вершині зроблено саме так. Кожній дії, завантаженню автомата, відповідає Y[і]. Ідентичні дії відповідають однаковим командам, Y[і]. Логічні умови позначаються – XL, однаковим умовам відповідають однакові XL. Функціональний алгоритм приведений на рисунку 1.5. Рис. 1.5 – Функціональний алгоритм 1.3 Розробка структурної схеми автомата 1.3.1. Визначення набору регістрів пам’яті: Rg:{RA,RB,RC,RS1 ,RS2 , RS3 } 1.3.2. Набір комбінаційних схем: Одномісні: КС1 : {L1 , L2 , L3 , R1 , R2 , R3 } На шину C повинні поступати всі аргументи одномісних операцій. Двомісні: КС2: {Sum, Sub} Припустимо, що операція відіймання виконується наступним чином: Sub:=B - A, тому від’ємне завжди повинно знаходитись на шині B, а від’ємник на шині А. В іншій двомісній операції Sumпорядок операндів значення не має. Рис. 1.6 – Структурна схема автомата 1.3.3. Зв'язки між регістрами та локальними шинами Наша схема має три шини: А та B – двомісні, та шина C – одномісна. A {RA, RB, RC, RS1 , RS2 ,RS3 } B {RA, RB, RC, RS1 , RS2 ,RS3 } C {RA, RB, RC, RS1 , RS2 ,RS3 } 1.3.4. Зворотні зв'язки шин Z1 та Z2 з регістрами пам’яті Шини, що є результативними: Z1 – результати одномісних операцій, а Z2 – двомісних операцій. Z1 {RA, RB, RC, RS1 , RS2 ,RS3 } Z2 {RA, RB, RC, RS1 , RS2 ,RS3 } Кожний елемент, котрий діє у схемі може виконуватись тільки при наявності відповідного керуючого сигналу y[n] . у1 , у2 , у3 – завантаження початкових даних на шини. у4 –у15 – завантаження даних у регістри пам'яті. у1 6 –у33 – завантаження з пам'яті на локальні шини А, B, C. у34 , у39 – завантаження результатів одномісних операцій на шину Z1 . y40 –у41 – завантаження результатів двомісних операцій на шину Z2 . Отримані таким чином дані заносимо до таблиці 1.1 Табл. 1.1 –Таблиця мікрооперацій Мікрооперація A B C Z1 Z2 Result Y формула регістр y регістр y регістр y форм. y форм. y регістр y 1 RA := <A> RB := <B> <B> y2 <A> y1 RA:=Z2 RB:=Z1 y4 y7 2 RC := <C> <C> y3 RC:=Z2 y8 3 RS3 := RA + RB RA y17 RB y21 RA+RB y40 RS3 :=Z2 y14 4 RS2 := RA – RB RB y20 RA y18 RA-RB y41 RS2 :=Z2 y12 5 RS1 := L3 (RS2 ) RS2 y28 L3 (RS2 ) y36 RS1 :=Z1 y11 6 RS1 := RS1 – RS2 RS2 y29 RS1 y27 RS1 -RS2 y41 RS1 :=Z2 y10 7 RS2 := L2 (RA) RA y16 L2 (RA) y35 RS2 :=Z1 y13 8 RS3 := L1 (RB) RB y19 L1 (RB) y34 RS3 :=Z1 y15 9 RS1 := RS2 – RS3 RS3 y32 RS2 y30 RS2 -RS3 y41 RS1 :=Z2 y10 10 RS1 := L2 (RA) RA y16 L2 (RA) y35 RS1 :=Z1 y11 11 RS1 := RS1 – RA RA y17 RS1 y27 RS1 -RA y41 RS1 :=Z2 y10 12 RS1 := R1 (RS1 ) RS1 y25 R1 (RS1 ) y37 RS1 :=Z1 y11 13 RS1 := RS1 – RB RB y20 RS1 y27 RS1 -RB y41 RS1 :=Z2 y10 14 RS3 := RB – RA RA y17 RB y21 RB-RA y41 RS3 :=Z2 y14 15 RS3 := R1 (RB) RB y19 R1 (RB) y37 RS3 :=Z1 y15 16 RS2 := RA – RS3 RS3 y32 RA y18 RA-RS3 y41 RS2 :=Z2 y12 17 RS2 := RA + RB RS3 := L1 (RC) RA y17 RB y21 RC y22 L1 (RC) y34 RA+RB y40 RS2 :=Z2 RS3 :=Z1 y12 y15 18 RS2 := RS2 – RS3 RS3 y32 RS2 y30 RS2 -RS3 y41 RS2 :=Z2 y12 19 RS2 := RS2 – RC RC y23 RS2 y30 RS2 -RC y41 RS2 :=Z2 y12 20 RS3 := L1 (RB) RB y19 L1 (RB) y34 RS3 :=Z1 y15 21 RS3 := RA – RS3 RS3 y32 RA y18 RA-RS3 y41 RS3 :=Z2 y14 22 RS2 := L3 (RS3 ) RS3 y31 L3 (RS3 ) y36 RS2 :=Z1 y13 23 RS2 := RS2 – RS3 RS3 y32 RS2 y30 RS2 -RS3 y41 RS2 :=Z2 y12 24 RS2 := R3 (RS2 ) RS2 y28 R3 (RS2 ) y39 RS2 :=Z1 y13 25 RS3 := RC + RB RB y20 RC y24 RB+RC y40 RS3 :=Z2 y14 26 RS3 := L1 (RS3 ) RS3 y31 L1 (RS3 ) y34 RS3 :=Z1 y15 27 RS3 := RS3 + RC RS3 y32 RC y24 RS3 +RC y40 RS3 :=Z2 y14 28 RC := L2 (RB) RS3 := RA – RB RB y20 RA y18 RB y19 L2 (RB) y35 RA-RB y41 RC:=Z1 RS3 :=Z2 y9 y14 29 RS3 := RS3 – RC RC y23 RS3 y33 RS3 -RC y41 RS3 :=Z2 y14 30 RS3 := RC – RA RA y17 RC y24 RC-RA y41 RS3 :=Z2 y14 31 RS3 := R2 (RS3 ) RS3 y31 R2 (RS3 ) y38 RS3 :=Z1 y15 32 RS1 := L1 (RS1 ) RS1 y25 L1 (RS1 ) y34 RS1 :=Z1 y11 33 RS1 := RS2 + RS1 RS1 y26 RS2 y30 RS1 +RS2 y40 RS1 :=Z2 y10 34 RS1 := RS2 – RS1 RS1 y26 RS2 y30 RS2 -RS1 y41 RS1 :=Z2 y10 35 RS1 := L2 (RS3 ) RS3 y31 L2 (RS3 ) y35 RS1 :=Z1 y11 36 RS1 := RS2 + RS1 RS1 y26 RS2 y30 RS1 +RS2 y40 RS1 :=Z2 y10 Рис. 1.7 – Структурна граф-схема операційного автомата 2. СИНТЕЗ КЕРУЮЧИХ АВТОМАТІВ З ЖОРСТКОЮ ЛОГІКОЮ На практиці використовуються дві моделі МПА - автомат Милі й автомат Мура, розходження між якими полягає у функції виходу. В автоматі Милі вихідний сигнал залежить від поточного стану і вхідного сигналу, а в автоматі Мура‑ тільки від стану. Незалежно від типу МПА для їхнього синтезу використовується однакова методика, що включає наступні етапи: 1. Оцінка станів автомата на ГСА. 2. Побудова таблиці переходів. 3. Кодування станів УА. 4. Побудова прямої структурної таблиці. 5. Формування системи булевських функцій (СБФ) для вихідних сигналів і функцій збудження елементів пам'яті 6. Синтез схеми в заданому елементному базисі. 2.1 Методика синтезу автомата Мура На першому етапі початкова і кінцева вершини відзначаються окремим станом. Побудова таблиці переходів зводиться, до формувань по відзначеної ГСА таблиці, що містить стовпці: am - вихідний стан; as - стан переходу; X(am , as ) - кон’юнкція вхідних перемінних, визначальний перехід (am , as ) і відповідна функції переходу іj, де Yі відзначений станом am , Y – стан As, Y(am ) - вихідні сигнали; h=1, H - номер переходу. При кодуванні станів необхідно прагнути до такого кодування, що зменшує кількість функцій збудження, що приймають одиничне значення, і, отже, складність схеми УА. Для цих цілей рекомендується використовувати алгоритми кодування. Структурна схема автомата Мура (див. рис. 2.1): 1. Пам'ять – зберігає код стану (Q); 2. Дешифратор (ДС) – виконує перетворення коду в унітарний код, вказує на поточний стан. На базі вектора станів А схема вихідних сигналів (СФВС) формує вихідні сигнали керуючого автомата y. Автомат Мура має свою відмінність - вихідний сигнал y залежить не від вхідного Х, а від стану. Автомат Мура, як і кожний інший автомат складається з двох частин: комбінаційна схема та пам'ять (тригер). Для синтезу автомата Мура потрібно позначити кожну операторну вершину через a[i] , починаючи з “початок” - і закінчуючи “кінець” - , так як це зроблено на рисунку 2.2. Записуємо до таблиці 2.2 отримані результати: поточний стан (мітка вершини та номер її значення в двійковій системі вираховування), наступний стан (мітка вершини та номер її значення в двійковій системі вираховування), вхідний сигнал Х, вихідний сигнал Y та функції збудження пам'яті у заданому тригері (згідно варіанта - у тригері RS). Рис. 2.2 – Граф-схема автомата Мура Табл. 2.1 – Структура переходів для автомата Мура № п/п Поточний стан Наступний стан Вхідний сигнал Х Вихідний сигнал y S входи тригерів R входи тригерів Am код As код 1 a0 000000 a1 000001 1 - S6 2 a1 000001 a2 000010 1 у1 у2 y4 y7 S5 R6 3 a2 000010 a3 000011 1 y3 у8 S6 4 a3 000011 a4 a7 a10 000100 000111 001010 X3 nX3 X4 nX3 nX4 у1 4 у17 у2 1 y40 S4 S4 S3 R5 R6 R6 5 a4 000100 a5 000101 1 y12 у1 8 у20 y41 S6 6 a5 000101 a6 000110 1 y11 y28 y36 S5 R6 7 a6 000110 a14 001110 1 y10 y27 y29 y41 S3 8 a7 000111 a8 001000 1 y13 y16 y35 S3 R4 R5 R6 9 a8 001000 a9 001001 1 y15 y19 y34 S6 10 a9 001001 a14 001110 1 y10 y30 y32 y41 S4 S5 R6 11 a10 001010 a11 001011 1 y11 y16 y35 S6 12 a11 001011 a12 001100 1 y10 y17 y27 y41 S4 R5 R6 13 a12 001100 a13 001101 1 y11 y25 y37 S6 14 a13 001101 a14 001110 1 y10 y20 y27 y41 S5 R6 15 a14 001110 a15 a17 a20 001111 010001 010100 X3 nX3 X4 nX3 nX4 y14 y17 y21 y41 S6 S2 S6 S2 R3 R4 R5 R3 R5 16 a15 001111 a16 010000 1 y15 y19 y37 S2 R3 R4 R5 R6 17 a16 010000 a25 011001 1 y12 y18 y32 y41 S3 S6 18 a17 010001 a18 010010 1 y12 y15 y17 y21 y22 y34 y40 S5 R6 19 a18 010010 a19 010011 1 y12 y30 y32 y41 S6 20 a19 010011 a25 011001 1 y12 y23 y30 y41 S3 R5 21 a20 010100 a21 010101 1 y15 y19 y34 S6 22 a21 010101 a22 010110 1 y14 y18 y32 y41 S5 R6 23 a22 010110 a23 010111 1 y13 y31 y36 S6 24 a23 010111 a24 011000 1 y12 y30 y32 y41 S3 R4 R5 R6 25 a24 011000 a25 011001 1 y13 y28 y39 S6 26 a25 011001 a26 a28 a30 011010 011100 011110 X3 nX3 X4 nX3 nX4 y14 y20 y24 y40 S5 S4 S4 S5 R6 R6 R6 27 a26 011010 a27 011011 1 y15 y31 y34 S6 28 a27 011011 a32 a34 a35 100000 100010 100011 X2 nX2 X1 nX2 nX1 y14 y24 y32 y40 S1 S1 S1 R2 R3 R5 R6 R2 R3 R6 R2 R3 29 a28 011100 a29 011101 1 y9 y14 y18 y19 y20 y35 y41 S6 30 a29 011101 a32 a34 a35 100000 100010 100011 X2 nX2 X1 nX2 nX1 y14 y23 y33 y41 S1 S1 S5 S1 S5 R2 R3 R4 R6 R2 R3 R4 R6 R2 R3 R4 31 a30 011110 a31 011111 1 y14 y17 y24 y41 S6 32 a31 011111 a32 a34 a35 X2 nX2 X1 nX2 nX1 y15 y31 y38 S1 S1 S1 R2 R3 R4 R5 R6 R2 R3 R4 R6 R2 R3 R4 33 a32 100000 a33 100001 1 y11 y25 y34 S6 34 a33 100001 a0 000000 1 y10 y26 y30 y40 R1 R6 35 a34 100010 a0 000000 1 y10 y26 y30 y41 R1 R5 36 a35 100011 a36 100100 1 y11 y31 y35 S4 R5 R6 37 a36 100100 a0 000000 1 y10 y26 y30 y40 R1 R4 2.2 Формування схеми автомата Мура 2.2.1 Функції збудження пам'яті та їх синтез у заданий базис: 2.2.2 Синтез дешифратора та його синтез у заданий базис: Синтез дешифратора для автомата Мура розробляється так само, як і синтез для автомата Мілі(див. далі). 2.2.3 Рівняння вихідних сигналів та їх синтез у заданий базис: 2.3 Методика синтезу автомата Мілі Структурна схема автомата Мілі (зображена на рис. 2.3) включає ті ж етапи, що і синтез КА Мура. Відрізняється від схеми автомата Мура тим, що вихідні сигнали Y залежать від вхідних Х. Порядок синтезу автомата Мілі: 1. Позначаємо вхід початкових та кінцевих станів; 2. Позначаємо вихід операторних вершин у паралельних гілках одним станом (див. рис. 2.4). Кожна операторна вершина відзначається окремим станом. Таблиця переходів автомата має наступні стовпці: am , as - вихідний стан і стан переходу. Х (am,as) - кон’юнкція вхідних перемінних, визначальний перехід (am , as ), Yh - вихідний сигнал на переході (am , as ). Для синтезу логічної схеми в заданому базисі необхідно перетворити СБФ за правилами Де-Моргана з урахуванням обмежень елементного базису - числа входів і навантажувальної здатності. Рис. 2.5 – Граф-схема автомата Мілі Табл. 2.2 – Структура переходів для автомата Мілі № п/п Поточний стан Наступний стан Вхідний сигнал Х Вихідний сигнал y S входи тригерів R входи тригерів Am код As код 1 a0 00000 a1 00001 1 у1 у2 y4 y7 S5 2 a1 00001 a2 00010 1 y3 у8 S4 R5 3 a2 00010 a3 00011 1 у1 4 у17 у2 1 y40 S5 4 a3 00011 a4 a6 a8 00100 00110 01000 X3 nX3 X4 nX3 nX4 y12 у1 8 у20 y41 y13 y16 y35 y11 y16 y35 S3 S3 S2 R4 R5 R5 R4 R5 5 a4 00100 a5 00101 1 y11 y28 y36 S5 6 a5 00101 a11 01011 1 y10 y27 y29 y41 S2 S4 R3 7 a6 00110 a7 00111 1 y15 y19 y34 S5 8 a7 00111 a11 01011 1 y10 y30 y32 y41 S2 R3 9 a8 01000 a9 01001 1 y10 y17 y27 y41 S5 10 a9 01001 a10 01010 1 y11 y25 y37 S4 R5 11 a10 01010 a11 01011 1 y10 y20 y27 y41 S5 12 a11 01011 a12 01100 1 y14 y17 y21 y41 S3 R4 R5 13 a12 01100 a13 a14 a16 01101 01110 10000 X3 nX3 X4 nX3 nX4 y15 y19 y37 y12 y15 y17 y21 y22 y34 y40 y15 y19 y34 S5 S4 S1 R2 R3 14 a13 01101 a20 10100 1 y12 y18 y32 y41 S1 R2 R5 15 a14 01110 a15 01111 1 y12 y30 y32 y41 S5 16 a15 01111 a20 10100 1 y12 y23 y30 y41 S1 R2 R4 R5 17 a16 10000 a17 10001 1 y14 y18 y32 y41 S5 18 a17 10001 a18 10010 1 y13 y31 y36 S4 R5 19 a18 10010 a19 10011 1 y12 y30 y32 y41 S5 20 a19 10011 a20 10100 1 y13 y28 y39 S3 R4 R5 21 a20 10100 a21 10101 1 y14 y20 y24 y40 S5 22 a21 10101 a22 a23 a24 10110 10111 11000 X3 nX3 X4 nX3 nX4 y15 y31 y34 y9 y14 y18 y19 y20 y35 y41 y14 y17 y24 y41 S4 S4 S2 R5 R3 R5 23 a22 10110 a25 11001 1 y14 y24 y32 y40 S2 S5 R3 R4 24 a23 10111 a25 11001 1 y14 y23 y33 y41 S2 R3 R4 25 a24 11000 a25 11001 1 y15 y31 y38 S5 26 a25 11001 a26 a0 a27 11010 00000 11011 X2 nX2 X1 nX2 nX1 y11 y25 y34 y10 y26 y30 y41 y11 y31 y35 S4 S4 R5 R1 R2 R5 27 a26 11010 a0 00000 1 y10 y26 y30 y40 R1 R2 R4 28 a27 11011 a0 00000 1 y10 y26 y30 y40 R1 R2 R4 R5 2. 4 Формування схеми автомата Мілі 2.4.1 Функції збудження пам'яті та їх синтез у заданий базис: 2.4.2 Синтез дешифратора та його синтез у заданий базис. Методика синтезу дешифратора до автомата Мілі: - таблиця істинності (Карта Карно); - Карта Карно для одержання мінімізованої функції збудження; - запис формул функцій збудження; - побудова схеми. Оскільки на кожнім наборі вхідних перемінних активний тільки один біт, то Карту Карно можна зобразити одну загальну для усіх вихідних сигналів. При цьому в осередках Карти Карно записуються не одиниці, а імена відповідних функцій. Табл. 2.3 – Карта Карно до дешифратора автомата Мілі 000 001 011 010 110 111 101 100 00 01 11 10 а0 а1 а3 а2 а6 а7 а5 а4 а8 а9 а11 а10 а14 а15 а13 а12 а24 а25 а27 а26 * * * * а16 а17 а19 а18 а22 а23 а21 а20 ... ... ... Електрична схема дешифратора зображена на рисунку 2.6. Рис. 2.6 – Дешифратор. Функціональна схема. 2.4.3 Рівняння вихідних сигналів та їх синтез у заданий базис: