Рисунок 7.9 – Схема алгоритму функціонування автомата

Рисунок 7.9 – Схема алгоритму функціонування автомата

1.Вибрати індивідуальний варіант алгоритму роботи автомата, для чого записати номер даного варіанту п’ятирозрядним двійковим числом в порядку зменшення ваг розрядів по лівих виходах умовних вершин Х1,Х2, Х3, Х4, Х5 відповідно. Значення правих виходів умовних вершин вибирають інверсними по відношенню до записаних. Нарисувати блок-схему індивідуального варіанту алгоритму, залишивши в ньому обов’язково операційні вершини У6,У7, У10 і У11, а з інших ті операційні вершини, які стоять в гілках “1” умовних вершин.

2. Розробити алгоритм синтезу автомата.

3. Обгрунтувати вибір типу автомата (Мілі чи Мура).

4. Провести структурний синтез автомата.

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

6. Зарисувати функціональну схему керуючого автомата.

В пункті 1 задачі вибирається індивідуальний алгоритм роботи автомата у відповідності до варіанту студента. Для цього записуємо двійковий код варіанта контрольної роботи (в даному випадку це число 30) і ставимо у відповідність його розрядам умовні вершини алгоритму:

Після цього на рисунку ліві гілки умовних вершин позначаємо цифрами відповідних розрядів, а праві – інверсними до них (рис.7.10):

Рисунок 7.10 – Розмітка умовних вершин для вибору індивідуального варіанта
Після цього вилучаємо з схеми алгоритму ті операційні вершини (вони позначені літерами У1 ч У10 в прямокутниках), які стоять в гілках “0” умовних вершин (виключення складають обов’язкові вершини У6, У7, У10, У11, які обов’язково залишаються в схемі алгоритму). Отримуємо для нашого випадку таку схему алгоритму (рис. 7.11):

Рисунок 7.11 – Вихідний алгоритм для синтезу автомата

В пункті 2 розробляємо алгоритм синтезу цифрового автомата (ЦА). Алгоритм синтезу ЦА можна представити у вигляді схеми, зображеної на рис.7.7.
В пункті 3 даємо обгрунтування вибору типу автомата. Як відомо, для кожного автомата Мілі існує еквівалентний автомат Мура і навпаки. Оскільки кількість станів в автоматі Мілі в більшості випадків менша, ніж в автоматі Мура, то при відсутності в даному випадку регламентуючих вимог з точки зору зменшення апаратних затрат вибираємо автомат Мілі.
Пункт 4. Згідно з алгоритмом синтезу цифрового автомата виконаємо формалізований опис ЦА у вигляді орієнтованого графа (рис.7.12). Вершинами графа є стани автомата, а його дуги описують всі можливі переходи із одного стану в інший в послідовності виконання етапів алгоритму роботи автомата. Початок дуги позначається вхідним сигналом, який ініціює перехід з попереднього стану в наступний, а вихід

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

Рисунок 7.12 – Формальний опис ЦА у вигляді орієнтованого графа
На етапі мінімізації ЦА вибирають автомат з мінімальною кількістю станів серед усіх еквівалентних автоматів. Для цього в множині станів знаходять еквівалентні класи і об’єднують їх в нові стани. В нашому випадку в один клас можна об’єднати початковий і кінцевий стани, які ми позначили як один стан q₀.

На етапі розробки схеми станів автомата спочатку визначають кількість елементів памґяті за формулою

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

Таблиця 7.1. Кодування станів автомата

СтанКод стануТ₃Т₂Т₁q₀000q₁001q₂010q₃011q₄100

Якщо виходи тригерів подати на входи дешифратора з виходами, то одиничний сигнал на одному з виходів дешифратора покаже стан автомата. Отже, схема станів автомата має такий вигляд (рис. 5.7):

Рисунок 7.13 – Схема станів розроблюваного автомата

Наступний етап структурного синтезу – розробка таблиці переходів автомата, яку будують відповідно до графа останнього ( див. рис. 5.6). Кількість рядків у таблиці переходів (табл.5.2) дорівнює кількості дуг на графі (кількості різних переходів із стану в стан). Для кожного переходу записують початковий стан, його двійковий код (стани тригерів), стан після переходу та його двійковий код, кон’юнкції вхідних сигналів, що уявляють собою умову переходу (записані на початку дуг орієнтованого графа рис.7.12), а також вихідні (керувальні) сигнали, що виробляються автоматом під час даного переходу (ними позначені кінці дуг графа).
Таблиця 7.2 – Таблиця переходів автомата

Почат-ковий стан ав-

томатаКод стануНаступ-ний стан ав-

томатаКод стануУмова переходуВихі-дні сиг-налиФункції

збудження тригерівТ_3пТ_2пТ_1пТ_3нТ_2нТ_1нD₃D₂D₁q₀000q₁001x₁ 001q₀000q₂010 010q₀000q₄100 100q₁001q₀000 000q₁001q₂010 -010q₂010q₃0111 011q₃011q₀000 000q₃011q₀000 -000q₄100q₀000 000q₄100q₀000 -000

В останній колонці табл. 7.2 наведено значення функцій збудження (функцій переходів) входів тригерів D₁, D₂, D₃, які потрібно подати на D-входи відповідних тригерів, щоб спричинити заданий перехід. З закону функціонування D-тригерів зрозуміло, що їх значення відповідають значенням виходів тригерів після переходу, тобто D₃= Т_3н, D₂= Т_2н, D₁= Т_1н. Для тригерів інших типів значення функцій збудження одержують за таблицями переходу даних тригерів.

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

, (7.2)

.

,

,

,

, (7.3)

,

,

.

Набір функцій (7.2) використовується для побудови логічної схеми переходів автомата, а (7.3) – схеми виходів автомата.

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

1. 
   Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 232 с.
   
2. 
   Биков М.М. та ін. Операційні пристрої обчислювальних машин та систем. - Київ: НМК ВО, 1991. - 200 с.
   
3. 
   Биков М.М., Міщенко С.М., Янчук Л.Н. Обчислювальні машини та інформаційні системи. Лабораторний практикум – Вінниця, ВДТУ, 2001. – 61 с.
   
4. 
   Биков М.М. Основи теорії цифрових автоматів. Електронний варіант. – Вінниця: ВНТУ, 2007. – 256 с.
   
5. 
   Каган Б.М. Электронные вычислительные машины и системы. -
   М.:Энергомашиздат, 1991. - 591 с.
   
6. 
   Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.
   
7. 
   Пєтух А.М., Войтко В.В. Прикладна теорія цифрових автоматів. – Вінниця: ВДТУ, 2003. – 67 с.
   
8. 
   Савельев А.Я. Прикладная теория цифровых автоматов. – М.: Высшая школа, 1987. – 271 с.
   
9. 
   Самофалов К.Г., Романкевич А.М.и др. Прикладная теория цифровых автоматов. - К.: Вища шк., 1987. -224 с.
   

• Додаткова

1. 
   Бабич М.П., Жуков І.А. Компґютерна схемотехніка. – Київ: МК-Пресс, 2004. – 478 с.
   
2. 
   Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. – 392 с.
   
3. 
   Коштоев В.В., Кипиани К.К. Основы прикладной теории цифровых автоматов. – Тбилиси, 1998. – 155 с.
   
4. 
   Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. – М.: Наука, 1985. – 320 с.
   
5. 
   Лихтциндер Б.Я., Кузнецов В.Н. МП и вычислительные устройства в радиотехнике. - К.: Вища школа, 1988. – 272 с.