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

Согласно заданию на курсовую работу выделено множество К контрольных точек (выходов). Оно имеет вид:

К={x₁, x₄, y, x₁₃}

Построим матрицы путей для каждого из этих выходов.

Бинарная матрица P=|| p_ij || путей размера l x m, где l – число путей, строится по следующему правилу:

Матрица путей выхода для x1

	w1	w2	w3	w4	w5	w6	w7	w8	u9	u10	u11	u12	u13	u14	u15	u16	u17	u18	u19	u20
1	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0

 

Матрица путей выхода для x4

	w1	w2	w3	w4	w5	w6	w7	w8	u9	u10	u11	u12	u13	u14	u15	u16	u17	u18	u19	u20
1	1	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0
2	0	1	0	0	0	0	0	0	1	0	1	0	0	0	0	0	0	0	0	0

 

Матрица путей выхода для y

	w1	w2	w3	w4	w5	w6	w7	w8	u9	u10	u11	u12	u13	u14	u15	u16	u17	u18	u19	u20
1	1	0	0	0	0	0	0	0	1	1	0	1	0	1	1	0	0	0	0	0
2	1	0	0	0	0	0	1	0	1	1	0	0	0	0	0	0	1	0	0	0
3	1	0	0	0	0	0	0	1	1	1	0	0	0	0	0	1	1	0	0	0
4	0	1	0	0	1	1	0	0	1	0	1	1	0	1	0	0	0	0	0	0
5	0	1	0	0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	0	0
6	0	1	0	0	0	0	0	1	1	0	1	0	0	0	0	1	1	0	0	0

 

Матрица путей выхода для x13

	w1	w2	w3	w4	w5	w6	w7	w8	u9	u10	u11	u12	u13	u14	u15	u16	u17	u18	u19	u20
x	1	0	1	1	1	1	0	0	1	1	0	1	0	1	0	1	0	0	0	0
x1	1	0	1	1	0	0	1	0	1	1	0	0	0	0	1	0	1	1	0	0
x2	1	0	1	1	0	0	0	1	1	1	0	0	0	0	0	1	1	1	0	0
x3	0	1	1	1	1	1	0	0	1	0	1	1	0	1	0	0	0	0	0	0
x4	0	1	1	1	0	0	1	0	1	0	1	0	0	0	1	0	1	1	0	0
x5	0	1	1	1	0	0	0	1	1	0	1	0	0	0	0	1	1	1	0	0

 

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

Бинарная матрица контуров C=|| c_ij || размера h x m, где h - число контуров, строится по следующему правилу:

Предварительно пронумеруем все контуры в произвольном порядке.

	w1	w2	w3	w4	w5	w6	w7	w8	u9	u10	u11	u12	u13	u14	u15	u16	u17	u18	u19	u20
1	1	0	1	1	1	1	0	0	1	1	0	1	0	1	0	0	0	1	0	1
2	1	0	1	1	0	0	1	0	1	1	0	0	0	0	1	0	1	1	0	1
3	1	0	1	1	0	0	0	1	1	1	0	0	0	0	0	1	1	1	0	1
4	0	1	1	1	1	1	0	0	1	0	1	0	0	1	0	0	0	1	0	1
5	0	1	1	1	0	0	1	0	1	0	1	0	0	0	1	0	1	1	0	1
6	0	1	1	1	0	0	0	1	1	0	1	0	0	0	0	1	1	1	0	1
7	0	0	0	0	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0
8	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0

 

Матрица касания контуров

Бинарная матрица контуров C _k =|| c_ij || размера h x k, где 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	0
8	1	1	1	1	1	1	0	1

 

Матрица касания путей и контуров

Бинарная матрица контуров C _l =|| c_ij || размера l x k, где l - число путей для заданного выхода, строится по следующему правилу:

 

Для 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

 

Формула Мэзона для заданного сигнального графа

Используя универсальную топологическую формулу, носящую имя Мэзона, можно получить передачу между любыми двумя вершинами. Формула имеет следующий вид:

 

где - передача k -го пути между вершинами j и r; D -определитель графа. Он характеризует контурную часть графа и имеет следующий вид:

где, L – множество индексов контуров, L₂ - множество пар индексов не касающихся контуров, L₃ - множество троек индексов не касающихся контуров, K_i – передача 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)

К₁=W₁W₃W₄W₅W₆

K₂=W₃W₄W₇

K3=W₁W₃W₄W₈

K4=W₂W₃W₄W₆ W₇

K5=W₂W₃W₄W₇

K6=W₂W₃W₄W₈

K7=W₅W₆

K8=W₃W₄

D=1- W₃W₄(W₁W₅W₆+ W₇+ W₁W₈+ W₂W₆ W₇+ W₂W₇+2W₂W₈+ 1)+ W₅W₆(W₃W₄(W₇+ W₁W₅W₆+ W₂W₇+ W₂W₈+1)-1)

Для x1

Для x4

Для y

Для х13

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