1. Структура ЦОМ, представлення ЦОМ як конечного автомата ЦОМ – цифрові обчислювальні машини або обчислювальні машини дискретної дії – працюють з інформацією, представленою в дискретній, а точніше в цифровій формі. Кінцевий(конечний) автомат - в теорії алгоритмів математична абстракція, що дозволяє описувати шляхи зміни стану об'єкта в залежності від його поточного стану і вхідних даних, за умови, що загальна можлива кількість станів скінченна. Кінцевий автомат є окремим випадком абстрактного автомата.^ 2. Модель фон Неймана. Модель фон Неймана (von Neumann) служила базовою моделлю при проектуванні всіх сучасних комп'ютерних систем Модель складається з чотирьох ключових компонентів: Система пам'яті, яка зберігає як команди, так і дані. Відома як система з програмою, яка зберігається. Доступ до цієї пам'яті здійснюється за допомогою регістра адреса (memory address register, MAR), куди підсистема пам'яті поміщає адрес елементу пам'яті, і регістра даних (memory data register, MDR), куди вона поміщає дані з осередку з вказаною адресою. Детальніше підсистема пам'яті обговорюється в розділі 4. Принаймні один блок обробки даних, найбільш відомий як арифметико-логічний пристрій (ALU). Ці блоки частіше називають центральними процесорами (CPU) .1 Цей блок відповідає за виконання всіх команд. Процесор також має невеликий об'єм пам'яті, званий набором регістрів. Обговорення процесорів буде докладніше. Блок управління, яке відповідає за операції між компонентами моделі. Включає лічильник команд, який містить наступну команду для завантаження, і регістр команд, в якому знаходиться поточна команда. Особливості моделі управління виходять за рамки цієї книги. Системі необхідний незалежний спосіб зберігання дані, а також видачі їх користувачеві і ухвалення вхідних даних. Це прерогатива підсистеми введення-виводу (I/O). головним чином стосується дискових накопичувачів як механізмів для введення-виводу.^ 3. представлення інформації в цифрових автоматах Інформація на зовнішньому світі представляється в безперервному або дискретному вигляді. Усередині ЕОМ інформація завжди представляється у вигляді чисел, записаних в тій або іншій системі числення. Якщо ж йдеться про текстовій інформації, то зазвичай вона кодується також за допомогою чисел. Питання про вибір системи числення для цифрового автомата — одне з найважливіших питань проектування як алгоритмів функціонування окремих пристроїв, так і розрахунок технічних характеристик цього автомата Система числення — сукупність прийомів і правил для запису чисел цифровими знаками. Найбільш відома десяткова система числення, в якій для запису чисел використовуються цифри О, 1, ..., 9. Будь-яка призначена для практичного використання система числення повинна забезпечувати: можливість представлення будь-якого числа в даному діапазоні величин; єдність предствлення (кожній комбінації символів повинна відповідати одна і лише одна величина); простоту операції числами. Всі системи представлення чисел ділять на позиційних і непозиційних. Непозиційна система числення — система, для якої значення символу не залежить від його положення в числі. Принципи побудови таких систем не складні. Для їх освіти використовують в основному операції складання і віднімання.Позиційна система числення — система, що задовольняє рівності (3.2). Природна позиційна система числення має місце, якщо q — ціле, позитивне число. У позиційній системі числення значення цифри визначається її положенням в числі: один і той же знак приймає різне значення. Наприклад, в десятковому числі 222 перша цифра справа означає дві одиниці, сусідня з нею — два десятки, а ліва — дві сотні.Поняття про алфавіт 5 поняття про системи числення Сукупність прийомів та правил найменування й позначення чисел називається системою числення. Звичайною для нас і загальноприйнятою є позиційна десяткова система числення. Як умовні знаки для запису чисел вживаються цифри. Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюється, називається непозиційною. Система числення, в якій значення кожної цифри залежить від місця в послідовності цифр у записі числа, називається позиційною. Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел. Добре відомим прикладом непозиційної системи числення є римська система, в якій роль цифр відіграють букви алфавіту: І - один, V - п'ять, Х - десять, С - сто, Z - п'ятдесят, D -п'ятсот, М - тисяча. Наприклад, 324 = СССХХІV. У непозиційній системі числення незручно й складно виконувати арифметичні операції.^ 7. Форми представлення чисел с фіксованою та плаваючими точкамиПредставлення чисел з фіксованою комою (точкою). Природна форма подання числа в цифровому автоматі характеризується тим, що положення його розрядів у автоматному зображенні залишається завжди постійним незалежно від величини самого числа. Існує також інша назва цієї форми запису чисел - представлення чисел з фіксованою комою (точкою).Щоб спростити функціонування цифрового автомата, необхідно обмежити вхідну інформацію якоюсь однією областю чисел (на вхід автомата бажано подавати або цілі числа, або правильні дроби, або будь-які числа), що дозволить визначити значення масштабного коефіцієнта КА - Наприклад, якщо на вхід цифрового автомата надходять тільки правильні дроби, то -1де [A] ф - машинне зображення числа для форми подання з фіксованою комою. Тоді число А буде представлено у вигляді А— [А]фКа- Величина масштабного коефіцієнта КА, що задовольняє умові (1), визначає той факт, що в машинному зображенні кома завжди стоїть після цілої частини дробу, тобто перед її старшим розрядом. Отже, можна зберігати тільки дробову частина числа (цифрову частина), а в розряді цілої частини писати додаткову інформацію. Представлення чисел в формі фіксованої точки.^ Подання чисел у формі з плаваючою комою. У нормальній формі Ан =mApAде тА - мантиса числа А; pA- порядок числа А (характеристика числа). Як видно з раніше викладеного, таке подання чисел не однозначно; для визначеності звичайно вводять деякі обмеження. Найбільш поширене і зручно для представлення в ЕОМ обмеження виду q-1≤│mA│ де q — основні системи числення.Нормалізована форма представлення чисел - форма представлення чисел, для якої справедливо умова (2).Оскільки в цьому випадку абсолютне значення мантиси лежить в межах від q -1 до 1 – q -n де п - кількість розрядів для зображення мантиси без знака, положення розрядів числа в його автоматному зображенні не постійно. Тому таку форму подання чисел називають також формою подання з плаваючою комою. Формат машинного зображення числа з плаваючою комою повинен містити знакові частини та поля для мантиси і «порядку» (мал. 2, а). Виділяються спеціальні розряди для зображення знака числа (мантиси) і знака порядку або характеристики (мал. 2, а, б). Кодування знаків залишається таким же, як було з фіксованою комою. Поскольку в этом случае абсолютное значение мантиссы лежит в пределах от q -1 до 1 – q -n где п — количество разрядов для изображения мантиссы без знака, положение разрядов числа в его автоматном изображении не постоянно. Поэтому такую форму представления чисел называют также формой представления с плавающей запятой. Формат машинного изображения числа с плавающей запятой должен содержать знаковые части и поля для мантиссы и порядка (рис. 3.3, а). Выделяются специальные разряды для изображения знака числа (мантиссы) и знака порядка или характеристики (рис. 3.3, а, б). Кодирование знаков остается таким же, как было с фиксированной запятой.Рис 2. Представлення чисел в формі з плаваючою точкою.^ 8. Точність представлення чисел в ЦОМ. Погрішності виконання арифметичних операщй. Представлення числової інформації в цифровому автоматі, як правило, спричиняє за собою появу погрішностей (помилок), величина яких залежить ось форми представлення чисел і ось довжини розрядної сітки автомата. Абсолютна погрішність уявлення — різниця між дійсним значенням вхідної величини Л і її значенням, отриманим з машинного зображення Ам, тобто А [Л] = А — Ам. Відносна погрішність уявлення — величина^ 8[А]=А[А]/АК. (3.30) Вхідні величини незалежно ось кількості значущих цифр можуть містити грубі помилки, що виникають із-за друкарських помилок, помилкових відліків показаний яких-небудь приладів, некоректною, постановки завдання або відсутності повнішої і точнішої інформації. Наприклад, часто приймають я =3,14. Проте ця величина може бути отримана з вищою точністю (800 знаків і більш). Якщо прийняти, що точне значення л= 3,14159265, то абсолютна погрішність рівна А [я] =0,00159265. Часто деяка величина в одній системі числення має кінцеве значення, а в іншій системі числення стає нескінченною величиною, наприклад, дріб '/ю має кінцеве десяткове уявлення, але, будучи переведена в двійкову систему числення, стає нескінченним дробом 0,0001100110011... Отже, при перекладі чисел з однієї системи числення в іншу неминуче виникають погрішності, оцінити які нескрутно, якщо відомі дійсні значення вхідних чисел. Відповідно до (3.19) числа зображаються в машині у вигляді Ач—[а~\ Кл, де масштабний коефіцієнт Кл вибирають так, щоб абсолютне значення машинного зображення числа А в системі числення з підставою ц = 2 було завжди менше 1: Ач = Кл [а.q~x + а_2q2 + - + a-nq-n + ...]. Оскільки довжина розрядної сітки автомата рівна п двійкових розрядів після коми, і абсолютна погрішність перекладу десяткової інформації в систему з підставою q буде А [Л] = а(n+1) q-(n+1)+. + а-(n+s) q-(n+s)+ ...=_ alql. (З.31) Максимальна погрішність перекладу десяткової інформації в двійкову не перевищуватиме одиниці молодшого розряду розрядної сітки автомата. Мінімальна погрішність перекладу рівна нулю. Усереднена абсолютна погрішність перекладу чисел в двійкову систему числення А [Л] = (0 + 2~")/2 = 0,5 • 2гп. Для представлення чисел у формі з фіксованою комою абсолютне значення машинного зображення числа 2-n Следовательно, относительные погрешности представления для минимального значения числа Для ЭВМ, как правило, п =16÷64, поэтому 1>>2-n, откуда Аналогічно, для максимального значення: З (3.34) видно, що погрішності представлення малих чисел у формі з фіксованою комою можуть бути дуже значними. Для представлення чисел у формі з плаваючою комою абсолютне значення мантиси Погрішність (3.32) — погрішність мантиси. Для знаходження погрішності представлення числа у формі з плаваючою комою величину цієї погрішності треба помножить на величину порядку числа рл:9 .Основні положення алгебри логікиОсновне поняття алгебри логіки — вислів. Вислів — деяка пропозиція, про яку можна стверджувати, що воно достеменне або лвжно. Наприклад, вислів «Земля — це планета Сонячної системи» істинно, а про вислів «на вулиці йде дбждь» можна сказати, істинно воно або помилково, якщо вказані додаткові відомості про погоду в даний момент. Будь-який вислів можна позначити символом х і вважати, що х=1, якщо вислів достеменний, а х = О— якщо вислів помилковий. Логічна функція (функція алгебри логіки) — функція 1(х\, Х2 ???, хп), що набуває значення, рівного нулю або одиниці на наборі логічних змінних х\, хч ..., хп. Логічні функції від однієї змінної представлені в таблиці. 10.1.Відповідно до введених визначень функція }\(х) є абсолютно достеменною (константа одиниці), а функція И*) — абсолютно помилковою функцією (константа нуля). Функція /з(х), що повторює значення логічної змінної, — тотожна функція (}3(х)= х), а функція /ч(*)> що набуває значень, зворотних значенням х, — логичеськбе_ заперечення, або функція НЕ (^(х) =~1д: = х).1>^ 10.Мінімізація функцій алгебри логіки. Методи мінімізації Метод Куайна — Мак-Класкі (метод простих імлікант) - табличний метод мінімізації булевих функцій розроблений Уілардом Куайном і Едвардом Мак-Класкі. Функціонально ідентичний карті Карно, але таблична форма робить його більш ефективним для використання в комп'ютерних алгоритмах. Карта Карно (K-карта скорчено), поліпшення зроблене Морісом Карно в 1953 Діаграм Вейча винайдених Едвардом Вейчем в 1952 , це метод спрощення виразів булевої алгебри. Карта Карно зменшує потребу в обширних обчисленнях, використовуючи перевагу людської можливості розпізнання шаблонів, дозволяє швидке розпізнавання і виключення потенційних станів гонитви. В карті Карно булеві змінні переносяться (зазвичай з таблиці істинності) і впорядковуються згідно з принципами кода Грея, в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2n комірок (n=0,1,2,3...)[1]. Далі, працюючи з цими групами, отримують мінімізовану ДНФ.^ 11 Мінімізація систем функцій алгебри логікиПеретворення логічних функцій з метою спрощення їх аналітичного подання називаються мінімізацією. Існують два напрямки мінімізації: 1. Найкоротша форма запису (мета - мінімізувати ранг кожного терма). При цьому виходять найкоротші форми КДНФ, ККНФ, КПНФ. 2. Отримання мінімальної форми запису (мета - отримання мінімального числа символів для запису всієї функції відразу). Існують різні методи мінімізації: 1. Метод безпосередніх перетворень логічних функцій. (1.1) При застосуванні даного методу: а) Записуються ДСНФ логічних функцій б) Форма перетворюється і спрощується з використанням аксіом алгебри логіки. При цьому, зокрема, виявляються у вихідному ДСНФ так звані сусідні min-терми, в яких є по одній не збігається змінної. Метод невизначених коефіцієнтів. (1.2) Суть методу полягає в перетворенні ДСНФ в МДНФ. На підставі теореми Жігалкіна будь-яку ФАЛ можна представити у вигляді трьох змінних змінних Суть методу зводиться до того, щоб перетворити ДСНФ в МДНФ.Завдання мінімізації за методом Квайна полягає в попарному порівнянні імплікант, що входять до ДСНФ з метою виявлення можливості склеювання з якоїсь пременной так: Таким чином, можна знизити ранг термів. Процедура проводиться до тих пір, поки не залишається жодного терма, що допускає склеювання з іншим. Причому склеюючі терми позначаються *. Для цього: 1. Складаються таблиці, в рядках яких пишуться знайдені первинні імпліканти, а в стовпцях вказуються терми первинної ФАЛ. 2. Клітини цієї таблиці зазначаються в тому випадку, якщо первинна імпліканта входить до складу якого-небудь первинного терма. 3. Завдання спрощення зводиться до знаходження такого мінімальної кількості імплікант, які покривають всі стовпці. Метод мінімізують карт (для ДСНФ і КСНФ). (1.5) Одним із способів графічного представлення бульових функцій від невеликого числа змінних є карти Карно. Їхній різновид - карти Вейча, які будуються як розгортки кубів на площині, при цьому вершини куба представляються клітинами карти, координати яких співпадають з координатами відповідних вершин куба. Для ДСНФ одиниці ставляться в клітці, відповідної номеру набору, на якому значення функції дорівнює одиниці, а нуль не ставиться, а для КСНФ - навпаки. Карти Карно використовуються для ручної мінімізації функцій алгебри логіки при невеликій кількості змінних. Правило мінімізації: склеювання піддаються 2,4,8,16, клітин і клітини, що лежать на кордоні карти. При кількості змінних 5 і більше відобразити графічно функцію у вигляді єдиної плоскої карти неможливо. Тоді будують комбіновані карти, що складаються з сукупності більш простих карт. Процедура мінімізації тоді полягає в тому, що спочатку знаходиться мінімальна форма 4-х мірних кубів (карт), а потім, розширюючи поняття сусідніх клітин, відшукують min-терми для сукупності карт. Причому сусідніми клітинами є клітини, що збігаються при поєднанні карт поворотом навколо спільного ребра.12. в чому полягає аналіз та синтез КС?^ Призначення аналізу і синтезу комбінаційних схем.Технічним аналогом булевої функції в обчислювальній техніці є, так звана, комбінаційна схема, на вхід якої поступають і з виходу знімаються електричні сигнали у вигляді одного з рівнів напруги, що відповідають значенням логічного 0 і логічної 1. Для з'ясування, що ж таке комбінаційна схема, розглянемо схему S, що має m входів і n виходів (мал. 1). На її входи можуть бути подані набори значень вхідних змінних Xi {0,1} , а на виходах формуються вихідні змінні Yj{0,1} .Схема S називається комбінаційною, якщо кожну з n функцій її виходів Y1,Y2 ..., Yn можна представити як булеву функцію вхідних змінних X1, X2 ..., Xm. Комбінаційна схема описується за допомогою системи рівнянь (1), де Fi – булева функція.(1) Як випливає з визначення комбінаційної схеми, значення вихідних змінних Yj в довільний момент часу однозначно визначаються значеннями вхідних змінних Xi. Структурно комбінаційна схема може бути представлена як сукупність елементарних логічних схем – логічних елементів (ЛЕ). ЛЕ виконують над вхідними змінними елементарні логічні операції типу І-НЕ, І, ^ АБО, АБО-НЕ і т.д. Число входів логічного елемента відповідає числу аргументів відтворюваної ним булевої функції. Графічне зображення комбінаційної схеми, при якому показані зв'язки між різними елементами, а самі елементи представлені умовними позначеннями, називається функціональною схемою. В ході розробки комбінаційних схем доводиться вирішувати задачі аналізу і синтезу.Задача аналізу полягає у визначенні статичних і динамічних властивостей комбінаційної схеми. В статиці визначаються булеві функції, реалізовувані комбінаційною схемою по відомій їй структурі. В динаміці розглядається здатність надійного функціонування схеми в перехідних процесах при зміні значень змінних на входах схеми, тобто визначається наявність на виходах схеми можливих небажаних імпульсних сигналів, які не виходять безпосередньо з виразів для булевих функцій, реалізовуваних схемою.Задача синтезу полягає в побудові із заданого набору логічних елементів комбінаційної схеми, що реалізовує задану систему булевих функцій. Вирішення задачі синтезу не є однозначним, можна запропонувати різні варіанти комбінаційних схем, що реалізовують одну і ту ж систему булевих функцій, але відрізняються по тих або інших параметрах. Розробник комбінаційних схем з цієї множинаі варіантів вибирає один, виходячи з додаткових критеріїв: мінімальної кількості логічних елементів, необхідних для реалізації схеми, максимальної швидкодії і т.д. Існують різні методи синтезу комбінаційних схем, серед яких найбільш розроблений канонічний метод.^ 13. які критерії якості комбінаційних схем. Технічним аналогом булевої функції в обчислювальній техніці є, так звана, комбінаційна схема, на вхід якої поступають і з виходу знімаються електричні сигнали у вигляді одного з рівнів напруги, що відповідають значенням логічного 0 і логічної 1. Структурно комбінаційна схема може бути представлена як сукупність елементарних логічних схем – логічних елементів (ЛЕ). ЛЕ виконують над вхідними змінними елементарні логічні операції типу І-НЕ, І, ^ АБО, АБО-НЕ і т.д. Число входів логічного елемента відповідає числу аргументів відтворюваної ним булевої функції. Графічне зображення комбінаційної схеми, при якому показані зв'язки між різними елементами, а самі елементи представлені умовними позначеннями, називається функціональною схемою.Складність схеми оцінюється кількістю устаткування, що складає схему. При розробці схем на основі конкретної елементної бази кількість устаткування звичайно вимірюється числом корпусів (модулів) інтегральних мікросхем, що використовуються в схемі. В теоретичних розробках орієнтуються на довільну елементну базу і тому для оцінки витрат устаткування використовується оцінка складності схем по Квайну.Складність (ціна) по Квайну визначається сумарним числом входів логічних елементів у складі схеми. При такій оцінці одиниця складності – один вхід логічного елемента. Ціна інверсного входу звичайно приймається рівною двом. Такий підхід до оцінки складності виправданий з наступних причин: складність схеми легко обчислюється по булевих функціях, на основі яких будується схема: для ДНФ складність схеми рівна сумі кількості букв,(букві із знаком заперечення відповідає ціна 2), і кількості знаків диз'юнкції, збільшеної на 1 для кожного диз'юнктивного виразу. всі класичні методи мінімізації булевих функцій забезпечують мінімальність схеми саме в значенні ціни по Квайну. Практика показує, що схема з мінімальною ціною по Квайну звичайно реалізується якнайменшим числом конструктивних елементів – корпусів інтегральних мікросхем.Швидкодія комбінаційної схеми оцінюється максимальною затримкою сигналу при проходженні його від входу схеми до виходу, тобто визначається проміжком часу від моменту надходження вхідних сигналів до моменту встановлення відповідних значень вихідних. Затримка сигналу кратна числу елементів, через які проходить сигнал від входу до виходу схеми. Тому швидкодія схеми характеризується значенням r, де - затримка сигналу на одному елементі. Значення r визначається кількістю рівнів комбінаційної схеми, яка розраховується таким чином. Входам КС приписується рівень нульової. Логічні елементи, пов'язані тільки з входами схеми відносяться до першого рівня . Елемент відноситься до рівня k, якщо він зв'язаний по входах з елементами рівнів k-1, k-2, і т.д. Максимальний рівень елементів r визначає кількість рівнів КС, і називається рангом схеми. Приклад визначення рангу r схеми приведений на рисунку 6.^ 14. Кінцеві автомати. Кінцевий автомат — в теорії алгоритмів математична абстракція, що дозволяє описувати шляхи зміни стану об'єкту в залежності ось його поточного стану і вхідних даних, за умови, що загальна можлива кількість станів кінцева. Кінцевий автомат є окремим випадком абстрактного автомата. Існують різні варіанти завдання кінцевого автомата. Наприклад, кінцевий автомат може бути заданий за допомогою п'яти параметрів: M=(Q,_},q0,F), ду: Q — кінцева безліч станів автомата; q0 — початковий стан автомата (q0 є Q); F — безліч завершуючих (або що допускають) станів, таких що F_Q; _ — допустимий вхідний алфавіт (кінцева безліч допустимих вхідних символів), з якого формуються терміни, які прочитуються автоматом; } — задано відображення безлічі Qx_ в безліч P(Q) підмножин Q: _ }:Qx_>P(Q)_ (іноді } називають функцією переходів автомата)._ Автомат починає роботу в змозі q0, прочитуючи по одному символу вхідної терміни. Лічений символ переводить автомат в те, що нове складається з Q відповідно до функції переходів. Якщо після закінчення прочитання вхідного слова (ланцюжки символів) автомат опиняється в одному з допускаючих станів, то слово «приймається» автоматом. В цьому випадку говорять, що оний належить мові даного автомата. Інакше слово «відкидається». Кінцеві автомати широко використовуються на практиці, наприклад в синтаксичних, лексичних аналізаторах, і тестуванні програмного забезпечення на основі моделей.Інші способи опису Діаграма станів (або іноді граф переходів) — графічне представлення безлічі станів і функції переходів. Навантажений однонаправлений граф, вершини якого — стани АЛЕ, дуги — переходи з одного стану в інше, а навантаження — символи, при яких здійснюється даний перехід. Якщо перехід з полягає q1 в q2 може бути здійснений при появі одного з декількох символів, то над дугою повинні бути надписані всі вони. Таблиця переходів — табличне представлення функції }. Зазвичай в такій таблиці кожному рядку відповідає один стан, а стовпцю — один допустимий вхідний символ. У осередку на перетині терміни і стовпця записується дія, яку повинен виконати автомат, якщо за ситуації, коли он знаходився в даному перебуванні на вході он отримав даний символ._Детермінована Кінцеві автомати підрозділяються на детермінованих і недетермінованих. Детермінованим кінцевим автоматом (ДКА) називається такий автомат, в якому для кожної послідовності вхідних символів існує лише один стан, в який автомат може перейти з поточного. Недетермінований кінцевий автомат (НКА) є узагальненням детермінованого. Недетермінованість автоматів досягається двома способами: Існує теорема, яка свідчить, що «Будь-який недетермінований кінцевий автомат може бути перетворений в детермінований так, щоб їх мови співпадали» (такі автомати називаються еквівалентними). Проте, оскільки кількість полягають в еквівалентному ДКА у гіршому разі росте експоненціально із зростанням кількості станів початкового НКА, на практиці подібна детерминизация не завжди можлива. Крім того, кінцеві автомати з виходом в загальному випадку не піддаються детерминизации. Через останні два зауваження, не дивлячись на велику складність недетермінованих кінцевих автоматів, для завдань, пов'язаних з обробкою тексту, переважно застосовуються саме НКА.^ Автомати і регулярні мови Для автомата можна визначити мову (безліч слів) в алфавіті _, який он представляє — так називається безліч слів, при введенні яких автомат переходить з початкового стану в один із станів безлічі F. Теорема Клини свідчить, що клас мов, уявних кінцевими автоматами, співпадає з класом регулярних мов. Крім того цей клас співпадає з класом мов, які задаються регулярними граматиками. Спеціалізовані мови програмування Мова послідовних функціональних схем SFC (Sequential Function Chart) - графічна мова програмування широко використовується для програмування промислових логічних контроллерів (ПЛК). У SFC програма описується у вигляді схематичної послідовності кроків, об'єднаних переходами.^ 15. Автомати Мілі і МураОсновні положення теорії цифрових автоматів Згідно теорії автоматів цифровим автоматом називається последовательностная схема, яка має набір станів, що позначаються зазвичай A 1, A 2 :, A N . У моменти приходу тактових імпульсів автомат переходить з одного стану в інше, визначуване як поточним станом, так і набором вхідних (осведомітельних) сигналів X 1, X 2 :, X N, при цьому формується послідовність наборів вихідних (керівників) сигналів Y 1, Y 2 :, Y N . Для кожного автомата задається закон функціонування або алгоритм переходів з одного стану в інше під дією різних комбінацій вхідних сигналів з описом комбінацій формованих при цьому вихідних сигналів. Такий алгоритм може бути заданий або у вигляді графа, або у вигляді таблиці переходів. Коли автомат не працює, він знаходиться в початковому стані A 1 . При запуску автомат зберігає стан A 1 протягом одного такту, за час якого формуються відповідні значення вхідних сигналів Х 1 . Після закінчення першого такту автомат перемикається в черговий стан A 2 наказане законом функціонування, і в ОА починає виконуватися наступний набір мікрооперацій. Момент закінчення мікропрограми наголошується поверненням автомата в початковий стан а 1 Прикладом цифрового автомата служить лічильник - автомат, в якого немає взагалі вхідних інформаційних сигналів, а є лише тактовий, на нього подаються рахункові імпульси. Число його станів дорівнює коефіцієнту перерахунку граф цього автомата є кільцем з послідовним переходом від одного стану до наступного. Складніші цифрові автомати можуть мати по декілька можливих переходів з кожного стану під дією різних наборів вхідних сигналів.Автомат Милі і автомат Мура За способом формування вихідних сигналів автомати підрозділяють на автомати Милі і автомати Мура. Для автомата Милі визначається наступний закон функціонуванняA(t + 1) = [A(t), X(t)];Y(t) = [А (t), Х (t)],Для автомата Милі, як видно з виразів, вихідні сигнали Y(t) залежать як від стану автомата A(t) у нинішній момент часу t, так і від вхідних сигналів X(t). Аналогічно для автомата МураA(t+1) = [А (t), X(t) ];Y (t) = [А (t)],Для нього, як видно з виразів, вихідні сигнали Y(t) залежать лише від стану автомата A(t) у нинішній момент часу t. Реалізація автоматів Милі, як правило, простіша, але в них виникають проблеми з синхронністю формування вихідних сигналів.Алгебра логіки — застосування алгебраїчних методів і символіки для вивчення логічних відношень і розв'язання логічних задач.^ 17 елементарні автоматиВ даний час в обчислювальній техніці, як правило, використовуються елементарні автомати, що мають такі особливості: 1. Елементарні автомати є автоматами Мура з двома внутрішніми станами; 2. Автомат видає два різних вихідних сигналу, що відповідають двом його внутрішнім станам. Надалі стану автомата і його вихідні сигнали будемо позначати однією літерою Q і кодувати цифрами 0 та 1; 3. Елементарні автомати можуть мати в загальному випадку кілька фізичних входів, на кожен з яких можуть подаватися сигнали, закодовані цифрами 0 і 1. Як елементарних автоматів в обчислювальній техніці використовуються, в основному, тригери різних типів. Розглянемо деякі з них: Т-тригер D-тригер Rs - тригер Jk тригер (універсальний тригер) ^ 18. Канонічні методи синтезу автоматів.Приклад канонічного методу структурного синтезу автомата. Виконаємо структурний синтез часткового автомата А, заданого своїми таблицями переходів і виходів (табл. 23 і 24.). Синтез виконуватимемо в наступному порядку:1. Виберемо як елементи пам'яті D-трігер, функція входів якого представлена в таблиці стор. 33.2. Закодуємо вхідні, вихідні сигнали і внутрішні стани автомата. Кількість вхідних абстрактних сигналів F = 3, отже кількість вхідних структурних сигналів L= ]log2F [ = ]log23[ = 2, тобто х1, х2. Кількість вихідних абстрактних сигналів G = 4, отже кількість вихідних структурних сигналів N =]log2G[ = ]log24[ = 2, тобто у1, у2. Кількість внутрішніх станів абстрактного автомата M = 4, отже кількість двійкових елементів пам'яті (трігерів) R = ] log2M [ = ]log24[ = 2. Отже, структура ЦА з урахуванням того, що початковий автомат є автоматом Мілі, як елементи пам'яті використовується D-трігер, може бути представлена у вигляді(мал. 29): Кодування вхідних, вихідних сигналів і внутрішніх станів представлена в таблицях: x1 x2 y1 y2 Q1 Q2 z1 0 0 w1 0 0 a1 0 0 z2 0 1 w2 0 1 a2 0 1 z3 1 1 w3 1 1 a3 1 1 w4 1 0 a4 1 0 Кодування, в загальному випадку, здійснюється довільно. Тому, наприклад, кожному з сигналів ^ Zi можна поставити у відповідність будь-яку двохрозрядну комбінацію х1, х2. Необхідно тільки, щоб різні вихідні сигнали Zi кодувалися різними комбінаціями х1, х2. Аналогічно для Wi і ai.Одержимо кодовані таблиці переходів і виходів структурного автомата. Для цього в таблицях переходів і виходів початкового абстрактного автомата замість Zi, Wi, ai ставимо відповідні коди. Одержимо таблиці: a1 a2 a3 a4 a1 a2 a3 a4 00 01 11 10 00 01 11 10 Z1 00 00 10 10 – Z1 00 01 00 11 – Z2 01 – 11 00 – Z2 01 – 11 00 – Z3 11 01 – 01 Q1Q2 Z3 11 00 – 10 y1y2 В кодованій таблиці переходів задані функції В кодованій таблиці виходів заданні функції: 4. При канонічному методі синтез зводиться до отримання функцій:і подальшій побудові комбінаційних схем, що реалізовують дану систему булевих функцій. Функції у1 і у2 можуть бути безпосередньо одержані з таблиці виходів, наприклад, у вигляді :Проте вирази для у1 і у2 можна істотно спростити в результаті мінімізації, наприклад, за допомогою карт Карно: 00 01 11 10 00 01 11 10 00 0 0 1 – 00 1 0 1 – 01 – 1 0 – 01 – 1 0 – 11 0 – 1 0 11 0 – 0 1 10 – – – – 10 – – – – В результаті мінімізації маємо: Для отримання виразів для D1 і D2 необхідно одержати таблиці функцій збудження. Для чого в загальному випадку необхідно скористатися таблицею переходів і функціями входів елементів пам'яті. Знаючи код початкового стану автомата і код стану переходу на підставі таблиці входів трігера одержуємо необхідне значення функції збудження, що забезпечує заданий перехід. Проте для D-трігеров, як наголошувалося раніше, таблиця переходів співпадає з таблицею функції збудження. Тоді або безпосередньо з цієї таблиці, або в результаті мінімізації набуваємо необхідні значення Di. Звичайно використовується мінімізація за допомогою карт Карно: 00 01 11 10 00 01 11 10 00 0 1 1 – 00 0 0 0 – 01 – 1 0 – 01 – 1 0 – 11 0 – 0 1 11 1 – 1 1 10 – – – – 10 – – – – В результаті мінімізації одержуємо:5. На підставі одержаних в результаті синтезу булевих виразів ((*) (**)), будуємо функціональну схему автомата. Для цього рівняння ((*) (**)) представимо у вигляді: Додатково на функціональній схемі показаний сигнал , встановлюючий автомат в початковий стан (в даному випадку 00) ^ 19. Методи усунення гонок в автоматах Усунути гонки можна апаратними засобами, або використовуючи спеціальні методи кодування . Одним із способів ліквідації гонок полягає в тестування вхідних сигналів автомата імпульсами певної тривалості, передбачається що окрім вхідних каналів Х1, …,Хеавтомата застосовується ще канал С від генератора синхросигналів по якому поступає сигнал С=1 у момент переходу імпульсу і С=0 при його відсутностіУ звязк уз чим вхідний сигнал на переході (am; as) буде не функція Zf, а функція CZf. Тоді Якщо тривалість імпульсу tc менша найкоротшого шляху переходу тактового сигналу зворотного зв’язку по комбінаційній схемі то до номеру переходу в проміжний стан ak сигналу C =0, а отже функція CZfтакож дор. 0. недоліком методу є складність встановлення імпульсу оскільки вона залежить від багатьох чинників що не піддаються строгому обліку. Іншим способом ліквідації гонок є використання подвійної пам’яті в цьому випадку кожен елемент пам’