Синтез автоматів з пам’яттю
Головною метою синтезу ЦА з пам’яттю є визначення всіх його можливих станів та переходів, відповідно заданому алгоритму функціонування, та отримання функцій збудження всіх входів тригерів, з яких складається автомат. Варіанти можливих реалізацій ЦА.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 13.04.2008 |
| Размер файла | 91,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Полтавський Військовий Інститут Зв'язку
Кафедра схемотехніки радіоелектронних систем
ОБЧИСЛЮВАЛЬНА ТЕХНІКА ТА МІКРОПРОЦЕСОРИ
напрям підготовки 0924 «Телекомунікації»
Синтез автоматів з пам'яттю.
Полтава - 2006
Навчальна література.
Тиртишніков О.І. Обчислювальна техніка та мікропроцесори. Частина 2. Цифрові автомати: Навчальний посібник. - Полтава: ПВІЗ, 2006. с. 62-71.
Калабеков Б.А., Мамзелев И.А. Цифровые устройства и микропроцессорные системы. М.: Радио и связь, 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 |
||
|
Початковий стан |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
2 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|
3 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
4 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
5 |
1 |
0 |
1 |
1 |
1 |
1 |
|
|
6 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
7 |
1 |
1 |
1 |
1 |
0 |
0 |
Рис.3. Діаграма станів лічильника
2. Складання таблиці переходів автомата. На підставі діаграми станів з урахуванням алгоритму функціонування Т-тригера складаємо таблицю переходів ЦА (табл. 2).
Таблиця 2
|
М |
Початковий стан |
Наступний стан |
Сигнали на входах тригерів |
|||||||
|
Т2 |
Т1 |
Т0 |
||||||||
|
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 |
3. Отримання функцій збудження тригерів ЦА (у вигляді ДДНФ).
4. Мінімізація функції збудження тригерів. Перший етап мінімізації функцій збудження Т-тригерів виконаємо із застосуванням карт Карно (рис. 4).
|
Q2 |
Q2 |
|||||
|
M |
1 |
1 |
||||
|
M |
Q0 |
|||||
|
1 |
1 |
Q0 |
||||
|
Q1 |
Q1 |
Рис. 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-тригера. Яке рішення буде оптимальним для конкретного ЦА, в загальному випадку заздалегідь невідомо.
Подобные документы
Граф-схема алгоритму. Серія інтегральних мікросхем. Структурний синтез автомата Мура. Розмітка станів ГСА. Таблиця переходів автомата. Кодування станів. Функції збудження тригерів та вихідних сигналів. Аналіз канонічного методу структурного синтезу.
курсовая работа [30,6 K], добавлен 28.02.2009Граф-схеми алгоритмів. Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів. Структурний синтез автомата Мура. Функції збудження тригерів та вихідних сигналів. Кодування станів. Можлива кількість перемикань тригерів.
курсовая работа [36,9 K], добавлен 28.02.2009Граф-схема автомата Мура та Мілі. Структурний синтез автомата Мура. Кодування станів. Функції збудження тригерів та вихідних сигналів. Переведеня у базис. Структурний синтез автомата Мілі. Кодування станів. Функції збудження тригерів та вихідних сигналів.
курсовая работа [114,6 K], добавлен 28.02.2009Таблиця істинності логічних функцій пристрою, який необхідно синтезувати. Отримання логічних функцій пристрою та їх мінімізація за допомогою діаграм Вейча. Побудова та аналіз структурної схеми пристрою в програмі AFDK з логічними елементами до 3-х входів.
курсовая работа [320,4 K], добавлен 03.05.2015Синтез комбінаційної схеми, яка реалізує задану функцію п`яти змінних. Побудування за результатами синтезу функціональної схеми в базисі. Проектування керуючих автоматів Мура та Мілі, принципових схем на елементах малого ступеня інтеграції заданої серії.
курсовая работа [156,8 K], добавлен 24.09.2010Синтезування мікропрограмного автомата за схемою Уілкса-Стрінжера у вигляді автоматів Мілі та Мура. Основні дані про автомати, їх класифікація. Змістовна схема алгоритму та таблиця кодування операційних та умовних верхівок. Схема операційного автомата.
курсовая работа [140,4 K], добавлен 08.08.2009Розробка операційного автомату. Розробка машинного алгоритму: граф-схема алгоритму; приклад реалізації. Синтез керуючого автомату: основи теорії керуючих автоматів; опис керуючого автомату Мілі. Кодування граф-схеми автомату. Синтез керуючого автомату.
курсовая работа [121,0 K], добавлен 26.12.2009Синтез комбінаційної схеми. Отримання вихідної БФ. Мінімізація БФ. Вибір базиса. Застосування факторного алгоритму. Синтез управляючого автомата Мура. Вибір вихідних даних для проектування. Розрахунок даних синтезу. Синтез управляючого автомата Мілі.
курсовая работа [271,5 K], добавлен 26.02.2009Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.
презентация [357,0 K], добавлен 16.10.2013Найпростішими елементами з пам’яттю є тригери – логічні елементи, яки можуть знаходитись у одному з двох стійких станів і переходити до іншого стану під впливом зовнішніх сигналів (через це тригер називають бістабільним елементом). Їх застосування.
лекция [74,7 K], добавлен 13.04.2008
