Граф синтезируемого автомата Мили для каждого варианта получается путем исключения некоторых ветвей обобщенного графа автомата, имеющего 4 внутренних состояния (рис.1). У такого графа из каждой вершины выходят 4 ветви (и столько же входят). Каждая ветвь символизирует переход автомата в другое внутреннее состояние а_k (k =1,2, 3,4) при совместном действии входного сигнала Z_i и выходного сигнала W_j и обозначается их комбинацией Z_i W_j для конкретного значения индексов. Эти индексы берутся из таблицы 8 в строке, номер которой совпадает с номером варианта задания. Здесь каждой вершине графа а_k поставлены в соответствие два набора индексов по 4 цифры: для i и j соответственно. При построении графа следует для каждой ветви, выходящей из каждой вершины, сформировать комбинацию Z_i W_j и указать ее на графе в соответствии с порядковой нумерацией выходящих ветвей. Этот процесс показан на рис.2.

Порядковая нумерация выходящих ветвей для каждой вершины указана на рис.

Рисунок 1. Обобщенный граф автомата с четырьмя внутренними состояниями

Рисунок 2. Схема нумерации внутренних состояний автомата

Пример конкретного варианта графа для следующей кодировки индексов сигналов : 1300 2100 0210 0330 0123 0311 0003 0002, приведен на рис.3.

Порядковая нумерация ветвей графа опущена, так как каждая ветвь задается определенной комбинацией сигналов. По такому графу легко записать таблицы переходов и выходов, которые необходимы для проведения структурного синтеза КА. За исходное состояние автомата принимается состояние а₁.

3.2 Структурный синтез конечных автоматов

Под цифровым конечным автоматом понимают дискретный преобразователь информации, состоящий из комбинационной схемы и элементов памяти. Комбинационная схема строится из логических элементов, память - из элементарных автоматов, а именно синхронных триггеров различных типов.

Работа подобных цифровых устройств описывается набором входных сигналов Z = {Z₁, Z_{2, … ,} Z_p}, набором выходных сигналов W= { W_1, Z_2, … , Z_s }, множеством внутренних состояний (выходных сигналов элементов памяти) А = {a₁, a_{2 ,}… , a_k}, двумя характеристическими функциями: функцией переходов д и функцией выходов, л, а также начальным состоянием автомата a₁ A.

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

а(t+1) = д [z(t), a(t)],

где t - автоматное время.

Отличаются автоматы Мили и Мура лишь записью функции выходов. Если в автомате Мили выходной сигнал зависит как от внутреннего состояния автомата, так и от входного сигнала в том же такте

W(t) = л [z(t), a(t)],

то в автомате Мура выходной сигнал определяется только внутренним состоянием в данном такте

W(t) = л [a(t)],

В частном случае возможно и W(t) = а(t), т.е. выходной сигнал автомата одновременно является выходным сигналом памяти.

Практически указанное отличие проявляется в том, что при смене входного сигнала в пределах такта в автомате Мили изменяется состояние выхода, а в автомате Мура - сохраняется неизменным, так как изменение состояния элементов памяти происходит только в момент действия импульсов синхронизации.

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

Z_i ~ х(t) ={ x₁, x₂. x_n} - входной сигнал;

W_i ~ y(t) ={ y₁, y₂. y_m} - выходной сигнал;

a_i ~ Q(t) ={ Q₁, Q₂. Q_r} - сигнал внутреннего состояния (состояния триггеров памяти);

U(t) ={ u₁, u₂... u_k} - входной сигнал памяти.

В такой записи символическим обозначениям Z_i, W_i и a_i соответствуют двоичные кодовые комбинации х(t), у(t) и Q(t), где х_j, y_j, Q_j, и u_j - отдельные биты кода, каждый из которых передается по своей информационной шине. Структурные схемы автоматов Мили и Мура показаны на рис. 4 и 5. Исходными данными для их синтеза являются таблицы переходов и выходов.

Рисунок 4. Структурная схема КА Мили

Рисунок 5. Структурная схема КА Мура

Структурный синтез КА Мили предполагает выполнение ряда этапов.

1. Выбирают систему логических элементов и элементов памяти, на которых будет строиться КА.

2. Определяют недостающие входные данные:

- число элементов памяти r ? log ₂ k

- число разрядов входной шины n ? log ₂ p

- число разрядов выходной шины m? log ₂ s ,

где k, p, s - количество внутренних состояний, входных Z_i и выходных W_i сигналов соответственно. Числа r, п, т - целые.

3. Кодируют автомат. Это означает, что каждому входному и выходному сигналу и внутреннему состоянию ставят в соответствие определенный двоичный код.

4. Переводят исходные таблицы выходов и переходов из символического алфавита в двоичный.

5. По таблице выходов составляют систему логических уравнений, связывающих выходные, сигналы КА у_j с внутренними состояниями и входными сигналами х_j . Общий вид такого уравнения У_j = f_j ( x₁, x₂,…,x_n,Q₁,Q₂,…,Q_r).

6. По таблице переходов составляют таблицу возбуждения памяти, т.е. двоичных сигналов, которые следует подавать на входы триггеров памяти для перевода их в требуемые состояния. Словари переходов наиболее часто применяемых триггеров приведены в таблице 3.

Таблица 3 - Словари переходов триггеров

Для синтезируемого КА с помощью словаря следует преобразовать его таблицу переходов в таблицу возбуждения памяти (процесс преобразования поясняется ниже на конкретном примере).

7. По таблице возбуждения памяти составляют систему логических уравнений, связывающих входные сигналы памяти U_j с внутренними состояниями Q_j и входными сигналами х_j: U_j = ц_j (x₁, x₂,…, x_n, Q₁, Q₂… Q_r).

8. Все уравнения, полученные в пп.5 и 7, минимизируют при помощи карт Карно. 9. По минимальным формам составляют полную логическую схему КА на микросхемах заданной серии.

3.3 Пример структурного синтеза автомата Мили

Зададим автомат Мили таблицами переходов и выходов (рис.6):

Рисунок 6. Исходный КА Мили

1. Выбираем в качестве элементов памяти JK - триггеры. Базис логических элементов - произвольный.

2. Для данного примера очевидно:

к = 4 -число внутренних состояний (а_к);

р = 3 -число входных сигналов (Z_i);

s=3- число выходных сигналов (W_I).

3. Находим:

- число элементов памяти r > log ₂ k = log ₂ 4 = 2;

- число разрядов входной шины n > log ₂ p = log ₂ 3 = 2;

- число разрядов выходной шины m > log ₂ s = log ₂ 3 = 2.

1. Кодируем автомат, ставя в соответствие каждому символическому сигналу произвольный двоичный код (число разрядов кода соответствует найденным r, n, m).

1. Титульный лист считается первым листом и не нумеруется.

2. На втором листе приводится содержание РГЗ. Он оформляется рамкой и содержит заполненный основной штамп по ЕСКД.

3. На третьем листе пишется задание на курсовую работу с указанием номера конкретного варианта. Третий и все последующие листы также оформляются рамкой.

4. Начиная с четвертого листа, размещается текст пояснительной записки, включающий следующие разделы:

а) общая характеристика синтезируемого устройства и принципы его работы, граф исходного автомата Мили;

б) все исходные логические функции и их преобразования, граф и схема автомата Мура, расчеты с подробным пояснительным текстом;

в) полные принципиальные схемы устройств, выполненные согласно ЕСКД;

д) предусмотреть во всех схемах кнопки начальной установки кода;

е) выводы по работе;

ж) список использованной литературы.

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

1. Смирнов Ю.А. Основы микроэлектроники и микропроцессорной техники/ Ю. А. Смирнов, С. В. Соколов, Е. В. Титов. - СПб: Лань, 2013 - 496 с.

2. Микушин А.В. Цифровые устройства и микропроцессоры/ А.В. Микушин, А .М.Сажнёв, В.И. Сединин.- СПб: БХВ-Петербург, 2010 - 832 с.

3. Безуглов Д.А. Цифровые устройства и микропроцессоры: Учебное пособие / Д.А. Безуглов, И. В. Калиенко.- Р-Д., 2008. - 469 с.

4. Сажнев А.М. Цифровые устройства и микропроцессоры: конспект лекций /А.М. Сажнев .- Новосибирск: Изд-во НГТУ, 2007. - Ч.1. - 116 с.

5. Пухальский Г.Я. Цифровые устройства: Учебное пособие для ВТУЗов.- СПб.: Политехника, 2006. - 885 с.

Размещено на Allbest.ru