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

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

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

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

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

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

|Выполнил студент гр. УИТС-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={И, Г, О, Р, Е, В, Ч}

Произведя соответствующие операции над множествами получим их мощности.

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

соответствующих полученным результатам типы соединений элементов в системе

автоматического управления.

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

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

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

(A(B(=(U\ A(B(=33-11=22

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

системой.

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

Граф прохождения сигнала G=, где Х – множество вершин, ( -

множество дуг, имеет следующие особенности.

1. Каждой вершине графа xi(X ставится в соответствие одна переменная

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

рисунке 1.1).

2. Каждой дуге (xi, xj)(X поставлена в соответствие передаточная

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

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

общая. Это устраняет в графе точки разветвления.

4. Если в вершину входит несколько ребер, то соответствующая этой

вершине переменная равна сумме входных сигналов. Это делает не

нужным использование в графе сумматоров.

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

сигнальному графу, перейдем от схемы рис. 1.1 к соответствующему

сигнальному графу (см. рис. 1.2).

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

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

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

n – число вершин графа, в которой

[pic]

|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 - число путей

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

[pic]

Для 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 Формула Мэзона для заданного сигнального графа

Используя универсальную топологическую формулу, носящую имя Мэзона,

можно получить передачу между любыми двумя вершинами. Формула имеет

следующий вид:

[pic]

где [pic]- передача k-го пути между вершинами j и r; [pic]( -

определитель графа. Он характеризует контурную часть графа и имеет

следующий вид:

[pic]

где, L – множество индексов контуров, L2 - множество пар индексов не

касающихся контуров, L3 - множество троек индексов не касающихся контуров,

Ki – передача i-го контура, [pic] - минор пути, это определитель подграфа,

полученного удалением из полного графа вершин и дуг, образующих путь [pic].

(=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

[pic]

[pic]

[pic]

Для x4

[pic] [pic]

[pic] [pic]

[pic]

Для y

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Для х13

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

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

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

Устройство, работа которого может быть представлена на языке алгебры

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

выходов и m входов. На каждый вход может быть подан произвольный символ

конечного множества Х, называемого входным алфавитом. Совокупность входных

символов, поданных на входы устройства, образует входное слово Рi в

алфавите Х. На выходе устройства появляются выходные слова Qj, составленные

из символов выходного алфавита Y. В силу конечности алфавитов X, Y и слов

Pi, Qj (длина слова всегда равна m, а выходного слова - h) общее количество

различных входных и выходных слов также конечно.

Элементарный такт работы устройства состоит в том, что при появлении на

входе слова Рi устройство выдает на выходах комбинацию символов yi,

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

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

комбинационной схемой.

Алгоритм функционирования комбинационного устройства будет определен,

если задать таблицу соответствия {Pi}->{Qj} для всех слов Pi. Если входной

алфавит X состоит из K различных символов, в таблице соответствия будет Km

строк. Так как символы входного и выходного алфавитов принимают только два

значения (в данном случае «1» или «0»), то при синтезе и анализе

логического устройства применяется булева алгебра.

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

автомату с двойным входом и выходом путем соответствующего кодирования.

Однако этот автомат должен оперировать со словами входного и выходного

алфавитов, длина которых больше длин соответствующих слов исходного

алфавита.

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

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

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

устройства.

Согласно заданию на курсовое проектирование было предложено

закодировать исходный алфавит кодом Грея и использовать для синтеза

конечного автомата базис {и, не}.

Код Грея является циклическим кодом, получается из двоично-десятичного

кода по следующим правилам:

1. пусть gn…..g1g0 – кодовый набор в коде Грея с (n+1) разрядами.

2. bn…b1b0 – соответствующее двоичное число.

3. тогда разряд g0 получается из следующего выражения:

gi=bi(bi+1; 0(i(n-1; gn=bn; где ( - символ операции сложения по модулю

2 (0+0=0, 0+1=1, 1+0=1, 1+1=0).

Закодируем входной алфавит в соответствии с этими правилами и с учетом

значений yi составим таблицу истинности (см. таблицу 2.1.1).

Таблица 2.1.1

|Нулевая группа |0000+ |Нулевая группа |0-00 |

|Первая группа |0100+ |Первая группа |-100, -011 |

|Вторая группа |1100, 1010, 0011 |Вторая группа |11-0, 1-10, 101- |

|Третья группа |1110, 1011 | | |

Расстановка меток. Остальные этапы нужны, чтобы отбросить некоторые

первичные импликанты. На данном этапе составляется таблица, число строк

которой равно числу полученных первичных импликант, число столбцов

совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит

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

столбца и строки ставится метка. В таблице 2.2.2 приведем результат

расстановки меток:

Таблица 2.2.2

|-100 |У | | |

|11-0 |У | |У |

|1-10 | |У |У |

|101- | |У | |

Выбор минимального покрытия. Исследуется результирующая таблица.

Выбирается такая совокупность первичных импликант, которая иссключает метки

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

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

покрытия с минимальным суммарным числом букв в простых импликантах,

образующих покрытие.

С учетом существенных импликант получим две МДНФ для этой функции

имеет вид:

1.[pic]

2. [pic]

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

Во втором варианте на одно отрицание меньше, поэтому берем его за искомое:

[pic]

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

Данный метод для минимизации функции в коде Грея. В каждую ячейку

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

ячеек размером 2a*2b , где a, b?[0,1,2…], в которых функция принимает

значение «1». В каждую группу должно входить максимальное число ячеек.

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

соответствовать конъюнктивный член размером n-a-b. Для получения МДНФ

каждую группу надо просматривать в горизонтальном и вертикальном

измерениях, с нахождения таких переменных, которые не меняют своего

значения в пределах группы. Если переменная не меняет своего нулевого

значения, то она вписывается в конъюнкцию с отрицанием, если не меняет

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

разорванные группы, то карту Карно надо свернуть в цилиндр. На

неопределенных наборах следует доопределить нулем или единицей, в

соответствии с выбираемой группой ячеек. Каждая единичная ячейка должна

быть включена хотя бы в одну группу.

Составим карту Карно для функции У3 (рисунок 2.3.1).

| |x3x4 |

|x1x2| |00 |01 |11 |10 |

| |00|1 | |1 | |

| |01|1 | | | |

| |11|1 | | |1 |

| |10| | |1 |1 |

Рис. 2.3.1 Карта Карно для функции У3

Таким образом, для функции У3 в МДНФ будет иметь следующий вид:

[pic]

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

Синтез схем на основе отдельно минимизированных функций является

неоптимальным, с точки зрения количества используемых элементов. Так как

вероятнее всего, имеются такие конъюнкции, которые дублируют друг друга.

Целью данного пункта является нахождение этих конъюнкций.

Для этого составим карты Карно для каждой функции из таблицы истинности

(таблица 2.1.1). Доопределим ее запрещенные наборы (таблица 2.1.1), а затем

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

количество на данной карте и максимальное совпадение таких групп между

картами для остальных функций.

Составим карты Карно для всех функций таблицы истинности (таблица

2.1.1)

|х1 х2 х3 | | | |

|0 0 0 |s1 |s1 |s1 |

|0 0 1 |s2 |s2 |s2 |

|0 1 0 |s1 |s1 |s1 |

|0 1 1 |s3 |s3 |s3 |

|1 0 0 |s1 |s1 |s1 |

|1 0 1 |s3 |s3 |s3 |

|1 1 0 |s2 |s2 |s2 |

|1 1 1 |s1 |s1 |s1 |

Таблица переходов – выходов представлена в таблице 3.2.2 .

Таблица 3.2.2

|S |s1 |s2 |s3 |

|х1 х2 х3 | | | |

|0 0 0 |у0 |у0 |у0 |

|0 0 1 |у0 |у2 |у4 |

|0 1 0 |у1 |у0 |у2 |

|0 1 1 |у0 |у2 |у4 |

|1 0 0 |у3 |у1 |у0 |

|1 0 1 |у0 |у2 |у4 |

|1 1 0 |у1 |у0 |у2 |

|1 1 1 |у0 |у2 |у4 |

Для того, чтобы хранить текущее состояние требуется n=[log?M]

элементов памяти, где М – мощность алфавита состояний, ? – число состояний

элементов памяти. Таким образом, необходимо log23=2 элементов памяти.

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

Кодирование входных символов представлено в таблице 3.3.1 .

Таблица 3.3.1

|Х |х3[p|х2 |х1 |

| |ic] | | |

|х1 |0 |0 |0 |

|х2 |0 |0 |1 |

|х3 |0 |1 |0 |

|х4 |0 |1 |1 |

|х5 |1 |0 |0 |

|х6 |1 |0 |1 |

|х7 |1 |1 |0 |

|х8 |1 |1 |1 |

Кодирование выходных символов представлено в таблице 3.3.2 .

Таблица 3. 3.2

| |у1 |у2 |у3 |

|у0 |1 |0 |1 |

|у1 |0 |0 |0 |

|у2 |1 |0 |0 |

|у3 |1 |1 |1 |

|у4 |1 |1 |0 |

Кодирование состояний автомата представлено в таблиц 3.3.3.

Таблица 3.3.3

|S |t1 |t2 |

|s1 |0 |0 |

|s2 |0 |1 |

|s3 |1 |1 |

В соответствии с таблицами 3.3.1 – 3.3.3 составляем таблицу переходов –

входов в кодированном виде.

Таблица 3.3.4

|х3х2х1\s1s2s3|00 |01 |11 |

|000 |00 |01 |11 |

|001 |00 |00 |00 |

|010 |01 |01 |01 |

|011 |00 |00 |00 |

|100 |11 |11 |11 |

|101 |00 |00 |00 |

|110 |01 |01 |01 |

|111 |00 |00 |00 |

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

Таблица 3.4.5

|х3х2х1\s1s2s|00 |01 |11 |

|3 | | | |

|000 |101 |101 |101 |

|001 |101 |100 |110 |

|010 |000 |101 |100 |

|011 |101 |100 |110 |

|100 |111 |000 |101 |

|101 |101 |100 |110 |

|110 |000 |101 |100 |

|111 |101 |100 |110 |

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

Построим обобщенную функциональную схему структурного автомата с

учетом заданного типа автомата и триггера (см. рис.3.4.1) .

Рис.3.4.1

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

блок - блок памяти, который состоит из двух элементов памяти (D – триггер,

П1, П2). Второй блок – комбинационная схема (КС1).

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

Из таблицы переходов выходов (табл. 3.4.5) можно получить СДНФ для у (

выходов нашего автомата).

[pic]

[pic][pic]

[pic]

Нахождение функций возбуждения памяти ( Ф1, Ф2) производится в

соответствии с типом триггера. D – триггер имеет один вход и один выход,

его изображение приведено на рис. 3.5.1 .

Рис.3.2 D – триггер

Функция переходов данного автомата памяти приведен в таблице 3.8 . Если

закодировать входные и выходные символы D – триггера (табл. 3.9.,3.10), то

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

Таблица 3.5.1

|(\( |0 |1 |

|0 |0 |0 |

|1 |1 |1 |

При построении функций возбуждения памяти автомата строят функцию

входов элемента памяти. Эту функцию задают в виде таблице. Функция входов

структурного автомата памяти П приведена в таблице 3.5.2 .

Таблица 3.5.2

|tисх |Ф |tнов |

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |0 |

|1 |1 |1 |

Функция возбуждения автомата памяти, построенная в соответствии с

таблицами 3.12 и 3.7 представлена в таблице 3.13 .

Таблица 3.5.3

|х3х2х1\t1t2 |00 |01 |11 |

|000 |00 |01 |11 |

|001 |00 |00 |00 |

|010 |01 |01 |01 |

|011 |00 |00 |00 |

|100 |11 |11 |11 |

|101 |00 |00 |10 |

|110 |01 |01 |01 |

|111 |00 |00 |10 |

Из этой таблицы для единичных значений функции Ф1 и Ф2 имеем:

[pic]

[pic]

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

С помощью программы Logic можно минимизировать, полученные в прошлом

разделе логические функции. В итоге они примут вид:

[pic]

[pic]

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

Схема автомата с памятью основанной на D-триггере представлена в

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

ЗАКЛЮЧЕНИЕ

В курсовой работе по дисциплине « Математические основы теории систем»

были выполнены два раздела, в которых были закреплены теоретические знания

по темам: анализ сигнального графа и синтез комбинационных схем.

В первом разделе исследуется сигнальный граф: преобразование

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

графа, использовались его структурные характеристики: матрица смежности,

матрица касания путей и контуров, матрица инциденций, матрица путей,

матрица контуров, матрица касания контуров.

Во втором разделе были получены некоторые навыки в области синтеза

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

схема управления светодиодами семисегментного индикатора.

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

содержательного описания алгоритма его работы.

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

Приложение 2

-----------------------

W1

W2

W4

W3

W5

W6

W7

W8

x

x1

x2

x3

x4

x5

x6

x8

x9

x

x10

y

x11

x12

x13

x7

Рисунок 1.1.1

X

x1

x2

x3

x4

x5

x6

x7

Y

x8

x9

x10

x11

x12

x13

КС1

П2

П1

y7

y6

y5

y4

y3

y2

y1

[pic]

х

&

[pic]

х2

х1

&

[pic]

х2

х1

1

[pic]

х

1

х3 х2 х1

у1 у2 у3

Ф1

Ф2

t1

t2

(

(

D

w1

w5

w6

w2

w7

w8

w4

w3

u9

u10

u11

u12

u15

u16

u13

u17

u18

u19

u20

u14

Рисунок 1.2.1