Общие сведения о цифровых автоматах

Размещено на http://www.allbest.ru/

Лекции

Общие сведения о цифровых автоматах

Лекция 1. Основные понятия и определения

сумматор цифровой автомат счетчик

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

Все схемы ЭВМ можно разделить на два больших класса:

1. Класс логических или комбинационных схем (КС).

2. Класс конечных автоматов.

В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1 t.

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

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

Переключательной или Булевой функцией называется функция f(x1, x2, …, xn), способная принимать так же как и её аргументы x1, x2, …, xn только два значения 0 или 1.

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

Свойства переключательных функций.

1. Любая ПФ n аргументов определена на 2n наборов.

2. Число различных ПФ n аргументов конечно и равно .

Мы будим использовать аппарат алгебры логики к синтезу схем ЭВМ. Это использование основано на следующем: будем отождествлять значение ПФ с выходными сигналами КС, а ее аргументы - с входными сигналами. Тогда ПФ будет описывать процесс преобразования КС входных сигналов в выходные и аппарат Булевой алгебры можно применять при синтезе таких схем. Под синтезом КС будем понимать определение таких способов соединения нескольких простейших схем, называемых логическими элементами, при которых построеные схемы реализуют заданный алгоритм преобразования сигналов при заданном критерии качества. В качестве критерии оценки качества технической реализации заданного алгоритма обычно используют критерий сложности или быстродействия схем.

Общий вид КС можно представить следующим образом:

Схема имеет n входов и m выходов и следовательно реализуют m ПФ от n аргументов. Любая сколь угодно сложная КС строится из более простых схем, называемых логическими элементами.

Логическим элементом называется электронная схема, реализующая элементарную ПФ и имеющая количество входов, равное числу аргументов ПФ и только один выход.

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

1. Последовательное соединение элементов.

2. Перестановка входов элементов.

Пусть имеется два логических элемента, реализующие ПФ f1(x1, x2) и f2(у1, у2). При последовательном соединении этих элементов получим схему, реализующую функцию уже трех аргументов:

Эта схема реализует функцию f3(x1,x2, y2), получаемую в результате постановки вместо аргумента y1 функции f2 (y1,y2) значение функции f1(x1,x2). Подстановка в функцию вместо ее аргументов других функций называется суперпозицией. Таким образом, последовательному соединению логических элементов соответствует математическая операция суперпозиция.

Изменим порядок подключения входов элементов.

В этом случае схема реализует функцию f4(y2,x1,x2), которая в общем случае отличается от функции f3(x1,x2, y2). В математическом плане мы заменили одни аргументы ПФ другими.

Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

Таким образом, перестановка входов логических элементов соответствует математической операции подстановки аргументов. В Булевой алгебре доказывается, что из ПФ одного или двух переменных можно с помощью операций суперпозиции и подстановки получить все ПФ от большего числа аргументов. Для нас это означает, что из логических одно или двухвходовых элементов можно построить любую сколь угодно сложную КС.

Рассмотрим ПФ от разного числа аргументов.

Переключательные функции одного аргумента.

Существует четыре различных ПФ одного аргумента, таблица истинности которых имеет следующий вид:

Х	f0(x)	f1(x)	f2(x)	f3(x)
0	0	0	1	1
1	0	1	0	1

Функция f0(x) называется константой нуля и обозначается f0(x)=0 при любом x.

Аналогично функция f3(x) и называется константа единицы т.е. f3(x)=1.

Функция f1(x) повторяет значение аргумента x и следовательно f1(x)=x.

Функция f2(x) принимает значение противоположное значению аргумента x. Эту функцию называют отрицанием (инверсией) переменной x и вводят для нее специальное обозначение f2(x)=. Черта стоящая над аргументом имеет смысл определенного функционального преобразования и называется знаком отрицания.

Логический элемент, реализующий функцию отрицания, называют элементом НЕ или инвертором и по ГОСТу обозначают следующим образом:

Переключательные функции двух аргументов.

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

X1	X2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

f0(x1,x2)=0 - функция константа нуля.

F15(x1,x2)=1 - функция константа единицы.

F3(x1,x2)=х1,

F5(x1,x2)=х2,

F12(x1,x2)=,

F10(x1,x2)=.

Рассмотрим оставшиеся десять ПФ от двух аргументов.

Функция f1(x1,x2) называется логическое произведение или конъюнкция и обозначается: f(x1,x2)=х1*х2=х1^х2=х1&х2.

Таблица истинности этой функции совпадает с таблицей умножения двух одноразрядных двоичных чисел т.е. f1(x1,x2)=1 тогда, когда аргументы равны между собой и равны единице, в остальных случаях функция равна нулю. Логический элемент, реализующий эту функцию, называют элементом И или конъюнктором. Обозначение конъюнктора на функциональных схемах:

Конъюнкция легко обобщается на случае n аргументов, когда реализуется функция вида: f(x1,x2,…,xn)=x1*x2*…*xn. Функция конъюнкция n аргументов равна единице тогда, когда все аргументы равны единицы.

Функция f7(x1,x2) - называется дизъюнкцией х1 или х2 и обозначается f7(x1,x2)=x1vx2.

Дизъюнкция реализуется элементом, который называется элементом ИЛИ или дизъюнктором.

Сигнал на выходе дизъюнктора принимает нулевое значение только в том случае, если ни один из входных сигналов не имеет в данный момент времени единичное значение.

Функция f9(x1,x2)=x1~x2 - равна единице тогда, когда оба аргумента равны между собой. Это функция носит название логической равнозначности.



Функция f6(x1,x2)=x1x2 - логическая неравнозначность или сумма по модулю 2. эта функция принимает единичное значение тогда, когда х1?х2. Второе название этой функции объясняется тем, что таблица истинности f6 совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю 2, т.е. 0+0=0, 1+0=1, 0+1=1, 1+1=0. Обобщим эту функцию на случай n аргументов. Такая функция принимает единичное значение тогда, когда число аргументов равных единице нечетно и равна нулю если число аргументов четно.

Функции f11(x1,x2)= и f13(x1,x2)= называются импликациями и читаются: если х2, то х1 для f11, или если х1, то х2 для f13.

Функция f11 принимает нулевое значение только тогда, когда х2=1, х1=0.

Функция f2(x1,x2)=x1x2 - читается: не верно, что если х1, то х2 и является инверсией функции импликации f13.

.

Функция f13:

.

Функция f14(x1x2)=x1/x2= называется штрихом Шеффера и является отрицанием функции конъюнкции. Элемент, реализирующий эту функцию, называется элемент И-НЕ и обозначается:

.

f8(x1x2)=x1vx2=. Функция f8 - называется стрелкой Пирса и является отрицанием от дизъюнкции. Элемент, реализующий эту функцию, называется элемент ИЛИ-НЕ и обозначается:

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

Система ПФ {f1, f2,,…,fm}, из которых с помощью операций суперпозиции и подстановки можно получить любую сколь угодно сложную ПФ, называется функционально полной системой (ФПС) ПФ. Такие системы ПФ называют базисом.

Приведем примеры некоторых базисов:

1. f=x1/x2

2. f=x1vx2

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

3. f1=x1vx2

f2=x1&x2

f3=

4. f1=x1x2

f2=x1&x2

f3=1 - базис Жигалкина

Возникает вопрос какие ПФ представляют наибольший практический интерес?

Оказывается, что наиболее удобный для решения задач синтеза схем ЭВМ является ФПС ПФ, содержащая операции конъюнкция, дизъюнкция и отрицание, т.е. булев базис. Этот набор ПФ обладает замечательным свойством: может построить любую КС так, что она будет содержать наименьшее количество элементов, в крайнем случае, равное. Поэтому эта система называется основной функционально полной системой ПФ.

Логические элементы.

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

В эту систему элементов входят как элементы универсального базиса: И-НЕ, ИЛИ-НЕ, так и комбинации операций булевого базиса: И-ИЛИ-НЕ.

Логические элементы характеризуются следующими параметрами:

1. коэффициентом объединения;

2. коэффициентом разветвления.

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

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

Покажем процедуру разделения входов на примерах:

1) Пусть необходимо реализовать в булевом базисе функцию от четырёх аргументов f=x1x2x3x4 при J=2.

2) Пусть необходимо реализовать функцию f= в базисе И-НЕ при J=2.

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

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

1) Дублированием выходного сигнала.

2) Дублированием элемента.

Покажем, как производится разгрузка элементов на примерах:

Пусть F=4 и к выходу некоторого элемента необходимо подключить семь входов других элементов. Тогда для дублирования сигнала можно использовать два инвертора.

Пусть элемент имеет два выхода прямой и инверсный:

Недостаток этого метода заключается в увеличении задержки сигнала в схеме. От этого недостатка свободен способ разгрузки за счет дублирования элемента.



Раздел 2. Синтез цифровых автоматов без памяти

Лекция 2. Этапы синтеза

Будем рассматривать синтез КС, реализующих одну ПФ. Процесс синтеза КС на элементах заданного базиса разбивается на следующие этапы:

1) Аналитическая запись ПФ в булевом базисе (запись в виде СДНФ или в СКНФ).

2) Минимизация ПФ в булевом базисе.

3) Представление полученного после минимизации выражения в заданном базисе (переход к заданному базису).

4) Построение КС, реализующей полученное выражение, с учетом коэффициентов объединения, разветвления и требуемого быстродействия.

Минимизация ПФ в булевом базисе.

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

В процессе минимизации СДНФ получается последовательно в начале сокращенная ДНФ, далее тупиковая и минимальная.

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

Метод минимизации Блейка-Порецкого.

Недостатком метода Квайна является то, что для его применения необходимо представить функцию в СДНФ. Процесс такого представления для функции с большим числом аргументов зачастую является весьма громоздкой задачей, т.е. было бы желательно найти возможность построения сокращенной ДНФ, не по СДНФ, а по произвольной ДНФ данной функции. Идея построения сокращенной ДНФ по произвольных ДНФ была предложена в работах А. Блейка и П.С. Порецкого и основывается на следующей лемме.

Лемма:

Если в ДНФ для данной функции f(x1,…,xn) входят две конъюнкции вида Ахi и B, то имеет место следующее равенство:

f=fvAB.

Доказательство леммы:

Запишем функцию f в следующем виде:

.

Из доказанной леммы вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что исходную функцию необходимо пополнить новыми членами вида АВ согласно лемме. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ. Процесс пополнения ДНФ осуществляется согласно лемме по формуле, которая называется операцией обобщенного склеивания:

Axi v B= Axi v B v AB.

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

Операция неполного склеивания является частным случаем операцией обобщенного склеивания при А=В.

Axi v A = A v Axi v A.

Рассмотрим примеры:

1. Найти сокращенную ДНФ для функции трех аргументов:

.

При использовании метода Блейка-Порецкого применяется операция поглощения, которую можно представить в виде х v xy=x.

2. Пусть дана функция трех аргументов:

.

Табличный метод минимизации ДНФ.

Метод диаграмм Вейча или карт Карно.

Методы Квайна и Блейка-Порецкого являются аналитическими. В этих методах наиболее трудоемким является процесс отыскания склеивающихся между собой конъюнкций. Существуют методы, которые позволяют упростить поиск склеивающихся членов. Один из наиболее удобных методов минимизации ПФ от небольшого числа переменных основан на использовании диаграмм Вейча или карт Карно. Диаграмма Вейча представляет собой фактически таблицу истинности ПФ, которая представляется не в виде столбцов, а в виде специальных карт. Каждой клетке диаграммы соответствует определенный набор значений аргументов. Поэтому диаграммы можно рассматривать как графическое представление совокупности всех конституэнт единицы. При этом диаграмма строится таким образом, что склеивающиеся между собой конституэнты оказываются расположенными в соседних клетках, т.к. отличаются значением только одной переменной. Приведем примеры построения диаграммы Вейча и карт Карно для ПФ от разного числа аргументов.

Переключательные функции двух аргументов.

Диаграмма Вейча:

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

Переключательные функции трех переменных.



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

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

Переключательные функции четырех переменных.



1) нарисуем схему в булевом базисе.

ДНФ:

КНФ:

Построим схему, реализующую функции f1 в базисе И-НЕ (штрих Шеффера). Для этого осуществим переход от булевого базиса к базису И-НЕ.

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

Лекция 3. Переключательная функция для пяти переменных

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

Преобразование функции в минимальную конъюнктивную нормальную форму (КНФ).

Для того, чтобы получить выражение заданной ПФ в форме, содержащей минимальное количество букв, следует, кроме минимальной ДНФ получить также минимальную КНФ и выбрать ту из них, которая содержит меньшее число букв. Существуют различные методы минимизации КНФ. Рассмотрим один из таких методов основанной на минимизации функции и в переходе с помощью формулы де Моргана к функции f. При минимизации можно использовать все методы, которые применялись ранее при нахождении минимальной ДНФ. После получения минимальной ДНФ функции с помощью формул де Моргана переходят к минимальной КНФ функции f.

Рассмотрим пример:

Возьмем функцию четырех переменных:

f=v(4,14)

.

Минимизация не полностью определенных переключательных функций.

В ЭВМ иногда применяются КС, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называются запрещенными. Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е. функциями, значения которых определены не на всех наборах аргументов. Поэтому минимизация не полностью определенных ПФ с помощью карт Карно сводится к такому до определению ПФ, при котором получаются группы с максимальным числом соседних единиц в каждой группе, а число таких групп минимально. При этом ПФ будет содержать минимум букв.

Пример:

Найти минимальную ДНФ и минимальную КНФ не полностью определенной ПФ от четырех переменных. Функция равна единице на наборах: f=v(2,12,13) и равна нулю на наборах: f=v(5,9,15). На остальных наборах функция не определена.

Минимизация систем переключательных функций.

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

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

Пусть дана система ПФ состоящая из трех ПФ от четырех аргументов

Раздел 3. Общая теория конечных цифровых автоматов с памятью

Лекция 4. Основные понятия и определения

В вычислительной технике в основном используется схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью комбинационных схем является наличие жесткой функциональной зависимости между выходным сигналом и входным:
y ( t ) = f ( x ( t )). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии комбинационных схем схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения.

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

Кодирование информации

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

Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1 и т.д.

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

Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

X(x1,…,xm)	--->	A(a0,...,an)	--->	Y(y1,…,yk)

Автомат функционирует в дискретные моменты времени, интервал, между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T=const) и асинхронного действия (Tconst). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.

Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, , ), где A = {a0,a1,a2,...,an}- множество внутренних состояний автомата, X = {x1, x2,…, xm} - множество входных сигналов (входной алфавит), xi - буква входного алфавита, Y = {y1, y2,…, yk} - множество выходных сигналов (выходной алфавит),

- функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находится в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, то есть a(t+1) = [a(t), x(t)],

- функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = [a(t), x(t)].

Автомат работает следующим образом: в каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний. Причем в начальный момент времени t = 0 он всегда находится в состоянии a(t = 0) = a0. В момент времени t автомат воспринимает входной сигнал x(t), выдает выходной сигналу y(t) = [a(t), x(t)] и переходит в следующее состояние a(t+1)=[a(t), x(t)]. Другими словами абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t+1) и y(t). Такие автоматы называют детерминированными. На преобразование информации в детерминированных автоматах наложены условия.

Условия преобразования информации в детерминированных автоматах:

1. Любое входное слово, длинною l букв, преобразуется в выходное слово той же длины.

2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l1 букв, в выходных словах первые l1 букв также совпадут.

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

Применяемые на практике автоматы принято разделять на два класса - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Функционирование автоматов строго подчиняется определённым законам (законы функционирования автоматов). Законы функционирования автоматов описываются системами уравнений: Автомат Мили:

a(t + 1) = [a(t),x(t)]

y(t) = [a(t),x(t)]

t = 1,2,3…

Автомат Мура:

a(t + 1) = [a(t),x(t)]

y(t) = [a(t)]

t = 1,2,3…

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.

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

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, , } . То есть необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов и выходов. При этом среди множества A = {a0,a1,…, an} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

Табличный способ

При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

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

xj\ai	a0	…	an
x1	(a0,x1)	…	( an,x1)
…	…	…	…
xm	( a0,xm)	…	( an,xm)

Таблица выходов

xj\ai	a0	…	an
x1	( a0, x1)	…	( an, x1)
…	…	…	…
xm	( a0, xm)	…	( an, xm)

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы - состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = [ ai, xj], в которые автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов - соответствующий этому переходу выходной сигнал yg = [ ai,xj]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.

Совмещенная таблица переходов и выходов автомата Мили.

xj\ai	a0	…	an
x1	(a0,x1)/ (a0,x1)	…	(an,x1)/ (an,x1)
…	…	…	…
xm	(a0,xm)/ (a0,xm)	…	(an,xm)/ (an,xm)

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

Отмеченная таблица переходов автомата Мура

yg	(a0)	…	(an)
xj\ac	a0	…	an
x1	(a0,x1)	…	(an,x1)
…	…	…	…
xm	(a0,xm)	…	(an,xm)

В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = (a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. Примеры табличного задания автоматов Мили и Мура.

Автомат Мура:

yg	y2	y1	y1	y3	y2
xj\xj	a0	a1	a2	a3	a4
x1	a2	a1	a3	a4	a2
x2	a3	a4	a4	a0	a1

Автомат Мили:

xj\ai	a0	a1	a2	a3
x1	a1/y1	a2/y3	a3/y2	a0/y1
x2	a0/y2	a0/y1	a3/y1	a2/y3

По этим таблицам можно найти реакцию автомата на любое входное слово.

Графический способ.

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, то есть as = (ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

Граф для автомата Мили

Граф для автомата Мура

Частичные автоматы.

В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат - частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai, xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще.

Пример таблицы переходов и выходов частичного автомата Мили

xj\ai	a0	a1	a2	a3
x1	a1/y1	a3/y3	a2/y2	a2/y1
x2	- / -	- / -	a0/y4	a0/y2

Лекция 5. Элементарные автоматы

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

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

Теорема о структурной полноте формулируется следующим образом:

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

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

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

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

Элементарные автоматы

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

1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями;

2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1;

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

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

Элементарный автомат

Т-триггер.

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

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

yg	0	1
xj\ai	0	1
T=0	0	1
T=1	1	0

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

Матрица переходов:

T	Q(t)	Q(t+1)
0	0	0
1	0	1
1	1	0
0	1	1

Матрица переходов определяет значения сигналов на входах элементарного автомата, обеспечивающие каждый их четырех возможных переходов. Здесь Q(t) и Q(t+1) - состояния автомата в моменты времени t и t+1 соответственно. Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки.

Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча по матрице перехода.

Диаграмму Вейча

T\Q(t)	0	1
0	0	1
1	1	0

Поскольку эта формула совпадает с аналитической записью переключательной функции сложение по модулю два, то Т-триггер часто называют триггером со счетным входом Т, а входной сигнал, поступающий на вход Т, счетным сигналом. На практике кроме асинхронного Т-триггера, работу которого мы рассмотрели, используют так же и синхронный Т-триггер, который в отличие от асинхронного меняет свои состояния только при Т = 1 и С = 1. Если хотя бы один из этих сигналов равен нулю, то триггер сохраняет свое состояние. Вход С называют входом синхронизации.

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

D-триггер. D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что Q(t+1) = D(t). Название D-триггера происходит от английского слова “delay” - задержка. Из определения следует, что состояние триггера в момент времени t+1 повторяет значение входного сигнала D(t) в момент времени t (отсюда и название триггера задержки).

Матрица переходов для D-триггера:

D	Q(t)	Q(t+1)
0	0	0
1	0	1
0	1	0
1	1	1

Обозначения асинхронного и синхронного D-триггеров:

В синхронном D-триггере при С=0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть

Q(t+1)=D(t)*C(t) v Q(t)*C(t)

Асинхронный D-триггер практического значения не имеет.

Граф D-триггера

RS-триггер

RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S такие, что при S=1 и R=0 триггер принимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым.

Матрица переходов RS-триггера:

R	S	Q(t)	Q(t+1)
b1	0	0	0
0	1	0	1
1	0	1	0
0	b2	1	1

Комбинация сигналов R=1 и S=1 является запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая может принимать два значения 0 v 1. Аналогично, переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R=0, S=0 и R=0, S=1. Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записана переменная b2. По матрице переходов можно построить граф RS-триггера.

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

Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча:

	SQ(t)
T	00	01	10	11
0	0	1	1	1
1	0	0	-	-

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

Q(t+1) = S v R *Q(t)

JK-триггер

JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K, который при условии J * K = 1 осуществляет инверсию предыдущего состояния (т.е. при J*K=1, Q(t+1) = Q(t)), а в остальных случаях функционируют в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Этот триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то есть зависимость Q(t+1) = f [J, K, Q(t)] имеет вид:

Таблица истинности JK-триггера

J	K	Q(t)	Q(t+1)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

По этой таблице можно построить диаграмму Вейча для Q(t+1), которую можно использовать для минимизации, и матрицу переходов:

	KQ(t)
J	00	01	10	11
0	0	1	0	0
1	1	1	0	1

Матрица переходов JK-триггера:

J	K	Q(t)	Q(t+1)
0	b1	0	0
1	b2	0	1
b3	1	1	0
b4	0	1	1

Q(t+1) = J* Q(t) v K *Q(t)

В интегральной схемотехнике применяются только тактируемые (синхронные) JK триггера, которые при C=0 сохраняют свое состояние, а при C=1 работают как асинхронные JK триггера.

Универсальный триггер.

Триггер JK относится к разряду универсальных триггеров, поскольку на его основе путем несложной внешней коммутации можно построить RS-, D- и T- триггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как эта комбинация является запрещенной для RS триггера.

Счетный триггер на основе JK триггера получается путем объединения входов J и K.

Триггер задержки (D-триггер) строится путем подключения к входу K инвертора, на который подается тот же сигнал, что и на вход J. В этом случае вход J выполняет функцию входа D, а все устройство в целом реализует таблицу переходов D-триггера.

Лекция 6. Структурная схема конечного автомата

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

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

Каждое состояние абстрактного автомата ai, где i={0, n}, кодируется в структурных автоматах набором состояний элементов памяти Qi, r={1, R}. Поскольку в качестве элементов памяти используются обычные триггера, то каждое состояние можно закодировать двоичным числом ai = Q1a1Q2a2... Qrar. Здесь аi={0, 1}, a Q - состояние автомата.

Общее число необходимых элементов памяти можно определить из следующего неравенства

Здесь (n+1) - число состояний. Логарифмируя неравенство получим

Здесь ] C [ - означает, что необходимо взять ближайшее целое число, большее или равное C.

В отличии от абстрактного автомата, имеющего один входной и один выходной каналы, на которые поступают сигналы во входном X={x1,x2,...,xm} и выходном Y={y1, y2,..., yk} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата.

xi = o1a1 o2a2... oLaL
yg = Z1a1Z2a2... ZNaN

Здесь of и Zh- состояния входных и выходных каналов соответственно.

Очевидно число каналов L и N можно определить по формулам

;

аналогичным формуле для определения R.

Изменение состояния элементов памяти происходит под действием сигналов U=(U1,U2,...,Ur), поступающих на их входы. Эти сигналы формируются комбинационной схемой II и называются сигналами возбуждения элементарных автоматов. На вход комбинационной схемы II, кроме входного сигнала xj, по цепи обратной связи поступают сигналы Q=(Q1, Q2, ..., QR), называемые функцией обратной связи от памяти автомата к комбинационной схеме. Комбинационная схема I служит для формирования выходного сигнала yg, причем в случае автомата Мили на вход этой схемы поступает входной сигнал xj, а в случае автомата Мура - сигнал xj не поступает, так как yg не зависит от xj.

Табличный метод структурного синтеза конечных автоматов

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

Пример. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:

xj\ai	a0	a1	a2
x1	a1/y1	a1/y2	a1/y2
x2	a2/y3	a2/y3	a0/y1

В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов - элементы И, ИЛИ, НЕ. Итак, имеем A={a0,a1,a2}; X={x1,x2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3.

1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов.

R = ] log2(n+1) [ = 2
L = ] log2 m [ = 1
N = ] log2 k [ = 2

Таким образом, необходимо иметь два элементарных автомата Q1 и Q2 (так как R=2), один входной канал O1 и два выходных канала Z1 и Z2.

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

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

Перерисованная совмещенная таблица переходов и выходов

xj\ai	00	01	10
0	01/00	01/01	01/01
1	10/10	10/10	00/00

В таблицах кодирования выходные каналы Z1 и Z2 называются физическими выходами автомата.

3. Пользуясь таблицами кодирования, можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний Qi(t+1) элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. То есть:

Qi(t+1)=fi[Q1(t), Q2(t),…,QR(t),O1(t),…, OL(t)]

В кодированной таблице выходов - выходные сигналы Zl(t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t. То есть:

Zl(t)=fi[Q1(t),Q2(t),…,QR(t),O1(t),…,OL(t)]

Кодированная таблица переходов и выходов (совмещенная) имеет следующий вид:

(t)	(t+1)
o1	Q1	Q2	Z1	Z2	Q1	Q2
0	0	0	0	0	0	1
0	0	1	0	1	0	1
0	1	0	0	1	0	1
0	1	1	-	-	-	-
1	0	0	1	0	1	0
1	0	1	1	0	1	0
1	1	0	0	0	0	0
1	1	1	-	-	-	-

В нашем случае:

Zl(t) = fi1[Q1(t), Q2(t), O1(t)], Z2(t) = fi2[Q1(t), Q2(t), O1(t)]

Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t.

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

J	K	Q(t)	Q(t+1)
0	b1	0	0
1	b2	0	1
b3	1	1	0
b4	0	1	1

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

Таблица функций возбуждения:

(t)	(t+1)
o1	Q1	Q2	J1	K1	J2	K2	Q1	Q2
0	0	0	0	b	1	b	0	1
0	0	1	0	b	b	0	0	1
0	1	0	b	1	1	b	0	1
0	1	1	-	-	-	-	-	-
1	0	0	1	b	0	b	1	0
1	0	1	1	b	b	1	1	0
1	1	0	b	1	0	b	0	0
1	1	1	-	-	-	-	-	-

Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени, что и Qi.

Поскольку функции возбуждения J(t) и K(t) определенны в тот же момент времени, что и их аргументы Q1(t), Q2(t) и O1(t), то эти функции являются переключательными. В результате мы получим систему переключательных функций Z1(t), Z2(t), J1(t), K1(t), J2(t) и K2(t) заданных в виде таблиц их истинности.

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

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

Диаграммы Вейча

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

Схема конечного автомата

Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе других схем ЭВМ. Например, в схеме регистра сдвига информации добавляется цепь «установка в 0». Другие изменения связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов.

Лекция 7. Технические особенности конечных автоматов

В схемах ЭВМ все сигналы изменяются и воспринимаются, как правило, в дискретные моменты времени, обозначаемые числами натурального ряда t=0, 1,…. Для отметки моментов дискретного времени ЭВМ содержит специальный блок, вырабатывающий синхронизирующие импульсы (СИ), следующие через равные интервалы времени Т. Этот интервал времени Т определяет такт работы устройства.

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

Под действием СИ1 формируются выходные сигналы Zl(t) = g[a(t),x(t)], а под действием СИ2 автомат переводится в новое состояние a(t+1). В результате структурная схема автомата имеет следующий вид:

Здесь U - сигналы возбуждения триггеров. Согласно приведенной схеме на входах каждого из триггеров стоят двухвходовые элементы И. На практике триггера часто выполняются в синхронном варианте (синхронные триггера), когда упомянутые элементы И включают в схему триггера.

Например, схему синхронного RS-триггера можно рассматривать как состоящую из асинхронного RS-триггера, ко входам R и S которого подключены двухвходовые элементы И. На эти элементы кроме входных сигналов поступает синхронизирующий сигнал, обозначаемый буквой C.

Очевидно, синхронные триггера будут сохранять свои состояния при С=0, а переходы в них возможны при С=1. Если С=1, то переходы в синхронном триггере будут осуществляться также, как в асинхронном. Применение синхронных триггеров в качестве элементов памяти конечного автомата облегчает организацию синхронизации таких автоматов.