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

ЗАДАНИЕ

 

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

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

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

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

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

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

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

   именно:         

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

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

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

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

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

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

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

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

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

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

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

 

РЕФЕРАТ

 

Курсовая  работа выполнена в объеме 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 АНАЛИЗ СИГНАЛЬНЫХ ГРАФОВ

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

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

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

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

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

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

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

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

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

= =33-9= 24

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

 

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

Тип соединения элементов блока	Мощность множества	Номер блока в общей блок-схеме
1	12
2	1
3	6
4	21

 

 

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

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

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

           

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

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

 

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

 

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

 

 

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

 

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

 

 

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

 

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

 

 

 

 

 

 

 

 

 

 

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

 

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

 

 

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

 

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

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