Етап 1. Завдання закону функціонування асинхронного автомата

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

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

Приклад. Необхідно синтезувати автомат (цифровий пристрій), що пропускає імпульси прямокутної форми х₀ якщо немає заборони (х₁ = 0), і не пропускає, якщо заборона існує (х₁ = 1). При цьому імпульси х₀ не повинні спотворюватись незалежно від моменту появи сигналу заборони х₁.

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

Рисунок 2.3 -Діаграми для вхідних і вихідних сигналів

На основі аналізу зміни вхідних і вихідних сигналів можна вводити ста­ни автомата, які характеризуються станом входу (сигналами х₀ та х₁ з вхідно­го алфавіту X) і станом виходу Y (сигналом у).

Різноманітним комбінаціям вхідних та вихідних сигналів припишемо відповідні номери, які характеризують всі можливі стани автомата. За по­чатковий оберемо стан Q₀₀ = 0, який характеризується значеннями вхідних сигналів х₁х₀ = 00 і значенням вихідного сигналу y= 0. СтанQ₀₀ = 0 є стійким, тобто таким, який не зміниться без дії вхідних сигналів. У таблиці ПТП (табл. 2.1), що будується, стійкі стани будемо виділяти дужками. Нестійкі стани автомата - це такі, які можуть змінюватися на стійкі без зміни вхідних сигналів. Такі стани в ПТП будемо позначати їх номерами без дужок.

Якщо на автомат, що перебуває у стійкому стані Q₀₀, діятиме вхідний сигнал х₁х₀ = 01, то він перейде в новий, спочатку нестійкий стан, який потім перейде у стійкий Q₁ = (1). Нестійкий стан відповідає ситуації, коли в ре­зультаті зміни вхідного сигналу X змінились сигнали збудження тригерів, але ще не змінився вихідний сигнал, тобто у залишився рівним нулю. По закінченні перехідних процесів автомат перейде у стійкий стан Q₁ = (1), який характеризується вхідними сигналами х₁х₀ = 011 вихідним у = 1.

Переходу зі стійкого стану (0) в нестійкий 1 у ПТП відповідає переміщення в межах першого рядка з клітинки з координатами х₁х₀ = 00 у клітинку з координатами х₁х₀= 01. Вихідний сигнал при цьому залишається незмінним: y = 0.

Переходу з нестійкого стану 1 у стійкий стан (1) в ПТП відповідає переміщення в межах од­ного стовпця з координатами х₁х₀ = 01 з першо­го рядка до другого. Вихідний сигнал при цьому змінюється і набуває значення y = 1 (табл. 2.1).

Звідси маємо, що перехід з одного стійкого стану (0) в інший стійкий стан (1) відповідає двом фрагментам переходу: спочатку у межах рядка, а потім у межах стовпця.

З часової діаграми, наведеної на рис. 2.3, видно, що стійкий стан (1) за умови х₁х₀ = 00 змінюється на стан (0), а потім під дією сигналу х₁х₀ = 10 переходить у стан (2), і т.д.

Номери станів на часовій діаграмі зображають так, щоб кожна змінюва­на ситуація в сигналах X, Y мала свій номер і щоб були враховані всі зов­нішньо однакові ситуації, які вимагають спеціального запам'ятовування. Наприклад, якщо автомат реагує на третій імпульс, то кожен з трьох імпульсів і кожну з двох пауз необхідно позначити своїм номером. Аналіз всієї часової діаграми дозволяє заповнити ПТП (див. табл. 2.2), але не повністю - частина кліти­нок залишається вільною. Наприклад, у першому рядку ПТП залишилась незаповненою клітинка з X = 11. Оскільки стан Q = 0 є стійким при X = 00, то перехід в новий стан, що відповідає X = 11, вимагає одночасної зміни обох вхідних сигналів х₁ і х₀, що практично неможливо.

Таблиця 2.1- Початкова таблиця переходів ПТП

X Q	x1x0	y
	(0)
		(1)

Таблиця 2.2- Таблиця переходів

X Q	x1x0	y
	(0)		-
		(1)		-
		-		(2)
	-		(3)
	-	-	(4)
		(5)	-	-

Оскільки перехід 00 ® 11 виконати не­можливо, в ПТП в відповідній клітині проставляється риска, яка інформує про наявність невизначеного стану. Аналогічно виключаються інші перехо­ди типу 00 «11, а також 01 «10.

Етап 2. Мінімізація кількості внутрішніх станів автомата.

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

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

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

Скорочення частини станів асинхронного автомата базується на виявленні еквівалентних і псевдоеквівалентних станів, а та­кож на виявленні та об'єднанні сумісних внутрішніх станів авто­мата (рядків ПТП).

Приклад. Автомат заданий ПТП, що наведена в табл. 2.3. Визначити екві­валентні та псевдоеквівалентні стани і скоротити кількість рядків ПТП.

Розв'язання. Відповідно до першої умови, еквівалентними можуть бути лише ті стани, які перебувають в одному і тому ж стовпчику таблиці, тобто стани (3) і (6); (1) і (4); (2) і (5); (2) і (7); (5) і (7).

З отриманих пар необхідно обрати стани, що відповідають другій умові, тобто такі, яким відповідає один і той же стан виходу. Наприклад, стан (5) має значення виходу, протилежне значен­ням виходів станів (2) і (7). Тому можемо стверджувати, що стани (2) і (5), а також (5) і (7) не с еквівалентними. З пар станів, що залишилися - (3) і (6); (1) і (4); (2) і (7), - еквівалентними будуть ті стани, які відповідають ще й третій умові.

Для того, щоб два стійкі стани задовольняли третю умову еквівалент­ності, в однакових стовпцях таблиці переходів у рядках, що відповідають цим станам, повинні перебувати одні і ті ж цифри або різні цифри, але які визначають еквівалентні стани. У прикладі, який розглядаємо, еквівалент­ними будуть стійкі стани (2) і (7); (1) і (4); (3) і (6).

Після того, як еквівалентні стани виявлені, їх об'єднують. При цьому кожній групі еквівалентних станів приписують один номер, а всі рядки, в які входять еквівалентні стани однієї групи, замінюються одним рядком. У розглянуто­му прикладі стійкий стан (7) замінюється на (2); (6) - на (3); (4) - на (1). Так само перену­меровуються і нестійкі стани 7,6 та 4 відпов­ідно на 2, 3, 1.

Таблиця 2.3 – Задана таблиця переходів автомата

X Q	x1x0	y
	(0)
			(1)
				(2)
		(3)
			(4)
				(5)
		(6)
				(7)

Таблиця 2.4 – Таблиця переходів зі скоро­ченою кількістю станів

X Q	x1x0	y
	(0)
			(1)
				(2)
		(3)
				(4)

У результаті отримуємо таблицю зі скоро­ченою кількістю станів (табл. 2.4).

Для збігання номерів стійких станів з номерами рядків у табл. необ­хідно стани 5 і (5) перенумерувати на 4 і (4).

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

Псевдоеквівалентними називаються такі два стійкі стани авто­мата, яким:

- відповідає один і той самий стан входу автомата;

- відповідають стани виходів автомата, між якими немає суперечності;

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

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

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

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

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

Об'єднання рядків з поєднаними стійкими станами виконують на основі таких правил:

- два або більше рядків можуть бути об'єднані, якщо значен­ня вихідних змінних (станів виходу) для цих рядків збігаються для автомата Мура і можуть бути будь-якими для автомата Мілі, а номери станів, що записані в одних і тих же стовпцях, збігаються між собою або з рискою;

- в разі об'єднання станів з однаковими номерами в дужках і без них результуючий стан повинен бути у дужках (стійким);

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

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

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

Як приклад розглянемо процедуру отримання скороченої (мінімальної) таблиці переходів з ПТП, що отримана для генера­тора із забороною (див. табл. 2.2). Аналіз цієї ПТП свідчить, що в ній відсутні еквівалентні і псевдоеквівалентні стани. Сумісни­ми будуть такі множини станів: {(0), (2)}; {(1), (4)}; {(2), (5)}; {(2),(3), (5)} за Муром (показано суц­ільними лініями). Крім того, суміс­ними, за Мілі, будуть стани (1)-(0), та (4)-(0) (зображено пунктирними лініями). Загальна діаграма суміс­ності зображена у вигляді ненапрямлених ліній на рис. 2.4.

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

Аналіз діаграми сумісності свідчить, що є можливість виділи­ти дві групи множин сумісності:

1. {(0), (2)}; {(1), (4)}; {(3), (5)};

2. {(0)}; {(1), (4)}; {(2), (3), (5)}.

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

Скорочена таблиця переходів, яка побудова­на на основі першого варіанта об'єднання ста­нів, наведена у табл. 2.27.

Рисунок 2.4 - Загальна діаграма суміс­ності

Таблиця 2.5 - Скорочена таблиця переходів

X Q	x1x0	y
(0, 2)	(0)			(0)
(1, 4)		(1)	(1)
(3, 5)		(2)	(2)

Об'єднання рядків варто виконувати у де­кілька етапів. Спочат­ку об'єднувані рядки зводять в один, з мен­шим номером, і всі ста­ни, що мають більші номери, замінюють меншими. Так, під час об'єднання рядків 0 і 2 двійки другого стовпця замінюють на нулі. Якщо в одному з об'єднуваних рядків маємо невизначений стан, то після об'єднання він замінюється визначеним (стовпець за умови х₁х₀ = 10 має невизначений стан у другому рядку). Після об'єднан­ня сумісних рядків виконується їх перейменування (у цьому при­кладі 3-й рядок замінюється на рядок з номером 2), а потім пере­нумеровуються всі відповідні стани новими цифрами (трійки за­мінюються на двійки).

Етап 3. Кодування станів автомата.

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

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

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

На рис. 2.5 зображені два графи, які не задовольняють вка­зані вимоги і не можуть бути закодовані сусідніми кодами.

Рисунок 2.5 – Приклади графів

Граф переходів для генератора із забороною (табл. 2.2) зоб­ражено на рис. 2.6. У розглянутому випадку граф має непарну кількість вершин, але контур незамкнений. Один з варіантів ко­дування станів приводить до табл. 2.6.

Рисунок 2.6 - Граф переходів для генератора із забороною

Таблиця 2.6 – Таблиця переходів

Стани	Код
q1	q0
Q0
Q1
Q2

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

Таблиця 2.7 - Таблиця переходів

X Q	x1x0	y
q1	q0

Етап 4. Визначення функцій збудження елементів пам’яті і функцій виходів автомата.

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

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

Таблицю переходів і RS-тригера наведено у табл. 1.36.

Визначимо функції збудження RS- тригерів. Для цього скористаємось закодованою таблицею переходів авто­мата (табл. 2.7), в якій замість пере­ходів Q_n ®Q_n+l підставимо значення сигналів збудження відповідних вхо­дів тригерів. Тоді вона набуде вигля­ду, зображеного у табл. 2.8.

Таблиця 2.8 – Таблиця переходів авто­мата

X Qn

x1x0

q1

q2

R1

S1

R0

S0

R1

S1

R0

S0

R1

S1

R0

S0

R1

S1

R0

S0

*

*

*

*

*

*

*

*

*

*

*

*

-

-

-

-

*

*

*

*

*

*

Заповнення клітинок табл. 2.8 забезпечується безпосереднім використанням табл. 2.9. Розглянемо, наприклад, заповнення клітинок з координатами q_1nq_0n = 00 і х₁х₀ = 00. У цих клітинках маємо значення q_1(n+1)q_0(n+1) =00. Оскільки q₁ і q₀ - це значення прямихвиходів двох тригерів,один з яких маєвходи R₁ S₁ дру­гий – R₀S₀,то, відповідно до табл. 2.9, значення входів R₁ S₁,R₀S₀ тригерів повинні відповідати незмінному q₁ = q₀ = 0 стану кожного тригера. Такі значення беруть з першого рядка табл. 5.34 і вписують у клітинки з координатами q_1nq_0n = 00 та х_хх₀ = 00 для кожного із входів тригерів. Для клітинок з координатами q_x„q_0n - 00 і х₁х₀ = 11 маємо q_1(n+1) = 1, тому з табл. 2.9 обираємо значення R, S з другого рядка, значення q_0(n+1) залишається незмінним на нульо­вому рівні, тому використовуємо перший рядок. Так послідовно заповнюють усі клітинки таблиці функцій збудження.

Для отримання функції збудження для кожного із входів три­герів переносимо їх значення на карти Карно (рис. 2.7, а - г).

Таблиця 2.9 - Значення входів R₁ S₁,R₀S₀ тригерів

qn	qn+1	Rn	Sn
		*
			*

Мінімізуючи кожну з функцій збудження входів, отримуємо:

;

а) б) в) г)

Рисунок 2.8 – Карти Карно для функцій збудження

Для визначення функції виходу кар­ту Карно будують на основі скороче­ної таблиці переходів табл. 2.8, в якій стійкі стани замінюють значеннями ви­хідного сигналу, а нестійкі символом "*" - довільним значенням функції. В результаті отримаємо карту, зображе­ну на рис. 2.9.

Рисунок 2.9 – Карти Карно для вихідного сигналу

З неї отримуємо мінімізоване значен­ня функції виходу: у = q_Q.

Етап 5. Складання функціональної (структурної) схеми авто­мата в обраному елементному базисі.

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

.

Рисунок 2.10 - Функціональ­на схема автомата

Розглянемо роботу синтезовано­го автомата відповідно до часової діаграми, що наведена на рис. 2.3.

У початковому стані за відсут­ності вхідних сигналів значення q₀ = q₁ = 0. У першому стані х₁ = 0, а х₀ = 1, тому, враховуючи, що =1, сигнал S_0n з виходу DDI буде поданий на тригер DD2 і встановить його вихід q в 1. Після повторення нульового стану тригер DDI установиться в почат­ковий стан нульовим значенням вхідного сигналу x₀.

У другому - третьому станах за умови х₁ = 1 на вході DD1 формується сигнал заборони для сигналу х₀ і т. д. З цього корот­кого опису бачимо, що функціональна схема цілком відтворює часову діаграму, за якою спроектований автомат

Контрольні питання і завдання

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

2. Яким умовам повинен задовольняти набір елементів для структурного синтезу ЦА?

3. У чому полягає особливість етапів оптимального синтезу?

4. За якому критерієм оцінюється оптимальність синтезованої схеми?

5. Автомати якого роду необхідно використовувати у разі застосування канонічного методу структурного синтезу і чому?

6. Назвіть особливості початкових таблиць переходів (ПТП) ЦА.

7. Які внутрішні стани ЦА називаються еквівалентними?

8. Які внутрішні стани ЦА є сумісними?

9. Чи є можливість здійснити сусіднє кодування станів ЦА, якщо в його графі переходів присутній замкнутий контур з не­парною кількістю вершин?.

10. Після мінімізації внутрішніх станів їх кількість зменшилась до 12. Яка кількість тригерів достатня для їх реалізації?

11. Автомат Мілі має m станів і p вхідних сигналів. Скільки станів матиме еквівалентний йому автомат Мура?

12. Поясніть різницю між еквівалентними та псевдоеквівален­тними станами автомата

13. Що є умовою для об'єднання трьох (чотирьох) сумісних внутрішніх станів автомата?

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

15. Скільки рядків і стовпчиків містить ПТП і СТП n -входового тригера?

16. Як перейти від ПТП до СТП, від ПТП до функції переходів?

17. Як побудувати ПТП синхронного тригера по ПТП асинхронного тригера того ж типу?

18. Сформулюйте теорему про структурну облиште для синтезу автоматів з пам'яттю.

19. Що називається повнотою системи переходів? Виходів?

20. У чому зміст кожного етапу структурного синтезу?