уктурній теорії вивчаються способи побудови автоматів з елементарних автоматів, способи кодування вхідних і вихідних сигналів елементарними сигналами тощо.
Одна з основних задач теорії цифрових автоматів, розв'язуваних стосовно до побудови різних цифрових пристроїв ЕОМ, полягає в тому, щоб задачу аналізу та синтезу таких пристроїв звести до задачі аналізу та синтезу комбінаційних схем. При цьому в якості основного математичного апарату використовується апарат алгебри логіки
1. Аналіз технічного завдання
Теоретичні відомості
У даному курсовому проекті необхідно виконати синтез двухразрядного мультиплексора на елементах І - НЕ.
Автомат - це дискретне пристрій, що задається трьома множинами:={x1, x2, ..., xn} - алфавіт вхідних сигналів;={y1, y2, ..., ym} - алфавіт вихідних сигналів; ={zi, z2, ..., ZK} - безліч станів автомата;
і двома функціями: (s + 1)=f (z (s), x (s)) - функція переходів;
y (s) =? (z (s), x (s)) - функція виходів;
Функція переходу f (z (s), x (s)) визначає стан автомата в (s + 1) -m такті в залежності від стану його в s-му такті і від вхідного сигналу в s-м такті. Функція виходів? (Z (s), x (s)) визначає вихідний сигнал автоматів у (s + 1) -m такті в залежності від стану його в s-му такті і від вхідного сигналу в sm такті.
Кінцеві автомати діляться на два типи. Автомати, описувані вищевказаними виразами, тобто функціями переходів і виходів, де значення функції виходів залежить як від стану автомата в s-му такті, так і від вхідного сигналу в s-му такті, називаються автоматами Мілі. Автомати, описувані функціями:
(s + 1)=f (z (s), x (s)) - функція переходів; y (s) =? (z (s)) - функція виходів,
де значення функції виходів у s-му такті залежить тільки від стану автомата в s-му такті, називаються автоматами Мура.
Узагальнена схема кінцевого цифрового автомата показана на малюнку 1.1. Вона складається з перемикальної схеми F, елементарних автоматів Q1, Q2, ..., Qt та перетворювачів П1 і П2, пов'язаних між собою таким чином, щоб виконувалися умови роботи автомата.
Вхідний алфавіт автомата являє собою безліч букв х1х2, ..., хn Перетворювач П1, називається перетворювачем вхідного алфавіту, перетворює символи вхідного алфавіту X1, x2, ..., xn в сукупність двійкових значень сигналів на фізичних входах автомата x1 *, х2 *, ..., хr, * причому різним вхідним сигналам хi і хj
(1 lt; i lt; n, 1 lt; j lt; n, i? j) повинні відповідати різні набори сигналів на фізичних входах автомата.
Вихідний алфавіт автомата являє собою безліч букв у1 у2, ..., уm Перетворювач П2, називається перетворювачем вихідного алфавіту, перетворює символи вхідного алфавіту y1 *, у2 *, ... уP * в сукупність двійкових значень сигналів на фізичних входах автомата yi *, y2 ..., yp * причому різним вхідним сигналам уi, і yj (1 lt; i lt; n, 1 lt; j lt; n, i? j) повинні відповідати різні набори сигналів на фізичних виходах автомата.
Безліч станів автомата містить 1 елементів z0, z1, ..., zl - 1, де z0 -початкової стан автомата. Кожному стану автомата відповідає сукупність станів елементарних автоматів Q1, Q2, ..., Qt, причому різним станам zi і zj (1 lt; i lt; n, 1 lt; j lt; n, i? J) повинні відповідати різні сукупності станів елементарних автоматів.
Переключательная схема F визначає логіку роботи автомата. На її входи подаються сигнали з фізичних входів автомата x1 *, х2 *, ..., хг * і з виходів елементарних автоматів Q1, Q2, ..., Qt а виходи схеми з'єднуються з фізичними виходами автомата yi *, уj *, ..., УР * і з входами елементарних автоматів q1, q2, ..., qt.
Структурний синтез автомата полягає в побудову такої схеми автомата, яка функціонує відповідно до заданих таблицями переходів і виходів автомата. Для цього необхідно:
призвести кодування вхідних і вихідних сигналів, тобто поставити у відповідність кожній з букв х і у вхідного і вихідного алфавітів сукупність із значень сигналів на фізичних виходах і входів автомата, т. е. визначити закони функціонування перетворювачів П1 і П2;
визначити кількість і вибрати типи елементарних автоматів;
у відповідність кожному станом автомата z, поставити сукупність станів Q1, Q2, ..., Qt елементарних автоматів, тобто призвести кодування станів автомата;
знайти переключательние функції q1, q2, ..., qt, а також функції виходів y1 *, У2 *, ..., УР *, визначивши тим самим структуру комбінаційної схеми F.
Кількість фізичних входів автомата визначається за форму...