Лекция 1. Общие понятия

Входные и выходные сигналы устройства управления могут быть двух видов: сигналы непрерывные (аналоговые) и прерывные (дискретные).

Использование дискретных сигналов имеет ряд преимуществ:

большая точность преобразования;

большая помехозащищенность;

простота устройств запоминания.

Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму.

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

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

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

ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем, что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние. Набор входных или выходных переменных в некоторый момент автоматного времени называется состоянием входа или выхода устройства управления.

Различают два типа дискретных устройств с разными свойствами. В устройствах первого типа значение каждого выходного сигнала у_i определяется только конкретными значениями входных сигналов х₁, х₂, …, х_n в рассматриваемый момент времени и не зависит от последовательности входных сигналов, подаваемых в предыдущие моменты времени. (Комбинационные схемы, автоматы без памяти)

В устройствах второго типа значение каждого выходного сигнала у_i зависят не только от конкретной комбинации значений входных сигналов х₁, х₂, …, х_n в рассматриваемый момент времени, но и от их предыдущих значений, имевших место в более ранние моменты времени. (Последовательные автоматы, автоматы с памятью)

Входная или выходная переменная называются «буквой»

Входной (выходной) «алфавит» - это непустое множество попарно различных символов (букв).

Конечная упорядоченная последовательность букв называется «словом» в данном алфавите.

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

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а₁) у которого:

1. A={a₁, a₂, ... ,a_k} – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.

2. X={x₁, x₂, ... ,x_m} – алфавит входных значений – множество значений, которые могут поступать на вход ЦА.

3. Y={y₁, y₂, ..., y_n} – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.

4. : AXA – функция переходов a(t+1)=(x(t),a(t)). Функция переходов определяет, в какое состояние a(t+1) перейдет автомат под воздействием входного сигнала x(t), если в текущий момент времени автомат находится в состоянии a(t).

5.  : AZW – функция выходов y(t)= (a(t),x(t)). Функция выходов определяет какое выходное значение y(t) будет установлено на выходе автомата в зависимости от входного значения x(t) и текущего состояния a(t).

6. a_iA - начальное состояние автомата – состояние, в которое устанавливается ЦА после подачи питания или после сброса

Рисунок 1 – Абстрактный автомат

Абстрактный автомат (рисунок 1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита X(t)  Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=[a(t), x(t)], a(t) A, y(t) Y.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где  - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рисунок 1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

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

Процесс проектирования сложных управляющих устройств включает следующие этапы:

1) составление алгоритма работы управления устройством;

2) блочный синтез. На этом этапе составляется структурная схема устройств;

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

Структурные схемы цифрового автомата.

Различают 2 вида автоматов:

1. Милли;

2. Мура;

Автомат Милли представляет собой:

a(t+1) - зависит от предыдущего нашего состояния и состояния входов. Функция выходов будет зависеть от того же.

Автомат Мура будет выглядеть так:

Синхронный автомат – такт формируется внешним сигналом от генератора.

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

Способы задания автоматов

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

Задать функцию переходов, значит задать определенный переход внутреннего состояния а_i во внутреннее состояние а_j, при воздействии входного сигнала х_n.

С оздать функцию выхода значит, что каждой паре (х_n, а_i) соответствует состоянию выхода y_i, причем y_i принадлежит множеству Y.

Графически это

выглядит следующим образом:

Существует 2 основных способа задания автомата: 1 способ. Задание таблиц переходов и выходов; 2 способ. Задание графов переходов.

Таблицы переходов и выходов более удобны при выполнении дальнейших преобразований.

При таком способе задания автоматов каждая строка таблицы переходов соответствует определённому состоянию входов автомата. Каждый столбец – внутреннему состоянию. На пересечении столбца а_i и строки x_k в таблице переходов ставятся состояния в которое автомат переходит из а_i под воздействием x_k.

Таблица перехода. Таблица выходов

	a1	a2	a3	а4
x1	a1	a3	a1
x2		a4	a1
x3	a4		a2	a4
x4	a2			a1

	a1	a2	a3	а4
x1	у1	у3	у1
x2		у1	у1
x3	у4		у2	у4
x4	у2			у1

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

Таблица переходов выходов может быть совмещена и называться совмещённой таблицей.

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

	a1	a2	a3	а4
x1	a1	a3	a1
x2		а1	a1
x3	a4		a2	a4
x4	a2			a1

Алгоритм построения таблиц переходов сводится к тому что предварительно фиксируется начальное состояние a₁, затем для каждого входного слова состоящего из к- букв, определяется «к» внутренних состояний a_1, a_2, a₃,… a_к.

В автомате Мура каждому внутреннему состоянию ставится в соответствии буква выходного алфавита.

x₁ x₂ x₃ x₁ x₂ x₃ x₄ x₁ –> y₁ y₂ y₃ y₁ y₃ y₂ y₂ y₁

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

х1	a1	y1
х2	a2	y2
x3	a3	y3
x1	a4	y1
x2	a5	y3
x3	a6	y2
x4	a7	y2
x1	a8	y1

Получим такую таблицу переходов

	y1	y2	y3	y1	y3	y2	y2	y1
	a1	a2	a3	a4	a5	a6	a7	a8
х1	a1		a4	a4			a8	a8
х2	a2	a2		a5	a5
x3		a3	a3		a6	a6
x4						a7	a7

Под действием сигнала x₂ автомата из состояниея a₁ переходит в состояние a₂, поскольку выходной сигнал продолжает действовать и после перехода, то возможен переход автомата под действием входного сигнала в любое другое состояние.

Чтобы состояние автомата были устойчивыми, необходимо доопределить таблицу переходов, т.е. на пересечении строки x_i со столбцом a_j записать состояние a_j, всё это делается для исключения произвольных переходов автомата.

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

	a1	a2	a3	a4	a5	a6	a7	a8
х1	a1/ y1		a4/ y1	a4/ y1			a8/ y1	a8/ y1
х2	a2/ y2	a2/ y2		a5/ y3	a5/ y3
x3		a3/ y3	a3/ y3		a6/ y2	a6/ y2
x4						a7/ y2	a7/ y2

Задание автоматов при помощи автоматных графов переходов.

1. Задание графа для автомата Мура.

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

Граф автомата Мили отличается от графа автомата Мура тем, что его вершины обозначаются одной буквой, а рёбра – двумя, первая из которых обозначает верхний сигнал под действием которого осуществляется переход, выходной сигнал – который вырабатывает автомат при соответствующем переходе; петля на графе соответствует устойчивому состоянию автомата.

x₃/y₃

Матричный способ задания автомата.

Матрица переходов – это математическая копия графа переходов у которой стороны и столбцы обозначены внутренними состояниями автомата. Элементы матрицы, которые находятся на пересечении строк и столбцов – это множество входных сигналов вызывающие переход автомата из состояния a_i в a_j и выходные сигналы вырабатываемые автоматом на соответствующем переходе.

	a1	a2	a3	a4
a1	x1/ y1	x2/ y1	x2/ y1	x1/ y1
a2			x3/ y2	x2/ y2
a3		x1/ y3		x3/ y3
a4	x3/ y4	x4/ y4

Задание автоматов при помощи графической схемы алгоритма.

Каждой вершине графа соответствует некоторый оператор реализующийся в этой вершине.

Оператором может быть формирование набора управляющих сигналов. Соединяющие вершины дуги указывают последовательность выполнения операторов.

Минимизация числа внутренних состояний.

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

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

Условиями работы автомата принято считать множество последовательных состояний входа и состояний выхода.

x₁, y₁; x₂, y₂; x₁, - ; x₃, y₁;

x₁, - ; x₂, y₂; x₁, y₂; x₃, y₁;

Безразличному состоянию выхода « – » может соответствовать любое значение «у».

Две последовательности не противоречивы, если в них не содержаться ни одной пары x_i y_j у которых одному и тому же состоянию входа соответствуют различные состояния выхода.

Два автомата реализующие одни и те же заданные условия работы называются эквивалентными.

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

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

Q=E[logB].

Q – количество элементов памяти.

B – количество внутренних состояний автомата.

E – округлить до ближайшего большего целого.

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

Минимизацию проводят 2-я методами:

1.Сначала берется автомат с одним внутренним состоянием, затем увеличивается количество внутренних состояний до тех пор, пока он не станет реализуемым.

2.С начала берется заведомо реализуемый автомат, затем минимизируется число внутренних состояний.

Наиболее разработан 2-й метод, когда автомат задан в виде таблицы переходов.

Рассмотрим метод минимизации числа внутренних состояний автоматов заданных таблицей переходов. Этот метод основан на выявлении и объединении эквивалентных, псевдо эквивалентных и совместимых внутренних состояний.

Эквивалентными состояниями полностью определённого автомата называются такие 2 состояния, которые удовлетворяют следующим условиям:

1)им соответствует одно и тоже состояние выхода автомата.

2) им соответствует одно и тоже состояние входа автомата.

3)любой последовательности состояний входа автомата соответствует одна и та же последовательность его выхода независимо от того какое из рассматриваемых состояний принято за исходное.

Для не доопределённого автомата кроме понятия эквивалентности введено понятие псевдо эквивалентности. Псевдо эквивалентными состояниями автомата называется такие 2 устойчивых состояния, которые удовлетворяют следующим 3-м условиям:

1) им соответствует одно и тоже состояние выхода автомата.

2) им соответствует непротиворечивое состояние входа автомата.

3) любой допустимой последовательности состояния входа соответствует непротиворечивые последовательности состояний его выхода.

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

(Мура)

	a1	a2	a3	a4	a5	a6	a7	a8
x1	a1		a4	a4			a8	a8
x2	a2	a2		a5	a5
x3		a3	a3		a6	a6
x4						a7	a7
	y1	y2	y3	y1	y3	y2	y2	y1

Группа объединенная в одно состояние обозначается произвольно выбранной буквой (S). Эти условия необходимы, но недостаточны для минимизации. Достаточным условием будет наличие в определённых строках объединяемых столбцов одинаковых символов S_i получаемых при преобразования группы символов a_i которые намечены к объединению.

Все символы внутренних состояний a_i разбивает на k - групп, количество которых равно количеству попарно различимых выходных состояний y_i. В каждую группу вносятся только те символы a_{i ,} которые отмечены одинаковыми выходными буквами y_i. Полученные группы символов состояний обозначим произвольно выбранными символами S_i.

S₁ – a₁ a₄ a₈ | a₄ - исключает

S₂ – a₂ a₆ a₇ | а₂

_{S3 – a3 a5 | а}5

	y1	y2	y3	y1	y3	y2	y2	y1
	a1	a2	a3	a4	a5	a6	a7	a8
	S1	S2	S3	S1	S3	S2	S2	S1
x1	S1		S1	S1			S1	S1
x2	S2	S2		S3	S3
x3		S3	S3		S2	S2
x4						S2	S2

Не имеет значения, в каком порядке будут объединены состояния:

а₁ а₈ – S₁ а₂ – S₂ а₃ – S₃ а₄ – S₅ а₅ – S₆ а₆ а₇ – S₄

	y1	y2	y3	y1	y3	y2	y2	y1
	S1	S2	S3	S5	S6	S4	S4	S1
x1	S1		S5	S5			S1	S1
x2	S2	S2		S6	S6
x3		S3	S3		S4	S4
x4						S4	S4

(Мили)

	a1	a2	a3	a4	a5	a6	a7	a8
x1	a1/y1		a4/y1	a4/y1			a8/y1	a8 y1
x2	a2/y2	a2/y2		a5/y3	a5/y3
x3		a3/y3	a3/y3		a6/y2	a6/y2
x4						a7/y2	а7/y2

Автомат Мили минимизируется так же объединением столбцов совмещённой таблицы переходов. Необходимое условие для объединения в одних и тех же строках объединяемых столбцов одинаковых входных букв y_i, либо выходных букв или клеток, или только свободных клеток.

Достаточное условие это наличие в одноимённых строках объединяемых столбцов одинаковых символов S_i полученных при образовании группы символов состояний в a_i неминимизированых таблицах переходов.

a₁ a₂ a₃ a₇ a₈ – S₁| a₃ - исключает

a₄ a₅ a₅ – S₂|

	S1	S1	S1	S2	S2	S2	S1	S1
	а1	a2	a3	a4	a5	a6	а7	a8
x1	S1/y1		S2/y1	S2/y1			S1/y1	S1/y1
x2	S1/y2	S1/y2		S2/y3	S2/y3
x3		S1/y3	S1/y3		S2/y2	S2/y2
x4						S1/y2	S1/y2

a₁ a₂ a₇ a₈ – S₁ a₃ a₄ – S₂ a₅ a₆ – S₃

	S1	S2	S3
x1	S1/ y1	S2/ y1
x2	S1/ y2	S3/ y3	S3/ y3
x3	S2/ y3	S2/ y3	S3/ y2
x4	S1/ y2		S1/ y2

Q=E log₂8=3 – для неминимизированной таблицы

Q=E log₂3=2 – для минимизированных автоматов.