Цифрові автомати (ЦА). Асинхронні і синхронні ЦА. Комбінаційні і послідовністі цифрові пристрої

Перетворення інформації в обчислювальній техніці відбувається за допомогою електронних цифрових пристроїв (ЦП) – логічних схем,які будуються з логічних елементів і забезпечують виконання арифметичних і логічних операцій над сукупністю цифрових вхідних сигналів Х_i, перетворюючи їх у сукупність вихідних сигналів Y_j. Розподіляють два класи таких пристроїв: комбінаційні схеми (КС) і послідовнісні схеми – цифрові автомати (ЦА).

В комбінаційних схемах результат перетворення – сукупність цифрових вихідних сигналів у будь-який момент часу t_n залежить лише від сукупності (комбінації) цифрових сигналів Х_i,які надходять на її входи у даний момент часу і не залежать від стану схеми, який передував надходженню сигналів Х_i. В таких схемахвідсутні елементи пам’яті, тому сигнали, які діють у такий схемі, не зберігається. Такі ЦП ще називають цифровими автоматами без пам’яті (примітивними автоматами). До КС відносяться досить прості елементи, вузли та блоки мікропроцесорних систем: шифратори, дешифратори, мультиплексори, демультиплексори, комбінаційні суматори, перетворювачі кодів, схеми контролю тощо.

До послідовністних схем відносяться ЦП, в яких результат перетворення Y_jзалежить не лише від комбінації цифрових сигналівХ_i, які надходять на її входи у даний момент часу t_n, а й від послідовності попередніх цифрових станів входів і виходів схеми – внутрішніх станів Z_f. Для запам’ятовування попередніх станів така схема повинна мати елементи пам’яті. Подібні схеми називають цифровими автоматами(ЦА). Можна стверджувати, що кількість внутрішніх станів і кількість елементарних запам’ятовувальних пристроїв в цифрових автоматах зв’язані між собою такою залежністю Z = 2^k, де k – кількість запам’ятовувальних елементів.

Загальна теорія ЦА поділяється на абстрактну і структурну. Абстрактна теорія досліджує поведінку автомата відносно зовнішнього середовища, на рівні алгоритмів його роботи, не вирішуючи задач його побудови. Абстрактна теорія ЦА показує принципові відміни КС від ЦА для можливості подання дискретних процесів і обмеження, які є при цьому. Важливий висновок, який отримано у цих дослідженнях, полягає в тому, що в ЦА можливо реалізувати нескінченні регулярні події, на відміну від КС, де є можливість реалізувати лише скінченні події. Регулярними подіями вважаються такі події, які у скінченному алфавіті X = {x₁, x₂,…, x_n} можливо отримати з елементарних слів алфавіту X при здійсненні над ними операцій диз’юнкції, перемноження та ітерації. Нерегулярні події реалізувати у ЦА неможливо, тому що це вимагає нескінченного обсягу пам’яті. На практиці звичайно розглядаються ЦА, які мають обмежений обсяг пам’яті і називаються скінченними ЦА.

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

Абстрактний ЦА можна повністю описати за допомогою сукупності п’яти об’єктів:

- множини вхідних сигналів (вхідний алфавіт) – Х = {x₀, x₁ … x_i};

- множини вихідних сигналів (вихідний алфавіт) – Y = {y₀, y₁ … y_j};

- множини стійких станів ЦА (алфавіт станів ЦА) – Z = {z₀, z₁ … z_f};

- функції переходів – φ, яка визначає стан ЦА Z в залежності від вхідного сигналу і попереднього стану;

- функції виходів – λ, яка визначає залежність вихідного сигналу від вхідного і попереднього станів.

В залежності від способу формування функції виходів абстрактні ЦА поділяються на цифрові автомати Міліі цифрові автомати Мура.

Якщо закон функціонування ЦА можна описати системою наступних рівнянь:

y(t+1) = λ{z(t), x(t)} – вихідний сигнал ЦА після переключення;

z(t+1) = φ{z(t), x(t)} – стан ЦА після переключення,

де t = 0, 1, 2, ... , то такий ЦА називається автоматом Мілі. Отже вихідний сигнал після переключення залежить від стану z(t), в якому ЦП знаходився у момент надходження сигналу і вхідного сигналу x(t).

В обчислювальній техніці широко використовуються пристрої, які можуть бути описані як ЦА Мура, який описується іншою системою рівнянь:

y(t+1) = λ {x(t)} – вихідний сигнал ЦА після переключення ;

z(t+1) = φ{z(t), x(t)} – стан ЦА після переключення,

де t = 0, 1, 2, ....

Звідси видно, що вихідний сигнал такого ЦА не залежить від стану автомата, а повністю визначений вхідним сигналом. Відповідні структурні схеми автоматів Мура і Мілі показано на рис. 1.9a і 1.9b.

a) b)

Рисунок 1.9 – Структурні схеми автоматів Мура і Мілі показано

Абстрактний ЦА, в якого виділено спеціальний початковий стан z₀ називається ініціальним. Зазвичай, усі вихідні сигнали у такому початковому стані дорівнюють нулю. Виділення такого стану обумовлено вимогами практичного використання пристроїв, в яких він є обов’язковим для правильного функціонування всієї системи. Таким чином, описати роботу ініціальних ЦА можливо так: якщо на вхід автомата Мілі або Мура, який знаходиться у початковому стані, подавати послідовність символів вхідного алфавіту x(0), x(1), x(2), ... x(i), то на виході отримаємо послідовність символів вихідного алфавіту. Тому на рівні абстрактної теорії функціонування ЦА описується як перетворення вхідного алфавіту у вихідний.

Якщо у ЦА функція переходів і функція виходів визначені для всіх пар Х_і і Z_f, то він називається повністю визначеним. ЦА, для якого функція переходів або функція виходів, або обидві разом не визначені для всіх пар X_і і Z_f, називається частково визначеним.

Реальні ЦА завжди скінченні, тому що множина вхідних і вихідних сигналів, а також множина внутрішніх станів обмежені.

Функціонування ЦА відбувається у певні часові інтервали – такти. Залежно від способу визначення такту ЦА поділяються на синхронні і асинхронні.

Синхронні ЦА змінюють свій внутрішній стан у суворо визначені моменти часу, які завдаються за допомогою спеціального пристрою – генератора тактових імпульсів (ГТІ), який формує послідовність імпульсів спеціального сигналу синхронізації. При цьому тривалість тактового інтервалу визначена і залишається постійною протягом усього часу роботи схеми.

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

Структурна схема ЦА у загальному виді показана на рис. 1.10 (ЦА Мура).

До цієї схеми входять: КС1 – комбінаційна схема 1, яка формує сигнали запису інформації (вхідний алфавіт) у запам’ятовувальний пристрій – ЗП, який може бути побудований з тригерів, елементів затримки сигналів та інших пристроїв, що здатні запам’ятовувати інформацію. Цей пристрій фіксує внутрішній стан (алфавіт станів) ЦА і зберігає його протягом такту. КС2 – комбінаційна схема 2, яка формує вихідні сигнали (вихідний алфавіт) ЦА.

Рисунок 1.10 – Узагальнена структурна схема ЦА

Слід зазначити, що як вхідні сигнали також використовуються всі або будь-яка частина сигналів внутрішніх станів ЦА, які по ланцюгах зворотного зв’язку надходять на входи КС1 з виходів ЗП. На входи КС2 можуть надходити вхідні сигнали або деякі з них. Наявність таких зв’язків необхідна для спрощення схем КС1 і КС2.

Описування алгоритму роботи абстрактного ЦА можна задати трьома способами: матричним, графічним і аналітичним.

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

Таблиця переходів визначає функцію переходів ЦА – φ, а таблиця виходів – функцію виходів λ. Таблиця переходів для деякого конкретного ЦА наведена у табл. 1.1. Вона будується таким чином, що стовпці цієї таблиці визначають символи станів цього автомата (вважаємо, що кількість бітів інформаційних сигналів відповідних кожному стану дорівнює 4), і вхідного алфавіту, символи якого переключають ЦА у наступні стани (вважаємо, що в описуваному ЦА вхідний алфавіт складається з чотирирозрядних двійкових чисел). Рядки таблиці завдають символи алфавіту станів у порядку їх появи. Вважаємо, що цей ЦА є ініціальним і після проходження циклу перемикань ЦА повертається у початковий стан Z₀. Тому що ЦА описується лише чотирма станами, то він є частково визначеним (усього в цього ЦА може бути Z = 2⁴ = 16 стійких станів).

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

Таблиця виходів ЦА визначає вихідні сигнали у кожному зі стійких станів. Таблиця виходів ЦА, який описано табл. 1.1, подана в табл. 1.2.

Розглянуті таблиці можливо об’єднати у одну, яка має назву відзначеної таблиці переходів. Вид такої таблиці для розглядуваного ЦА показано в табл. 1.3.

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

Риски у відповідних клітинках відповідають неможливим комбінаціям сигналів і станів.

Таблиця 1.2 – Таблиця виходів ЦА

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

Таблиця 1.3 – Відзначена таблиця переходів

Стани ЦА, Z	Алфавіт вхідних сигналів
Х(4)	Х(3)	Х(2)	Х(1)	Х(0)
Z(0)	– –	– –	– –	– –	Z1 Y0
Z(1)	– –	– –	– –	Z2 Y1	– –
Z(2)	– –	– –	Z3 Y2	– –	– –
Z(3)	– –	Z4 Y3	– –	– –	– –
Z(4)	Z0 Y4	– –	– –	– –	– –

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

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

Матриця з’єднань для ЦА, який ми описуємо, показана на рис. 1.11.

Рисунок 1.11 – Матриця з’єднань цифрового автомата

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

Рисунок 1.12 – Спрямований граф роботи цифрового автомату

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

При розробленні принципової схеми ЦА вигляд і склад запам’ятовувального пристрою, як правило визначено, тому задача розробки ЦА зводиться до задачі проектування цифрових пристроїв – комбінаційних схем КС 1 і КС 2, які представляють собою логічні схеми.

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

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

Правила функціонування логічних схем (ЛС) можуть задаватися у різний спосіб:

- словесне описування;

- за допомогою таблиць істинності;

- за допомогою часових діаграм;

- аналітичний – за допомогою логічних (булевих) виразів;

- у вигляді координатних діаграм.

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

Слід зазначити, що для спрощення розв’язання задачі синтезу загальна ЛС поділяється на декілька схем, кожна з яких має один вихід (із сукупності вихідних сигналів Y_j) і стільки входів, скільки входить у сукупність вхідних сигналів Х_i, необхідних для формування Y_j. Для більшого спрощення дозволяється подальше роздрібнення схеми таким чином, щоб зменшити кількість вхідних сигналів Х. Після закінчення синтезу схем усі ці дрібні схеми об’єднують в одну загальну схему КЦП. Розв’язання задачі синтезу виконується за декілька етапів.

На першому етапі відбувається описування функціонування ЛС, як правило, у вигляді таблиці істинності, яка описує кожен із стійких станів ЦП, як співвідношення вхідних і вихідного сигналів і кожен рядок таблиці відповідає певному часовому інтервалу роботи. Описування виконується переважно для схем, які мають один вихід Y, а кількість входів рекомендується вибирати не більше ніж п’ять. Таблиця істинності повинна описувати всі можливі стани роботи ЛС, тому кількість рядків такої таблиці дорівнює кількості можливих станів. Якщо ЛС є частково визначеною, то значення вихідної функції позначається, як ~.

На другому етапі відбувається подання описування роботи ЛС в аналітичному виді – у вигляді досконалої диз’юнктивної нормальної форми (ДДНФ), або у вигляді досконалої кон’юнктивної нормальної форми (ДКНФ). Вибір форми подання можливо обумовити співвідношенням кількості нулів та одиниць у вихідному сигналі (логічній функції) і їх розташуванням за номерами рядків таблиці істинності або технічним завданням на проведення синтезу схеми.

На третьому етапі відбувається мінімізація схеми КЦП. Найбільш просто і наочно рекомендується проводити мінімізацію за допомогою координатних діаграм (карти Карно або діаграми Вейча). Різниця між цими способами полягає лише у поданні системи координат на діаграмі. На рис. 1.13,а показано вид карти Карно, а на рис. 1.13,б – вид діаграми Вейча.

Рисунок 1.13 – Координатні діаграми

Кількість можливих комбінацій значень вхідних сигналів (логічних змінних) Х, а також кількість можливих стійких станів (логічних функцій) дорівнює K = 2^N, де N – кількість вхідних сигналів. Слід зазначити, що деякі стійкі стани можуть бути відсутніми, тобто вихідний сигнал Y (логічна функція) індиферентний до комбінації вхідних сигналів Х_i у цей час. Це можливо трактувати, як відсутність деяких комбінацій вхідних сигналів Х_i у повному наборі можливих. Так, наприклад, дешифратор для керування цифровим індикатором, який відображує десять десяткових цифр 0...9, має чотири входи для подання кодів двійкових чисел від 0000 до 1001, а кількість стійких станів для такої схеми дорівнює K = 2⁴ = 16. Таким чином, шість комбінацій сигналів (16_D –10_D = 6_D) не можуть бути сформовані на виходах такого пристрою. Значення сигналу карти Карно (рис. 1.13,а) і діаграми Вейча (рис. 1.13,б) для трьох вхідних змінних х₀ , х₁ , х₂, при однаковому розміщенні вхідних змінних на сторонах прямокутників, які є осями координат (загалом, вибір системи координат може бути довільним, обов’язковим є тільки зсув координат на одну клітинку відповідно одна до одної на тих напрямках, на яких необхідно розміщувати дві змінні). У клітинках на рис. 1.13,а показано набори вхідних сигналів, а на рис. 1.13,б номери рядків таблиці істинності, які відповідають один одному.

У результаті мінімізації отримуємо аналітичну функцію, яка складається з мінімальної кількості логічних функцій, за допомогою яких вона реалізується у вигляді мінімальної диз’юнктивної нормальної форми (МДНФ) або мінімальної кон’юнктивної нормальної форми (МКНФ).

Критеріями оптимальності для цих способів є розробка схеми ЛС з мінімальною кількістю логічних елементів і мінімальною кількістю з’єднань між ними, внаслідок чого схема буде споживати мінімум енергії і вартість її буде менше, ніж у інших можливих.

На четвертому етапі за отриманими МДНФ або МКНФ можливо побудувати принципову схему КЦП у базисі ТА-АБО-НІ. Якщо принципову схему необхідно мати в іншому базисі, то виконуємо необхідне перетворення і будуємо схему у відповідному базисі ТА-НІ (АБО-НІ). За необхідності на цьому етапі можливо зробити розрахунок часу затримки сигналу й інших параметрів схеми.