Реферат: Синтез автоматів з пам’яттю
Полтавський Військовий ІнститутЗв’язку
Кафедрасхемотехніки радіоелектронних систем
ОБЧИСЛЮВАЛЬНА ТЕХНІКА ТА МІКРОПРОЦЕСОРИ
напрямпідготовки 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
Такт
М=0; код 8421
М=1; код Грея
Х2
Х1
Х0
Х2
Х1
Х0
Початковий стан 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 1 1 6 1 1 1 1 7 1 1 1 1/>
/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> <td/>/>
/> <td/> />/>
/>/>
/> /> /> />/>
/> /> />/>
/>/>
/> /> /> /> />/>
/>/>
/>/>
/> /> /> />/>
/> />/>
/>/>
Рис.3.Діаграма станів лічильника
2. Складаннятаблиці переходів автомата.На підставі діаграми станів з урахуванням алгоритмуфункціонування Т-тригера складаємо таблицю переходів ЦА (табл. 2).
Таблиця 2
МПочатковий стан
Наступний стан
Сигнали на входах тригерів
/>
/>
/>
/>
/>
/>
Т2
Т1
Т0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3. Отримання функцій збудженнятригерів ЦА(увигляді ДДНФ).
/>
/>/>
4. Мінімізація функції збудженнятригерів.Перший етап мінімізації функцій збудження Т-тригерів виконаємо іззастосуванням карт Карно (рис. 4).
/> /> /> /> /> /> /> /> />Q2
Q2
/>
/>
M
1 1/>
M
1 1Q0
/>
1 1 1 1Q0
/>
1 1 1 1/>
/>
Q1
Q1
/>
<td/>Q2
Q2
/>
/>
M
/>
M
1 1Q0
/>
1 1 1 1Q0
/>
/>
/>
Q1
Q1
/>
/> /> <td/>Т0
/>Т1
Q2
Q2
/>
/>
M
1
1
/>
M
Q0
/>
1
1
Q0
/>
/>
/>
Q1
Q1
/>
/> <td/>Т2
Рис.4. Мінімізація функцій збудження тригерів за допомогою карт Карно
Отримаємо функціїзбудження тригерів у вигляді МДНФ:
/>
/>
/>
Використовуючивідомі співвідношення (розподільний закон, правило де Моргана та ін.) остаточноотримаємо:
/>
/>/>
5. Складання логічної схемиавтомата.Логічна схема комбінаційної частини ЦА, що формує необхідні функції збудженнятригерів, подана на рис. 5.
/>
Рис.5. Схема комбінаційної частини ЦА
Особливостісинтезу ЦА з пам’яттю на основі JK-тригерів.
При виконаннісинтезу ЦА на основі JK-тригерів необхідно враховувати деякіособливості, пов’язані з тим, що даний тип тригерів, порівняно з іншими, маєнайбільш розвинуті логічні можливості.
Таблицю переходівJK-тригера можна подати у вигляді табл. 3.
Таблиця 3
/>
J
K
/>
* 1 * 1 1 * 1 1 * 1Із аналізу табл.3 можна зробити деякі важливі висновки.
По-перше, перехідтригера з будь-якого стану в інший однозначно визначається тільки одним з двохвхідних сигналів (J або K) та не залежить від значення другогосигналу. Наприклад, якщо J = 1, тригер перейде з нульового станув одиничний, незалежно від того, яке значення має K.
По-друге, перехідтригера з нульового стану в будь-який інший (0 або 1) визначається виключнозначенням J, а перехід тригера з одиничного стану – виключно значенням К.Це твердження можна записати таким чином:
/>
Ця властивістьдозволяє отримати дуже прості функції збудження, для чого необхідно складатитаблицю переходів синтезованого ЦА з урахуванням вмісту табл. 3. Наприклад,таблиця переходів для синтезованого дворежимного лічильника з використанням JK-тригерів(табл. 4) містить удвічі більше стовпчиків для вхідних сигналів тригерів(функцій збудження), ніж табл. 2, але в кожному рядку цих стовпчиків присутніневизначені значення сигналів. Як відомо, при використанні карт Карно цізначення довизначаються за вибором виконавця з метою підвищення ефективностімінімізації, що дозволяє отримати більш прості логічні функції.
Таблиця4
МПочатковий стан
Наступний стан
Сигнали на
входах тригерів
/>
/>
/>
/>
/>
/>
J2
K2
J1
K1
J0
K0
1 * * 1 * 1 1 * 1 * * 1 1 1 1 * * 1 * 1 1 1 1 * * 1 * 1 1 1 1 * * 1 * 1 1 1 1 * 1 * * 1 1 1 1 1 1 * * 1 * 1 1 1 * 1 * 1 * 1 1 1 * * 1 * 1 1 1 1 * 1 * * 1 1 1 1 1 * * * 1 1 1 1 * * * 1 1 1 * 1 * * 1 1 1 1 * * * 1 1 1 1 1 1 1 * * 1 * 1 1 1 1 1 1 * * 1 *ВИСНОВОК
Головною метою синтезу ЦА з пам’яттю є визначення всіх його можливихстанів та переходів, відповідно заданому алгоритму функціонування, та отриманняфункцій збудження всіх входів тригерів, з яких складається автомат. Цьогодостатньо для складання логічної схеми ЦА.
Багатоваріантність можливих реалізацій ЦА пов’язана з вибором типутригерів та способу побудови його комбінаційної частини. Теоретично будь-якийЦА може бути побудований на тригерах будь-якого типу. Найбільш розповсюджені всхемотехніці D- та JK-тригери. JK-тригер має більшрозвинені логічні можливості, тому для нього можна отримати більш простіфункції збудження, але кількість функцій буде удвічі більшою, ніж для D-тригера. Яке рішення буде оптимальним для конкретного ЦА, в загальномувипадку заздалегідь невідомо.