Абстрактный автомат Мили

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

Содержание

1. Абстрактные автоматы

.1 Задание на первую часть курсового проекта

.2 Минимизация абстрактного автомата Мили

.3 Синтез схемы конечного автомата

.4 Проверка по первой части курсового проекта

.5 Моделирование работы абстрактного автомата

. Микропрограммные автоматы на базе логических матриц

.1 Задание на вторую часть курсового проекта

.2 Синтез микропрограммного автомата

.3 Синтез счётчика числа микрокоманд

.4 Разработка цифровой линии задержки (таймера)

. Список литературы

1. Абстрактные автоматы

.1 Задание на первую часть курсового проекта

.2 Минимизация абстрактного автомата Мили

Автомат Мили задан таблицами переходов (табл.1.1) и выходов (табл.1.2).

Таблица. 1.1.

s1s2s3s4s5s6s7s8х1s3s4s2s7s3s4s5s5х2s2s8s4s1s6s8s3s3х3s4s1s7s3s4s5s6s2Таблица. 1.2.

s1s2s3s4s5s6s7s8х1y3y1y3y1y3y1y3y3х2y2y3y2y3y2y3y2y2х3y1y2y1y2y1y2y1y1B1B2B1B2B1B2B1B1

Разбиение на 1-классы эквивалентности осуществляется путём выявления одинаковых столбцов таблицы 1.2 , при этом получаем:

Строим таблицу 1-разбиения (табл. 1.3.) и из неё находим разбиение на 2-классы.

Таблица. 1.3.

1B1B2s1s3s5s7s8s2s4s6х1B1B2B1B1B1B2B1B2х2B2B2B2B1B1B1B1B1х3B2B1B2B2B2B1B1B1C1C2C1C3C3C4C5C4

Строим таблицу 2-разбиения (табл. 1.4.) и из неё находим разбиение на 3-классы.

абстрактный автомат микрокоманда цифровой

Таблица. 1.4.

2C1C2C3C4C5s1s5s3s7s8s2s6s4x1C2C2C4C1C1C5C5C3x2C4C4C5C2C2C3C3C1x3C5C5C3C4C4C1C1C2D1D1D2D3D3D4D4D5

Дальнейшее разбиение невозможно. Таким образом, найдены ? - классы, которым соответствует автомат Мили, описываемый таблицами переходов (табл. 1.5.) и выходов (табл. 1.6.).

Таблица 1.5.

s1s2s3s4s7х1s3s4s2s7s1х2s2s7s4s1s3х3s4s1s7s3s2

Таблица 1.6.

s1s2s3s4s7х1y3y1y3y1y3х2y2y3y2y3y2х3y1y2y1y2y1

Построим реакции исходного и оптимизированного автоматов на входное воздействие x2x1x3x1x3x3x1x2, при начальном состоянии автомата s[0]=s1(табл. 1.7.).

Таблица 1.7.

Входное воздействиеx2x1x3x1x3x3x1x2Реакция исходного автоматаy2y1y2y3y2y1y1y2Реакция минимизированного автоматаy2y1y2y3y2y1y1y2

Построим граф-схемы исходного (рис. 1.1) и оптимизированного (рис. 1.2.) автоматов.

Рис. 1.1. Граф-схема исходного автомата.

Рис. 1.2. Граф-схема минимизированного автомата.

1.3 Синтез схемы конечного автомата

Абстрактный синтез

. Выбор количества триггеров. Так как автомат имеет 5 состояний, то требуется q=]log25[=3 триггера.

. Кодирование внутренних состояний входных, выходных сигналов:

Q1Q2Q3S1000S2001S3010S4011S7100

QnQn+1?00011110-01+

XV1V2Х100Х201Х310

YW1W2Y100Y201Y310

. Составление таблицы переходов. На основании графа переходов составляем таблицу переходов (табл. 1.8.), указывая текущие и будущие состояния триггеров, а также значения операторов перехода.

Таблица 1.8.

Nsnsn+1входныевыходныеv1v2K(Sn)K(Sn+1)?xiv1v2yiw1w2Q1Q2Q3Q1Q2Q3Q1Q2Q31s1s3x100y310000000100+02s1s2x201y2010100000100+3s1s4x310y100100000110++4s2s4x100y100000010100+15s2s7x201y31001001110+0-6s2s1x310y2011000101100-7s3s2x100y310000101100-+8s3s4x201y2010101000001+9s3s7x310y10010010010+-010s4s2x100y10000011000+--11s4s1x201y310010110010--12s4s3x310y2011001111001-13s7s1x100y31000100001-0014s7s3x201y20101100011-+015s7s2x310y10010100000-0+

Структурный синтез

Составление обобщенных карт Карно. Так как автомат содержит три триггера, то составляем три обобщенных карты Карно (содержат в клетках значения оператора переходов) и две карты Карно для получения логического выражения для функции выхода.

1. Синтез на базе Т-триггеров в базисе ИЛИ-НЕ.

Для того чтобы составить логическое выражение для сигнала возбуждения Т, с помощью операции пересечения, необходимо на обобщенной карте Карно охватить контурами все клетки, помеченные знаками 1 и 0, и пустые клетки, т. е. функция возбуждения Т-триггера определяется выражением:

Т=? {1,0,()}.

Нахождение функций выходов.

v1v2Q1 Q2 Q300000101101011011110110000100110101100111000000

v1v2Q1 Q2 Q300000101101011011110110000000000110011111001100

Нахождение функций переходов:

v1v2Q1 Q2 Q30000010110101101111011000000+0-010+00-1110000+-

v1v2Q1 Q2 Q300000101101011011110110000++--00100-1+1110+01-0

v1v2Q1 Q2 Q30000010110101101111011000001-+001+--+01110+--0+

Схемная реализация. На основании полученных выше выражений составляем схему абстрактного автомата. На количество входов логических элементов ограничения не налагаем.

Рис. 1.3. Схема автомата на Т-триггерах.

. Синтез на базе JK-триггеров в базисе И-НЕ.

Для того чтобы составить логическое выражение для сигнала J, необходимо на обобщенной карте Карно охватить контурами все клетки, помеченные знаком + (причем для его минимизации разрешается включать в контуры единичные и пустые клетки и клетки, помеченные знаком -), а для сигнала К - все клетки, помеченные знаком - (для минимизации разрешается включать нулевые и пустые клетки и клетки, помеченные +), т. е. функции возбуждения .JK-триггера определяются выражениями:

=U{+, (-), (1), ()}; K= U {-, (+), (0), ()};