МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНІЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ „ХПІ"
Кафедра „Обчислювальна техніка та програмування”
Синтезмікропрограмних автоматів
Альбом документів курсового проекту по дисципліні
«Спеціалізовані комп’ютерні системи»
КІТ32.02198.022 ДКП
Керівник проекту:
___________
Виконав:
студент групи
____________________
„ __”___________________ 2007 р.
Харків
Зміст
Вступ
1. Технічне завдання
1.1 Синтезувати мікропрограмний автомат за схемоюУілкса-Стрінжера у вигляді автомата Мілі
1.2 Синтезувати мікропрограмний автомат за схемою Уілкса-Стрінжера у вигляді автомата Мура
2. Базові теоретичні дані
2.1 Основні дані про автомати
2.2 Класифікація атоматів
3. Методика вирішення
3.1 Синтез мікропрограмного автомата за схемоюУілкса-Стрінжера у вигляді автомата Мілі
3.1.1 Змістовна схема алгоритму
3.1.2 Змістовна таблиця кодування операційних та умовнихверхівок
3.1.3 Закодована мікроопераційна схема алгоритму
3.1.4 Таблицякодування мікрокоманд
3.1.5 Закодована мікрокомандна схема алгоритма
3.1.6 Основна таблиця автомата (СІ — синхроімпульс)
3.1.7 Граф-схема переходів
3.1.8 Система рівнянь переходів
3.1 9. Системарівнянь виходів
3.1.10 Кодування внутрішніх станів автомата
3.1.11 Побудова схеми операційного автомата
3.1.12 Схемаопераційного автомата
3.2 Синтез мікропрограмного автомата за схемоюУілкса-Стрінжера у вигляді автомата Мура
3.2.1 Змістовна схема алгоритму
3.2.2 Змістовна таблиця кодування операційних та умовнихверхівок
3.2.3 Закодована мікроопераційна схема алгоритма
3.2.4 Таблиця кодування мікрокоманд
3.2.5 Закодована мікрокомандна схема алгоритма
3.2.6 Основна таблиця автомата (СІ — синхроимпульс)
3.2.7 Граф-схема переходів
3.2.8 Система рівнянь переходів
3.2.9 Кодуваннявнутрішніх станів автомата
3.2.10 Побудова схеми операційного автомата
3.2.11 Схемаопераційного автомата
Висновки
Список літератури
Вступ
Поряд з теорією формальних мов і заснованих наній методів побудови компіляторів кінцеві автомати активно використовуються вкомп'ютерних іграх, у реалізації мережних протоколів, системах стискуінформації. Іншими словами, там, де потрібна велика надійність і де логікаповодження надто складна, щоб програміст зміг реалізувати її на одному лишерівні здорового глузду.
З появою структурного програмування сталоочевидним, що з трьох головних конструкторів керування: проходження, циклу ірозгалуження останній є найважчим у сприйнятті програміста, оскільки прибезлічі альтернатив перетворює лінеаризовану структуру алгоритму вдеревоподібну. При цьому складність навіть послідовних програм росте стрімко ічасом може перевершувати дерево варіантів у настільки непростий дляавтоматичного аналізу моделі, як традиційні шахи. Розбивка програми на процесий об'єкти з заміною багатоступінчастого розгалуження засобами обробкиповідомлень (подій) заміняє одну проблему на іншу: вкладеність зменшується,зате кількість взаємодіючих компонентів помітно зростає. Логіка «розмивається»і в підсумку ми одержуємо погано контрольовану ситуацію, коли через хаотичність«ручного» синтезу і неможливості побудувати вичерпний набір тестівнемає ніякої впевненості в коректності побудованої системи. Ключ до рішенняскладається в застосуванні формальних методів, у створенні зручної абстракції,здатної «вичавити» з алгоритму квінтесенцію логіки його роботи і датиможливість проводити весь необхідний аналіз. Однією з таких зручних абстракційможуть служити кінцеві автомати, серед різновидів яких варто виділити автоматиМілі і Мура. Близькість до булевої алгебри і теорії графів, наочністьграфічного представлення і детермінованість поводження є помітнимидостоїнствами цієї абстракції.
1. Технічне завдання1.1 Синтезувати мікропрограмнийавтомат за схемою Уілкса-Стрінжера у вигляді автомата Мілі
Побудувати операційний автомат, що обчислюєкількість парних елементів у двох одномірних масивах (A [n], B [m]).
Мікропроцесорний автомат необхідно реалізуватиза схемою Уілкса-Стрінжера у вигляді автомата Мілі.
Оптимальну функціональну схему керуючих частинавтомата синтезувати на елементах системи І, АБО, НЕ, RS-, D — тригерах,доповнюючи її необхідними по алгоритму функціональними автоматами.
1.2 Синтезувати мікропрограмнийавтомат за схемою Уілкса-Стрінжера у вигляді автомата Мура
Побудувати операційний автомат, який знаходитьмаксимальний парний елемент в кожному рядку масива (A [n,n]).
Мікропрограмний автомат необхідно реалізуватиза схемою Уілкса-Стрінжера у вигляді автомата Мура.
Оптимальну функціональну схему керуючих частинавтомата синтезувати на елементах І, НЕ, RS-, D — тригерах.
2. Базові теоретичні дані2.1 Основні дані про автомати
Автомат — модель пристрою з кінцевою пам'яттю,призначена для обробки інформації.
В абстрактному змісті автомат — зовсім нечорний ящик, що переробляє послідовність вхідних дискретних сигналів упослідовність вихідних сигналів. У загальному випадку, автомат представляєтьсясхемою, основними частинами якої є логічний перетворювач і пам’ять. Логічнийперетворювач складається з логічних елементів, з'єднаних один з одним унеобхідну схему. У правильно спроектованому автоматі логічні елементи і весьлогічний перетворювач можуть вважатися безінерційними, притаманні елементамзапізнювання в зміні сигналів використовуються для створення пам’яті. Вавтоматі виділяються чотири види сигналів: вхідні, вихідні, проміжні і синхронізуючі.Якщо число вхідних і вихідних сигналів кінцеве, то схема представляє кінцевийавтомат.
Кінцевий автомат — це схема, що має обмеженийнабір станів. Роль кінцевих автоматів складається в тому, що будь-яка система (наприклад,програма), що володіє обмеженим набором можливостей, що можуть бути позначеніокремими станами (чи навіть їх комбінаціями), може бути представлена кінцевимавтоматом. Кінцеві автомати природні для програми керування (операційних систем)на комп'ютері та для трансляторів. Кінцевий автомат є моделлю, яка широковикористовується при створенні різних пристроїв обробки інформації.
2.2 Класифікація атоматів
Розрізняють два класи кінцевих автоматів. Синхроннийавтомат характеризується тим, що генератор тактових імпульсів синхронізаціївпливає через вхід S на автомат, поділяючи час на такти. Інтервали часу міжтактовими імпульсами повинні бути більше будь-якої затримки. Вихідні сигнали всинхронному автоматі зчитуються тільки під час видачі цих імпульсів, коли підвпливом вхідних і проміжних сигналів автомат перейшов вже в новий стан. Васинхронному автоматі вихідні сигнали зчитуються в будь-який час, а перехід уновий стан визначається лише часом спрацьовування всіх логічних елементів, щовходять у логічний перетворювач. На вхід S не подається ніякий сигнал (цей вхідвідсутній).
Пристрої, які створені на основі асинхронногоавтомата, характеризуються високою швидкодією. Однак, синхронні автоматирозробляються в більш короткий термін, легко налагоджуються і модифікуються. Синхронніавтомати легко стикуються з комп'ютерами, що також є синхронними пристроями.
Кінцеві автомати створюються на базіІнтегральних Схем (ІС). Особливо зручна їх реалізація на основі програмувальнихлогічних матриць (ПЛМ). Часто логічний перетворювач виконується у виді однієїінтегральної схеми.
3. Методика вирішення
3.1 Синтез мікропрограмного автоматаза схемою Уілкса-Стрінжера у вигляді автомата Мілі
Побудувати операційний автомат, що обчислюєкількість парних елементів у двох одномірних масивах (A [n], B [m]).
Мікропроцесорний автомат необхідно реалізуватиза схемою Уілкса-Стрінжера у вигляді автомата Мілі.
Оптимальну функціональну схему керуючих частинавтомата синтезувати на елементах системи І, АБО, НЕ, RS-, D — тригерах,доповнюючи її необхідними по алгоритму функціональними автоматами.3.1.1 Змістовна схема алгоритму
До складу змістовної схеми алгоритму (Рис.1)входять операційні та умовні верхівки. Наш алгоритм виконує знаходженнякількості парних елементів у двох одномірних масивах розмірністю [n] та [m],використовуючи при цьому чотири (4) умовні верхівки і десять (10) операційнихверхівок. Позначення операційних верхівок показано на Рис.2. Позначенняумовних верхівок на Рис.3. Перевірка елементів масивів виконується відстовпчика до стовпчика.
/> />
/>/>/>3.1.2 Змістовнатаблиця кодування операційних та умовних верхівок
Кожна верхівка, чи то операційна чи умовна,кодується. При чому, якщо, мікро операції повторюються і умовні верхівкиповторюються, вони кодуються однаково. У даному прикладі мікроопераціїповторюються двічі, тому, однакові верхівки ми можемо кодувати одним кодом. Таблицякодування верхівок зображена у Таблиці1.
Таблиця1Код Зміст Примітка
mY1 i = 1
mY2 kol = 0
mY3 A [i] Ввід А [і]
mY4 kol = kol + 1
mY5 i = i + 1
mY6 B [i]
mY7 kol Вивід kol
X1 A [i] mod 2 = 0 так — 1, ні — 0
X2 i £ n так — 1, ні — 0
X3 B [i] mod 2 = 0 так — 1, ні — 0
X4 i ≤ m так — 1, ні — 0 3.1.3 Закодована мікроопераційнасхема алгоритму
Закодована мікроопераційна схема алгоритмубудується на основі змістовної схеми алгоритму (Рис.1) і таблицікодування операційних та умовних верхівок (Таблиця 1), шляхом замінивідповідних блоків. Схема алгоритму зображена на Рис.4.
/> />
/>3.1.4Таблиця кодування мікрокоманд
Складаємо таблицю кодування мікрокоманд. Кожнамікрооперація кодується своєю мікрокомандою. Мікрооперації, які виконуютьсяодна за одною послідовно на протязі одного такту часу, поєднуються до однієїмікрокоманди. У даному прикладі дві мікрооперації (mY1, mY2)виконуються одна за одною послідовно. Тому ми поєднуємо їх в одну мікрокоманду.Таблиця кодування зображена в Таблиці 2.
Таблиця 2Мікрокоманда Мікрооперація
Y1
mY1, mY2
Y2
mY3
Y3
mY4
Y4
mY5
Y5
mY1
Y6
mY6
Y7
mY7 3.1.5 Закодована мікрокомандна схемаалгоритма
Складаємо закодовану мікрокомандну схемуалгоритму (Рис.5). Проставляємо мітки внутрішніх станів автомата Мілітаким чином:
мітки ставляться після кожної мікрокоманди (передблоком після операційного);
початок та кінець мікрокомандної схемиалгоритму відмічається міткою а0;
мітки проставляються згідно з порядковимномером;
/> />
/>3.1.6 Основна таблиця автомата (СІ — синхроімпульс)
Будуємо основну таблицю автомата (Таблиця 3).Ця таблиця складається на основі закодованої мікрокомандної схеми алгоритму(Рис.5) В першому стовпчику таблиці записуються усі стани, в яких можезнаходитися наш автомат. В першому рядку таблиці записуються способи переходуавтомата з одного стану в інший (вхідні сигнали), тобто, чи то буде СІ (тойперехід, в процесі якого на шляху не зустрілась жодна верхівка), чи то припереході автомату буде поставлена умова. В клітинках таблиці фіксується,перехід до якого стану здійснюється, і що буде на виході. Наприклад, із стану а0автомат може здійснити перехід до стану а1 і в результаті цьогопереходу на виході автомата буде Y1, тобто, автомат виконає тімікрооперації, які виконуються на протязі одного такту часу (mY1 іmY2 закодовані мікрокомандою Y1), при чому, цей перехідстанеться під синхроімпульсним сигналом.
Таблиця 3 СІ=1
X1
/>
X2
/>
X3
/>
X4
/>
a0
a1/Y1
a1
a2/Y2
a2
a3/Y3
a3/__
a3
a4/Y4
a4
a1/__
a5/Y5
a5
a6/Y6
a6
a7/Y3
a7/__
a7
a8/Y4
a8
a5/__
a0/Y7 3.1.7 Граф-схема переходів
Будуємо граф-схему переходів (Рис.7). Граф-схемабудується на основі Рис.5. і Таблиці 3. Кружочками позначаютьсяможливі стани автомата. Стрілки указують на перехід із стану i до стану j. Надстрілкою указується, під яким вхідним сигналом станеться перехід, і, що прицьому буде на виході автомата.
/>
3.1.8 Система рівнянь переходів
Складаємо систему рівнянь переходів. Цясистема складається на основі граф-схеми переходів (Рис.7) або основноїтаблиці абстрактного автомата (Таблиця 3). Сигнал СІ опущений.
/>
3.1 9.Система рівнянь виходів
Складаємо систему рівнянь виходів. Ця системаскладається на основі закодованої мікрокомандної схеми алгоритму (Рис.5),де Х — вхід,
Y — вихід.
/>3.1.10 Кодування внутрішніх станівавтомата
Для того, щоб закодувати внутрішні станиавтомата, визначаємо кількість необхідних для цього тригерів (n). Кількістьтригерів розраховується із співвідношення: log2 A ≤ n, де
n — кількість необхідних тригерів;
А — кількість станів аi (a0 — a8)
А = 9log2 9 ≤ nÞn = 4, Намнеобхідні 4 тригери, значить внутрішні стани автомата будемо кодуватичотирьох-розрядним двійковим кодом. Процес кодування зображений у Таблиці 4.
Таблиця 4
S1
S2
S3
S4
a0
a1 1
a2 1
a3 1 1
a4 1
a5 1 1
a6 1 1
a7 1 1 1
a8 1 3.1.11 Побудова схеми операційногоавтомата
Операційний автомат складається з п’яти (5) частин(Рис.5).
У вхідній частині розташовані чотири (4)RS-тригери, чотири (4) логічних елементи АБО, на які подається вхідний сигнал,декодер та дві шини, одна з яких необхідна для передачі сигналів, які надходятьз декодера, а інша — для сигналів з виходів компаратора.
У перехідній частині автоматавиконується перетворення сигнала на протязі одного такту часу. Пройшовши черезлогічні елементи І та (або) АБО, чи того не роблячи, сигнал змінюється ірезультат надходить на шину (at), відкіля продовжує передаватися допрограмованої логічної матриці (ПЛМ). Перехідна частина будується на основісистеми рівнянь переходів.
Вихідна частина. Цячастина будується на основі системи рівнянь виходів. Тут виконується той самийпроцес, що й у перехідній частині, тільки сигнали подаються на вихідну шину Yt,з якої сигнал надходить до вихідної матриці.