Табличний спосіб завдання ЦА

Існує кілька способів завдання опису функціонування ЦА. Для завдання простих ЦА набули значне поширення табличні способи опису його функціонування у вигляді представлених таблиць 12.1а,б: переходів, виходів автомата Мілі (а) та відмічених таблиць переходів автомата Мура (б).

Таблиця 12.1 – Приклади Таблиць переходів, виходів (а) та таблиці відмічених станів автомата (б)

а б

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

13.1 Канонічний метод синтезу ЦА

Теоретичним обґрунтуванням структурного синтезу автоматів є теорема про структурну повноту.

Усяка система елементарних автоматів, що містить автомат Мура з нетривіальною пам’яттю, що володіє повною системою переходів і повною системою виходів, і яку-небудь функціонально повну систему елементів логічних функцій, є структурно повною.

Канонічний метод структурного синтезу припускає подання структурної й логічної схеми автомата у вигляді двох частин рисунку 13.1: пам’яті й комбінаційної схеми.

Пам’ять автомата складається з елементарних, повних автоматів Мура П₁,...,П_i…П_t.

Будь-який автомат Мура повинен мати повну систему переходів і повну систему виходів. Це означає, що для будь-якої пари станів автомата пам’яті знайдеться вхідний сигнал, що переключить його в інший стан. Повнота системи виходів автомата Мура полягає в тому, що кожному стану відповідає свій кодований сигнал на його виході. Інакше кажучи, у повному автоматі Мура його внутрішній стан ототожнюється з виходом, тобто, за його виходом можна визначити в якому стані він перебуває.

Загальна кількість елементів пам’яті Мура в автоматі визначається необхідною сукупністю всіх його внутрішніх станів , де 2 − основа бінарної системи числення. Так, наприклад, автомат, який має п’ять елементів пам’яті може мати 2⁵ станів. Коди внутрішніх станів автомата (елементів пам’яті) визначаються бінарним числом із 5-ти розрядів.

Рисунок 13.1 – Структура цифрового автомата Мілі

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

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

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

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

13.1.1 Приклад синтезу ЦА канонічним методом

Завдання. Синтезувати цифровий частковий автомат , заданий таблицею 13.1 переходів і виходів. Використати канонічний метод структурного синтезу автоматів. Прийняти: як елементарні автомати − логічний розширений базис Буля; як елементи пам’яті − повний автомат Мура з бінарним алфавітом вхідних/вихідних сигналів і станів.

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

Рішення. Для переходу від абстрактного автомата до його структурного подання, закодуємо вхідні/вихідні сигнали каналів й стани автомата Мілі − і автомата Мура − . У заданому абстрактному автоматі кожний канал Хі, має два стани: або сигналу немає − , або сигнал є − . Вихідні канали за аналогією − . Тому, у структурному автоматі на кожний абстрактний канал досить вибрати один вхідний або один вихідний сигнал із двома станами {0,1} кожний. Результати кодування сигналів і таблиця переходів для структурного автомата представлені таблицею 13.2.

Таблиця 13.2 – Приклад кодів сигналів і таблиця переходів

Автомат має чотири стани (див. таблицю 13.1), тому необхідні два елементи пам’яті і . Три абстрактних вхідних і чотири вихідних сигнали можуть бути представлені кодами двох вхідних і двох вихідних каналів. Представимо структурну схему автомата на рис. 13.2.

Рисунок 13.2 – Структурна схема автомата А

Структурна схема представлена канонічним методом структурного синтезу цифрових автоматів. Вона розподілена на дві частини: комбінаційну та два елементи пам’яті, які складають другу частину схеми.

Присвоїмо коди вхідним/вихідним каналам та каналу переключення елементів пам’яті. В таблиці 13.3 структурного автомата А представлені кінцеві результати присвоєння кодів вхідним, вихідним сигналам, заданих таблицею 13.1 для абстрактного ЦА і переключення станів елементів П1, П2.

Таблиця 13.3 – Коди вхідних/вихідних каналів та станів А

Тепер переходимо до кодування функцій переходів і виходів структурного автомата А (таблиця 13.4), використовуючи коди таблиці 13.3 і підставляючи їх у таблицю13.1 заданого абстрактного автомата.

Застосовуючи математичну модель канонічного методу структурного синтезу автомата (рисунок 13.2), будуємо систему логічних функцій:

;

Таблиця 13.4 – Переходи і виходи автомата А

Функцію отримаємо відразу безпосередньо з таблиці 13.4 для виходів структурного автомата, як диз’юнкцію наборів змінних на яких функції приймають значення 1. Ці значення розміщені в кодах на пересіченні стовпців ірядків . Перша цифра відповідає значенню функції , а друга . Запишемо функції:

(13.1)

Для одержання логічних функцій , , необхідно побудувати таблицю сигналів переключення елементів пам’яті П₁ і П₂. Для одержання цієї таблиці використаємо таблицю 13.4 переходів структурного автомата. В цій таблиці на пересіченні стовпців і рядків розміщенні значення переходів станів елементів пам’яті П₁, П₂ (перша цифра − значення П₁, друга − П₂), а в заголовках стовпців розміщенні значення вихідних сигналів П₁, П₂ або (ототожнюючи вихід Пі − стан) значення станів П₁, П₂, що були до переключення. Порівнюючи ці стани зі станами переходів, визначаємо елементи пам’яті, які треба переключати (на їхні входи треба подавати сигнал ) і які не треба переключати (на їхні входи треба подавати сигнал ). Заповнюючи цими значеннями таблицю 13.5, одержимо таблицю сигналів дляпереключення елементів пам’яті.

Таблиця 13.5 – Таблиця переключення

Безпосередньо з цієї таблиці визначаємо систему логічних функцій в ДДНФ для одиничних наборів :

Логічні функції систем рівнянь 13.1, 13.2 є математичним рішенням поставленого завдання структурного синтезу логічної схеми ЦА канонічним методом. За цими функціями будуємо логічну схему. Приклад схемного рішення логічної функції системи 13.2 представлен рис. 13.3.

Рисунок 13.3 – Логічна схема функції u1

В якості елемента пам’яті зручно вибрати тригер з лічильним входом. Він має прямій і інверсний вихід. Таблиця переходів тригера збігається з таблицею переходів автомата Мура П таблиці 13.2.

Завдання ЦА графом

Абстрактний автомат часто задають за допомогою графа.

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