Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем (Mots)

Посмотреть архив целиком

Министерство специального и высшего образования

Хабаровский государственный технический университет


Кафедра «Автоматика и системотехника»





Курсовой проект

По предмету: Математические основы теории систем




Выполнил студент гр. УИТС-21у:

Д.И. Хоменко

Проверил:

В.В. Воронин








г. Хабаровск

2003 г.

ЗАДАНИЕ


Курсовая работа состоит из 3-х разделов, в каждом из которых рассматривается отдельный параграф дисциплины «Математические основы теории систем».

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

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

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

РЕФЕРАТ

Курсовая работа содержит пояснительную записку состоящую из трех разделов на 38 листах формата А4, включающую 6 рисунков, 2 схемы, 14 таблиц и 3 литературных источника.

Объектом исследования являются система автоматического управления и логическое устройство, в данном случае семисегментный элемент.

Цель работы состоит в том чтобы закрепить на практике теоретический материал курса лекций «Математические основы теории систем» и приобретение навыков по анализу систем и синтезу схем.

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

Содержание

ЗАДАНИЕ 2

РЕФЕРАТ 3

Содержание 4

Задание 1. Анализ сигнальных графов. 7

1.1 Выбор варианта задания 7

1.2 Преобразование структурной схемы к сигнальному графу 7

1.2 Преобразование структурной схемы к сигнальному графу 8

1.4 Матрица инцидентности 9

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

1.6 Бинарная матрица контуров. 12

1.7 Матрица касания контуров 12

1. 8 Матрица касания путей и контуров 13

1.9 Формула Мэзона для заданного сигнального графа 13

Задание 2. Синтез комбинационных схем. 16

2.1 Определение поставленной задачи 16

2.2 Составление логических функций 19

2.2.1 Дизъюнктивная совершенная нормальная форма 19

2.2.2 Конъюнктивная совершенная нормальная форма 20

2.3 Минимизация булевых функций 20

2.3.1 Пример минимизации методом неопределенных коэффициентов 21

2.3.2 Пример минимизации методом Квайна-Мак-Класки. 22

2.3.3 Пример минимизации картами Карно 25

2.4 Совместная минимизация всех функций 26

2.5 Запись МДНФ в заданном базисе 27

3. СИНТЕЗ АВТОМАТА С ПАМЯТЬЮ 29

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

3.2 Формальное описание абстрактного автомата 29

3.3 Кодирование входных и выходных символов состояний 31

3.4 Обобщенная функциональная схема структурного автомата 32

3.5 Каноническая система логических уравнений 33

3.6 Минимизация логических функций 35

3.7 Построение комбинационной схемы автомата с памятью 35

ЗАКЛЮЧЕНИЕ 36

Приложение 1. 37

Приложение 2 38



Задание 1. Анализ сигнальных графов.

    1. Выбор варианта задания

Из букв, образующих фамилию, имя и отчество получим три множества А, В и С символов русского алфавита.

Хоменко А={Х, О, М, Е, Н, К}

Дмитрий B={Д, М, И, Т, Р, Й}

C={И, Г, О, Р, Е, В, Ч}

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

AB={ Х, О, М, Е, Н, К , Д, И, Т, Р, Й }=11

( AB)С={Е, И, О, Р}=4

C\A={И, Г, Р, В, Ч}=5

AB=U\ AB=33-11=22

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

Рисунок 1.1.1



1.2 Преобразование структурной схемы к сигнальному графу

Граф прохождения сигнала G=<x, >, где Х – множество вершин, - множество дуг, имеет следующие особенности.

  1. Каждой вершине графа xiX ставится в соответствие одна переменная структурной схемы (обозначение переменных сигналов приведено на рисунке 1.1).

  2. Каждой дуге (xi, xj)X поставлена в соответствие передаточная функция одного из блоков структурной схемы.

  3. Если из вершины исходит несколько дуг, то для них входная величина общая. Это устраняет в графе точки разветвления.

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

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

В

Рисунок 1.2.1

ершины отмеченные серым цветом – это заданные контрольные точки.

1.3 Матрица смежности

Матицей смежности графа G называется матрица R=[rij] размером nxn, где n – число вершин графа, в которой


x

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

y

x

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

x1

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

x2

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

x3

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

x4

0

0

0

0

0

1

0

0

1

1

0

0

0

0

0

x5

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

x6

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

x7

0

0

0

0

0

1

0

0

0

0

0

0

0

0

1

x8

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

x9

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

x10

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

x11

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

x12

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

x13

1

0

0

0

0

0

0

0

0

0

0

1

0

0

0

y

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0


1.4 Матрица инцидентности

Матрицей инцидентности графа G называется матрица S=[sij] размера nxm, где n – число вершин графа, а m – число дуг графа, в которой:

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



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

x

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

-1

x1

1

1

0

0

0

0

0

0

-1

0

0

0

0

0

0

0

0

0

0

0

x2

-1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

x3

0

-1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

x4

0

0

0

0

0

0

1

1

0

-1

-1

1

0

0

0

0

0

0

0

0

x5

0

0

0

0

1

0

0

0

0

0

0

-1

-1

0

0

0

0

0

0

0

x6

0

0

0

0

-1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

x7

0

0

0

0

0

-1

0

0

0

0

0

0

1

1

0

0

0

0

0

0

x8

0

0

0

0

0

0

-1

0

0

0

0

0

0

0

1

0

0

0

0

0

x9

0

0

0

0

0

0

0

-1

0

0

0

0

0

0

0

1

0

0

0

0

x10

0

0

0

0

0

0

0

0

0

0

0

0

0

0

-1

-1

1

0

0

0

x11

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

-1

-1

0

x12

0

0

-1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

x13

0

0

0

-1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

y

0

0

0

0

0

0

0

0

0

0

0

0

0

-1

0

0

-1

1

0

0


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

Согласно заданию на курсовую работу выделено множество К контрольных точек (выходов). Оно имеет вид:

К={x1, x4, y, x13}

Построим матрицы путей для каждого из этих выходов.

Бинарная матрица P=pij путей размера lxm, где l – число путей, строится по следующему правилу:

Матрица путей выхода для x1


w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0


Матрица путей выхода для x4


w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

2

0

1

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0


Матрица путей выхода для y


w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1

0

0

0

0

0

0

0

1

1

0

1

0

1

1

0

0

0

0

0

2

1

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

1

0

0

0

3

1

0

0

0

0

0

0

1

1

1

0

0

0

0

0

1

1

0

0

0

4

0

1

0

0

1

1

0

0

1

0

1

1

0

1

0

0

0

0

0

0

5

0

1

0

0

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

6

0

1

0

0

0

0

0

1

1

0

1

0

0

0

0

1

1

0

0

0


Матрица путей выхода для x13


w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

x

1

0

1

1

1

1

0

0

1

1

0

1

0

1

0

1

0

0

0

0

x1

1

0

1

1

0

0

1

0

1

1

0

0

0

0

1

0

1

1

0

0

x2

1

0

1

1

0

0

0

1

1

1

0

0

0

0

0

1

1

1

0

0

x3

0

1

1

1

1

1

0

0

1

0

1

1

0

1

0

0

0

0

0

0

x4

0

1

1

1

0

0

1

0

1

0

1

0

0

0

1

0

1

1

0

0

x5

0

1

1

1

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

0


1.6 Бинарная матрица контуров.

Бинарная матрица контуров C=cij размера hxm, где h - число контуров, строится по следующему правилу:

Предварительно пронумеруем все контуры в произвольном порядке.


w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1

0

1

1

1

1

0

0

1

1

0

1

0

1

0

0

0

1

0

1

2

1

0

1

1

0

0

1

0

1

1

0

0

0

0

1

0

1

1

0

1

3

1

0

1

1

0

0

0

1

1

1

0

0

0

0

0

1

1

1

0

1

4

0

1

1

1

1

1

0

0

1

0

1

0

0

1

0

0

0

1

0

1

5

0

1

1

1

0

0

1

0

1

0

1

0

0

0

1

0

1

1

0

1

6

0

1

1

1

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

1

7

0

0

0

0

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

8

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0


1.7 Матрица касания контуров

Бинарная матрица контуров Ck=cij размера hxk, где k - число контуров, строится по следующему правилу:



1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

1

2

1

1

1

1

1

1

1

1

3

1

1

1

1

1

1

1

1

4

1

1

1

1

1

1

1

1

5

1

1

1

1

1

1

1

1

6

1

1

1

1

1

1

1

1

7

1

1

1

1

1

1

1

0

8

1

1

1

1

1

1

0

1


1. 8 Матрица касания путей и контуров

Бинарная матрица контуров Cl=cij размера lxk, где l - число путей для заданного выхода, строится по следующему правилу:


Для x1


1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

0

0


Для x4


1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

0

0

2

1

1

1

1

1

1

0

0


Для y


1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

0

2

1

1

1

1

1

1

0

0

3

1

1

1

1

1

1

0

0

4

1

1

1

1

1

1

1

0

5

1

1

1

1

1

1

0

0

6

1

1

1

1

1

1

0

0


Для x13


1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

1

2

1

1

1

1

1

1

0

1

3

1

1

1

1

1

1

0

1

4

1

1

1

1

1

1

1

1

5

1

1

1

1

1

1

0

1

6

1

1

1

1

1

1

0

1


1.9 Формула Мэзона для заданного сигнального графа

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


где - передача k-го пути между вершинами j и r; - определитель графа. Он характеризует контурную часть графа и имеет следующий вид:

где, L – множество индексов контуров, L2 - множество пар индексов не касающихся контуров, L3 - множество троек индексов не касающихся контуров, Ki – передача i-го контура, - минор пути, это определитель подграфа, полученного удалением из полного графа вершин и дуг, образующих путь .

=1-К1-К2-К3-К4-К5-К6-К7-К8+К7К2+К7К3+К7К5+К7К6+К7К8=1- К1-К2-К3-К4-К5-К6-К7-К8+К7(К2+К3+К5+К6+К8)

К1=W1W3W4W5W6

K2=W3W4W7

K3=W1W3W4W8

K4=W2W3W4W6 W7

K5=W2W3W4W7

K6=W2W3W4W8

K7=W5W6

K8=W3W4

=1- W3W4(W1W5W6+ W7+ W1W8+ W2W6 W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1)


Для x1

Для x4

Для y