Объем памяти. Памятью автомата называют число его состояний

1. Объем памяти. Памятью автомата называют число его состояний.

2. Механизм случайного выбора. В детерминированных автоматах поведение и структура автомата в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата. В вероятностных автоматах они зависят от случайного выбора.

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

В теории автоматов наиболее полно описаны синхронные автоматы. В зависимости от способа определения выходного сигнала в синхронных автоматах существует две возможности:

1) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент;

2) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени. Следовательно, закон функционирования абстрактного автомата может быть задан следующим образом:

для автомата первого рода

q(t)=(q(t-1), х(t)),

y(t)=(q(t-1), x(t), t=1, 2…);

для автомата второго рода

q(t)=(q(y-1), x(t)),

y(t)=(q(t), x(t)), t=1,2...).

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

₁(q, x)=((q, х), x).

Для дальнейшего изложения примем, что произвольные автоматы первого рода будут называться автоматами Мили, а частный случай автоматов второго рода, для которых сдвинутая функция выходов (q, х) не зависит от второй переменной х — автоматами Мура.

Закон функционирования автоматов Мура задается в виде:

q(t)=(q-1), x(t)),

y(t)=(q(t)).

В отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала.

Совмещенная модель автомата (C-автомат). Абстрактный C-автомат — математическая модель дискретного устройства, для которого заданы следующие параметры:

Q={q₁ ... q_s} — множество состояний;

X={x₁(t) ... x_n(t)} — входной алфавит;

Y={y₁(t) ... y_k(t)} — выходной алфавит типа 1;

U={u₁(t) ... u_m(t)} — выходной алфавит типа 2;

:QXQ — функция переходов, реализующая отображение D_ QX в Q,

_l:QXY — функция выходов, реализующая отображение D_1  QX на У;

₂:QU — функция выходов, реализующая отображение D_2  Q на U,

q₀Q — начальное состояние автомата.

Р
ис. 2. Совмещённая модель автомата с одним входом и двумя выходами.

Абстрактный C-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из выходных алфавитов Y и U (рис. 2).

Отличие C-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов ₁ и ₂, каждая из которых характерна для этих моделей в отдельности.

Примером ЦА могут служить многосчётчиковые бухгалтерские автоматы "Аската".

Автомат "Аската" относится к группе машин двухпериодного действия, — за первый период осуществляется набор цифр на клавиатуре, за второй — печать цифровых данных на бумаге и подсчёт чисел в счётчиках машины.

Технические характеристики и эксплуатационные данные автоматов: количество счётчиков, в зависимости от моделей — от 3 до 55, три из них — сальдирующие для сложения и сальдирования итогов и 52 — накапливающие счётчики (регистры), выполняющие вычитание до нуля. Отрицательное содержание этих счётчиков может быть записано дополнительным кодом. Все счетчики автомата имеют ёмкость 12-разрядного десятеричного арифметического числа. Максимальная ёмкость вводного устройства (цифровая клавиатура и наборная каретка) равна 10-разрядному числу. Программирование и управление автоматом осуществляется при помощи сменной шины управления, закреплённой на подвижной части каретки.

Итак, проанализировав вышеизложенную информацию можно определить возможную сферу применения проектируемого устройства: оно может быть использовано для формирования управляющих слов при исследовании какого-либо синхронного цифрового автомата, например на учебных лабораторных стендах, во-вторых, не исключена возможность применения данного устройства в системах автоматического управления технологическими процессами, где сигналы, снимаемые с выходной шины могут подаваться на различные механизмы и устройства, либо на входы ЦАП. Применение устройства в данной сфере удобно тем, что для начала процесса необходимо лишь запустить счётчик, а остальные операции будут производиться автоматически.

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

Специальная часть.

3. 1. Определение задачи.

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

3. 2. Разработка структурной схемы проектируемого устройства.

Первым шагом проектирования устройства является разработка структурной схемы.

Цифровой автомат является синхронным цифровым устройством, сохраняющим своё значение в каждом такте. Следовательно, для запоминания состояния цифрового автомата в устройстве управления должно быть предусмотрено наличие запоминающих элементов — триггеров. Для формирования управляющих сигналов, которые выставляются на выходной шине устройства, в соответствие с кодом микрокоманды в состав УУ должна входить комбинационная логическая схема — шифратор.

Для обеспечения УУ автоматического последовательного переключения в 4 различные состояния, необходима схема, обеспечивающая формирование сигналов обратной связи, переводящие УУ в следующее состояние.

И
сходя из определённых выше требований, структура УУ может выглядеть так:

3. 3. Разработка функциональной схемы устройства.

После определения структуры УУ и функций каждым элемента имеются все необходимые данные для разработки функциональной схемы устройства.

Из задания ясно, что УУ должно на выходной шине формировать управляющие последовательности кодов в соответствие с кодами микрокоманд. Следовательно, для разработки функциональной схемы необходимо определить коды микрокоманд и управляющих последовательностей по заданным преподавателем формулам.

Коды микрокоманд определяются по формулам:

N_mk1=N_ж+20

N_mk2= N_mk1+2

N_mk3= N_mk2+2

N_mk4= N_mk3+2,

где N_ж — номер студента по списку в журнале, N_mk1, N_mk2, N_mk3, N_mk4 — коды 4-х микрокоманд.

Итак, рассчитываем коды микрокоманд, исходя из того, что N_ж=21:

N_mk1=21+20=41D=101001B,

N_mk2= 41+2=43D=101011B,

N_mk3= 43+2=45D=101101B,

N_mk4= 45+2=47D=101111B.

Состояния УУ фиксируются и сохраняются в параллельном 6-разрядном регистре, построенном на синхронных JK-триггерах, где вход J переводит триггер в состояние (Q=1,Q=0), а вход K — в состояние (Q=0,Q=1). Запись информации в триггер происходит при наличии сигналов либо на входе J, либо на входе К триггера и лишь только в момент действия тактирующего импульса С (C=1). Также в триггерах имеются инверсные асинхронные входыS иR, которые используются при начальной установке триггеров в исходное состояние L1 (S=0), либо L0 (R=0). Поскольку входыR иS инверсные, то их срабатывание происходит в момент наличия на них сигнала, имеющего уровень L0. Так как эти входы асинхронны, то они позволяют устанавливать триггер в исходное состояние в любой момент времени, независимо от уровня тактового импульса C.

Сигналы обратной связи, определяющие следующее состояние регистра, формируются с помощью дешифраторов состояния регистра (ДС). Они выполняются на логических элементах И, причём единичный сигнал на выходе каждого ДС формируется в ответ на некоторую единственную входную комбинацию.

Начальное состояние регистра определяется кодом первой МК и фиксируется в регистре путем установки в состояние единицы соответствующих коду разрядов регистра. Установка производится сигналами логического нуля (L0) по асинхронным входам S. При этом на выходе дешифратора состояния регистра ДС1 формируется сигнал обратной связи, переводящий регистр в следующее заданное состояние, соответствующее коду микрокоманды N_mk2. В следующее состояние регистр переводится с подачей синхроимпульса. После этого формируется сигнал обратной связи уже на выходе дешифратора ДС2 и в регистр помещается код микрокоманды N_mk3 и т. д. Сигналом ДС4 регистр сбрасывается в состояние L0 по установочным входам R через инвертор, выполняющий также роль элемента задержки.

Шифратор представляет собой комбинационное устройство с шестью входами и десятью выходами, который преобразует коды состояния реги­стра в коды выходных управляющих сигналов.

Синхронизирующее устройство состоит из задающего генератора тактовой частоты ЗГ и ключа , обеспечивающего прохождение синхроимпульсов на регистр лишь после установки кода N_mk1. Ключевая схема состоит из асинхронного вспомогательного RS-триггера Т7 и элемента И. Триггер Т7 устанавливается в состояние L1 после подачи сигнала с ДС1 и отпирает ключ, выполненный на элементе И — сигналы с ЗГ поступают на тактовые входы регистра. Сигналом с ДС4 триггер сбрасывается в состояние L0 и запирает ключ на элементе И, после чего прохождение СИ на тактовые входы регистра прерывается.

Как было определено выше, код первой микрокоманды N_mk1=101001B. Следовательно, начальное состояние устанавливается подачей сигнала нулевого уровня на S-входы триггеров Т1, Т4, Т6 (S1, S4, S6).

Н
а входы дешифратора состояния регистра подаются сигналы прямых либо инверсных выходов триггеров, в зависимости от того, на каком из них в данный момент имеется уровень L0. Соответственно кодам состояния УУ, дешифраторы реализуют следующие функции:

Составим таблицу переходов:

Код состояния	Двоичный код состояния	Переход	Адрес подачи сигнала обратной связи
Начало	000000	041	Вх. S1, S4, S6
41	101001	4143	ДС1 – J2
43	101011	4345	ДС2 – J3, K2
45	101101	4547	ДС3 – J2
47	101111	470	ДС4 – R1, R2, R3, R4, R5, R6

Из записи двоичных кодов состояний 41 и 43, видно, что для перехода из состояния 41 в состояние 43 необходимо триггер второго разряда Т2 перевести в состояние L1 по входу J2. Сигналы обратной связи для остальных переходов определяются аналогичным образом. Следует отметить, что если на один из входов сигнал поступает несколько раз, то на этот вход ставится элемент ИЛИ с соответствующим количеством входов.

Далее необходимо разработать схему шифратора. На его вход подаются сигналы с выходов регистра Q1, Q2, Q3, Q4, Q5, Q6, а на выходах формируются десятиразрядные кодовые управляющие последовательности.

Значения выходных сигналов определяются по формулам, заданной преподавателем. Формула имеет следующий вид:

УКП1=N_ж+600,

УКП2= УКП1+1,

УКП3= УКП2+10,

УКП4= УКП3+100,

где УКП1, УКП2, УКП3, УКП4 — выходные кодовые последовательности. Определим их значения (как было указано выше, N_ж=21):

УКП1=21+600=621D=1001101101B,

УКП2= 621+1=622D=1001101110B,

УКП3= 622+10=632D=1001111000B,

УКП4= 632+100=732D=1011011100B.

Составляем таблицу работы шифратора:

Код сост. рег.	X6	X5	X4	X3	X2	X1	Код упр. сигн.	Y10	Y9	Y8	Y7	Y6	Y5	Y4	Y3	Y2	Y1
41	1	0	1	0	0	1	621	1	0	0	1	1	0	1	1	0	1
43	1	0	1	0	1	1	622	1	0	0	1	1	0	1	1	1	0
45	1	0	1	1	0	1	632	1	0	0	1	1	1	1	0	0	0
47	1	0	1	1	1	0	732	1	0	1	1	0	1	1	1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Таким образом, получение табличное задание логических функций Y₁₀...Y₁. Для их реализации их можно представить в алгебраической форме и, по возможности минимизировать с помощью диаграмм Вейча.

Однако, после детального рассмотрения таблицы можно прийти к выводу, что некоторые из функций являются весьма простыми и не требуют дальнейшей минимизации. Так, видно, что состояние выходного сигнала Y₁₀ соответствует состоянию входных сигналов X₁, X₄ и X₆. Примем Y₁₀=X₁. Далее, видно, что выходной сигнал Y₉ не меняется на протяжении всех тактов и имеет значение L0, тогда Y₉=0. Сигнал Y₇ всегда равен сигналу Y₁₀: Y₇= Y₁₀. Из сопоставления сигналов Y₈ и Y₆ видно, что Y₆=Y₈ и Y₆=0 в случае сброса устройства, тогда: Y₆=Y₈X₁. Также можно утверждать, что Y₅=X₃.

Переключательные функции же для сигналов Y₁, Y₂, Y₃, Y₄ и Y₈ необходимо минимизировать при помощи карт Карно. Для этого необходимо составить карту Карно размером 88 ячеек, поскольку значения выходных сигналов зависят от 6-ти переменных, то X₃X₂X₁ откладывают по столбцам, а X₆X₅X₄ — по строкам.

Строим карту Карно для переменной Y₁:

	011	010	000	001	101	100	110	111
011	x	x	x	x	x	x	x	x
010	x	x	x	x	x	x	x	x
000	x	x	0	x	x	x	x	x
001	x	x	x	x	x	x	x	x
101	0	x	x	1	0	x	x	0
100	x	x	x	x	x	x	x	x
110	x	x	x	x	x	x	x	x
111	x	x	x	x	x	x	x	x

K₁=X₃X₂ X₁; Y₁= K₁=X₃X₂ X₁. Строим карту Карно для сигнала Y₂:

	011	010	000	001	101	100	110	111
011	x	x	x	x	x	x	x	x
010	x	x	x	x	x	x	x	x
000	x	x	0	x	x	x	x	x
001	x	x	x	x	x	x	x	x
101	1	x	x	0	0	x	x	0
100	x	x	x	x	x	x	x	x
110	x	x	x	x	x	x	x	x
111	x	x	x	x	x	x	x	x

K₁=X₃ X₂;

Y₂= K₁=X₃X₂.

Строим карту Карно для сигнала Y₃:

	011	010	000	001	101	100	110	111
011	x	x	x	x	x	x	x	x
010	x	x	x	x	x	x	x	x
000	x	x	0	x	x	x	x	x
001	x	x	x	x	x	x	x	x
101	1	x	x	1	0	x	x	1
100	x	x	x	x	x	x	x	x
110	x	x	x	x	x	x	x	x
111	x	x	x	x	x	x	x	x

K₁= X₂;

K₂=X₃X2 X₁;

Y₃ = K₁+ K₂= X₂+X₃X2 X₁.

Строим карту Карно для переменной Y₈ и минимизируем её:

	011	010	000	001	101	100	110	111
011	x	x	x	x	x	x	x	x
010	x	x	x	x	x	x	x	x
000	x	x	0	x	x	x	x	x
001	x	x	x	x	x	x	x	x
101	0	x	x	0	0	x	x	1
100	x	x	x	x	x	x	x	x
110	x	x	x	x	x	x	x	x
111	x	x	x	x	x	x	x	x

K₁= X₃ X₂;

Y₁= K₁= X₃ X₂.

Следует отметить, функции Y₁ и Y₃ имеют общий минтермX₃X₂ X₁, поэтому Y₃ можно выразить как Y₃= X₂+ Y₁.

Т
аким образом получены следующие логические функции всех выходных сигналов шифратора, имеющие вид:

Т
еперь, по полученным логическим функциям можно построить шифратор.

3. 3. Разработка принципиальной схемы устройства.

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

Для разработки принципиальной схемы необходимо использовать стандартные промышленные микросхемы, такие как: JK-триггеры с инверсными асинхронными входами, а также простейшие логические микросхемы, содержащие элементы, реализующие основные функции булевой алгебры: логические элементы И, ИЛИ, а также элемент ИЛИ-НЕ, реализующий функцию Пирса и инверторы. Для индикации состояний устройства применены светодиоды и семисегментный светодиодный индикатор. В качестве средств управления УУ применяются микропереключатели и микрокнопки. В связи с многообразием различных серий стандартных микросхем, в составе которых содержатся вышеуказанные необходимые микросхемы, отличающихся по своим техническим характеристикам, и технологии изготовления при неизменности своих функциональных возможностей, более подробно осветим вопрос выбора и обоснования элементной базы.

3. 4. Подбор элементной базы.

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

На сегодняшний день выпускается множество серий цифровых микросхем, основным различием которых является тип применяемой логики. Вообще различают такие основные технологии: резисторно-связная логика (РСЛ), эмиттерно-связная логика (ЭСЛ), диодно-транзисторная логика (ДТЛ), транзисторно-транзисторная логика (ТТЛ) и др.

В результате проведенного анализа было принято решение о целесообразности применения в данном устройстве микросхем технологии ТТЛ, поскольку функциональный набор микросхем данной структуры содержит все необходимые элементы для разработанной схемы. Ещё одно достоинство этой структуры состоит в том, что напряжение питания для всех серий микросхем ТТЛ одинаково, что упрощает решение вопроса питания всего устройства.

Следующим этапом подбора элементной базы являлся анализ непосредственно серий микросхем ТТЛ по их основным параметрам. В нижеследующей таблице приведены характеристики основных параметров микросхем различных серий:

Параметры	Серии
	К134	К155	К531*	К555*
Напряжения питания, В	5	5	5	5
Время задержки распространения сигнала, нс	33	10	3	10
Потребляемая мощность, мВт	1	10	20	2
Емкость нагрузки, пФ	50	15	15	15
Энергия переключения, пДж	33	100	60	20
Нагрузочная способность,	10	10	10	20

После проведенного анализа было принято решение о применении для разработанного устройства микросхем серии К555. Такое решение основано на наибольшей нагрузочной способности, наименьшей энергии переключения и малой потребляемой мощности, что делает применение этой серии по сравнению с аналогами серий К134, К155 и К531 наиболее экономичным.

Далее приведены основные технические характеристики, принципиальные схемы и количество необходимых микросхем, примененных в данном устройстве.

JK-триггер с инверсными асинхронными входами.

П
рименён в блоке триггеров. Микросхема К555ТВ9 в количестве 3 штук.

Тип корпуса	238.16-1
Мин. вых. напр. высокого уровня	2,7 В
Макс. вых. напр. низкого уровня	500мВ
Макс. вх. ток высокого уровня	80мкА
Макс. вх. ток низкого уровня	800мкА
Макс. ток потребления	8мА
Напр. питания	5В
Технология	ТТЛШ

Элемент 2ИЛИ.

П
рименяется в схеме шифратора. Микросхема К555ЛЛ1. Содержит 4 элемента 2ИЛИ. Необходимое количество — 1 штука.

Тип корпуса	201.14 - 1
Напряжение питания	5В
Макс. ток низкого уровня	4,4мА
Макс. ток высокого уровня	1,6мА
Макс. вых. напряжение низкого уровня	0,5В
Мин. вых. напряжение высокого уровня, В	2,7
Макс. вх. ток низкого уровня	0,36мА
Тип корпуса	201.14-1
Технология	ТТЛШ
Макс. вх. ток высокого уровня	0,02мА
Диапазон рабочих температур	-10 - + 70С
Масса	1г.

Элемент 4И.

Применяется в качестве дешифратора состояния регистра. Микросхема К555ЛИ6. Необходимое количество — 4 штуки. 1 микросхема содержит 2 элемента 4И. Соединение элементов для получения необходимой функции осуществляется следующим образом:

П

ринципиальная схема микросхемы имеет следующий вид:

Тип корпуса	201.14-8
Мин. вых. напр. высокого уровня	2,7 В
Макс. вых. напр. низкого уровня	500мВ
Макс. вх. ток высокого уровня	20мкА
Макс. вх. ток низкого уровня	360мкА
Макс. ток потребления	2,4мА
Напр. питания	5В

Элемент НЕ.

П
рименяется в схемах шифратора, а также как элемент задержки (на выходе ДС4) и в других целях. Микросхема К555ЛН1. Необходимое количество — 1 штука. 1 микросхема содержит 6 элементов НЕ с открытым коллектором. Принципиальное обозначение схемы представлено ниже:

Технология	ТТЛШ
Тип корпуса	201.14-8
Мин. вых. напр. высокого уровня	2,7 В
Макс. вых. напр. низкого уровня	500мВ
Макс. вх. ток высокого уровня	20мкА
Макс. вх. ток низкого уровня	400мкА
Макс. ток потребления при высоком уровне вых. напр.	2,4мА
Макс. ток потребления при низком уровне вых. напр.	6,6мА
Напр. питания	5В

Элемент 2И.

П
рименяется в схеме шифратора и в качестве ключа в схеме ЗГ. Микросхема К555ЛИ1. Содержит 4 элемента 2И. Для построения схемы необходимы 2 микросхемы. Ниже приведены принципиальная схема и технические характеристики микросхемы.

Технология	ТТЛШ
Тип корпуса	201.14 - 1
Напряжение питания	5
Макс. ток низкого уровня	не более 8,8
Макс. ток высокого уровня	не более 4,4
Макс. вых. напряжение низкого уровня	не более 0,5
Мин. вых. напряжение высокого уровня, В	не менее 2,7
Макс. вх. ток низкого уровня	не более -0,36
Макс. вх. ток высокого уровня	не более 0,02
Диапазон рабочих температур	-10 - + 70С
Масса	1г.

Асинхронный RS-триггер.

Применяется в ключевой схеме ЗГ. Микросхема К555ТР2. Содержит 4 асинхронных RS-триггера с инверсными входами. Необходимое количество — 1 штука. Сигналы будем подавать на входы второго триггера (R₂ иS₂). Принципиальная схема микросхемы и её технические характеристики таковы:

Т ехнология	ТТЛШ
Тип корпуса	238.16-2
Мин. вых. напр. высокого уровня	2,7 В
Макс. вых. напр. низкого уровня	500мВ
Макс. вх. ток высокого уровня	20мкА
Макс. вх. ток низкого уровня	400мкА
Макс. ток потребления	7мА
Напр. питания	5В
Диапазон рабочих температур	-10 - + 70С

Питание к микросхемам, К555ЛЛ1, К555ЛИ1, К555ЛН1, К555ЛИ6 подводится: общий — 7, +5В — 14;

к микросхемам К555ТВ9, К555ТР2 — общий — 8, +5В — 16.

Также для контроля и управления работой устройства использованы:

Светоизлучающие диоды АЛ 307;

Семисегментный светодиодный индикатор АЛС324;

Переключатель МТ1;

Кнопка МП1.