31299

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

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

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

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

Украинкский

2013-08-28

880 KB

2 чел.

ПРАКТИЧНЕ ЗАНЯТТЯ № 6

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

Мета заняття:  Закріпити теоретичні знання щодо поетапного канонічного синтезу схем асинхронних автоматів за словесним описом

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

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

Рис. 6.1 Етапи структурного синтезу цифрових пристроїв

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

Структурний синтез комбінаційного цифрового пристрою потребує після цього виконання ряду етапів (ліва гілка алгоритму на рис. 6.1).

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

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

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

,    .

Кожен вхідний сигнал  абстрактного автомата можна закодувати вектором вхідних сигналів структурного автомата довжиною :

,  ,  .

Стани в структурному автоматі фіксує пам’ять, що містить  елементарних елементів . Кожен стан  абстрактного автомата закодовано в структурному автоматі вектором довжини  вихідних сигналів елементів пам’яті:

,  ,  .

Структурний автомат (див. рис. 6.2) складається з двох комбінаційних схем КС1 та КС2 і пам’яті П. Стани елементів пам’яті Т1 - ТR, що визначають стан автомата, у формі сигналів  за колами прямого зв’язку надходять на входи КС2 і зворотного - на входи КС1. На входи КС1 надходять також вхідні сигнали  (для автомата Мура), в автоматі Мілі вони надходять на входи КС2.

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

Комбінаційна схема КС2, сприймаючи на вході вихідні сигнали елементів пам’яті  (для автоматів Мура), а для автоматів Мілі - і вхідні сигнали , виробляє вихідне слово . Таким чином, комбінаційна схема КС2 структурного автомата реалізує вихідну функцію  абстрактного автомата.

Наведений опис принципу побудови структурного автомата свідчить про те, що для його реалізації треба синтезувати схему станів П (пам’ять на тригерах), а також комбінаційні схеми КС1 та КС2. Послідовність етапів синтезу цих схем зображено в правій гілці на рис. 6.2.

Основи канонічного методу синтезу автоматів з пам'яттю 

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

  1.  кодування;
  2.  вибір елементів пам'яті автомата;
  3.  вибір структурно-повної схеми елементів;
  4.  побудова рівнянь функцій переходів і виходів автомата;
  5.  побудова функціональної схеми автомата.

Розглянемо кожний з перерахованих етапів докладніше.

Кодування

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

Самим ідеальним випадком була би можливість переключення при переході автомата зі стану в стан тільки одного розряду коду стану, що відповідало би реалізації тільки однієї функції керування пам'яттю. Причиною такої необхідності є неоднозначність трактування переходу у випадку зміни більш ніж одного розряду коду стану. Так, якщо відбувається перехід зі стану  з кодом 001 у стан  з кодом 111, можливий короткочасний перехід автомата в стани з кодами 011 чи 101 через різний час затримки при формуванні функцій керування, тобто можуть виникнути помилкові спрацьовування автомата поза межами основного циклу. У деяких випадках цей процес можливо попередити на етапі проектування, скориставшись для кодування, приміром, картою Карно.

Правила кодування станів автомата по карті Карно:

1) У вільні клітки карти Карно спочатку заносяться стани з найбільшою кількістю зв'язків.

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

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

Вибір елементів пам'яті автомата

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

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

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

Повнота системи виходів означає, що різним станам автомата відповідають різні вихідні сигнали. Звичайно, нульовому стану елементарного автомата відповідає нульовий вихідний сигнал, одиничному – одиничний.

Число елементів пам'яті структурного автомата дорівнює числу компонент вектора його станів.

Як елементи пам'яті структурного автомата звичайно використовуються різні тригери (D, T, JK, RS), лічильники, регістри, ПЗУ і т.п., що задовольняють вимогам щодо повноти переходів і виходів

Вибір структурно-повної системи елементів

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

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

Функція збудження структурного автомата є векторною. Її аргументи – пари двійкових векторів , а значення функції – двійковий вектор, кожна i-а компонента якого є значення бульової функції збудження i-го елемента пам'яті автомата, що визначає той двійковий сигнал, який необхідно подати на вхід елемента пам'яті для забезпечення його переключення відповідно до вимог структурної таблиці переходів. Якщо векторна функція переходів задає перехід з одного вектора стану структурного автомата в інший вектор стану під впливом двійкового вектора вхідного сигналу, то векторна функція керування пам'яттю автомата задає двійковий вектор, який необхідно подати на входи елементів пам'яті, щоб забезпечить необхідний перехід (відповідно до векторної функції переходів автомата). Останнє означає, що перемінними, від яких залежить векторна функція керування пам'яттю, є ті ж перемінні, що і для векторної функції переходів автомата, тобто виходи всіх елементів пам'яті і усі входи автомата.

Тому структурний автомат Мура, у загальному випадку, може бути представлений структурною схемою, зображеної на рис. 6.3, а структурний автомат Милі – схемою, зображеної на рис. 6.4.

Рис. 6.3  Рис. 6.4

Побудова рівнянь бульових функцій переходів і виходів автомата

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

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

Загальний вид структурної таблиці для асинхронного автомата з пам'яттю відбитий у таблиці 6.1.

Рис. 6.5 Класичний граф автомата Мура

Таблиця 6.1

Вихідний

стан

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

Вихідний сигнал

Вхідний сигнал   

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

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

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

Стани з графа заносяться в структурну таблицю в такий спосіб:

- береться перший стан  і заноситься в 1-й стовпець таблиці;

- відповідний йому вихідний сигнал заноситься в 3 стовпець таблиці;

- далі описуються всі можливі переходи з даного стану (тобто усі вихідні дуги на графі);

- події, зв'язані з вихідними, заносяться в 5 стовпець таблиці, у 4 стовпець заносяться вхідні сигнали, під впливом яких відбувається перехід з вихідного в наступний+стан;

- код станів може вибиратися довільно або з умов мінімізації числа елементів пам'яті, що переключаються одночасно. Другий спосіб, як було відзначено раніше, більш кращий.

Побудова функціональної схеми автомата

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


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

Синтезуємо схему асинхронного автомата Мура за наступним словесним описом:

Ворота цеха відкриваються після натискання кнопки, а закриваються з витримкою часу 50с. При закриванні контролюється наявність перешкоди в створі воріт. При наявності перешкоди закривання припиняється, ворота зупиняються, 5с дзвенить дзвоник. Закривання воріт продовжується після натискання кнопки.

Проведемо канонічний синтез згідно з наведеними вище його етапами:

  1.  Визначимо команди і вхідні сигнали.

Вхідні сигнали:

- кнопка на відкриття воріт;

- кінцевий вимикач (ворота відкриті);

- витримку часу 50с завершено;

- від датчика наявності перешкоди в створі воріт;

- витримку часу 5с завершено;

- кнопка зняття блокування воріт;

- кінцевий вимикач (ворота закриті).

Команди:

- відкрити ворота;

- закрити ворота;

- зупинити ворота, запустити таймер на 50 с;

- зупинити ворота, запустити таймер на 5 с, включити дзвоник;

- відключити дзвоник;

- зупинити ворота.

2. Побудуємо відмічену ГСА автомата (див. рис. 6.6).

Рис. 6.3 Відмічена ГСА автомата

  1.  Побудуємо на основі ГСА класичний граф.

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

  1.  Визначимо кількість станів і необхідну кількість тригерів.

Станів у нас 6, тобто для їх опису необхідно 3 тригери. Три тригери описують 23=8 станів, отже введемо до графу на рис. 6.4 два незначущі стани  та , до яких автомат може потрапити через апаратні збої, і передбачаємо вихід з них за сигналом, припустимо, .

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

Рис. 6.5 Кодування станів автомата

Таким чином, коди станів:

, , , , , , , .

  1.  На основі графу, враховуючи коди станів, побудуємо структурну таблицю (схему автомата будемо будувати на RS - тригерах).

Табл.6.1

Вихідний стан

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

Вихідний сигнал

Вхідний сигнал

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

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

Функції переходу

(RS)

000

001

S3

001

101

S1

101

100

R3

100

000

R1

110

S2

110

111

S3

111

100

R2, R3

010

-

000

R2

011

-

000

R2, R3

  1.  Запишемо функції переходу та виходу:

- функції переходу:

; ; ; ; ; .

- функції виходу:

; ; ; ; ; .

  1.  Реалізуємо функціональну схему автомата, при цьому його стани отримаємо на виході дешифратора (рис. 6.6).

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

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

Синтезувати асинхронний автомат Мура за наступним словесним описом:

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

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

  1.  Що називають структурним синтезом цифрового автомата?
  2.  Охарактеризуйте структурний цифровий автомат.
  3.  Назвіть основні етапи канонічного методу структурного синтезу автоматів з пам’яттю.
  4.  Чим відрізняються змістова та відмічена ГСА?
  5.  Як визначається необхідна кількість елементів пам’яті цифрового автомата?
  6.  З якою метою проводиться кодування станів автомата за картою Карно?
  7.  На основі яких даних проходить заповнення структурної таблиці?
  8.  Як на основі структурної таблиці записати вирази для функції переходу та виходу?
  9.  На виходах яких елементів функціональної схеми автомата формуються стани? Коди станів?

12


 

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

71382. Разработка и экономическое обоснование проекта как обеспечение финансовой устойчивости компании 1.69 MB
  Предметом исследования исследование финансовой устойчивости предприятия а также разработка путей повышения финансовой устойчивости на нем. Цель работы проанализировать и дать оценку финансовой устойчивости предприятия и внести предложения по ее повышению.
71383. Вивчення брендів на основі узагальнення 3.27 MB
  Мною були поставлені завдання: вивчити основи формування бренду дослідити особливості спортивного брендингу. Докладно описуються такі питання як створення і позиціонування бренду. В останньому розділі курсової роботи розглядається специфіка бренду в спорті на прикладі ФЦ Барса.
71384. Проектирование контактной сети постоянного тока 314.22 KB
  Для подачи электроэнергии на подвижной состав применяются устройства контактной сети. Контактная сеть может быть выполнена с контактным рельсом или контактной подвеской. Основным элементами контактной сети с контактной подвеской являются провода контактной сети контактный провод...
71386. Анализ финансового состояния предприятия на примере ОАО «ВК и ЭХ» 191.12 KB
  Финансовое состояние – важнейшая характеристика экономической деятельности предприятия Она определяет конкурентоспособность, потенциал в деловом сотрудничестве, оценивает, в какой степени гарантированы экономические интересы самого предприятия и его партнёров в финансовом и производственном отношении.