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.  Що являють собою повна та скорочена структурна таблиця синхронного автомата?


 

А также другие работы, которые могут Вас заинтересовать

39679. ОБЕСПЕЧЕНИЕ ИНФОРМАЦИОННОГО ОБМЕНА В КОММУНИКАТИВНЫХ СИСТЕМАХ 113.5 KB
  Структура знаний намного сложнее структуры информации. Потоки информации циркулирующие в обществе обслуживают различные социальные образования социальные институты организации группы и др. Или иначе массовая информация является видом социальной информации которым пользуется большая по величине масса людей как на этапе ее производства как и на этапах распространения и потребления. Массовая коммуникация как вид социальной коммуникации представляет собой процесс распространения массовой информации.
39680. ЭФФЕКТИВНОСТЬ КОММУНИКАЦИИ 39 KB
  ЭФФЕКТИВНОСТЬ КОММУНИКАЦИИ Для эффективной организации этой работы необходимо: ü осуществление всех мероприятий мониторинга в комплексе; ü сочетание мониторинга с другими методами сбора данных; ü учет правовых аспектов свободы средств массовой информации; ü учет точек критического состояния массовой аудитории при проведении мониторинга определение пороговых величин значений социальных индикаторов; ü учет обратных связей возникающих в процессе мониторинга. На первом этапе ставятся задачи связанные...
39681. КОММУНИКАЦИЯ В РАЗЛИЧНЫХ СФЕРАХ ОБЩЕСТВЕННОЙ ЖИЗНИ 57.5 KB
  Различие состоит в том что основной функцией PR является управленческая и приоритет отдается межличностной коммуникации. На отдельных предприятиях для внутренней коммуникации имеются замкнутые системы радиовещания и телевидения. Результативность коммуникации складывается из многих компонентов. Она зависит и от выбора слов и речевых образцов принятых в деловой сфере коммуникации и от правильная ориентация на тип коммуникации межличностной внутригрупповой или массовой.
39682. Коммуникаторы и коммуниканты как субъекты коммуникации 63.5 KB
  Исходным понятием для изучения коммуникативной личности понятие личность. Множественность подходов и многообразие теорий и концепций личности раскрывает сложность проблемы обоснования социально значимых признаков личности. Социологическая концепция личности сформировалась в конке 19 в начале 20 века. В зависимости от придаваемой роли стадиям процесса формирования личности различаются подходов в исследовании личности.
39683. АУДИТОРИЯ И КОММУНИКАЦИЯ 28 KB
  Информация пронизывает весь процесс управления все его стадии. В такой системе обратная связь проявляется как реакция на управленческое действие которое осуществляет субъект управления в виде системы информации о состоянии управляемого объекта и его изменении в соответствии с заданной программой. Наличие такой обратной связи позволяет корректировать управленческие действия в процессе управления социальным развитием. Таким способом через обратную связь объект управления воздействует на субъект управления и оперативно оценивается...
39684. Основные этапы развития отечественной отоларингологии 347.5 KB
  Конец эпохи средневековья и период Возрождения характеризуются заметным прогрессом в медицине и прежде всего в развитии анатомии человека в том числе и анатомии уха носа и горла. К первым отечественным руководствам по болезням уха носа и горла следует отнести соответствующий раздел капитального труда по хирургии выдержавшего с 1807 по 1823 г. описана операция на лобных пазухах носа. Основой объединения болезней уха носа и горла в специальную дисциплину явилось анатомотопографическое единство этих органов их тесная физиологическая и...
39685. Проектирование технологических процессов 1.21 MB
  Задачами технологического проектирования являются определение условий изготовления изделий определение типа производства видов исходных заготовок проектирование технологического маршрута обработки выявление необходимых средств производства и порядка их применения определение себестоимости и трудоемкости изготовления изделий определение исходных данных для календарного планирования для организации технического контроля определение состава рабочей силы. Руководящая информация включает: стандарты устанавливающие требования к...
39686. ОСНОВЫ ПРОЕКТИРОВАНИЯ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ В МАШИНОСТРОЕНИИ 70 KB
  Общие принципы технической подготовки производства Рациональная организация производственного процесса невозможна без проведения тщательной технической подготовки производства. Техническая подготовка производства включает в себя следующее. 1 Конструкторскую подготовку производства.
39687. Расчетный метод определения точности 465 KB
  Блоксхема факторов влияющих на качество обрабатываемой заготовки на настроенном станке в общем виде представлена на рис. К числу первичных погрешностей обработки относятся: погрешность установки заготовки; погрешность от упругих деформаций технологической системы; погрешность настройки станка; погрешность от износа режущего инструмента; погрешность изза геометрической неточности станка и изготовления режущего инструмента; погрешность изза температурных деформаций системы; погрешность изза остаточных напряжений в заготовке....