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

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

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

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

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

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

	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

 

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

	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 xm, где 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 xk, где 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 xk, где l - число путей для заданного выхода, строится по следующему правилу:

 

Для x 1

	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	0	0

 

Для x 4

	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₇+2 W₂ W₈+ 1)+ W₅ W₆( W₃ W₄( W₇+ W₁ W₅ W₆+ W₂ W₇+ W₂ W₈+1)-1)

Для x1

Для x4

Для y

Для х13

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

⇐ Предыдущая12345Следующая ⇒

Поделиться: