Синтез автоматів з пам"яттю

Полтавський Військовий Інститут Зв^язку

Кафедра схемотехніки радіоелектронних систем

 

ОБЧИСЛЮВАЛЬНА ТЕХНІКА ТА МІКРОПРОЦЕСОРИ

напрям підготовки 0924 «Телекомунікації»

 

Синтез автоматів з пам^яттю.

Полтава – 2006

Навчальна література.

 

1.         Тиртишніков О.І. Обчислювальна техніка та мікропроцесори. Частина 2. Цифрові автомати: Навчальний посібник. – Полтава: ПВІЗ, 2006. с. 62-71.

2.         Калабеков Б.А., Мамзелев И.А. Цифровые устройства и микропроцессорные системы. М.: Радио и связь, 1987.

1.         Алгоритм синтезу послідовнісних ЦА.

 

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

Багатоваріантність можливих реалізацій ЦА пов^язана з вибором типу тригерів та способу побудови його комбінаційної частини. Теоретично будь-який ЦА може бути побудований на тригерах будь-якого типу. Найбільш розповсюджені в схемотехніці D- та JK-тригери. JK-тригер має більш розвинені логічні можливості, тому для нього можна отримати більш прості функції збудження, але кількість функцій буде удвічі більшою, ніж для D-тригера. Яке рішення буде оптимальним для конкретного ЦА, заздалегідь невідомо.

Алгоритм синтезу ЦА з пам^яттю містить такі основні етапи:

1.         Запис та формалізація умов функціонування автомата. Як і для комбінаційних пристроїв, вихідне завдання функціонування ЦА з пам^яттю може виконуватися в різних формах, у тому числі і словесній. У результаті формалізації необхідно отримати таблиці або формули, що повно та однозначно описують алгоритм функціонування ЦА у всіх можливих режимах роботи.

2.         Мінімізація та кодування станів. На цьому етапі необхідно визначити мінімальну кількість всіх можливих станів ЦА з урахуванням всіх необхідних напрямків переходу. Кодування станів найчастіше виконується з використанням двійкових кодів. Якщо ЦА може функціонувати в декількох різних режимах, доцільно скласти граф переходів (діаграму станів), що наочно відображає як можливі стани ЦА, так і напрямки переходів у різних режимах функціонування.

3.         Складання таблиці переходів. На основі діаграми станів (для ЦА, режим роботи яких завжди однаковий – безпосередньо на основі вихідної таблиці) складається таблиця переходів, в якій необхідно показати не тільки попередні та наступні стани тригерів, але і сигнали на їх входах.

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

5.         Мінімізація функцій збудження тригерів. Функції збудження тригерів реалізовуються комбінаційною частиною автомата, що в загальному випадку має n + m входів (n – кількість вхідних сигналів ЦА, m – кількість виходів всіх тригерів ЦА) та l + k виходів (l – кількість вихідних сигналів ЦА, k – кількість входів всіх тригерів ЦА). Це пояснюється узагальненою структурною схемою послідовнісного ЦА, що зображена на рис.1. Тобто, на цьому етапі виконується спільна мінімізація l + k логічних функцій n + m аргументів. Для мінімізації функцій використовуються будь-які існуючі методи – наприклад, карти Карно.

Рис. 1. Узагальнена структурна схема послідовнісного ЦА

6.         Перехід до заданого базису та складання логічної схеми ЦА виконуються практично таким же чином, що і при синтезі комбінаційних схем. Однак, слід мати на увазі, що поняття логічного базису застосовується лише до комбінаційної частини ЦА, але не відноситься до пам^яті автомата (тип тригерів, що реалізовують пам"ять ЦА, визначається вихідними умовами задачі або вибирається проектувальником).

Завершується проектування ЦА його аналізом – тобто моделюванням або макетуванням отриманої схеми з метою перевірки правильності її функціонування.

2.         Приклад синтезу послідовнісного ЦА.

 

Поставлення завдання (вихідне завдання функціонування): необхідно синтезувати трирозрядний додаючий двійковий лічильник на основі Т-тригерів, алгоритм функціонування якого визначає керуючий сигнал М. Якщо М = 0, лічильник працює як звичайний лічильник прямого рахування; якщо М = 1, лічильник працює в коді Грея. Зміна керуючого сигналу М відразу веде до зміни режиму роботи, тобто наступний стан лічильника буде належати вже іншому коду.

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

На основі опису ЦА можливо відразу отримати його структурну схему, що зображена на рис. 2.

Рис. 2. Структурна схема ЦА

 

Комбінаційна схема реалізує необхідні функції збудження Т-тригерів на основі їх станів та керуючого сигналу М. Всі тригери мають загальні входи скидання та синхронізації.

1.   Формалізоване завдання функціонування. Мінімізація та кодування станів автомата. Алгоритм функціонування лічильника в обох заданих режимах може бути поданий табл. 1.

На підставі табл. 1 складемо граф переходів (діаграму станів) лічильника, що показана на рис. 3. Напрямки переходів на діаграмі вказані: для рахування в коді 8421 – пунктирними лініями, для рахування в коді Грея – суцільними лініями. Ділянки діаграми, де напрямки переходів у двох режимах співпадають, вказані подвійними лініями.

Таблиця 1

 

Рис.3. Діаграма станів лічильника

 

2.         Складання таблиці переходів автомата. На підставі діаграми станів з урахуванням алгоритму функціонування Т-тригера складаємо таблицю переходів ЦА (табл. 2).

Таблиця 2

 

3.   Отримання функцій збудження тригерів ЦА (у вигляді ДДНФ).

 

4.   Мінімізація функції збудження тригерів. Перший етап мінімізації функцій збудження Т-тригерів виконаємо із застосуванням карт Карно (рис. 4).

	Q2 Q2 M 1 1 M 1 1 Q0 1 1 1 1 Q0 1 1 1 1 Q1 Q1				Q2 Q2 M M 1 1 Q0 1 1 1 1 Q0 Q1 Q1
		Т0				Т1

 

 

 

 

 

 

 

 

 

	Q2	Q2
M	1		1
M					Q0
		1	1		Q0
		Q1	Q1

	Т2

Рис. 4. Мінімізація функцій збудження тригерів за допомогою карт Карно

Отримаємо функції збудження тригерів у вигляді МДНФ:

Використовуючи відомі співвідношення (розподільний закон, правило де Моргана та ін.) остаточно отримаємо:

5.   Складання логічної схеми автомата. Логічна схема комбінаційної частини ЦА, що формує необхідні функції збудження тригерів, подана на рис. 5.

Рис. 5. Схема комбінаційної частини ЦА

Особливості синтезу ЦА з пам^яттю на основі JK-тригерів.

При виконанні синтезу ЦА на основі JK-тригерів необхідно враховувати деякі особливості, пов^язані з тим, що даний тип тригерів, порівняно з іншими, має найбільш розвинуті логічні можливості.

Таблицю переходів JK-тригера можна подати у вигляді табл. 3.

Таблиця 3

	J	K
0	0	*	0
0	1	*	1
1	*	1	0
1	*	0	1

Із аналізу табл. 3 можна зробити деякі важливі висновки.

По-перше, перехід тригера з будь-якого стану в інший однозначно визначається тільки одним з двох вхідних сигналів (J або K) та не залежить від значення другого сигналу. Наприклад, якщо J = 1, тригер перейде з нульового стану в одиничний, незалежно від того, яке значення має K.

По-друге, перехід тригера з нульового стану в будь-який інший (0 або 1) визначається виключно значенням J, а перехід тригера з одиничного стану – виключно значенням К. Це твердження можна записати таким чином:

Ця властивість дозволяє отримати дуже прості функції збудження, для чого необхідно складати таблицю переходів синтезованого ЦА з урахуванням вмісту табл. 3. Наприклад, таблиця переходів для синтезованого дворежимного лічильника з використанням JK-тригерів (табл. 4) містить удвічі більше стовпчиків для вхідних сигналів тригерів (функцій збудження), ніж табл. 2, але в кожному рядку цих стовпчиків присутні невизначені значення сигналів. Як відомо, при використанні карт Карно ці значення довизначаються за вибором виконавця з метою підвищення ефективності мінімізації, що дозволяє отримати більш прості логічні функції.

Таблиця 4

М	Початковий стан			Наступний стан			Сигнали на входах тригерів
							J2	K2	J1	K1	J0	K0
0	0	0	0	0	0	1	0	*	0	*	1	*
0	0	0	1	0	1	0	0	*	1	*	*	1
0	0	1	0	0	1	1	0	*	*	0	1	*
0	0	1	1	1	0	0	1	*	*	1	*	1
0	1	0	0	1	0	1	*	0	0	*	1	*
0	1	0	1	1	1	0	*	0	1	*	*	1
0	1	1	0	1	1	1	*	0	*	0	1	*
0	1	1	1	0	0	0	*	1	*	1	*	1
1	0	0	0	0	0	1	0	*	0	*	1	*
1	0	0	1	0	1	1	0	*	1	*	*	0
1	0	1	0	1	1	0	1	*	*	0	0	*
1	0	1	1	0	1	0	0	*	*	0	*	1
1	1	0	0	0	0	0	*	1	0	*	0	*
1	1	0	1	1	0	0	*	0	0	*	*	1
1	1	1	0	1	1	1	*	0	*	0	1	*
1	1	1	1	1	0	1	*	0	*	1	*	0

ВИСНОВОК

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

Багатоваріантність можливих реалізацій ЦА пов^язана з вибором типу тригерів та способу побудови його комбінаційної частини. Теоретично будь-який ЦА може бути побудований на тригерах будь-якого типу. Найбільш розповсюджені в схемотехніці D- та JK-тригери. JK-тригер має більш розвинені логічні можливості, тому для нього можна отримати більш прості функції збудження, але кількість функцій буде удвічі більшою, ніж для D-тригера. Яке рішення буде оптимальним для конкретного ЦА, в загальному випадку заздалегідь невідомо.