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

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

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

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

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

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

Полтава – 2006

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

    Формалізоване завдання функціонування. Мінімізація та кодування станів автомата. Алгоритм функціонування лічильника в обох заданих режимах може бути поданий табл. 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>

Т>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

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

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

Q>2>

Q>2>

M

1

1

M

1

1

Q>0>

1

1

1

1

Q>0>

1

1

1

1

Q>1>

Q>1>

Q>2>

Q>2>

M

M

1

1

Q>0>

1

1

1

1

Q>0>

Q>1>

Q>1>


Т>0>

Т>1>


Q>2>

Q>2>

M

1

1

M

Q>0>

1

1

Q>0>

Q>1>

Q>1>


Т>2>


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

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

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

    Складання логічної схеми автомата. Логічна схема комбінаційної частини ЦА, що формує необхідні функції збудження тригерів, подана на рис. 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

М

Початковий стан

Наступний стан

Сигнали на

входах тригерів

J>2>

K>2>

J>1>

K>1>

J>0>

K>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

ВИСНОВОК

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

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