Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Білет 4
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2011
Тип роботи:
Державний іспит
Предмет:
Інші
Варіант:
4
Частина тексту файла (без зображень, графіків і формул):
Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура.
Цифровий автомат цей пристрій, що характеризується набором деяких внутрішніх станів A = {a1(t), a2(t), ..., an(t)}= у які воно потрапляє під впливом вхідних сигналів і команд програми рішення задачі.
Хай є автомат з одним входом і одним виходом:
A = {ai(t)}
z(t)
(t)
Рис.1.3. Цифровий автомат
Цифрові автомати можуть бути з "жорсткою", або схемної, логікою і з логікою, що зберігається в пам'яті. Розрізняють два класи автоматів: асинхронні і синхронні.
Синхронний автомат характеризується тим, що функціонує під управлінням тактових (або що синхронізують) сигналів - ТС, з постійною тривалістю tТС і постійною частотою fТС, якщо квантування часу рівномірне. Такт (квант) часу ti поєднується з фронтом i-того сигналу ТС. Вхідні сигнали можуть впливати на автомат лише за наявності сигналу ТС і не змінюються протягом tТС. Період проходження сигналів ТС повинен бути більше або рівний часу, який необхідний реальному автомату для переходу з одного стану в інший. Коли розглядається абстрактний автомат, то вважається, що зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними ТС, а вихідні сигнали формуються по фронту чергового ТС.асинхронных
В автоматах тривалість інтервалу часу, протягом якого залишається незмінним стан вхідних сигналів, є величиною змінної і визначається часом, який необхідний автомату для установки відповідних вихідних сигналів і завершення переходу в новий стан. Отже, асинхронний автомат повинен формувати яким-небудь відповідним способом сигнал про завершення чергового такту, по якому поточні вхідні сигнали можуть бути зняті, після чого може початися наступний такт, тобто можливо надходження нових вхідних сигналів.
Як наголошувалося у розділі 1, абстрактний автомат з одним входом і одним виходом можна представити таким чином:
A
X
Y
Для завдання кінцевого автомата фіксуються три кінцеві множини (алфавіту): - безліч можливих вхідних сигналів: X = {x1, x2, ..., xm};
- безліч можливих вихідних сигналів: Y = {y1, y2, ..., yk};
- безліч можливих внутрішніх станів автомата: A = {a0, a1, ..., an}.
На цих множинах задають двох логічних операторів: - функцію переходів f, що визначає стан автомата а(t + 1) у момент дискретного часу t + 1 залежно від стану автомата а(t) і значення вхідного сигналу x(t) у момент часу t: а(t + 1)= f[а(t), x(t)]; (10.1) - функцію виходів , що визначає залежність вихідного сигналу автомата у(t) від стану автомата а(t) і вхідного сигналу x(t) у момент часу t: y(t) = [a(t), x(t)]. (10.2) Крім того, на безлічі станів автомата фіксують один з внутрішніх станів а0 як початковий стан. Поняття стан автомата використовується для опису систем, вихідні сигнали яких залежать не тільки від вхідних сигналів в даний момент часу, але і від деякої передісторії, тобто сигналів, які поступали на входи системи раніше. Отже, цифрові автомати відносяться до последовательностним схем, які, як вже наголошувалося, володіють пам'яттю. Поняття стан автомата відповідає деякій пам'яті про минуле, тому введення цього поняття дозволяє усунути час як явну змінну і виразити вихідні сигнали як функцію станів і вхідних сигналів. Роботу абстрактного автомата слід розглядати стосовно конкретних інтервалів часу, оскільки кожному інтервалу дискретності t відповідатиме свій вихідний сигнал у(t). Отже, функціонування автомата розглядається через дискретні інтервали часу кінцевої тривалості. У абстрактній теорії цифрових автоматів вважається, що вхідні сигнали впливають на синхронний автомат у момент початку кожного i-того інтервалу (кванта) часу, виділеного відповідним синхроімпульсом (тактом), а зміна внутрішніх станів автомата відбувається в інтервали часу між суміжними синхроімпульсами, коли немає дії вхідних сигналів. Оператори, що описують роботу автомата, звичайно задають таблицею переходів і таблицею виходів. У таблиці переходів показують в який стан потрапляє автомат від того або іншого вхідного сигналу. У таблиці виходів показують який вихідний сигнал генерує автомат залежно від типу вхідного сигналу і поточного стану автомата. Наприклад, розглянемо таблиці переходів і виходів деякого автомата.
Таблиця переходів автомата Таблиця виходів автомата
У клітку таблиці переходів, що знаходиться на перетині стовпця з буквою аi і рядки з буквою xj, записується стан автомата, в який він переходить із стану аi при подачі на вхід сигналу xj. У аналогічну клітку таблиці виходів записується вихідний сигнал yi, який формується автоматом при такому переході. Оператори переходів і виходів можуть бути задані однією таблицею, по якій однозначно визначаються переходи і виходи автомата.
Таблиця переходів і виходів автомата
велику наочність забезпечує завдання кінцевих автоматів за допомогою графів або діаграм станів.
Граф автомата складається з вузлів, сполучених гілками. Вузли (кухлі на схемі графа) ототожнюють внутрішні стани автомата. Кожна гілка графа, тобто орієнтована лінія, стрілка якої указує наступний стан автомата, наголошується вхідним сигналом, що викликає в автоматі відповідний даній гілці перехід, і вихідним сигналом, який виникає при цьому переході. Вхідний і відповідний йому вихідний сигнали розділяються на кресленні комою або косою межею. Якщо деякий вхідний сигнал не міняє стану автомата, то відповідна гілка замикається на кружку (вузлі), з якого вона виходить. Оскільки таблиця станів і граф (діаграма) станів несуть одну і ту ж інформацію, їх можна перетворити один в одного. Кожен стан представляється кружком, а кожен елемент таблиці перетвориться у відрізок орієнтованої лінії, що сполучає відповідні кухлі. Процедура зворотного перетворення очевидна. В даний час в класі синхронних атоматов розглядають, в основному, два типу автоматів: автомат Милі і автомат Мура. Графа атомата Милі, заданого вищенаведеними таблицями, відображений на мал. 10.1. Закон функціонування автоматів Милі може бути заданий таким чином: а(t + 1)= f[а(t), x(t)]; y(t) = [a(t), x(t)], де t = 1, 2 ..... Відмітна особливість автоматів Милі полягає в тому, що їх вихідні сигнали в деякий момент часу не залежать як від стану автомата, так і від значення вхідного сигналу в цей же момент часу.
Мал. 10.1. Граф автомата Милі.
У автоматів Мура вихідні сигнали у момент часу t однозначно визначаються станом автомата в цей же момент часу і в явному вигляді не залежать від значення вхідних сигналів xi(t). Функції переходів і виходів автомата Мура, заданого на безлічі вхідних сигналів X, безлічі внутрішніх станів A = {a0, a1,,an} і безлічі вихідних сигналів Y, можна записати у вигляді а(t + 1)= f[а(t), x(t)] (10.3) y(t) = [a(t)]. (10.4) цих операторів зручно задавати відміченою таблицею переходів. Такі таблиці будуються так само, як і таблиці переходів автомата Милі, але над символами кожного внутрішнього стану записуються вихідні сигнали, які видає автомат в даному стані. Відмічена таблиця переходів автомата
Граф автомата Мура, заданого цією таблицею, приведений на мал. 10.2. На цьому малюнку стану автомата позначаються сиволамі bi. На графах автомата Мура значення вихідних сигналів записуються біля вузлів.
Між автоматами Милі і Мура існує відповідність, що дозволяє перетворити закон функціонування одного з них в іншій або назад. Автомат Мура можна розглядати як окремий випадок автомата Милі, маючи на увазі, що послідовність станів виходів автомата Милі випереджає на один такт послідовність станів виходів автомата Мура, т.е відмінність між автоматами Милі і Мура полягає в тому, що в автоматах Милі стан виходу виникає одночасно із зухвалим його станом входу, а в автоматах Мура - із затримкою на один такт, т.к в автоматах Мура вхідні сигнали змінюють тільки стан автомата. Крім автоматів Милі і Мура виділяють ще, так званий, суміщений автомат - С-автомат. Абстрактний С-автомат можна представити у вигляді пристрою з одним входом, на який поступають вхідні сигнали X, і двома виходами, на яких з'являються вихідні сигнали Y і U.
A
Y мал. 10.3
X
U
Тут X - вхідний алфавіт; A - безліч станів; Y - вихідний алфавіт першого типа; U = {u1(t) ... um(t)} - вихідний алфавіт другого типа. Відмінність С-автомата від моделей Милі і Мура полягає в тому, що він одночасно реалізує дві функції виходів 1 і 2, кожна з яких характерна для цих моделей окремо. Цей автомат можна описати наступною системою рівнянь:
а(t+1)= f [а(t), x(t)]; (10.5) y(t) = 1[a(t), x(t)]; u(t) = 2[a(t)]. Вихідний сигнал u = 2 (as) виділяється весь час, поки автомат знаходиться в стані as. Вихідний сигнал yk = 1(as, xn) видається під час дії вхідного сигналу xn при знаходженні автомата в стані as. Від С-автомата легко перейти до автоматів Милі або Мура (з урахуванням можливих зміщень в часі на один такт), так само як можлива трансформація автомата Милі в автомат Мура і навпаки.
Принстонська та гарвардська архітектури.
Пригадаємо принципи, що закладено до принстонської (університет міста Princeton, США, де працював Нойман) архітектури та гарвардської (університет міста Harvard, США) архітектури. Перша архітектура має спільну головну пам’ять, де зберігаються коди даних та коди програм. Відрізнення одних кодів від інших виконують контекстно. Друга архітектура містить дві відокремлені пам’яті, одну – для даних, іншу – для програм.
Необхідність використання гарвардської архітектури можна пояснити так. Ядро комп’ютера Ноймана утворено процесором та головною пам’яттю. Бажано аби обидві компоненти ядра не пригальмовували один одного, тобто працювали з рівною швидкодію. На практиці вузол пам’яті є значно (на два/три порядки) повільнішим від процесора і ця прірва у швидкодії з прогресом технологій лише зростає.
Подолати прірву можна структурними методами, збільшуючи смугу (пропускання) пам’яті. Саме цей підхід реалізує гарвардська архітектура з двома запам’ятовувальними пристроями. Зрозуміло, що тут паралельно виконують операції вибирання інструкцій програми, з одного боку, а з другого – вибирання та запис кодів даних і результатів обчислень.
Проте швидкі машини гарвардської архітектури не дозволяють розроблювати для себе програми. Це за них виконують засобами кросових технологій машини принстонської архітектури.
Зрозуміло, що бажано створити машину з дуальною архітектурою, яка водночас запозичує нову якість – швидкодію від гарвардської архітектури та стандартну парадигму розробки програм від принстонської архітектури. Злиття двох архітектур виконують на рівні внутрішньої кеш-пам’яті процесора, у спосіб поділу кеша на кеш даних та кеш інструкцій. Зазначене ілюструє поданий вище рисунок. Злиттям архітектур програмісту надано зручність програмних технологій принстонської архітектури, а процесор відчуває гарвардську архітектуру та значно менше пригальмовується з боку головної пам’яті. Реально ситуація є більш складною, оскільки замість суто гарвардської архітектури застосовують її модифікацію, коли пам’ять програм містить частину кодів даних.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора