Ирина Эланс

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

Анализ сигнальных графов

ЗАДАНИЕ

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

Для выполнения первого раздела необходимо:

1. Из букв, образующих фамилию, имя и отчество

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

2. По исходной блок-схеме получить схему САУ и

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

3. Определить структурные характеристики графа, а

именно:

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

4. По формуле Мезона рассчитать передачи для заданных

контрольных точек.

Во втором разделе необходимо разработать схему устройства в базисе {И, НЕ}. Устройство содержит четыре входа, управляемые переменными х₁, х₂, х₃, х₄, и семь выходов y₁, y₂, y₃, y₄, y₅, y₆, y₇. Закон кодообразования: код с весами.

Для выполнения данного раздела следует:

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

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

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

Параметр алгоритма – слова типа un…d, тип триггера-RS.

Для выполнения данного раздела требуется:

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

РЕФЕРАТ

Курсовая работа выполнена в объеме 28 страниц, содержит 11 таблиц и 10 рисунков.

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

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

СОДЕРЖАНИЕ

Введение 4

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

1.1 Получение структурной схемы 5

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

1.3 Определение структурных характеристик графа 8

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

1.3.2 Матрица инцидентности 8

1.3.3 Бинарная матрица путей 9

1.3.4 Бинарная матрица контуров 10

1.3.5 Бинарная матрица касания контуров 10

1.3.6 Бинарная матрица касания путей и контуров 11

1.4 Передаточные функции 12

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

2.1 Задание 13

2.2 Таблица истинности 13

2.3 Переход от таблицы истинности к логической функции 14 2.3.1 ДСНФ 15

2.3.2 КСНФ 15

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

2.4.1 Метод Квайна-Мак-Класки 15

2.4.2 Метод неопределенных коэффициентов 17

2.4.3 Карты Карно 18

2.5 Совместная минимизация 19

2.6 Построение логической схемы 20

3 Синтез автоматов с памятью 22

3.1 Исходные данные 22

3.2 Обобщенная структурная схема автомата 24

3.3 Каноническая система логических функций. ДСНФ. 24

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

3.5 Структурная схема автомата 26

Заключение 27

Список использованных источников 28

ВВЕДЕНИЕ

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

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

Курсовая работа состоит из трёх разделов:

1 Анализ сигнальных графов;

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

3 Синтез автомата с памятью.

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

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

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

1 АНАЛИЗ СИГНАЛЬНЫХ ГРАФОВ

Получение структурной схемы

Согласно заданию получим три множества:

Арнаут А = {а,р,н,у,т} |А|=5,

Дмитрий В = {д,м,и,т,р,й} |В|=6,

Иванович С = {и,в,а,н,о,ч} |С|=6.

Над этими множествами выполним следующие операции:

||=|{а,р,н,у,т,д,м,и,й}| = 9

|()|=|{а,н,и}|= 3

=|{и,в,о,ч}|= 4

==33-9= 24

В последнем соотношении U - универсальное множество, которое в данном случае представляет собой множество всех букв русского алфавита.

Таблица 1.1 – Таблица блоков САР

Тип соединения элементов блока

Мощность множества

Номер блока в общей блок-схеме

Согласно таблице 1.1, и полученных мощностей множеств, определим четыре типа соединений элементов блок-схемы.

Рисунок 1.1 – Исходная блок-схема САР

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

Рисунок 1.2 – Схема САР

На рисунке 1.2 изображена окончательная схема для рассматриваемого варианта. На ней определены направления потоков информации x_i, и обозначены модели _i. Полученная схема называется структурной схемой САУ. От данной схемы следует перейти к сигнальному графу.

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

Сигнальный граф , где - множество вершин, - множество дуг, строится по следующему принципу:

каждой вершине графа ставится в соответствие

сигнал на структурной схеме;

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

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

Рисунок 1.3 – Результирующий сигнальный граф

Данный граф имеет тринадцать вершин, шестнадцать дуг и шесть контуров. Затемненные вершины – контрольные точки.

1.3 Определение структурных характеристик графа

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

Матрицей смежности графа называется матрица размера , где - число вершин графа, в которой

Для сигнального графа, приведенного на рисунке 1.3, имеем:

Матрица смежности определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма.

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

Матрицей инцидентности графа называется матрица размера , где - число вершин графа, - число дуг, определяется по следующему правилу:

Исходя из данного правила, матрица будет иметь вид:

Матрица инцидентности определяет граф с точностью до изоморфизма.

1.3.3 Бинарная матрица путей

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

Бинарная матрица путей размера , где - число путей, строится по следующему правилу:

Матрица путей для входной вершины 12 и выходной 1:

Матрица путей для входной вершины 12 и выходной 3:

Матрица путей для входной вершины 12 и выходной 11:

Матрица путей для входной вершины 12 и выходной 13:

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

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

Таким образом, данная матрица будет иметь вид:

Строки контурной матрицы соответствуют контурам, а столбцы – ветвям схемы.

1.3.5 Бинарная матрица касания контуров

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

Матрица является квадратной и симметричной относительно главной диагонали.

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

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

Матрица касания путей и контуров для выходной вершины 12 и выходной 1:

Матрица касания путей и контуров для выходной вершины 12 и выходной 3:

Матрица касания путей и контуров для выходной вершины 12 и выходной 11:

Матрица касания путей и контуров для выходной вершины 12 и выходной 13:

1.4 Передаточные функции

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

(1.1)

где - передача между фиксированными сигналами;

- передача k-го пути между x_i и x_j;

- минор k-го пути между входной вершиной x_i и выходной x_j;

- определитель графа, который характеризует

контурную часть.

(1.2)

где - передача i-го контура;

- множество индексов контуров;

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

контуров;

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

контуров.

Контуры имеют следующие передачи:

k₁=W₁*W₂*W₄*W₁₅

k₂=W₁*W₂*W₄*W₁₆

k₃=W₁*W₂*W₃*W₁₅

k₄=W₁*W₂*W₃*W₁₆

k₅=W₁*W₂*W₅*W₉*W₁₅

k₆=W₁*W₂*W₅*W₉*W₁₆

Определитель графа:

= 1- (k₁+k₂+k₃+k₄+k₅+k₆)

Для точки x₁: , где P_12,1=1, _12,1 = 1

Для точки x₃: , где P_12,3=W₁, _12,3=1

Для точки x_13: , где P_12,13=W₁*W₂*W₄+ W₁*W₂*W₃+ W₁*W₂*W₅*W₉,

_12,13=1

Для точки x₁₁: , _12,11=1

где P_12,11= W₁*W₂*W₄*W₁₅+ W₁*W₂*W₄*W₁₆+W₁*W₂*W₃*W₁₅+ W₁*W₂*W₃*W₁₆+ W₁*W₂*W₅*W₉*W₁₅+ W₁*W₂*W₅*W₉*W₁₆

2 СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ

2.1 Задание

Разработать схему управления семисегментного светодиодного индикатора (рис. 2.1) в базисе {И-НЕ}. Схема должна иметь четыре входа, управляемые переменными х₁, х₂, х₃, х₄, и семь выходов у₁, у₂, у₃, у₄, у₅, у₆, у₇. Каждому из выходных сигналов у_i однозначно соответствует своя комбинация переменных х_i, образуемая по закону кодообразования Грея. Устройство осуществляет ввод каждого кодового набора переменных х_i, в двоично-десятичном виде. В качестве блока отображения информации используется семисегментный светодиод.

2.2 Таблица истинности

Составим таблицу истинности для семисегментного индикатора, изображенного на рисунке 2.1.

Рисунок 2.1 – Семисегментный индикатор

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

Таблица 2.1 – Таблица истинности

Десятичные цифры	Код c весами 3321							Y₁		Y₂		Y₃	Y₄	Y₅	Y₆	Y₇
	Х₄	Х₃		Х₂		Х₁
0	0	0		0		0		1		1		1	1	1	1	0
1	0	0		0		1		0		1		1	0	0	0	0
2	0	0		1		0		1		1		0	1	1	0	1
3	0	0		1		1		1		1		1	1	0	0	1
4	1	0		0		1		0		1		1	0	0	1	1
5	0	1	1		0		1		0		1		1	0	1	1
6	1	1	0		0		1		0		1		1	1	1	1
7	1	1	0		1		1		1		1		0	0	0	0
8	1	1	1		0		1		1		1		1	1	1	1
9	1	1	1		1		1		1		1		1	0	1	1
Запрещенные наборы	0	1	0		0		Х		Х		Х		Х	Х	Х	Х
	0	1	0		1		Х		Х		Х		Х	Х	Х	Х
	0	1	1		1		Х		Х		Х		Х	Х	Х	Х
	1	0	0		0		Х		Х		Х		Х	Х	Х	Х
	1	0	1		0		Х		Х		Х		Х	Х	Х	Х
	1	0	1		1		Х		Х		Х		Х	Х	Х	Х

2.3 Переход от таблицы истинности к логической функции

Существует два способа записи логической функции по таблице истинности – дизъюнктивно совершенная нормальная форма (ДСНФ) и конъюнктивно совершенная нормальная форма (КСНФ), которые рассмотрим на примере функции y_1. Так как функция не полностью определена, доопределим ее на недостающих наборах нулями. Согласно этому таблица истинности для y₁будет иметь вид:

Таблица 2.2 –Таблица истинности функции y₁

Х₄	Х₃	Х₂	Х₁	Y₁
0	0	0	0	1
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
1	0	0	1	0
0	1	1	0	1
1	1	0	0	1
1	1	0	1	1

Продолжение таблицы 2.2

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

Таблица истинности связывает значение входных и выходных переменных.

2.3.1 ДСНФ

Входные наборы, на которых функция принимает значение единицы: 0000, 0010, 0011, 0110, 1100, 1101, 1110, 1111, 0111, 1010. Тогда ДСНФ будет иметь следующий вид:

(2.1)

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

2.3.2 КСНФ

Входные наборы, на которых функция принимает значение нуль: 0001, 1001, 0100, 0101, 1000, 1011. Тогда КСНФ будет выглядеть следующим образом:

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

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

2.4.1 Метод Квайна-Мак-Класки

При использовании данного метода минимизируемая функция должна быть заданна в ДСНФ (2.1):

Запишем минитермы и произведем операцию склеивания. Знак * означает, что для данной минитермы произошло склеивание:

Исходные минитермы (ДСНФ)

0-ая группа: 0000*

1-ая группа: 0100*

2-ая группа: 0011*,0101*, 1100*

3-ья группа: 0111*, 1011*, 1110*

4-ая группа: 1111*

Минитермы 1-го ранга:

0-ая группа: 0-00

1-ая группа: 010-*,01-0*,-100*

2-ая группа: 0-11*,-011*,01-1*,011-*,-110*,11-0*

3-ья группа: -111*,1-11*,111-*

Минитермы 2-го ранга:

0-ая группа: отсутствует

1-ая группа: 01--,-1-0

2-ая группа: --11,-11-

Минитермы 3-го ранга:

0-ая группа: отсутствует

1-ая группа: отсутствует

Первичные импликанты

0-00,--11,01--,-1-0,-11-

Составим таблицу меток:

Таблица 2.3 – Таблица меток

	0000	0011	0100	0101	0110	0111	1011	1100	1110	1111
0-00	*		*
--11		*				*	*
01--			*	*	*	*
-1-0			*		*			*	*
-11-					*	*			*	*

Выпишем 0-00, --11, 01--, -1-0.

Таким образом, выпишем МДНФ:

Мы получили МДНФ под которым понимается такое выражение, которое содержит минимальное число символов вида по сравнению с другим ДНФ данной функции.

2.4.2 Метод неопределенных коэффициентов

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

Так как в ряде случаев функция принимает значение «0», следовательно, коэффициенты для данных наборов также должны равняться нулю. Рассмотрев все наборы, на которых функция обращается в нуль, получим нулевые коэффициенты. В оставшихся уравнениях, в которых функция принимает значение «1», также вычеркнем все нулевые коэффициенты, определенные ранее. Таким образом, таблица коэффициентов на рисунке 2.4 будет иметь вид:

Рисунок 2.4 – Таблица коэффициентов

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

(2.3)

На основании (2.3) запишем МДНФ:

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

2.4.3 Карты Карно

На рисунке 2.2 изображена карта Карно для функции y₁:

X₃x₄

	00	01	11	10
00	1	0	1	0
01	1	1	1	1
11	1	0	1	1
10	0	0	1	0

X₁X₂
Рисунок 2.2 – Карта Карно

Анализ сигнальных графов 📙 Курсовая → 🆔 18886