Анализ и синтез автоматов

Дисциплина "Математические основы теории систем" является составной частью фундаментальной теоретической подготовки по специальности «Информационные системы и технологии». Предметом изучения являются общие средства математического описания объектов управления и носителей информации - сигналов; а также математические методы исследования с применением ЭВМ,
Цель выполнения курсовой работы – закрепление знаний и приобретение навыков по анализу сигнальных графов, синтезу комбинационных схем и разработке автоматов с памятью.

ВВЕДЕНИЕ
1. АНАЛИЗ СИГНАЛЬНЫХ ГРАФОВ
1.1 Методика выбора задания
1.2 Преобразование структурной схемы к сигнальному графу
1.3 Определение структурных характеристик графа
2. СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ
2.1 Общие положения
2.1.1 Конечный автомат
2.1.2 Анализ технического задания
2.2 Минимизация логических функций
2.2.1 Общие положения
2.2.3 Минимизация методом Квайна-Мак-Класки
2.2.4 Минимизация методом неопределённых коэффициентов
2.3 Разработка функциональной схемы
3. СИНТЕЗ АВТОМАТА С ПАМЯТЬЮ
3.1 Анализ технического задания
3.2 Формальное описание абстрактного автомата
3.3 Структурный синтез
ЗАКЛЮЧЕНИЕ
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

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

1.2 Преобразование структурной схемы к сигнальному графу
Граф прохождения сигнала , где Х – множество вершин,– множество дуг, имеет следующие особенности:
1. Каждой вершине графа ставится в соответствие одна переменная структурной схемы (обозначение переменных сигналов приведено на рис. 1.2 в произвольном порядке).
2. Каждой дуге поставлена в соответствие передаточная функция одного из блоков структурной схемы (пример – рис. 1.3)

Рис 1.3 Преобразование звеньев
Рис 1.4 Преобразование разветвлений
3. Если из вершины исходит несколько дуг, то для них входная величина общая. Это устраняет в графе точки разветвления. Фрагмент подобной ситуации приведён на рис. 1.4.
4. Если в вершину входит несколько рёбер, то соответствующая этой вершине переменная равна сумме входных сигналов. Это делает ненужным использование в графе сумматоров. Пример такой особенности рассмотрен на рис 1.5.

Рис 1.
...

1.3 Определение структурных характеристик графа
Современные методы проектирования САУ базируются на использовании машинных процедур. Широко применяется для анализа и синтеза электронных схем и САУ формула Мэзона. Эта формула выражается в таких понятиях теории графов, как путь, контур и отношение касания на множествах путей и контуров. Поэтому в этом подразделе определим следующие характеристики графа прохождения сигнала:
1. Матрицу смежности графа;
2. Матрицу инциденций;
3. Бинарную матрицу путей от входной вершины до каждой из заданных выходных вершин;
4. Бинарную матрицу контуров;
5. Бинарную матрицу отношения касания контуров;
6. Бинарную матрицу отношения касания путей и контуров графа.
Граф , где и , задан.
1. Матрицей смежности графа G называется матрица размера nxn, где n – число вершин графа, в которой


2.1.1 Конечный автомат

Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n выходов и m входов (рис 2.1.1).
На каждый вход может быть подан произвольный сигнал конечного множества Х, называемого входным алфавитом. Совокупность символов, поданных на входы устройства, образует входное слово Pi в алфавите Х. На выходе устройства появляются выходные слова Qi, составленные из символов входного алфавита Y. В силу конечности алфавитов X,Y и слов Pi, Qi (длина слова Pi всегда равна m, а выходного слова - n) общее количество различных входных и выходных слов также конечно.
Элементарный такт работы устройства состоит в том, что при появлении на выходе слова Pi устройство выдает на выходах комбинацию символов yi , образующих слово Qi.
Если слово Qi определяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти или комбинационной схемой.

Рис. 2.1.
...

2.1.2 Анализ технического задания

В данном разделе курсовой работы предлагается разработать и синтезировать комбинационную схему устройства в заданном базисе логических элементов.
Схема содержит четыре входа, управляемых переменными x1, x2, x3, x4, и семь выходов y1, y2, y3, y4, y5, y6, y7. Каждому их выходных сигналов yi однозначно соответствует своя комбинация переменных xi, представленная в двоичном коде Грея. Базис, используемый при синтезе комбинационных схем: “И-ИЛИ-НЕ”.
Устройство должно осуществлять вывод каждого кодового набора непосредственно в десятичном виде. В качестве блока отображения информации будем использовать семисегментный светодиод. Его внешний вид показан на рисунке 2.1.2. Семь сегментов могут включатся каждый по отдельности или несколько в любом нужном сочетании.

Рис. 2.1.2 Семисегментный индикатор

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

2.1 Общие положения
2.1.1 Конечный автомат

Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n выходов и m входов (рис 2.1.1).
На каждый вход может быть подан произвольный сигнал конечного множества Х, называемого входным алфавитом. Совокупность символов, поданных на входы устройства, образует входное слово Pi в алфавите Х. На выходе устройства появляются выходные слова Qi, составленные из символов входного алфавита Y. В силу конечности алфавитов X,Y и слов Pi, Qi (длина слова Pi всегда равна m, а выходного слова - n) общее количество различных входных и выходных слов также конечно.
Элементарный такт работы устройства состоит в том, что при появлении на выходе слова Pi устройство выдает на выходах комбинацию символов yi , образующих слово Qi.
Если слово Qi определяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти или комбинационной схемой.
...

2.2.3 Минимизацияметодом Квайна-Мак-Класки

Воспользуемся доопределенной таблицей истинности функции y1 .
При использовании этого метода минимизируемая функция должна быть задана в ДСНФ:
Будем называть конъюнкции длины n, входящие в ДСНФ минимизируемой функции, минитермами длины n. Метод Квайна состоит из последовательного выполнения следующих этапов:
Нахождение первичных импликант. Все минитермы данной функции сравниваются между собой попарно. Если минитермы mi и mj таковы, что они имеют вид и , то выписывается конъюнкция , являющаяся минитермом длины (n – 1)
(склеивание по одному аргументу). Минитермы длины n, для которых произошло склеивание, отмечаются. После построения всех минитермов длины (n – 1) вновь сравнивают их попарно, выписывают минитермы (n – 2) и отмечают склеивающиеся минитермы (n – 1) и т.д. Этап заканчивается, когда вновь полученные минитермы длины k уже не склеиваются между собой.
...

2.2.4 Минимизацияметодом неопределённых коэффициентов

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

Здесь представлены все возможные конъюнктивные члены, которые могут входить в дизъюнктивную форму представления функции y1. Коэффициенты k с различными индексами являются неопределёнными и подбираются так, чтобы получавшаяся после этого дизъюнктивная форма была минимальной. Если теперь задавать всевозможные значения аргументов x1, x2, x3, x4 и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему из 16-ти уравнений для определения коэффициентов k.
...

3. Синтез автомата с памятью
3.1 Анализ технического задания
Предполагается синтезировать автомат с памятью на основе содержательного описания алгоритма его работы.
Автомат работает следующим образом. Автостраду пересекает второстепенная дорога. На перекрестке установлен светофор, система управления которого получает сигналы от реле времени и от параллельно соединенных датчиков давления, вмонтированных в полотно второстепенной дороги в определенных местах. Система должна функционировать следующим образом. Сигнал от реле времени отсутствует в течение 60 сек. (x1=0) и появляется на 30 сек. (x1=1). Красный сигнал светофора (z=1) на автостраде может включаться лишь на интервале, на котором x1=1. Включившись в начале этого интервала, он должен оставаться включенным на протяжении всего интервала. Срабатывание датчиков давления (x2=1) приводит к включению светофора (z=1) на автостраде на очередном интервале включения реле (x1=1).
...

2.1.2 Анализ технического задания

В данном разделе курсовой работы предлагается разработать и синтезировать комбинационную схему устройства в заданном базисе логических элементов.
Схема содержит четыре входа, управляемых переменными x1, x2, x3, x4, и семь выходов y1, y2, y3, y4, y5, y6, y7. Каждому их выходных сигналов yi однозначно соответствует своя комбинация переменных xi, представленная в двоичном коде Грея. Базис, используемый при синтезе комбинационных схем: “И-ИЛИ-НЕ”.
Устройство должно осуществлять вывод каждого кодового набора непосредственно в десятичном виде. В качестве блока отображения информации будем использовать семисегментный светодиод. Его внешний вид показан на рисунке 2.1.2. Семь сегментов могут включатся каждый по отдельности или несколько в любом нужном сочетании.

Рис. 2.1.2 Семисегментный индикатор

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

3.2 Формальное описание абстрактного автомата
Чтобы формально описать автомат, необходимо определить входной алфавит, выходной алфавит, множество состояний, функцию переходов и функцию выходов.
Из технического задания определяем входной алфавит , где x1 – сигнал от реле, а x2 – сигнал от датчиков давления.
Выходной алфавит определим как , где z – состояние красного сигнала светофора.
Зададим множество состояний как , где s0 – состояние автомата, когда сигналов от реле и от датчиков давления нет, s1 – когда сигнала от реле нет, а сигнал от датчиков давления есть и s2 – когда есть сигналы и от реле, и от датчиков давления.

Таблица 3.2.1
Таблица функций переходов и выходов
X
s0
s1
s2
X0
s0
s1
s0
X1
s1
s1
s1
X2
s0
s2
s2
X3
s2
s2
s2
Y
y0
y0
y1
Для того, чтобы хранить текущее состояние, требуется элементов памяти, где М – мощность алфавита состояний, θ – число состояний элементов памяти. Таким образом, необходимо log23 = 2 элементов памяти с входными каналами ϕ1, ϕ2.
...

3.3 Структурный синтез
Задачей структурного синтеза является построение схемы, реализующий автомат из логических элементов. Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне структурных схем.
Требуется закодировать три состояния автомата (s0, s1, s2,), для этого используем двоично-десятичный код. В схеме используется два T-триггера. Их работа описывается следующими таблицами:
Таблица 3.3.1
Функция переходов T-триггера

0
1
0
0
1
1
1
0
Таблица 3.3.2
Функция выходов T-триггера
τисх
ϕ
τпер
0
0
0
0
1
1
1
0
1
1
1
0

Теперь составим таблицу функций возбуждения элементов памяти:
Таблица 3.3.3
Функции возбуждения элементов памяти
t1t2
x1x2
00
01
11
00
00
00
11
01
01
00
10
10
00
10
00
11
11
10
00
Итак, например, чтобы перевести автомат из состояния 00 в состояние 01, возбуждается второй триггер, первый остаётся в невозбуждённом состоянии.
...

Воронин В.В. Основы синтеза и диагностирования автоматов. Хабаровск: Изд-во Хабар. гос. техн. ун-та, 2002. – 235 с.
Ангер С. Асинхронные последовательностные схемы. М.: Наука, 1977. – 400 с.