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

Матрица путей для входной вершины 12 и  выходной 1: 

             Матрица путей для входной  вершины 12 и выходной 3:

             Матрица путей для входной  вершины 12 и выходной 11:

 

            Матрица путей для входной  вершины 12 и выходной 13:

 

 

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

 

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

Таким образом, данная матрица будет иметь вид:

Строки контурной матрицы соответствуют  контурам, а столбцы – ветвям схемы.

 

 

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

 

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

 

Матрица является квадратной и симметричной относительно главной диагонали.

 

 

 

 

 

1.3.6 Бинарная  матрица касания путей и контуров

 

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

 

Матрица касания путей и контуров для выходной вершины 12 и выходной 1:

Матрица касания путей и контуров для выходной вершины 12 и выходной 3:

Матрица касания путей и контуров для выходной вершины 12 и выходной 11:

Матрица касания путей и контуров для выходной вершины 12 и выходной 13:

 

 

 

 

 

 

1.4 Передаточные  функции

 

Для расчета  передаточных функций воспользуемся формулой Мезона:

                                                                                                 (1.1)                                

где - передача между фиксированными сигналами;

      - передача k-го пути между x_i и x_j;

      - минор k-го пути между входной вершиной x_i и выходной x_j;

     - определитель графа, который характеризует

        контурную  часть.

                                                    (1.2)

где - передача i-го контура;

     - множество индексов контуров;

      - множество индексов пар не касающихся

         контуров;

     - множество индексов троек не касающихся

         контуров.

Контуры имеют  следующие передачи:

k₁=W₁*W₂*W₄*W₁₅

k₂=W₁*W₂*W₄*W₁₆

k₃=W₁*W₂*W₃*W₁₅

k₄=W₁*W₂*W₃*W₁₆

k₅=W₁*W₂*W₅*W₉*W₁₅

k₆=W₁*W₂*W₅*W₉*W₁₆

 

Определитель графа:

      = 1- (k₁+k₂+k₃+k₄+k₅+k₆)

 

Для точки x₁: , где P_12,1=1,      _12,1 = 1

Для точки x₃: , где P_12,3=W₁,      _12,3=1

 

Для точки x_13: , где P_12,13=W₁*W₂*W₄+ W₁*W₂*W₃+ W₁*W₂*W₅*W₉,

_12,13=1

Для точки x₁₁: ,      _12,11=1

где P_12,11= W₁*W₂*W₄*W₁₅+ W₁*W₂*W₄*W₁₆+W₁*W₂*W₃*W₁₅+ W₁*W₂*W₃*W₁₆+ W₁*W₂*W₅*W₉*W₁₅+ W₁*W₂*W₅*W₉*W₁₆

 

 

 

 

2 СИНТЕЗ  КОМБИНАЦИОННЫХ СХЕМ

    2.1 Задание

 

Разработать схему управления семисегментного светодиодного индикатора (рис. 2.1) в базисе {И-НЕ}. Схема должна иметь четыре входа, управляемые переменными х₁, х₂, х₃, х₄, и семь выходов у₁, у₂, у₃, у₄, у₅, у₆, у₇. Каждому из выходных сигналов у_i однозначно соответствует своя комбинация переменных х_i, образуемая по закону кодообразования Грея. Устройство осуществляет ввод каждого кодового набора переменных х_i, в двоично-десятичном виде. В качестве блока отображения информации используется семисегментный светодиод.

 

2.2 Таблица истинности

 

Составим  таблицу истинности для семисегментного индикатора, изображенного на рисунке 2.1.

 

          Рисунок 2.1 – Семисегментный индикатор

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 2.1 –  Таблица истинности

Десятичные  цифры	Код c весами 3321							Y1		Y2		Y3	Y4	Y5	Y6	Y7
	Х4	Х3		Х2		Х1
0	0	0		0		0		1		1		1	1	1	1	0
1	0	0		0		1		0		1		1	0	0	0	0
2	0	0		1		0		1		1		0	1	1	0	1
3	0	0		1		1		1		1		1	1	0	0	1
4	1	0		0		1		0		1		1	0	0	1	1
5	0	1	1		0		1		0		1		1	0	1	1
6	1	1	0		0		1		0		1		1	1	1	1
7	1	1	0		1		1		1		1		0	0	0	0
8	1	1	1		0		1		1		1		1	1	1	1
9	1	1	1		1		1		1		1		1	0	1	1
Запрещенные наборы	0	1	0		0		Х		Х		Х		Х	Х	Х	Х
	0	1	0		1		Х		Х		Х		Х	Х	Х	Х
	0	1	1		1		Х		Х		Х		Х	Х	Х	Х
	1	0	0		0		Х		Х		Х		Х	Х	Х	Х
	1	0	1		0		Х		Х		Х		Х	Х	Х	Х
	1	0	1		1		Х		Х		Х		Х	Х	Х	Х

 

2.3 Переход от таблицы истинности к логической функции

 

Существует  два способа записи логической функции  по таблице истинности – дизъюнктивно совершенная нормальная форма (ДСНФ) и конъюнктивно совершенная нормальная форма (КСНФ), которые рассмотрим на примере функции y_1. Так как функция не полностью определена, доопределим ее на недостающих наборах нулями. Согласно этому таблица истинности для y₁ будет иметь вид:

 

 

 

 

Таблица 2.2 –Таблица истинности функции y₁

 

 

Х4	Х3	Х2	Х1	Y1
0	0	0	0	1
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
1	0	0	1	0
0	1	1	0	1
1	1	0	0	1
1	1	0	1	1

 

 

 

 

 

 

 

 

 

 

 

 

 

Продолжение таблицы 2.2

1	1	1	0	1
1	1	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	1	1
1	0	0	0	0
1	0	1	0	1
1	0	1	1	0

 

 

 

 

 

 

 

 

 
Таблица истинности связывает значение входных и выходных переменных.

 

2.3.1 ДСНФ

 

Входные наборы, на которых функция принимает  значение единицы: 0000, 0010, 0011, 0110, 1100, 1101, 1110, 1111, 0111, 1010. Тогда ДСНФ будет иметь следующий вид:

       (2.1)                    

Таким образом, мы получили дизъюнкции, соответствующие  входным наборам, на которых функция  принимает значение 1, и объединили их знаками конъюнкции.

 

 

2.3.2 КСНФ

 

Входные наборы, на которых функция принимает  значение нуль: 0001, 1001, 0100, 0101, 1000, 1011. Тогда КСНФ будет выглядеть следующим образом:

 

Мы получили конъюнкции, соответствующие входным  наборам, на которых функция принимает  значение 0, и объединили их знаками  дизъюнкции.

 

            

             2.4 Минимизация логической функции

2.4.1 Метод Квайна-Мак-Класки

 

При использовании  данного метода минимизируемая функция должна быть заданна в ДСНФ (2.1):

 

Запишем минитермы и произведем операцию склеивания. Знак * означает, что для данной минитермы произошло склеивание:

 

 

Исходные  минитермы (ДСНФ)

   0-ая  группа: 0000*

   1-ая  группа: 0100*

   2-ая  группа: 0011*,0101*, 1100*

   3-ья  группа: 0111*, 1011*, 1110*

   4-ая группа: 1111*

 Минитермы 1-го ранга:

   0-ая  группа: 0-00

   1-ая  группа: 010-*,01-0*,-100*

   2-ая  группа: 0-11*,-011*,01-1*,011-*,-110*,11-0*

   3-ья  группа: -111*,1-11*,111-*

   Минитермы 2-го ранга:

   0-ая  группа: отсутствует

   1-ая  группа: 01--,-1-0

   2-ая  группа: --11,-11-

   Минитермы 3-го ранга:

   0-ая  группа: отсутствует

   1-ая  группа: отсутствует

Первичные импликанты 

   0-00,--11,01--,-1-0,-11-

Составим  таблицу меток:

 

Таблица 2.3 –  Таблица меток

	0000	0011	0100	0101	0110	0111	1011	1100	1110	1111
0-00	*		*
--11		*				*	*
01--			*	*	*	*
-1-0			*		*			*	*
-11-					*	*			*	*

 

Выпишем 0-00, --11, 01--, -1-0.

Таким образом, выпишем МДНФ:

 

Мы получили  МДНФ под которым понимается такое выражение, которое содержит минимальное число символов вида по сравнению с другим ДНФ данной функции.

 

 

 

 

 

 

2.4.2 Метод неопределенных коэффициентов

 

Логическая  функция представляется суммой всевозможных конъюнктивных членов, взвешенных неизвестными коэффициентами. Для каждого набора аргументов логической функции выписывается сумма коэффициентов, которая затем  приравнивается к соответствующему значению функции. Таблица коэффициентов  представлена на рисунке 2.4.

Так как  в ряде случаев  функция принимает  значение «0», следовательно, коэффициенты для данных наборов также должны равняться нулю. Рассмотрев все наборы, на которых функция обращается в  нуль, получим нулевые коэффициенты. В оставшихся уравнениях, в которых  функция принимает значение «1», также вычеркнем все нулевые  коэффициенты, определенные ранее. Таким  образом, таблица коэффициентов  на рисунке 2.4 будет иметь вид:

 

    

Рисунок 2.4 – Таблица коэффициентов

 

 

 

 

 

 

 

 

 

После устранения нулевых коэффициентов получим  систему уравнений (не коэффициенты), где приравняем к нулю в каждом уравнении системы все коэффициенты кроме одного самого короткого, окончательно получаем следующий результат:

                                                                

                                                                                              (2.3)

                                                               

 

                      

На основании (2.3) запишем МДНФ:

 

 

Рассмотренный метод характеризуется  тем, что для минимизируемой функции выписываются всевозможные коньюнкции, которые могут входить в ДНФ этой функции.

 

2.4.3 Карты Карно

 

На рисунке 2.2 изображена карта Карно для  функции y₁:

 

X₃x₄

	00	01	11	10
00	1	0	1	0
01	1	1	1	1
11	1	0	1	1
10	0	0	1	0

 

 

 

 

                                     X₁X₂ 
Рисунок 2.2 – Карта Карно