/>Министерство специального ивысшего образования/>Хабаровский государственныйтехнический университет/>Кафедра «Автоматика и системотехника»/>Курсовой проект/>По предмету: Математические основы теории систем />Выполнил студент гр. УИТС-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.1 Выбор варианта задания
Из букв, образующих фамилию, имя и отчество получимтри множества А, В и С символов русского алфавита.
Хоменко А={Х, О, М, Е, Н, К}
Дмитрий B={Д, М, И, Т, Р, Й}
C={И, Г, О, Р, Е, В, Ч}
Произведя соответствующие операции над множествамиполучим их мощности. Из таблицы возможных мощностей методического указаниявыбираются типы соответствующих полученным результатам типы соединенийэлементов в системе автоматического управления.
½AÈB½=½{ Х, О, М, Е, Н, К, Д, И, Т, Р, Й }½=11
½( AÈB)ÇС½=½{Е, И, О, Р}½=4
½C\A½=½{И, Г, Р, В, Ч}½=5
½AÈB½=½U\ AÈB½=33-11=22
По полученным результатампостроим схему автоматического управления системой./> /> /> /> /> /> /> />
Рисунок 1.1.1
1.2 Преобразованиеструктурной схемы к сигнальному графу
Граф прохождения сигналаG=x, q>, где Х – множество вершин, q — множество дуг, имеет следующиеособенности.
1. Каждой вершине графа xiÎX ставится в соответствие однапеременная структурной схемы (обозначение переменных сигналов приведено нарисунке 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 1
x1 1 1
x2 1
x3 1
x4 1 1 1
x5 1
x6 1
x7 1 1
x8 1
x9 1
x10 1
x11 1
x12 1
x13 1 1 y 1 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 1 -1
x1 1 1 -1
x2 -1 1
x3 -1 1
x4 1 1 -1 -1 1
x5 1 -1 -1
x6 -1 1
x7 -1 1 1 x8 -1 1 x9 -1 1
x10 -1 -1 1
x11 1 -1 -1
x12 -1 1
x13 -1 1 1 y -1 -1 1 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 1
Матрица путей выхода для x4 w1 w2 w3 w4 w5 w6 w7 w8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 u20 1 1 1 1 2 1 1 1
Матрицапутей выхода для y w1 w2 w3 w4 w5 w6 w7 w8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 u20 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 1 4 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 6 1 1 1 1 1 1
Матрицапутей выхода для x13 w1 w2 w3 w4 w5 w6 w7 w8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18 u19 u20 x 1 1 1 1 1 1 1 1 1 1 x1 1 1 1 1 1 1 1 1 1 x2 1 1 1 1 1 1 1 1 1 x3 1 1 1 1 1 1 1 1 1 x4 1 1 1 1 1 1 1 1 1 x5 1 1 1 1 1 1 1 1 1
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 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 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 8 1 1 1 1 1 1 1
1. 8 Матрицакасания путей и контуров
Бинарная матрица контуров Cl=||cij||размера lxk, где l — число путей для заданного выхода,строится по следующему правилу:
/>
Дляx1 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1
Дляx4 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 2 1 1 1 1 1 1
Дляy 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 4 1 1 1 1 1 1 1 5 1 1 1 1 1 1 6 1 1 1 1 1 1
Для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 1 3 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1.9 Формула Мэзонадля заданного сигнального графа
Используя универсальнуютопологическую формулу, носящую имя Мэзона, можно получить передачу междулюбыми двумя вершинами. Формула имеет следующий вид:
/>
где /> — передача k-го пути между вершинами j и r; />D— определительграфа. Он характеризует контурную часть графа и имеет следующий вид:
/>
где, L – множество индексов контуров, L2- множество пар индексовне касающихся контуров, L3- множество троек индексовне касающихся контуров, Ki – передача i-го контура, /> - минор пути, этоопределитель подграфа, полученного удалением из полного графа вершин и дуг,образующих путь />.
D=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=W2W3W4W6W7
K5=W2W3W4W7
K6=W2W3W4W8
K7=W5W6
K8=W3W4
D=1-W3W4(W1W5W6+ W7+ W1W8+ W2W6W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1)
Для x1
/>
/>
/>
Для x4
/> />
/> />
/>
Для y
/>
/>
/>
/>
/>
/>
/>
/>/>/>
/>/>/>/>/>/>/>/>Длях13
/>
/>
/>
/>
/>
/>
/>
/>/>/>
/>/>/>/>/>/>/>
Задание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…..g1g– кодовый набор в коде Грея с (n+1) разрядами.
2. bn…b1b– соответствующее двоичное число.
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
Выходной символ
Сигнал (код)
y1
y2
y3
y4
y5
y6
y7
x4
x3
x2
x1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 3 3 1 1 1 1 1 1 2 4 1 1 1 1 1 1 6 5 1 1 1 1 1 1 1 1 7 6 1 1 1 1 1 1 1 1 5 7 1 1 1 1 4 8 1 1 1 1 1 1 1 1 1 12 9 1 1 1 1 1 1 1 1 1 13 10 1 1 * * * * * * * 8 11 1 1 1 * * * * * * * 9 12 1 1 1 * * * * * * * 10 13 1 1 1 1 * * * * * * * 11 14 1 * * * * * * * 14 15 1 1 * * * * * * * 12
Если не удается заполнить все строкиэтой таблицы, то функция называется не полностью определенной, а наборы накоторых она не определена, носят название запрещенных. В этом случае схеманазывается неполной. Доопределение функции производится произвольно.
2.2 Составлениелогических функций
Существует два способазаписи логической функции по таблице истинности: запись дизъюнктивнойсовершенной нормальной формы (ДСНФ) и запись конъюнктивной совершеннойнормальной формы (КСНФ). В первом случае образуют дизъюнкции, соответствующиевходным наборам, на которых функция принимает значение «1», их объединяютзнаками конъюнкции. Во втором случае организуют конъюнкции, соответствующиевходным словам, на которых функция принимает значение «0», эти конъюнкцииобъединяют знаками дизъюнкции. Рассмотрим на примере функции у3.2.2.1Дизъюнктивная совершенная нормальная форма
Введем понятие логическойстепени, которою будем обозначать />. Тогда,логическая степень будет определяться по формуле (2.1)
/> (2.1)
Любую функцию от n переменных можно представить в виде(см.(2.2))
/> (2.2)
/>означает, что коллективныечлены формируются только для таких наборов (α1, α2,…,αn) для которых функция принимаетединичное значение.
Форма (2.2) определяеталгоритм перехода от таблицы истинности к аналитическому ее виду. Для такогоперехода используется следующий алгоритм:
а) Выбрать в таблице истинности все наборы, в которыхфункция обращается в единицу.
б) Выписать конъюнкции,соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «1», то онвписывается без изменения в конъюнкцию, соответствующую данному набору. Если жевходит в данный набор как «0», то в соответствующую конъюнкцию вписывается егоотрицание.
в) Все полученныеконъюнкции объединяют знаком дизъюнкции.
Для функции у3 СДНФ будетиметь вид:
/>2.2.2Конъюнктивная совершенная нормальная форма
Любую функцию от n переменных можно представить в виду:
f= />
/>означает, что коллективные членыформируются только для таких наборов, (α1, α2,…, αn) для которых функция принимаетнулевое значение.
Следующий алгоритмпозволяет перейти от табличной записи функции к СКНФ:
а) Выбрать в таблицеистинности все наборы, в которых функция обращается в «0».
б) Выписать дизъюнкции,соответствующие этим наборам аргументов. При этом если аргумент хi входит в данный набор как «0», то онвписывается без изменения в дизъюнкцию, соответствующую данному набору. Если жевходит в данный набор как «1», то в соответствующую дизъюнкцию вписывается егоотрицание.
в) Все полученныедизъюнкции объединяют знаком конъюнкции
Функция У3 ввиде СКНФ будет иметь вид:
/>2.3 Минимизациябулевых функций
Минимизация сводится кпоиску минимальных форм (ДНФ и КНФ). Минимальной форме соответствует самаяпростая логическая схема, реализующая данную функцию и требующая минимальныхаппаратных затрат.
В ходе курсовогопроектирования была выполнена минимизация полученных булевых функций следующимиметодами:
1. метод неопределенных коэффициентов
2. метод Квайна-Мак-Класки
3. карты Карно
Для примера в курсовомпроекте рассмотрена минимизация этими способами для функции y3.2.3.1 Пример минимизации методомнеопределенных коэффициентов
Данный метод является посвоим идеям наиболее простым. Для функции записываются все возможные конъюнктивные члены, которые могут входить в дизъюнктивную форму представленияфункции. Коэффициенты К с различными индексами являются неопределенными иподбираются так, чтобы получающаяся после этого дизъюнктивная форма быламинимальной.
Если теперь задаватьвсевозможные наборы значений аргументов и приравнивать полученное после этого выражениезначению функции на выбранных наборах, то получим систему 24уравнений для определения коэффициентов К:
/>
Находим выражения, имеющие в правойчасти ноль. Исходя из определения дизъюнкции вычеркиваются все элементы в этихуравнениях и эти же элементы находящиеся в других уравнениях. В итоге получимуравнения:
/>
Из оставшихся коэффициентов приравниваем единицекоэффициент, определяющий конъюнкцию наименьшего возможного ранга, а остальныекоэффициенты в левой части данного уравнения приравняем нулю(это можно сделать,так как дизъюнкция обращается а единицу, если хотя бы один член ее равенединице). Тогда уравнения примут вид:
/>
/>2.3.2 Пример минимизации методом Квайна-Мак-Класки.
При минимизации по данному методу предполагается, чтоминимизируемая функция задана в СДНФ. Метод Квайна – Мак – Класки состоит изпоследовательного выполнения следующий этапов.
Метод Квайна состоит изпоследовательного выполнения этапов:
1) Нахождениепервичных импликант
2) Расстановка меток
3) Нахождениесущественных импликант
4) Вычеркиваниелишних столбцов
5) Вычеркиваниелишних
6) Получениеминимального покрытия
Выполним, приведенныеэтапы, для функции У3.
Нахождение первичныхимпликант. Все минитермы (элементарные конъюнкции, входящие в ДНФ) даннойфункции записываются в виде их двоичных номеров. Все номера разбиваются почислу единиц в этих номерах на не пересекающиеся группы. При этом в i-тую группу войдут все номера,имеющие в своей двоичной записи ровно iединиц. По парное сравнение (склеивание) можнопроизводить только между соседними по номеру группами. При образованииминитермов с рангом выше нулевого в разряды, соответствующие исключеннымпеременным, пишется знак тире. Минитермы, не склеивающиеся между собой,называются первичными импликантами.
СДНФ, которую мы нашли ранее, дляфункции У3 имеет вид:
/>
Составим минитермы дляэтой функции:
Таблица2.2.1
Минитермы длиной 4
Минитермы длиной 3
Нулевая группа 0000+
Нулевая группа 0-00
Первая группа 0100+
Первая группа -100, -011
Вторая группа 1100, 1010, 0011
Вторая группа 11-0, 1-10, 101-
Третья группа 1110, 1011
Расстановка меток. Остальные этапы нужны, чтобыотбросить некоторые первичные импликанты. На данном этапе составляется таблица,число строк которой равно числу полученных первичных импликант, число столбцовсовпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая– либо из первичных импликант, то на пересечении соответствующего столбца и строкиставится метка. В таблице 2.2.2 приведем результат расстановки меток:
Таблица 2.2.2
0000
0100
1100
1010
0011
1110
1011 1 2 3 4 5 6 7 1
0-00 У У 2
-100 У У 3
-011 У У 4
11-0 У У 5
1-10 У У 6
101- У У
Нахождение существенных импликант. Если в каком – либоиз столбцов таблицы меток стоит только одна метка, то первичная импликанта,стоящая в соответствующей строке, называется существенной импликантой. Всесущественные импликанты запоминаются. А из таблицы меток исключаются строки,соответствующие существенным импликантам, и столбцы минитермов «покрываемых»этими существенными импликантами.
Существенными являются импликанты 0-00 и -011. Поэтомувычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.
Составим сокращенную таблицу меток:
Таблица 2.2.3
1100
1010
1110
-100 У
11-0 У У
1-10 У У
101- У
Выбор минимального покрытия. Исследуетсярезультирующая таблица. Выбирается такая совокупность первичных импликант,которая иссключает метки во всех столбцах (по крайней мере по одной в каждомстолбце). При нескольких возможных вариантах такого выбора отдаетсяпредпочтение варианту покрытия с минимальным суммарным числом букв в простыхимпликантах, образующих покрытие.
С учетом существенных импликант получим две МДНФ дляэтой функции имеет вид:
1./>
2. />
Число букв составляющих простые импликации в каждомварианте одинаково. Во втором варианте на одно отрицание меньше, поэтому беремего за искомое:
/>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в МДНФ будет иметь следующий вид:
/>2.4 Совместнаяминимизация всех функций
Синтез схем на основе отдельно минимизированныхфункций является неоптимальным, с точки зрения количества используемыхэлементов. Так как вероятнее всего, имеются такие конъюнкции, которые дублируютдруг друга. Целью данного пункта является нахождение этих конъюнкций.
Для этого составим карты Карно для каждой функции изтаблицы истинности (таблица 2.1.1). Доопределим ее запрещенные наборы (таблица2.1.1), а затем сгруппируем ячейки таким образом, чтобы таких групп быломинимальное количество на данной карте и максимальное совпадение таких группмежду картами для остальных функций.
Составим карты Карно для всех функций таблицыистинности (таблица 2.1.1)
/>
1 * 1 1 * 1 1 * 1 1 * 1 1 * 1 * * 1 * * 1 * * 1 * * 1 1 * * 1 * * 1 1 * * 1 * * 1 * * 1 1 * * 1 * 1 1 * 1 * 1 1 1 * 1 1 * 1 1
/>1 * 1 1 1 * 1 1 1 * * 1 1 * * 1 * * 1 * * 1 1 * 1 * 1 1
Тогда МДНФ этих функций будет иметь вид:
/>2.5 Запись МДНФ взаданном базисе
Система функций,полученная в пункте 2.4 была записана в системе базисных функций отрицания,конъюнкции и дизъюнкции. Данный базис является не минимальным, и может бытьуменьшен за счет выбрасывания из него конъюнкции или дизъюнкции. После чегополученные базисы являются минимальными.
Запишем функции,полученные в пункте 2.4 в базисе {И-НЕ}. Для этого примем правила ДеМоргана. Тогда функции будут иметь вид:
/>
Рассмотренная проблема минимизацииимеет большое значение для практических целей. Если выбор той или иной базиснойсистемы функций предопределяет выбор стандартного набора типовых логическихэлементов, то решение проблемы минимизации связано с проблемой экономнойреализации различных схем и устройств на базе выбранных типовых элементов.
2.6 Построение функциональной схемы
Каждой логической функции можнопоставить в соответствие особое устройство модулирующие данную функцию. Этоустройство называется логическим элементом. Устройство имеет один вход и n выходов (n – число аргументов логической функции, причем i – ый вход соответствует i – му аргументу ).
/>/>/>/>Стандартные графические обозначения логических элементовприведены на рис. 2.6.1.
/>
а) б) в) г)
Рис. 2.6.1графическое обозначение логических элементов
а)элемент «НЕ» б) элемент «ИЛИ» в) элемент «И» г) элемент в базисе «И-НЕ»
Построим функциональную схему на основе базиса {И-НЕ}(Приложение 1).
3. СИНТЕЗАВТОМАТА С ПАМЯТЬЮ3.1 Анализтехнического задания
В данном разделе курсовой работынеобходимо синтезировать автомат с памятью на основе содержательного описанияалгоритма его работы.
Автомат управляетгрузовым лифтом.
Грузовой лифт,обслуживает трехэтажный магазин, имеет кнопку вызова на каждом этаже и работаетпо следующим правилам: если нажата одна кнопка, то лифт движется насоответствующий этаж; если нажато одновременно несколько кнопок, то лифтдвижется на самый нижний из всех этажей на которые нажаты кнопки. Ни однакнопка не может быть нажата во время движения.
Согласно заданию накурсовую работу, в качестве элементов памяти следует использовать D – триггеры.
3.2 Формальноеописание абстрактного автомата
Абстрактный автомат зададим в видеавтомата Милли.
Для формального описанияабстрактного автомата необходимо задать входной алфавит, выходной алфавит,множество состояний, функцию переходов и функцию выходов.
Автомат имеет три входа,соответствующих различным комбинациям подаваемых сигналов.
Входной алфавит:
Х={х1, х2, х3},
где х1 означает,что нажата кнопка первого этажа; х2 означает, что нажата кнопкавторого этажа, х3 означает, что нажата кнопка третьего этажа.
Выходной алфавит:
У= {у0, у1,у2, у3, у4},
где
у0– лифтстоит на месте,
у1 – лифтедет на один этаж вверх,
у2 — лифтедет на один этаж вниз,
у3 — лифтедет на два этажа вверх,
у4 — лифтедет на два этажа вниз.
Множество состояний:
S= { s1, s2, s3};
где s1 — лифт на первом этаже; s2 – лифт на втором; s3 – лифт натретьем этаже.
Теперь, можно составитьтаблицы переходов – входов и переходов выходов.
Таблица переходов –входов представлена в таблице 3.2.1 .
Таблица3.2.1
S
s1
s2
s3
х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/>
х2
х1 х1 х2 1 х3 1 х4 1 1 х5 1 х6 1 1 х7 1 1 х8 1 1 1
Кодирование выходных символовпредставлено в таблице 3.3.2 .
Таблица 3. 3.2 у1 у2 у3
у0 1 1
у1
у2 1
у3 1 1 1
у4 1 1
Кодирование состояний автоматапредставлено в таблиц 3.3.3.
Таблица 3.3.3S
t1
t2
s1
s2 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\s1s2s3 00 01 11 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) можно получить СДНФ для у ( выходов нашего автомата).
/>
/>/>
/>
Нахождение функцийвозбуждения памяти ( Ф1, Ф2) производится в соответствиис типом триггера. D – триггер имеетодин вход и один выход, его изображение приведено на рис. 3.5.1 .
/>
/>
/> /> /> /> /> /> />
Рис.3.2 D – триггер
/>
Функция переходов данногоавтомата памяти приведен в таблице 3.8. Если закодировать входные и выходныесимволы D – триггера (табл. 3.9.,3.10), токодированная таблица переходов примет вид таблицы 3.5.1.
Таблица 3.5.1j\t 1 1 1 1
При построении функцийвозбуждения памяти автомата строят функцию входов элемента памяти. Эту функциюзадают в виде таблице. Функция входов структурного автомата памяти П приведенав таблице 3.5.2 .
Таблица 3.5.2
tисх Ф
tнов 1 1 1 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 имеем:
/>
/>
3.6 Минимизациялогических функций
С помощью программы Logic можно минимизировать, полученные впрошлом разделе логические функции. В итоге они примут вид:
/>
/>3.7 Построение комбинационной схемы автомата с памятью
Схема автомата с памятью основаннойна D-триггере представлена в Приложении 2.
ЗАКЛЮЧЕНИЕ
В курсовой работе по дисциплине «Математические основы теории систем» были выполнены два раздела, в которых былизакреплены теоретические знания по темам: анализ сигнального графа и синтезкомбинационных схем.
В первом разделеисследуется сигнальный граф: преобразование структурной схемы к сигнальномуграфу, расчет передач графа. Для описания графа, использовались его структурныехарактеристики: матрица смежности, матрица касания путей и контуров, матрицаинциденций, матрица путей, матрица контуров, матрица касания контуров.
Во втором разделе былиполучены некоторые навыки в области синтеза комбинационных схем. Результатомпроделанной работы явилась комбинационная схема управления светодиодамисемисегментного индикатора.
В третьем разделенеобходимо синтезировали автомат с памятью на основе содержательного описанияалгоритма его работы.
Приложение 1.
Приложение 2