Тема 2. ИзучениеVHDL-моделей систем

Цель:исследование представлений схем двудольным графом.

Теоретические сведения

Граф – это конечное множество вершин и ребер, соединяющих их, т. е.:

G = (V,E),

где V – конечное непустое множество вершин; Е – множество ребер (пар вершин).

Если пары Е (ребра) имеют направление, то граф называется ориентированным (орграф), если иначе - неориентированный (неорграф). Если в пары Е входят только различные вершины, то в графе нет петель. Если ребро графа имеет вес, то граф называется взвешенным. Степень вершины графа равна числу ребер, входящих и выходящих из нее (инцидентных ей). Неорграф называется связным, если существует путь из каждой вершины в любую другую.

Обозначим количество вершин как n = ¦ V¦, а количество ребер как m = ¦ E ¦.

Графы в памяти могут представляться различным способом. Один из видов представления графов – это матрица смежности B(n*n); В этой матрице элемент b[i,j]=1, если ребро, связывающее вершины Vi и Vj существует и b[i,j]=0, если ребра нет. У неориентированных графов матрица смежности всегда симметрична.

Во многих случаях удобнее представлять граф в виде так называемого списка пар. Список пар содержит для каждой вершины из множества вершин V список тех вершин, которые непосредственно связаны с этой вершиной.

Граф G = (V,E) называется двудольным графом (биграфом), если множество V его вершин допускает разбиение на 2 непересекающихся подмножества V1 и V2 (две доли). Причем каждое ребро графа соединяет вершины из различных долей. Обозначается через G = (V1,V2,E) – двудольный граф с долями V1 и V2.

Моделью структурного описания является двудольный граф, одной долей которого являются порты (выводы) экземпляров элементов и порты самого устройства, а второй долей – цепи, соединяющие порты. Обозначения выводов экземпляров элементов предваряются его именем, показанным на рис. 2.1 в прямоугольнике фигуры. Экземпляры показаны прямоугольниками (не являются элементами графа), вершинами графа являются выводы экземпляра в прямоугольнике. Вершины цепей показаны кружками. Обозначения (имена) выводов и некоторых цепей для упрощения рисунка опущены.

Рис. 2.1 – Неориентированный двудольный граф структуры цифрового устройства

Задание для самостоятельной работы

В заданной логической схеме (рис. 2.1):

1) Отметить (назвать) цепи и элементы;

2) Построить список цепей (netlist) в виде списка пар двудольного графа схемы. Для примера на рис. 2.1 этот список имеет вид:

(N1: a, x.IN1, y.IN1)

(N2: b, x.IN2, y.IN2)

(N3: x.OUT, z.IN1)

(N4: y.OUT, z.IN2)

(N5: z.OUT, c)

3)Для схемы на рис. 2.2 нарисовать двудольный граф, одна доля которого – это цепи, вторая – контакты.

Рис. 2.2 – Электрическая схема
сети элементов

Тема 3. Изучениевходных-выходных сигналов систем безопасности

Цель:исследование схем без памяти (комбинационных схем).

Теоретические сведения.

Комбинационные схемы – это схемы, у которых выходные сигналы
Y = (у₁, у₂,..., у_m) в любой момент дискретного времени однозначно определяются совокупностью входных сигналов Х = (х₁, х₂..., х_п), поступающих в тот же момент времени t. Реализуемый в КС способ обработки информации называется комбинационным потому, что результат обработки зависит только от комбинации входных сигналов и формируется сразу же при поступлении входных сигналов. Поэтому одним из достоинств комбинационных схем является их высокое быстродействие. Преобразование информации однозначно описывается логическими функциями вида Y = f(X). Значение функции различно для разных комбинаций входных переменных и может быть задано с помощью специальной таблицы – Таблицы истинности.

В левой части этой таблицы перечислены всевозможные комбинации входных переменных (наборы значений), а в правой - возможные реакции выходных сигналов.По данной таблице нетрудно составить аналитическое выражение (зависимость) для функции. Для этого наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логическое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значении, то такая форма функций называется совершенной.

Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия – [ , дизъюнкция - v, конъюнкция - л или &}.Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции «отрицание дизъюнкции» –Стрелка Пирса и «отрицание конъюнкции» –штрих Шеффера.

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

Таблица истинности функции Y=f(x₁, x₂, x₃)