Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИВЧЕННЯ МЕТОДІВ АНАЛІЗУ ТА СИНТЕЗУ СКІНЧЕННИХ АВТОМАТІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Захисту інформації
Кафедра:
Не вказано
Інформація про роботу
Рік:
2015
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
схемотехніка пристроїв технічного захисту інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ВИВЧЕННЯ МЕТОДІВ АНАЛІЗУ ТА СИНТЕЗУ СКІНЧЕННИХ АВТОМАТІВ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 5
з курсу «Схемотехніка пристроїв технічного захисту інформації»
для студентів базового напряму 6.170102 «Системи технічного захисту інформації»
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № 12 від 07.05.2015р.
Львів – 2015
Мета роботи: вивчення методів аналізу і синтезу скінченних автоматів.
1. ОСНОВНІ ВІДОМОСТІ
Цифровий автомат - це пристрій, що здійснює прийом, зберігання і перетворення дискретної інформації за деяким алгоритмом.
Загальну теорію автоматів ділять на абстрактну і структурну. Абстрактна теорія, абстрагуючись від структури автомата (тобто не цікавлячись способом його побудови), вивчає тільки поведінку автомата відносно зовнішнього середовища.
Структурна теорія цікавиться як структурою самого автомата, так і структурою вхідних дій і реакцією на них автомата. В структурній теорії вивчаються способи побудови автоматів, способи кодування вхідних дій і реакцій на них автомата.
1.1. Абстрактні цифрові автомати. Основні поняття
Абстрактний цифровий автомат з пам’яттю А задається сукупністю п’яти об’єктів: , де , - множина абстрактних вхідних сигналів автомата А (вхідний алфавіт автомата А); , - множина абстрактних станів автомата А (алфавіт станів автомата А); , - множина абстрактних вихідних сигналів автомата А (вихідний алфавіт автомата А); - функція переходів автомата А - визначає стан автомата в такті в залежності від стану автомата і від значення вхідної букви на - ому такті:
, (1) ( - дискретні моменти часу); - функція виходів автомата А - визначає значення вихідної букви на - ому такті в залежності від стану автомата і від вхідної букви на тому ж - ому такті:
(2) На множині Z як правило фіксується один із станів як початковий.
Зауваження:
Поняття стану у визначенні абстрактного автомата введено в зв’язку з тим, що більшість реальних процесів, якими керують цифрові автомати, вимагають для свого правильного протікання знання передісторії розвитку процесу в часі. Іншими словами вихідний сигнал, що видається автоматом в деякий момент часу, визначається не тільки вхідною дією на автомат (командою), але й станом, в якому автомат перебував в попередній момент часу. Наприклад, якщо потрібно побудувати автомат керування переключенням світлофору при умові, що на вхід автомата надходить тільки один абстрактний вхідний сигнал «переключити світлофор», то в кожен момент часу для організації правильної роботи автомату, крім згаданого вхідного сигналу, потрібно мати також інформацію про попередній стан світлофора.
Букви - це не є в загальному випадку двійкові (або інші цифрові) змінні. Це абстрактне значення відповідно вхідної інформації, стану автомата і вихідної інформації, які відрізняються від всіх інших можливих значень. Вже на рівні структурної теорії кожну з цих букв можна закодувати певною кількістю цифрових (наприклад двійкових) змінних. Наприклад, на рівні абстрактної теорії деяка абстрактна вхідна буква може мати значення «збільшити швидкість в 2 рази», а на рівні структурної теорії ця абстрактна буква може бути закодована двома структурними двійковими змінними і мати значення 10: (, ).
Загалом, абстрактний автомат реалізує відображення множини букв вхідного в множину букв вихідного алфавітів і має тільки один вхідний і один вихідний канали, а отже є лише математичною моделлю реального процесу.
Функція виходів автомата може бути двох типів. Якщо вихідний сигнал автомата визначається виразом (2), тобто залежить як від стану автомата, так і від вхідного сигналу, то пристрій називають автоматом Мілі. Якщо ж вихідний сигнал не залежить від вхідного, а однозначно визначається станом автомата:
, (3) то пристрій називають автоматом Мура.
Є різні способи задання функцій виходів і переходів . В цій роботі ми будемо користуватися табличним способом задання цих функцій. При такому способі функція переходів автомата Мілі задається таблицею переходів (приклад - Таблиця 1), а функція виходів автомата Мілі - таблицею виходів (Таблиця 2).
Таблиця 1
Таблиця 2
Стовпці таких таблиць позначаються символами з множини , а рядки - символами з множини . В клітинку таблиці переходів (Таблиця 1), що знаходяться на перетині стовпця та рядка записується стан автомата , в який він перейде із стану () під дією вхідного сигналу (). В таких же клітинках таблиці виходів (Таблиця 2) записують вихідні сигнали .
Функції переходів і виходів автомата Мура задаються однією позначеною таблицею переходів, що будується як таблиця переходів автомата Мілі, але над символами , що позначають стовпці таблиці, вказують символи вихідних сигналів, які однозначно (у відповідності до (3)) відповідають - ому стану (приклад - Таблиця 3).
Крім задання тим чи іншим способом функцій переходів і виходів, на етапі абстрактного синтезу автомата при необхідності вирішується також задача мінімізації числа станів цифрового автомата, що дозволяє мінімізувати апаратні затрати на його майбутню реалізацію [3].
Розглянемо процес складання абстрактних таблиць виходів і переходів автомата на прикладі.
Таблиця 3
Приклад 1. Нехай потрібно задати табличним способом функції виходів і переходів абстрактного автомату, що керує роботою світлофору. Опишемо роботу світлофору. Нехай світлофор може працювати в двох режимах: неробочому (при подачі відповідного вхідного сигналу постійно горить жовте) і робочому (щоразу при подачі відповідного вхідного сигналу світлофор переключається в послідовності зелене-жовте-червоне-жовте-зелене).
Очевидно, що множина абстрактних вхідних сигналів X автомату визначається двома своїми елементами, назвемо їх та :
- вхідний абстрактний сигнал - його значення «включити неробочий режим»;
- вхідний абстрактний сигнал «робочий режим: переключити світлофор».
Множина абстрактних вихідних сигналів Y містить три елементи:
- «зелене»;
- «жовте»;
- «червоне».
Множина абстрактних станів автомата Z складається з чотирьох різних станів. Причому стан «зелене» приймемо за початковий (з нього починається робота світлофора в робочому режимі):
- «зелене»; - «жовте після зеленого»;
- «червоне»; - «жовте після червоного».
Таблиця 4
Далі складаємо абстрактні таблиці переходів і виходів автомата, які будуть мати 4 стовпці і 2 рядки (Таблиці 4, 5).
Таблиця 5
Наприклад, в клітинку, що лежить на перетині стовпця і рядка Таблиці 4 записуємо , тому що при подачі на вхід автомату сигналу - «робочий режим: переключити світлофор» і при стані світлофору в даний момент часу - «зелене», автомат повинен перейти в наступний стан - «жовте після зеленого». З тих же міркувань в ту ж клітинку Таблиці 5 записуємо вихідний сигнал автомату в даний момент часу - «зелене». Так само заповнюються інші клітинки Таблиць 4,5.
1.2. Структурний синтез цифрових автоматів
В загальному випадку задача структурного синтезу автоматів з пам’яттю зводиться до знаходження загальних прийомів побудови структурних схем складних автоматів на основі композиції деяких елементарних автоматів, тобто пошуку певних способів їх з’єднання між собою. Така побудова не завжди можлива, а якщо можлива, то кажуть, що вибрана система елементарних автоматів структурно повна. Якщо ж говорити про ефективний структурний синтез автоматів, то такий синтез можливий сьогодні тільки на основі структурно повних систем елементарних автоматів деякого спеціального виду. Розглянемо один з методів такого синтезу, який дозволяє звести задачу структурного синтезу довільного автомата з пам’яттю до задачі синтезу комбінаційних схем. Такий метод відомий за назвою канонічного методу структурного синтезу автоматів з пам’яттю. Метод оперує елементарними автоматами двох класів. Перший клас - елементарні автомати з пам’яттю (елементи пам’яті). Другий клас - елементарні комбінаційні автомати (логічні елементи). Результатом роботи метода є рівняння логічних функцій автомата в канонічній формі. Вхідними даними для початку роботи метода є абстрактний цифровий автомат з пам’яттю.
Канонічний метод структурного синтезу умовно можна поділити на такі етапи:
кодування;
вибір елементів пам’яті автомата;
вибір структурно - повної системи елементів;
побудова рівнянь логічних функцій виходів автомата і рівнянь логічних функцій збудження елементів пам’яті;
побудова функціональної схеми автомата.
Розглянемо зміст кожного з цих етапів.
Кодування.
При кодуванні вхідні і вихідні сигнали абстрактного автомата, а також його стани, кодуються наборами значень структурних двійкових змінних. Якщо , , - відповідно потужності вхідного алфавіту абстрактного автомата, алфавіту станів і алфавіту вихідних сигналів (тут потужність - це кількість букв в алфавіті, або кількість елементів відповідних множин),то мінімальна кількість структурних двійкових змінних (або розрядів коду) , , , необхідна для кодування відповідно вхідних сигналів, станів і вихідних сигналів абстрактного автомата, визначаються співвідношеннями:
(4) (5) , (6) тут символ означає операцію заокруглення в бік більшого цілого числа.
Процес заміни букв алфавітів абстрактного автомата двійковими векторами називається кодуванням і може бути описаний таблицями кодування. Таблиця кодування складається так: в лівій її частині вказують всі букви (наприклад вхідного алфавіту абстрактного автомату), а в правій - двійкові вектори, які ставляться у відповідність цим буквам.
Детальніше зміст цього етапу синтезу розглянемо на прикладі.
Приклад 2 Нехай потрібно синтезувати автомат, заданий абстрактними таблицями переходів (Таблиця 1), і виходів (Таблиця 2).
1-ий етап синтезу - кодування.
З таблиць видно, що кількість букв вхідного і вихідного алфавіту абстрактного автомата - 3 (). Отже . Кількість букв алфавіту станів - 4 (). Тобто . Користуючись співвідношеннями (4) - (6) знаходимо:
;
;
Таблиця 7
Вихідні
сигнали
Код вихідних
сигналів
0
0
1
0
1
0
Таблиця 8
Стани
автомата
Код
станів
0
0
1
1
0
1
0
1
Таблиця 6
Вхідні
сигнали
Код вхідних
сигналів
0
0
1
0
1
0
Отже, для кодування букв кожного з трьох алфавітів заданого абстрактного автомата необхідно використати як мінімум дві структурні двійкові змінні. Далі складаємо таблиці кодування: вхідних сигналів (Таблиця 6), вихідних сигналів (Таблиця 7) і станів автомата (Таблиця 8). При цьому структурні змінні називаємо довільно. Так само довільно обираємо набір значень цих структурних змінних (тобто двійковий вектор), який ми ставимо у відповідність кожній букві з алфавітів абстрактного автомата. Але обов’язково дві різні букви (одного й того самого алфавіту) мають кодуватися різними двійковими векторами.
Вибір елементів пам’яті автомата.
Структурний автомат повинен запам’ятовувати двійковий вектор стану автомата, для чого і служать елементи пам’яті.
Канонічний метод структурного синтезу автоматів використовує як елементи пам’яті елементарні автомати Мура з двома станами, що мають повну систему переходів і виходів.
Повнота системи переходів автомата означає, що для будь-якої пари станів автомата існує такий вхідний сигнал, який переводить елементарний автомат з одного стану в інший. Таблиця переходів елементарного автомата з повною системою переходів містить в кожній стрічці всі можливі стани.
Повнота системи виходів означає, що різним станам автомата відповідають різні вихідні сигнали. Як правило, нульовому стану елементарного автомата відповідає нульовий вихідний сигнал, а одиничному - одиничний.
Очевидно, що число елементів пам’яті, необхідних для побудови структурного автомата, дорівнює числу компонентів двійкового вектора його стану.
Як елементи пам’яті структурного автомата використовують D - тригери, T - тригери, RS - тригери, JK - тригери, які задовільняють умовам повноти переходів і виходів. Таблиці переходів (збудження) цих тригерів, якими будемо користуватися далі при структурному синтезі автоматів, подано, відповідно, в Таблиці 9, Таблиці 10, Таблиці 11 і Таблиці 12. Повернемося тепер до Прикладу 2.
2-ий етап синтезу - вибір елементів пам’яті.
Таблиця 9
00
01
10
11
0
1
0
1
Таблиця 10
00
01
10
11
0
1
1
0
Таблиця 11
00
01
10
11
*
0
1
0
0
1
0
*
При розв’язуванні Прикладу 2, на попередньому етапі структурного синтезу ми виконали кодування абстрактних сигналів і станів автомату. Тепер виберемо елементи пам’яті. У відповідності з Таблицею 8 в нас має бути два елементи пам’яті. Адже згідно з Таблицею 8, в двійковому векторі, який ідентифікує кожен абстрактний стан автомату, є два компоненти (два розряди коду , ). Виберемо для реалізації функцій елементів пам’яті D - тригер і JK - тригер (таблиці переходів цих тригерів – в Таблиці 9 і Таблиці 12).
Вибір структурно повної системи елементів.
Таблиця 12
00
01
10
11
0
1
*
*
*
*
1
0
Теоретичним фундаментом канонічного методу структурного синтезу автоматів з пам’яттю є теорема про структурну повноту: будь-яка система, що містить елементарні автомати Мура з повною системою переходів і виходів, а також яку-небудь функціонально-повну систему логічних елементів, є структурно-повною, тобто дозволяє синтезувати довільний цифровий автомат з пам’яттю. Таким чином, для побудови структурного автомата необхідно крім елементів пам’яті мати комбінаційну схему, що реалізує логічні функції збудження елементів пам’яті і логічні функції формування вихідних сигналів автомата (тобто сумарна кількість логічних функцій дорівнює сумі інформаційних входів всіх елементів пам’яті і вихідних структурних змінних автомата). Пояснимо суть цього етапу синтезу на Прикладі 2.
3-ій етап синтезу - вибір структурно повної системи елементів.
На попередньому етапі розв’язування Прикладу 2 ми вибрали елементи пам’яті. Для формування структурно-повної системи елементів потрібно вибрати ще функціонально-повну систему логічних елементів. При цьому комбінаційна схема, яку будемо синтезувати, має реалізувати п’ять логічних функції: функцію збудження D - тригера; дві функції збудження JK - тригера (за кількістю інформаційних входів); а також функції формування першого () і другого () компонентів вихідного вектора структурного автомата (тобто значень вихідних структурних змінних автомата).
Знаходження рівнянь логічних функцій виходів автомата і рівнянь логічних функцій збудження елементів пам’яті автомата.
Кодування і вибір системи елементів однозначно визначають комбінаційну частину автомата. Для її синтезу спочатку будують таблицю істинності для функцій збудження елементів пам’яті автомата і для функцій вихідних сигналів. Вхідними даними для побудови такої таблиці є: - для функцій збудження елементів пам’яті - таблиця переходів абстрактного автомата, таблиці кодування вхідних сигналів і станів автомату, таблиці переходів (таблиці збудження) вибраних елементів пам’яті; для функцій виходів структурного автомату - таблиця виходів абстрактного автомата, таблиці кодування вхідних і вихідних сигналів, а також станів автомату.
Після складання таблиці істинності здійснюють мінімізацію логічних функцій будь-яким з відомих методів. Мінімізовані логічні рівняння записують у формі, яка відповідає вибраній системі логічних елементів. Розглянемо зміст цього етапу на Прикладі 2.
4-ий етап структурного синтезу - знаходження рівнянь логічних функцій виходів автомата і рівнянь логічних функцій збудження елементів пам’яті автомата.
Таблиця 13
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
0
0
1
0
1
1
*
0
*
*
1
*
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
0
0
1
*
0
*
*
1
*
1
0
0
1
1
1
0
0
0
1
1
1
1
0
0
0
0
0
0
1
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
*
0
*
*
0
*
0
0
0
0
1
0
1
1
0
-
-
-
-
1
1
1
1
1
1
1
1
0
0
1
1
0
1
0
1
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Складемо таблицю істинності (Таблиця 13) структурного автомата, який ми синтезуємо в межах Прикладу 2.
Пояснимо послідовність складання і заповнення таблиці істинності. Отже, стовпчики , , , - це стовпчики для запису двійкових векторів (кодів) вхідних команд і станів автомата на - ому такті його роботи. Тобто це вхідні змінні автомата, від яких залежать значення у всіх інших стовпчиках таблиці. Тому ці стовпчики заповнюємо, перебираючи всі можливі значення цих кодів - починаючи від набору значень 0000 і закінчуючи набором 1111. Далі, керуючись кодами в стовпчиках , , , і таблицями кодування абстрактних вхідних сигналів і станів автомата (Таблиця 6, Таблиця 8), записуємо в перший (допоміжний) стовпчик Таблиці 13 пару абстрактних сигналів , яка на даному - ому такті (який відповідає даному рядку таблиці) впливає на роботу автомата. Наприклад, для першого рядка таблиці: код абстрактного вхідного сигналу (стовпчики , ) - 00, що відповідає абстрактній вхідній змінній (див. Таблицю 6); код абстрактного стану автомата (стовпчики , ) - 00, що відповідає абстрактному стану автомата (див. Таблицю 8). Отже, на даному такті на автомат діє пара абстрактних величин . Аналогічно заповнюються інші рядки в першому стовпчику таблиці істинності.
Далі, керуючись зробленими записами в першому стовпчику таблиці, а також таблицями переходів і виходів абстрактного автомата (Таблиця 1, Таблиця 2), визначаємо на кожному такті (для кожного рядка Таблиці 13) пару абстрактних величин - абстрактний стан, в який перейде автомат на наступному такті роботі і абстрактний вихідний сигнал, який автомат має cформувати на даному такті роботи. Наприклад, для того ж першого рядка таблиці: пара , у відповідності з Таблицями 1,2 визначає: , . Отже, загалом в перший рядок першого стовпчика Таблиці 13 має бути записане відображення: . Аналогічно заповнюються інші рядки цього стовпчика.
Пара абстрактних величин , а також таблиці кодування станів автомата і вихідних сигналів (Таблиця 8, Таблиця 7), визначають коди в стовпчиках , , , таблиці істинності. Наприклад, для першого рядка Таблиці 13: пара абстрактних величин має значення , тому в стовпчики , записуємо код 01, яким ми закодували абстрактний стан (див. Таблицю 8), а в стовпчики , записуємо код 10, який відповідає абстрактному вихідному сигналу (див. Таблицю 7). Так само заповнюються інші рядки цих стовпчиків.
В стовпчик записуємо значення сигналу, який треба подати на інформаційний вхід першого вибраного нами елемента пам’яті (а ми вибрали D - тригер), щоб цей елемент пам’яті перейшов із стану в стан . Стовпці , вже заповнені, а значення для даного переходу вибираємо з таблиці переходів вибраного тригера (в нашому прикладі це Таблиця 9). Наприклад, для першого рядка Таблиці 13: в стовпчиках , маємо перехід 00. Такому переходу D - тригера відповідає значення інформаційного сигналу (див. Таблицю 9). Тому в стовпчику таблиці істинності, в першому рядку записуємо 0. Аналогічно заповнюються інші рядки стовпчика , а також стовпчики Таблиці 13, які відповідають інформаційним входам другого елемента пам’яті (для виконання функцій другого елемента пам’яті ми вибрали JK - тригер. Отже в першому рядку Таблиці 13, в стовпчиках , маємо перехід 01, якому відповідають (Таблиця 12) значення інформаційних сигналів - саме ці значення записуємо в стовпцях , ).
Зауваження.
В останніх чотирьох рядках першого стовпчика Таблиці 13 ставимо прочерки, тому що коду 11 (стовпці , ) не відповідає жодний з вхідних абстрактних сигналів (див. Таблицю 6). Відповідно в інших семи стовпцях цих рядків можуть бути будь-які значення - *.
Код абстрактних вхідних, вихідних сигналів і станів автомата є позиційним. Тому треба слідкувати за тим, щоб не сплутати і не поміняти місцями структурні змінні, значеннями яких кодуються відповідні абстрактні сигнали чи стани. Наприклад, якщо ми вибрали першим елементом пам’яті D - тригер, то саме його вихідному сигналу ставимо у відповідність структурну змінну Q1 - і в таблицях кодування і в таблиці істинності і в структурній схемі автомата. Відповідно вихідний сигнал JK - тригера позначаємо Q2 - і в таблицях кодування і в таблиці істинності і в структурній схемі автомата.
Після заповнення таблиці істинності переходимо до мінімізації отриманих логічних функцій. Таких функцій в нашому прикладі п’ять: - функція збудження першого елемента пам’яті; , - функції збудження другого елемента пам’яті; -функція першої структурної вихідної змінної, -функція другої структурної вихідної змінної. Всі ці логічні функції залежать від чотирьох логічних змінних: , , , . Для мінімізації скористаємося методом карт Карно - складаємо п’ять карт Карно для функцій чотирьох змінних, які заповнюємо за допомогою Таблиці 13 (Рис.1).
Після мінімізації отримаємо:
; ; ; (7) ; (8)
Побудова функціональної схеми автомата.
На основі отриманих виразів для логічних функцій збудження елементів пам’яті автомата і логічних функцій виходів автомата будуються: комбінаційна схема для формування логічних функцій збудження елементів пам’яті автомата і комбінаційна схема формування вихідних сигналів автомата. До побудованих комбінаційних схем підключаються елементи пам’яті. При цьому вживають заходів для синхронізації схеми автомата і забезпечення стійкості його роботи (в цифровому автоматі з пам’яттю наступні стани залежать від попередніх, тобто існують зворотні зв’язки. Тому як тільки тригери автомата переключаться, їх вихідні сигнали через кола зворотного зв’язку подадуться на входи збудження тригерів і вони знову можуть переключитися в наступний стан і т.д. Тому застосовують різні способи стабілізації роботи автомата, наприклад вводять тактуючий вхід, на який подають синхроімпульси. При цьому як елементи пам’яті використовують синхронні тригери, тактовані перепадом рівня тактового сигналу. Таким чином розводять в часі момент подачі вхідних сигналів автомата і момент спрацювання елементів пам’яті. Реалізуємо цей етап синтезу в межах Прикладу 2.
1
1
*
*
*
*
*
*
*
*
*
*
1
*
1
1
*
1
1
*
1
*
1
*
*
*
*
1
1
*
1
1
*
*
*
*
*
1
*
*
1
*
1
1
*
1
*
1
*
1
*
*
1
Рис.1
5-ий етап структурного синтезу - побудова функціональної схеми автомата.
На цьому - останньому - етапі синтезу цифрового автомата згідно Прикладу 2, скориставшись рівняннями (7), (8), побудуємо функціональну схему (Рис.2) автомата, робота якого описується абстрактною таблицею переходів (Таблиця 1) і абстрактною таблицею виходів (Таблиця 2). При цьому як елементи пам’яті вибираємо синхронні тригери, що тактуються фронтом тактового сигналу C.
Рис.2
2. ЗАВДАННЯ
2.1. Теоретична частина (виконується при підготовці до лабораторного заняття)
Ознайомитися з основними відомостями.
Визначити свій варіант таблиць переходів і виходів автомата.
Таблиця 14 Таблиця 15
Таблиця 16
Тип
тригера
000
001
010
011
100
101
110
111
першого ()
T
T
JK
JK
D
D
JK
D
другого ()
D
T
T
D
D
JK
JK
T
Для цього необхідно номер варіанта (задає викладач) перевести в двійкову систему числення і підставити шість розрядів отриманого двійкового числа в Таблиці 14, 15 (1 - молодший розряд).
3. На основі отриманих в п. 2 таблиць переходів і виходів та заданих Таблицею 16 типів елементарних автоматів, синтезувати структурну схему скінченного автомата.
2.2. Експериментальна частина
Синтезовану схему скінченного автомата побудувати в схемному редакторі САПР Foundation Series.
Проконтролювати правильність функціонування автомату за допомогою моделювальника САПР, визначивши значення вихідних сигналів і наступних станів для всіх наборів значень вхідних змінних і станів автомату.
Замалювати часові діаграми роботи схеми.
Зауваження.
Повний контроль функціонування автомата необхідно здійснювати не за таблицями виходів і переходів, а за таблицею істинності. Відповідно і схема автомата, яка передбачає можливість його моделювання (тестування), має ряд особливостей. Така схема будується виходячи з припущення, що в початковий момент часу автомат може знаходитися в будь-якому з можливих станів, тобто передбачається можливість асинхронного встановлення елементів пам’яті автомата в той чи інший початковий стан. Для реалізації такої можливості найпростіше вибрати тригери з входами асинхронного встановлення. Загалом схема автомата, яка забезпечує можливість його тестування, відрізняється від синтезованої структурної схеми автомата тільки схемами включення елементів пам’яті. Рекомендовані схеми включення тригерів різного типу наведено на Рис.3 (замість індексу і при побудові схем підставляють номер елемента пам’яті – 1 або 2). На Рисунку 3 назви входів і виходів, що є зовнішніми входами і виходами автомата, обведено контуром. Інші входи і виходи підключаються до комбінаційних схем автомата у відповідності з синтезованою структурною схемою. Наприклад, вихід тригера Qi підключено до виходу схеми (на Рис.3 обведено прямокутником). Крім того цей-же сигнал Qi може бути аргументом функцій збудження елементів пам’яті або логічних функцій вихідних структурних змінних автомата. Тому на Рис.3 показано ще один вихід Qi (не обведено контуром), сигнал з якого може подаватися на комбінаційні схеми автомата. Таким чином схема автомата буде мати такі входи і виходи:
- структурні входи, на які подається код вхідного сигналу;
- входи асинхронного встановлення першого і другого елементів пам’яті автомата в початковий стан - сигнали на цих входах мають відповідати тим, які фігурують в стовпчиках ,таблиці істинності;
- вхід подачі послідовності синхроімпульсів;
- структурні виходи, з яких знімається код вихідного сигналу;
- виходи елементів пам’яті автомата - сигнали на цих виходах при моделюванні мають відповідати тим, які фігурують в стовпчиках , таблиці істинності.
Для задання тестових сигналів на входах автомату при моделюванні рекомендується скористатись сигналами з виходів 5-ти тригерів віртуального 16-ти розрядного двійкового підсумовуючого лічильника. Виходи цього лічильника доступні у вікні стимулів Моделювальника САПР. Якщо через B1 позначити прямий вихід молодшого тригера цього лічильника, то на входи автомата подаються:
B1 - на вхід автомата;
B2 - на вхід автомата;
B3 - на вхід автомата;
B4 - на вхід автомата;
B5 - на вхід автомата.
Контроль функціонування автомата здійснюється за таблицею істинності і часовими діаграмами, отриманими при моделюванні. При низькому рівні сигналу на вході перевіряють код вихідного сигналу автомата на кожному -ому такті (виходи ). При високому рівні сигналу на вході перевіряють стан автомата на такті (виходи автомата).
Після тестування схеми, для забезпечення її правильної роботи згідно таблиць виходів та переходів, необхідно розірвати кола встановлення елементів пам’яті в початковий стан.
Зміст звіту
Назва і мета роботи.
Всі матеріали, що стосуються синтезу цифрового автомата у відповідності з теоретичною частиною завдання.
Часові діаграми роботи цифрового автомату, що досліджувався в лабораторії.
Короткі висновки за результатами роботи.
Література:
Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ. Теория и проектирование. - К.: Вища шк., 1989.
Б.Є.Рицар. Цифрова техніка. - К.: НМК ВО, 1991.
Самофалов К.Г., Романкевич А.М., Валуйский В.Н., Каневский Ю.С., Пинкевич М.М. Прикладная теория цифрових автоматов.- К.: Вища шк. Головное изд-во, 1987.- 375с.
Рис.3. Схеми включення елементів пам’яті
02.12.2018 16:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора