shpora2010oct17_2011

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Кафедра ЕОМ

ПРИКЛАДИ ВИКОРИСТАННЯ ТЕОРІЇ ЦИФРОВИХ АВТОМАТІВ ТА КОМП’ЮТЕРНОЇ ЛОГІКИ.

ПОСЛІДОВНІСНІ СХЕМИ

Методичні вказівки до практичних занять

з дисципліни «Прикладна теорія цифрових автоматів» та «Комп’ютерна логіка»

для студентів базового напрямку 6.050102 «Комп’ютерна інженерія»

Затверджено на засідання кафедри

«Електронні обчислювальні машини». Протокол № 1 від 31.08.2010 р.

Львів – 2010

1

Методичні вказівки «Приклади використання теорії цифрових автоматів та комп’ютерної логіки. Послідовнісні схеми» до практичних занять з дисциплін

«Прикладна теорія цифрових автоматів» та «Комп’ютерна логіка» для студентів бакалаврату 6.050102 «Комп'ютерна інженерія» /Укл. В.С.Глухов. Львів: НУ"ЛП", 2010. - 110 с.

Укладач В.С.Глухов, к.т.н.

Рецензенти: В.А.Голембо, к.т.н.,

Р.Б.Дунець, д.т.н.

2

Вступ Даний набір прикладів призначений для використання на практичних

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

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

білетів вступних іспитів для навчання в магістратурі для спеціальностей

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

Варіанти завдань утворюються зміною чисел, які зустрічаються у формулюванні питань.

Усі приклади містять лише один з великої кількості інших варіантів відповіді.

Для підготовки методичних вказівок використовувалися засоби студентської версії пакету Active-HDL version 7.2.1644 Student Edition, яка доступна для вільного завантаження за адресою:

http://www.aldec.com/Products/Evaluation.aspx?productevaluationid=da3b4fe8- 427d-4945-919d-53bd8eef6d27

Використання пакету Active-HDL наклало деякі обмеження на зображення функціональних схем та позначення елементів та сигналів на цих схемах:

позиційне позначення цифрових елементів на схемах складається з двох літер

DD з наступним порядковим номером елемента на схемі;

інверсія позначається маленькою літерою n перед назвою сигнала (x = nx);

усі елементи одного типу мають однакові схемотехнічні символи;

індекси в назвах сигналів пишуться таким же шрифтом як і назви сигналів;

позначення вхідних та вихідних сигналів відповідають правилам мови VHDL; 3

позначення вхідних та вихідних контактів на схемах не відповідають вимогам ЄСКД.

Можливі також інші відхилення від позначень, які визначаються Державними стандартами України.

Наведені у прикладах VHDL-описи у своїй більшості автоматично згенеровані засобами пакету Active-HDL із графів та за допомогою вбудованого в пакет Active-HDL генератора ядер IP Core Generator.

Основу прикладів складають прості автомати (1 вхідний сигнал, 1 вихідний сигнал, 4 внутришніх стани).

У прикладах більша увага приділена D-тригерам, що спрацьовують по фронту. Дані тригери найбільш часто використовуються як елементи пам’яті цифрових автоматів. Тільки для них (а також для найпростіших RS-тригерів)

наведена схема електрична функціональна на елементах монобазиса І-НЕ. Для інших тригерів такі схеми не наведені, але вони відомі.

Основна увага приділена реалізації комбінаційних частин автоматів на елементах базиса Буля (І, АБО, НЕ). Для автоматів Мура наведена реалізація комбінаційних частин на елементах монобазису І-НЕ. Також наведена реалізація автоматів Мілі та Мура у вигляді мікропрограмних автоматів (коли комбінаційна частина реалізується на ПЗП). Наведені приклади реалізації комбінаціних схем на дешифраторах і мультиплексорах. Також наведений синтез більш складного автомата Мура із збільшеною кількістю входів (2), виходів (3) та внутришніх станів

(6) як автомата на жорсткій логіці (на елементах базиса Буля) так і як мікропрограмного автомата (на ПЗП).

Вважається, що користуючись даними методичними вказівками, студенти зможуть синтезувати довільні автомати Мура та Мілі на будь-якій елементіній базі комбінаційної частини (базис Буля, монобазис І-НЕ, монобазис АБО-НЕ,

мультиплексори, дешифратори, ПЗП) і пам’яті (D-тригери, T-тригери, JK-тригери).

У Примітки до відповідей винесені додаткові відомості, які необов’язково можуть бути присутні у відповідях студентів.

4

Зауваження та пропозиції надсилати на адресу glukhov@polynet.lviv.ua і

вказувати тему листа: «Приклади використання теорії цифрових автоматів та комп’ютерної логіки».

5

1 Загальні відомості про цифрові схеми

1.1 Транзисторні схеми елементів монобазисів Будь-яка цифрова схема може бути представлення у вигляді структури, що

складається з елементів монобазисів І-НЕ та АБО-НЕ. Вирази, які записані у базисі Буля, можуть бути записані у одному з монобазисів. Схеми, які складаються з елементів базису Буля, можуть бути трансформовані у схеми з елементів монобазисів.

Елементи монобазисів найчастіше реалізуються на транзисторах за КМОН-

технологією (на КМОН-транзисторах). Цифровий скінчений автомат дозволяє реалізувати будь-який алгоритм. Тобто, для рішення якоїсь задачі, для якої відомий алгоритм рішення, необхідно мати якусь кількість КМОН-транзисторів.

Рис. 1.1 Схемотехнічний символ, схема елемента 2АБО-НЕ за КМОН-технологією та його таблиця істинності

Рис. 1.2 Схемотехнічний символ, схема елемента 2І-НЕ за КМОН-технологією та його таблиця істинності

6

Для елементів монобазисів І-НЕ та АБО-НЕ існує залежність між кількість транзисторів NТр та кількістю входів NВх у елемента монобазиса: кількість транзисторів удвічі більша за кількість входів: NТр 2NВх .

1.2 Загальні відомості про цифрові автомати

Рис. 1.3 Загальна структурна схема цифрового автомата

Рис. 1.4 Структурна схема автомата Мура

Рис. 1.5 Структурна схема автомата Мілі

7

1.3 Рекомендована послідовність синтезу цифрових автоматів

1.3.1. Синтез абстрактного автомата

1.3.1.1Синтез алгоритма роботи автомата.

1.3.1.2Вибір структури автомата (Мура або Мілі).

1.3.1.3Фіксація алгоритма у вигляді графа.

1.3.2. Синтез структурного автомата

1.3.2.1Вибір елементної бази комбінаційної частини.

1.3.2.2Вибір елементної бази пам’яті автомата.

1.3.2.3Вибір способу кодування вхідних та вихідних сигналів.

1.3.2.4Вибір способу кодування внутришніх станів автомата.

1.3.2.5Створення таблиці переходів автомата.

1.3.2.6Створення таблиці виходів автомата.

1.3.2.7Мінімізація формул для сигналів збудження тригерів автомата.

Фіксація результатів у вигляді диз’юнктивної нормальної форми (ДНФ).

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

1.3.2.8 Мінімізація формул для виходів автомата. Фіксація результатів у вигляді диз’юнктивної нормальної форми (ДНФ).

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

1.3.3.Синтез пам’яті автомата.

1.3.4.Синтез комбінаційної частини автомата.

8

2 Тригери – елементи пам’яті цифрових автоматів

2.1 RS-тригер

Намалювати символ, таблицю істинності та схему RS-тригера і часову діаграму зміни станів його прямого та інверсного виходів, якщо на протязі 8 тактів роботи на його входи подається послідовність сигналів, яка представлена 16-ковими числами: 10 на вході R, та 91 на вході S. Послідовність починається з старших розрядів двійкового коду, які на протязі такту не змінюються. Початковий стан тригера 0.

Відповідь:

1016 = 0001 00002;

9116 = 1001 00012;

02 – низький рівень на часовій діаграмі;

12 – високий рівень на часовій діаграмі.

Таблиця 2.1 - Таблиця істинності RS-тригера

Рис. 2.6 Схемотехнічний символ RS-тригера

9

Рис. 2.7 Функціональна схема RS-тригера

Рис. 2.8 Часова діаграма роботи RS-тригера

2.2 RS -тригер

Намалювати символ, таблицю істинності та схему RS -тригера і часову діаграму зміни станів його прямого та інверсного виходів, якщо на протязі 8 тактів роботи на його входи подається послідовність сигналів, яка представлена 16-ковими

числами: 48 на вході R , та 89 на вході S . Послідовність починається з старших розрядів двійкового коду, які на протязі такту не змінюються. Початковий стан тригера 0.

Відповідь:

4816 = 0100 10002;

9116 = 1001 00012;

02 – низький рівень на часовій діаграмі;

12 – високий рівень на часовій діаграмі.

Таблиця 2.2 - Таблиця істинності RS -тригера