Логические сети

Логические сети

Содержание

Введение

.        Логические сети

1.1       Определение и реализация булевых функций

1.2     Схемы функциональных элементов

.3       Мультиплексоры

.4       Программируемые логические матрицы

.        Практическая часть

Заключение

Список литературы

Введение

Логические сети - этот обобщенное название технологий, реализующих кодовые преобразования. Например, мультиплексоры и программируемые логические матрицы.

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

В микропроцессорной технике программируемые логические матрицы (ПЛМ) наиболее широко используются для реализации микропрограммных устройств управления. По способу программирования различают ПЛМ программируемые в процессе изготовления и программируемые пользователем.

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

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

1. Логические сети

.1 Определение и реализация булевых функций

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

На рисунке 1 приведен пример контактной схемы с двумя полюсами а1 и а6.

Рисунок 1

(k+1) - полюсная схема, в которой один полюс выделен (он называется входным), а остальные полюса (выходные) равноправны, называется (1,k)-полюсником. Таким образом, если в приведенной на рисунке 1 двухполюсной схеме рассматривать, например, полюс а1 как входной, а полюс а6, как выходной, то получаем (1, 1)-полюсник.

Ребра контактной схемы называются контактами. Контакт, соответствующий логической переменной  называется замыкающим и обозначается через . Замыкающий контакт пропускает ток при  Контакт, соответствующий литере  называется размыкающим и обозначается как . Через него ток проходит при  Таким образом, значение 1 интерпретируется как состояние переключателя “ток проходит”, а 0 - “ток не проходит”. Функции  соответствует последовательное соединение контактов , а функции  - параллельное соединение контактов

Нетрудно заметить, что схеме, показанной на рисунке 1, соответствует электрическая схема, приведенная на рисунке 2, а также схема контактов, изображенная на рисунке 3. На последнем рисунке показаны контакты, зависящие от значений переменных  а также схема соединений контактов.

Рисунок 2

Рисунок 3

Пусть a, b - полюса контактной схемы ,  - некоторая цепь из а в b,  - конъюнкция литер, приписанных ребрам цепи . Функция , определяемая формулой  в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, называется функцией проводимости между полюсами a и b схем  Говорят, что функция  реализуется (1, k)-полюсником, если существует такой выходной полюс  что  где а - входной полюс. (1,1)-полюсники называются эквивалентными, если они реализуют одну и ту же булеву функцию. Сложностью (1,1)-полюсника называется число контактов. (1,1)-полюсник, имеющий наименьшую сложность среди эквивалентных ему схем, называется минимальным. Сложность минимального (1,1)-полюсника, реализующего функцию  называется сложностью функции  в классе (1,1)-полюсников и обозначается через .

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

 (1)

математический метод логический матрица задача

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

Эффективное уменьшение числа контактов достигается с помощью нахождения минимальной ДНФ булевой функции.

Найдем минимальную ДНФ функции (1), реализуемой схемой на рисунке 2. Придавая логическим переменным  все возможные значения, но схеме или формуле (1) получаем таблицу истинности:

С помощью таблицы истинности определим совершенную ДНФ:

Используя один из методов нахождения минимальной ДНФ, получаем формулу  эквивалентную формуле (1) и соответствующую схеме, состоящей из семи контактов (рисунок 4а).

Рисунок 4

Отметим, что схема, изображенная на рисунке 4а, допускает упрощение, соответствующее формуле  которое приведено на рисунке 4б и является минимальной схемой. Сложность минимальной схемы равна 6: .

.2 Схемы из функциональных элементов

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

)        если а входной полюс, то полустепень захода вершины а равна нулю: ;

)        если вершина а не является полюсом и помечена n-местным функциональным символом  то и дуги, входящие в а, перенумерованы от 1 до n.

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

Пример 1. На рисунке 5а представлена схема из функциональных элементов. Здесь входные символы помечены символами переменных  - одноместный функциональный символ, соответствующий операции отрицания; & - двухместный символ, соответствующий операции конъюнкции.  - некоторый двухместный символ,  - некоторые трехместные символы. Вершины, помеченные символами , являются выходными полюсами. Им соответствуют термы:

 На рисунке 5б изображен функциональный элемент, определяемый вершиной, помеченной символом  Ему соответствует устройство, показанное на рисунке 5в.

Рисунок 5

В примере 1 продемонстрировано, что каждый вывод схемы порождает некоторый терм.

Говорят, что функция  реализуется схемой, если существует такой выход а схемы , что функция  соответствующая терму выхода а, эквивалента функции .

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

Пример 2. Сложность функции  совпадает со сложностью -функциональной схемы, изображенной на рисунке 6, и равна 8: .

Рисунок 6

.3 Мультиплексоры

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

На рисунке 7 показан мультиплексор.

Рисунок 7

Пример 3. Если  то

С помощью мультиплексора , придавая переменным постоянные значения, можно реализовать любую булеву функцию

.4 Программируемые логические матрицы

Рассмотрим схему, состоящую из  входов , и  выходов  (рисунок 8), в которой значения выходов определяются матрицей соединений  по следующим правилам:

Рисунок 8

Таким образом,  где  а остальные  равны 0. Полученная схема называется решеткой с  входами и  выходами элементов &, которая определяется матрицей соединений .

Программируемой логической матрицей (ПЛМ) называется изображенная на рисунке 9 схема, получающаяся соединением решетки А с 2n входами и k выходами, определяемой матрицей соединений , и решетки В с k входами и m выходами, определяемой матрицей соединений .

Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных  Поскольку к каждому входу  присоединен инвертор , на 2п входов решетки А подаются значения переменных  После прохождения решетки A h-й выход принимает значение функции  а последующей операции инвертирования соответствует функция:

Полученные k значений  подаются на входы решетки В, после прохождения которой на выходе j образуется значение функции

В заключение после инвертирования по законам де Моргана на выходе j получаем значение функции:

Функции  соответствует дизъюнкция конъюнктов (определяемых формулами

 ) таких, что

Рисунок 9

Таким образом, при соответствующем выборе матриц  и  можно одновременно реализовать m произвольных ДНФ, содержащих не более k различных конъюнктов переменных от

2. Практическая часть

I.       Исследовать систему булевых функций на полноту. Является ли она базисом. .