Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
µйдем от схемы рис. 1.1 к соответствующему сигнальному графу (см. рис. 1.2).
Вершины отмеченные серым цветом это заданные контрольные точки.1.3 Матрица смежности
Матицей смежности графа G называется матрица R=[rij] размером nxn, где n число вершин графа, в которой
xx1x2x3x4x5x6x7x8x9x10x11x12x13yx010000000000000x1001100000000000x2000010000000000x3000010000000000x4000001001100000x5000000100000000x6000000010000000x7000001000000001x8000000000010000x9000000000010000x10000000000000001x11000000000000100x12000000000000010x13100000000001000y000000000001000
1.4 Матрица инцидентности
Матрицей инцидентности графа G называется матрица S=[sij] размера nxm, где n число вершин графа, а m число дуг графа, в которой:
Для построения графа пронумеруем все дуги графа в произвольном порядке, но с учетом нумерации передаточных функций.
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20x0000000010000000000-1x111000000-100000000000x2-10000000010000000000x30-1000000001000000000x4000000110-1-1100000000x500001000000-1-10000000x60000-1100000000000000x700000-100000011000000x8000000-10000000100000x90000000-1000000010000x1000000000000000-1-11000x1100100000000000000-1-10x1200-110000000000000000x13000-10000000000000011y0000000000000-100-1100
1.5 Построение бинарных матриц путей выхода для заданных контрольных точек.
Согласно заданию на курсовую работу выделено множество К контрольных точек (выходов). Оно имеет вид:
К={x1, x4, y, x13}
Построим матрицы путей для каждого из этих выходов.
Бинарная матрица P=pij путей размера lxm, где l число путей, строится по следующему правилу:
Матрица путей выхода для x1
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20100000000100000000000
Матрица путей выхода для x4
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20110000000110000000000201000000101000000000
Матрица путей выхода для y
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20110000000110101100000210000010110000001000310000001110000011000401001100101101000000501000010101010101000601000001101000011000
Матрица путей выхода для x13
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20x10111100110101010000x110110010110000101100x210110001110000011100x301111100101101000000x401110010101000101100x501110001101000011100
1.6 Бинарная матрица контуров.
Бинарная матрица контуров C=cij размера hxm, где h - число контуров, строится по следующему правилу:
Предварительно пронумеруем все контуры в произвольном порядке.
w1w2w3w4w5w6w7w8u9u10u11u12u13u14u15u16u17u18u19u20110111100110101000101210110010110000101101310110001110000011101401111100101001000101501110010101000101101601110001101000011101700001100000010000000800110000000000000010
1.7 Матрица касания контуров
Бинарная матрица контуров Ck=cij размера hxk, где k - число контуров, строится по следующему правилу:
12345678111111111211111111311111111411111111511111111611111111711111110811111101
1. 8 Матрица касания путей и контуров
Бинарная матрица контуров Cl=cij размера lxk, где l - число путей для заданного выхода, строится по следующему правилу:
Для x1
12345678111111100
Для x4
12345678111111100211111100
Для y
12345678111111110211111100311111100411111110511111100611111100
Для x13
12345678111111111211111101311111101411111111511111101611111101
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
Для х13
Задание 2. Синтез комбинационных схем.
2.1 Определение поставленной задачи
Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n выходов и m входов. На каждый вход может быть подан произвольный символ конечного множества Х, называемого входным алфавитом. Совокупность входных символов, поданных на входы устройства, образует входное слово Рi в алфавите Х. На выходе устройства появляются выходные слова Qj, составленные из символов выходного алфавита Y. В силу конечности алфавитов X, Y и слов Pi, Qj (длина слова всегда равна m, а выходного слова - h) общее количество различных входных и выходных слов также конечно.
Элементарный такт работы устройства состоит в том, что при появлении на входе слова Рi устройство выдает на выходах комби?/p>