Лабораторная работа № 4

Тема: «Конечные автоматы с памятью»

Цель: Приобретение практических навыков синтеза конечных автоматов.

4.1. Теоретические сведения [1].

Основные определения.

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

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

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

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

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

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

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

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

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

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

Конечный автомат М определяется двумя характеристическими функциями:

;

,

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

Рис.4.1 Блок-схема конечного автомата

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

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

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

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

	0	1	2	3			0	1	2	3
0 1 2 3	3 3 3 3	2 2 2 0	1 1 2 0	3 3 3 1		0 1 2 3	0 1 1 0	0 0 0 0	0 0 1 1	0 1 1 1

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

	0	1	2	3
0 1 2 3	3/0 3/1 3/1 3/0	2/0 2/0 2/0 0/0	1/0 1/0 2/1 0/1	3/0 3/1 3/1 1/1

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

На рис. 4.2 показан граф, построенный в соответствии с приведенной выше таблицей переходов. Так как из состояния 0 автомат переходит в состоянии 1,2 и 3, то из вершины0 графа исходят дуги к вершинам 1, 2 и 3. При этом переход в состояние 1 совершается под воздействием 2 и ему соответствует выход 0, поэтому дуга из вершин 0 и 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как 1/0. Переходы в состояние 3 совершаются под воздействиями 0 и 3 и им обоим соответствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция . Аналогично определяются и другие дуги графа. Так рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, которым соответствуют выходы 0 и 1. Следовательно, петля при вершине2 помечается как .

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

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

	0 0	0 1	0 2	0 3		1 0	1 1	1 2	1 3		2 0	2 1	2 2	2 3		3 0	3 1	3 2	3 3
	3 0	3 1	3 1	3 0		2 0	2 0	2 0	0 0		1 0	1 0	2 1	0 1		3 0	3 1	3 1	1 1

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

	0 0	0 0	0 0	0 0		0 1	0 1	0 1	0 1		1 0	1 0	1 0	1 0		1 1	1 1	1 1	1 1
	0 0	0 1	1 0	1 1		0 0	0 1	1 0	1 1		0 0	0 1	1 0	1 1		0 0	0 1	1 0	1 1
	1 1	1 1	1 1	1 1		1 0	1 0	1 0	0 0		0 1	0 1	1 0	0 0		1 1	1 1	1 1	0 1
	0	1	1	0		0	0	0	0		0	0	1	1		0	1	1	1

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным,и переменным состояния,, а также три выхода, соответствующие переменным состояния,и выходной переменной. Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки ЭЗ₁ и ЭЗ₂, получим структурную схему автомата (рис. 4.3).

Рис. 4.3 Структурная схема конечного автомата

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

Отличительной особенностью триггера как функционального устройства является свойство запоминания двоичной информации. Под памятью триггера подразумевают способность оставаться в одном из двух состояний и после прекращения действия переключающего сигнала. Приняв одно из состояний за «1», а другое за «0», можно считать, что триггер хранит (помнит) один разряд числа, записанного в двоичном коде.

Характеристическое уравнение триггера: , где

- значение выходной переменной на () - м такте;

- значение входной переменной на - м такте;

- значение выходной переменной на - м такте.

Типы триггеров: RS, JK, D, T

R (Reset – сброс) – вход для раздельной установки триггера в состояние «0» (Q=0, Q=1);

S (Set – установка) – вход для раздельной установки триггера в состояние «1» (Q=1, Q=0);

J (Jerk – внезапное включение);

К (Kill – внезапное отключение);

Т (Toggel – релаксатор) счетный вход триггера;

D (Delay – задержка, Drive - передача) информационный вход для установки триггера в «0» или «1»;

RS – триггер

RS-триггер - триггер, который сохраняет своё предыдущее состояние при нулевых входах и меняет своё выходное состояние при подаче на один из его входов единицы. Граф RS-триггера показан на рис. 4.4.

Рис.4.4 Граф переходов асинхронного RS-триггера

При подаче единицы на вход S (от англ. Set — установить) выходное состояние становится равным логической единице. А при подаче единицы на вход R (от англ. Reset — сбросить) выходное состояние становится равным логическому нулю. Состояние, при котором на оба входа R и S одновременно поданы логические единицы, в некоторых случаях является запрещённым, при такой комбинации RS-триггер переходит в третье состояние QQ=00. Одновременное снятие двух «1» практически невозможно. При снятии одной из «1» RS-триггер переходит в состояние, определяемое оставшейся «1». Таким образом RS-триггер имеет три состояния, из которых два устойчивых (при снятии сигналов управления RS-триггер остаётся в установленном состоянии) и одно неустойчивое (при снятии сигналов управления RS-триггер не остаётся в установленном состоянии, а переходит в одно из двух устойчивых состояний).

- функция перехода RS – триггера

Получим характеристическое уравнение RS – триггера. Для этого построим таблицу истинности:

i	0	1	2	3	4	5	6	7
	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	0	1	1	1	0	0	Х	Х

Представим функцию перехода на карте Карно:

По карте запишем:(4.1)

Чтобы записать выражение для преобразуем (4.1) в базисне - или :

(4.2)

По Карте Карно получим для :

(4.3)

Преобразуем (4.3) в базис не-или:

(4.4)

Учитывая (4.2) и (4.4) построим логическую схему RS – триггера в базисе не - или:

Структурная схема условное графическое

изображение

Аналогично, преобразуем (4.1) в базис не -и:

(4.5)

Преобразуем (4.3) в базис и - не:

(4.6)

Учитывая (4.5) и (4.6) имеем:

Структурная схема условное графическое

изображение

Т – триггер со счетным входом

Синхронный Т-триггер, при единице на входе Т, по каждому такту на входе С изменяет своё логическое состояние на противоположное, и не изменяет выходное состояние при нуле на входе T. Т-триггер может строиться на RS – триггере.

- функция перехода Т – триггера,

где - значение сигнала на выходе Q после действия управляющего импульса, т.е на () - м такте;

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

С (Clock – тактовый вход) разрешает запись информации в триггер.

Аналогично, как и в предыдущем случае, получим по таблице истинности характеристическое уравнение Т – триггера.

i	0	1	2	3
	0	0	1	1
	0	1	0	1
	0	1	1	0

- характеристическое уравнение Т-триггера

Условно-графическое изображение

На рис. 4.5 представлены структурная схема Т – триггера, построенного на двух синхронныхRS – триггерах.

Рис.4.5 Структурная схема Т – триггера

В интервале между входными импульсами С₁=0 и С₂=1 на выходах Т₂ получаем те же сигналы, что и на входах Т₁: . Когда поступает управляющий импульс (С₁=1), информация с выходов Т₂ записывается в Т₁ и получаем: . В это время С₂=0 и состояние Т₂ не изменяется. По окончании управляющего импульса вновь имеем С₂=1 и информация из Т₁ теперь записывается в Т₂, так, что состояние изменяется на противоположное. Следовательно, в результате действия каждого управляющего импульса Т-триггер переключается в противоположное состояние с задержкой, равной длительности этого импульса (рис.4.6).

Рис.4.6 Временные диаграммы работы Т – триггера

Пример.На ленте конвейера в произвольном порядке движутся детали типа А и В. Синтезировать КА, который будет комплектовать из этих деталей упорядоченные тройки АВА, АВА,….АВА.

Словесное описание работы.

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

Тогда множество входных сигналов это типы деталей А и В.

или .

Состояния автомата , где

0 – начальное состояние (нет деталей);

1 – отобрана деталь А;

2 – отобраны детали А,В.

Сброс детали на дополнительный конвейер сопровождается сигналом и будет являться выходом КА. Тогда , 0 и 1 это непорядковые номера, а «0» - означает, нет сигнала сброса, «1» - есть сигнал сброса.

Граф-схема

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

	А	В
0	1	0
1	1	2
2	0	2

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

	А	В
0	0	1
1	1	0
2	0	1

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

	0 0 0 1 1 1
	0 1 2 0 1 2
	1 1 0 0 2 2
	0 1 0 1 0 1

Зададим КА в виде таблицы закодированных состояний

	0 0	0 0	0 0	0 1	0 1	0 1
	0 0	0 1	1 0	0 0	0 1	1 0
	0 1	0 1	0 0	0 0	1 0	1 0
	0	1	0	1	0	1

Изобразим структурную схему КА

Выпишем структурные формулы в СДНФ по каждому выходу, оперируя таблицей:

Построим схему КА на логических элементах

4.2. Задание

а) сконструировать замок с секретом. Замок имеет две кнопки: А и В. Открываться он должен после того, как буква за буквой будет введено слово ААВ. Во всех остальных случаях должен звучать сигнал тревоги;

б) синтезировать автомат, который в беспорядочной последовательности деталей А и В подсчитывал бы число случаев, когда детали А расположены парами и только парами. Т. е. Автомат должен подавать сигнал в счетчик после каждой встреченной им пары АА, расположенной обязательно между деталями В;

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

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

4.3. Контрольные вопросы

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

4.3.2. Какими основными характеристическими функциями может быть задан КА?

4.4.3. Перечислите способы представления КА.

4.4.4. В чем заключается синтез КА.

4.4.5. Какие элементы могут быть использованы для реализации памяти КА?

4.4.6. Что такое триггер? Характеристическое уравнение триггера в общем виде.

4.4.7. Реализация логической схемы RS – триггера в базисах {не-и, не-или}.

СПИСОК ЛИТЕРАТУРЫ

1. “Конспект лекций по курсу: «Основы дискретной математики» для студентов, обучающихся по направлениям подготовки «Системная инженерия», «Телекоммуникации»./ Жукова Н.В., Зайцева Е.Є. – Донецк. ДонНТУ, 2010.– 103 с.,

2. Математический аппарат инженера. Сигорский В.П. «Техника», 1975, 768с.

3. Ерусалимский Я.М. Дискретная математика: Теория, задачи, приложения. – 5-е изд.- М.: Вузовская книга, 2002. – 268с.

4. Джеймс Андерсон Дискретная математика и комбинаторика.: Пер. с англ. – М.:Вильямс, 2003. – 960 с.: ил.

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов–М.: Наука, 1975.-240с.

6. Бойко В.И. и др. Схемотехника электронных систем. Цифровые устройства. СПб: БХВ – Петербург, 2004. – 512с.:ил.