Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2018-01-05 | 182 |
5.00
из
|
Заказать работу |
|
|
Цель: исследование представлений схем двудольным графом.
Теоретические сведения
Граф – это конечное множество вершин и ребер, соединяющих их, т. е.:
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 этот список имеет вид:
(N 1: a, x. IN 1, y.IN 1)
(N 2: b, x. IN 2, y. IN 2)
(N 3: x. OUT, z. IN 1)
(N 4: y.OUT, z.IN 2)
(N 5: z. OUT, c)
3)Для схемы на рис. 2.2 нарисовать двудольный граф, одна доля которого – это цепи, вторая – контакты.
Рис. 2.2 – Электрическая схема
сети элементов
Тема 3. Изучениевходных-выходных сигналов систем безопасности
Цель: исследование схем без памяти (комбинационных схем).
Теоретические сведения.
Комбинационные схемы – это схемы, у которых выходные сигналы
Y = (у1, у2,..., уm) в любой момент дискретного времени однозначно определяются совокупностью входных сигналов Х = (х1, х2..., хп), поступающих в тот же момент времени t. Реализуемый в КС способ обработки информации называется комбинационным потому, что результат обработки зависит только от комбинации входных сигналов и формируется сразу же при поступлении входных сигналов. Поэтому одним из достоинств комбинационных схем является их высокое быстродействие. Преобразование информации однозначно описывается логическими функциями вида Y = f(X). Значение функции различно для разных комбинаций входных переменных и может быть задано с помощью специальной таблицы – Таблицы истинности.
В левой части этой таблицы перечислены всевозможные комбинации входных переменных (наборы значений), а в правой - возможные реакции выходных сигналов.По данной таблице нетрудно составить аналитическое выражение (зависимость) для функции. Для этого наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логическое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормальных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значении, то такая форма функций называется совершенной.
|
Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия – [, дизъюнкция - v, конъюнкция - л или &}.Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.
Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции «отрицание дизъюнкции» –Стрелка Пирса и «отрицание конъюнкции» –штрих Шеффера.
Логическое выражение функции, получаемое на основе Таблицы истинности в виде совершенной дизьюнктивной формы, может быть упрощено путем его минимизации.
Таблица истинности функции Y=f(x 1, x2, x3)
x 1 | x2 | x3 | Y |
По данным таблицы запишем аналитическое выражение:
Рис.3.1 – Структурная схема полусумматора (а) и обозначение полусумматора (б)
Задание для самостоятельной работы:
По логической схеме рис 3.1:
1) построить алгебраическое представление функций S и P;
2) построить таблицы истинности функций S и P;
3)построить алгебраическое представление реализуемых функций
по заданной комбинационной схеме.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!