31298

Синтез схем синхронних автоматів з памяттю

Практическая работа

Информатика, кибернетика и программирование

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

Украинкский

2013-08-28

3.18 MB

2 чел.

ПРАКТИЧНЕ ЗАНЯТТЯ5 

Тема:  Синтез схем синхронних автоматів з пам'яттю

Мета роботи:  Закріпити отримані теоретичні знання зі знань теорії дискретних автоматів, навчитися визначати бульові функції і будувати функціональні схеми простих синхронних автоматів, заданих словесним описом

1  ТЕОРЕТИЧНІ  ВІДОМОСТІ

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

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

За внутрішньою структурою автомати розділяються на три класи:

  1.  Автомати Мілі;
  2.  Автомати Мура;
  3.  Змішані.

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

-  - вхідні сигнали;

-  - вихідні сигнали;

-  - внутрішні стани;

- функції переходів і функції виходів.

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

Для рішення задач аналізу й синтезу цифрових автоматів наводиться поняття автоматного часу. Функціонування автомата розглядається через дискретні інтервали часу кінцевої тривалості (інтервал дискретності).

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

У теорії автоматів найбільше докладно описані синхронні автомати. У залежності від способу визначення вихідного сигналу в синхронних автоматах існує дві можливості:

1) вихідний сигнал  однозначно визначається вхідним сигналом  і станом  автомата в попередній момент;

2) вихідний сигнал  однозначно визначається вхідним сигналом  і станом  автомата в даний момент часу. Отже, закон функціонування абстрактного автомата може бути заданий таким чином:

- для автомата першого роду

(5.1)

- для автомата другого роду

(5.2)

Для подальшого аналізу важливо розглянути питання про взаємовідношення автоматів першого й другого родів.

Припустимо, що довільний автомат  другого роду заданий рівняннями (5.2). Для цього автомата побудуємо нову функцію 

. (5.3)

На підставі закону функціонування (5.2)

(5.4)

У підсумку отриманий новий автомат  першого роду, заданий тією же функцією переходу й функцією виходів .

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

 . (5.5)

Надалі приймемо, що довільні автомати першого роду (формула (5.2)) будемо називати автоматами Мілі, а окремий випадок автоматів другого роду, для яких зрушена функція виходів  не залежить від другої перемінної  - автоматами Мура. Закон функціонування автоматів Мура має вигляд:

(5.6)

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

Між моделями Мілі й Мура існує відповідність, що дозволяє перетворювати закон функціонування одного з них в інший і назад. Таке перетворення породжує пари описів законів функціонування, еквівалентних в тому, що їм відповідає однакова залежність між вхідними Х та вихідними Y послідовностями.

В якості елементів пам’яті ЦА використовуються двійкові лічильники, регістри, ПЛМ, ПЗП, але найчастішеелементарні елементи пам’ятітригери.

Розглянемо основні типи тригерів, що використовуються в схемах цифрових автоматів.

На найдокладніший розгляд заслуговує RS- тригер, бо тригери інших типів побудовано на його базі. Тригером RS - типу називають елементарний автомат з двома стійкими станами, який має два інформаційних входи R і S; якщо S=1 і R=0, то він перебуває в одиничному стані Q=1, а коли S=0 і R=1в нульовому Q=0. Принцип дії цього тригера описують таблиця переходів (таблиця 5.1) і логічне рівняння, яке пов’язує стан його виходів у (n+1) -й момент часу із станом виходів та вихідними сигналами в n -й момент часу:

(5.7)

Таблиця 5.1

Режим роботи

Входи

Виходи

Зберігання

0

0

Установлення 1

0

1

1

0

Установлення 0

1

0

0

1

Заборонений

1

1

х

х

З таблиці 5.1 видно, що коли , то тригер не змінює свого стану. Якщо на входи тригера одночасно надійдуть сигнали , то протягом їх дії , а по її закінченні тригер перебуватиме в невизначеному стані і може перейти в довільний стан. Тому комбінація  і  заборонена, і на це вказує друга частина (5.7). Логічне рівняння для інверсного виходу RS- тригера можна дістати інверсією (5.7):

.  (5.8)

Розрізняють RS- тригери, реалізовані на базі логічних елементів АБО-НЕ і І-НЕ (рис. 5.1 а і б відповідно).

 а) б)

Рис. 5.1 Варіанти реалізації RS- тригерів

Тригер D- типу відомий під назвоютригер затримки” (від англійського delay -  затримка). D- тригером (рис. 5.2) називають логічний пристрій з двома стійкими станами та одним інформаційним входом D, закон функціонування якого можна описати таблицею переходів (таблиця 5.2) і логічним рівнянням:

.  (5.9)

Таблиця 5.2

Режим роботи

Вхід

Вихід

Установлення 1

1

1

Установлення 0

0

0

Таблиця 5.2 і рівняння (5.9) вказують на те, що в (n+1) -й тактований момент часу вихідний стан тригера збігається з інформаційним сигналом, який діє на вході D у n -й момент часу.

Схему D- тригера легко одержати з RS- тригера, з’єднавши входи S та R через інвертор (рис. 5.3).

Рис. 5.2 Структурна схема й умовне позначення 

синхронізованого D- тригера

Рис. 5.3 Схема одержання D- тригера з RS- тригера

JK- тригернайпоширеніший універсальний тригер, який має характеристики всіх інших типів тригерів (рис. 5.4). Тригером JK- типу називають елементарний автомат з двома стійкими станами та двома інформаційними входами J і K, який за умови  робить інверсію попереднього стану , а в решті випадків функціонує згідно з таблицею істинності RS- тригера, коли вхід J еквівалентний входові S, а KR (таблиця 5.3). Логічне рівняння  JK- тригера:

.  (5.10)

Рис. 5.4 Структурна й функціональна схеми JK- тригера

Таблиця 5.3

Режим роботи

Входи

Виходи

Зберігання

0

0

Установлення 0

0

1

0

1

Установлення 1

1

0

1

0

Перемикання

1

1

Тригером Т- типу (рис. 5.5), або лічильним тригером, називають елементарний автомат з двома стійкими та одним інформаційним входом Т, надходження сигналу на який змінює стан Т- тригера на супротивний (таблиця 5.4). Логічне рівняння Т- тригера:

.  (5.11)

Так як вихідний сигнал Т- тригера повторюється після кожних двох сигналів на вході, ця його властивість використовується під час побудови війкових лічильників.

 Таблиця 5.4

Режим роботи

Вхід

Виходи

Перемикання

1

Зберігання

0

Рис. 5.5 Схема Т-тригера

2 КОНТРОЛЬНИЙ ПРИКЛАД

Визначити бульові функції і побудувати функціональну схему:

  1.  Підсумовуючого лічильника з паралельним переносом і модулем рахунку 15, використовуючи Dтригери.
  2.  Синхронного автомата, виконаного на RSтригерах, що має в циклі 8 тактів і генерує на трьох виходах послідовність: 1, 2, 3, 4, 5, 6, 7, 0.

Рішення.

  1.  Так як модуль рахунку підсумовуючого лічильника 15, то його максимальний вихідний стан –(враховуючи стан 0000).

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

Рис. 5.6 Класичний граф цифрового автомата

На основі класичного графу побудуємо структурну таблицю автомата, визначивши, що для його реалізації необхідно 4 елементи пам’яті (зі співвідношення , де - кількість елементів пам’яті, - кількість станів автомата (модуль рахунку). Структурна таблиця має наступний вигляд (див. таблицю 5.4).

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

     Таблиця 5.4

Код вихідного стану

Код наступного стану

Функції керування пам'яттю

q1

q2

q3

q4

q1

q2

q3

q4

D1

D2

D3

D4

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

0

1

1

1

0

1

1

1

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

0

1

1

1

0

1

1

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

1

0

0

0

0

0

0

0

0

0

Враховуючи це, визначаємо функції керування пам'яттю D1-D4, карти Карно для яких зображено на рис. 5.7-5.10. Значення сигналів для обраної функції керування заносяться в клітини карти Карно за адресами, що відповідають вихідним станам. 

 Рис. 5.7 Карта Карно для функції D1 Рис. 5.8 Карта Карно для функції D2

 Рис. 5.9 Карта Карно для функції D3  Рис. 5.10 Карта Карно для функції D4

Так як стан 1111 не є активним для розробленого автомата, в клітині карті Карно з цим адресомневизначений стан, що може прийматися і за 0 і за 1.

З рис. 5.7-5.10 функції керування тригерами: 

; ;

; .

 Функціональну схему розробленого автомата зображено на рис. 5.11.

Рис. 5.11 Функціональна схема автомата 

2. На відміну від попереднього випадку, цього разу необхідно провести повний синтез автомата, так як задано закон зміни його вихідних сигналів (послідовність на виході). Необхідну кількість елементів пам’яті визначимо як в попередньому випадку (їх достатньо 3). Кількість вихідних сигналів визначається з максимального числа послідовності таким же чином, як і кількість елементів пам’яті (так як максимальне число послідовності,  схема автомата повинна мати 3 виходи. Вихідний граф автомата зображено на рис. 5.12. 

Рис. 5.12 Вихідний граф автомата

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

 Виконавши мінімізацію функцій переходу за принципом, описаним в попередньому прикладі, отримаємо:

;

;

;

;

;

.

Мінімізацію функцій виходу, доречі, можна проводити таким же методом для будь-якого автомату. Для даного випадку значення функцій виходу заносяться в карту Карно за адресами, що відповідають вихідним станам автомату (див. рис. 5.13 - 5.15). 

  Таблиця 5.5

Код вихідного стану

Код наступного

стану

Функції керування пам'яттю

Функції виходу

q1

q2

q3

q1

q2

q3

R і S

Y1

Y2

Y3

0

0

0

0

0

1

S3

0

0

1

0

0

1

0

1

0

S2, R3

0

1

0

0

1

0

0

1

1

S3

0

1

1

0

1

1

1

0

0

S1, R2, R3

1

0

0

1

0

0

1

0

1

S3

1

0

1

1

0

1

1

1

0

S2, R3

1

1

0

1

1

0

1

1

1

S3

1

1

1

1

1

1

0

0

0

R1, R2, R3

0

0

0

 Рис. 5.13 Карта Карно для функції Y1 Рис. 5.14 Карта Карно для функції Y2

Рис. 5.15 Карта Карно для функції Y3

Пам’ятаючи, що для автомата Мура функція виходу характеризує лише стан автомату, отримаємо:

;

;

.

Функціональну схему автомата у відповідності з отриманими виразами для функцій керування пам’яттю та виходу зображено на рис. 5.16.

Рис. 5.16 Функціональна схема синхронного автомата

3 ЗАВДАННЯ НА САМОСТІЙНУ РОБОТУ

Визначити бульові функції і побудувати функціональну схему:

1. Підсумовуючого лічильника з паралельним переносом і модулем рахунку 13, використовуючи 

а) Ттригери;

б) RSтригери. 

2. Автомата, що має в циклі 8 тактів і генерує на трьох виходах послідовність: 

а) 7, 5, 2, 4, 13, 11, 6, 7  (на JK - тригерах);

б) 1, 7, 2, 5, 3, 12, 3, 15, 5 (на D - тригерах).

4 КОНТРОЛЬНІ ПИТАННЯ

  1.  Дайте визначення цифрового автомата.
  2.  На які класи розділяються автомати з пам’яттю?
  3.  Напишіть рівняння, що задають автомат Мілі.
  4.  Напишіть рівняння, що задають автомат Мура.
  5.  Поясніть, чим відрізняється синхронний автомат від асинхронного.
  6.  На яких мікросхемах може бути реалізована пам’ять цифрових автоматів?
  7.  Дайте порівняльну характеристику основних типів тригерів, що використовуються при побудові цифрових автоматів.
  8.  Поясніть принцип дії, таблицю істинності та особливості схемної реалізації RS- тригерів.
  9.  Поясніть принцип дії, таблицю істинності та особливості схемної реалізації D- тригерів.
  10.  Поясніть принцип дії, таблицю істинності та особливості схемної реалізації JK- тригерів.
  11.  Поясніть принцип дії, таблицю істинності та особливості схемної реалізації T- тригерів.
  12.  Дайте визначення синхронного автомата з пам’яттю.
  13.  Назвіть основні етапи синтезу синхронного автомата з пам’яттю.
  14.  Що являють собою повна та скорочена структурна таблиця синхронного автомата?