Главная страница Случайная лекция
Мы поможем в написании ваших работ!
Порталы:
БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика
Мы поможем в написании ваших работ!
СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
Наряду с представлением булевских функций формулами применяется представление таких функций с помощью специальных схем, наглядно представляющих процесс вычисления значений б.ф. на произвольных наборах значений переменных. Такие схемы позволяют осуществлять логическое проектирование реальных электронных схем на основании набора простейших узлов, из которых эти схемы собираются по определенным правилам.
Каждый такой узел способен вычислять или реализовывать некоторую булеву функцию. Логическая модель узла называется функциональным элементом (ф.э.). Выберем в качестве набора функциональных элементов элементы, реализующие функции &, Ú,` .
Будем изображать такие элементы в виде:
 |
& 
Здесь стрелки, ведущие в ф.э. (входы элементов), представляют каналы, по которым в такие ф.э. поступают значения переменных.
По стрелкам, выходящим из ф.э. (выходам элемента), выдаются значения функций, вычисляемых элементами.
В функционировании всякого ф.э. предполагается, что на его входы (или вход) одновременно поступают двоичные наборы, а на выходе в тот же момент времени появляются значения функции, соответствующей такому элементу.
Из отдельных элементов строятся схемы из функциональных элементов (с.ф.э.), которые удовлетворяют следующим требованиям:
1) схема имеет конечное число входов, помеченных символами переменных;
2) выходы всякого входа схемы или элемента схемы могут разветвляться;
3) на всякий вход каждого функционального элемента в схеме подается ровно один выход входа схемы или выход другого функционального элемента;
4) ориентированные дуги, соединяющие функциональные элементы, не могут образовывать циклы.
Примером с.ф.э. может служить схема, приведенная на рис. 4.1.
x1 x2 x3
&
&
Рис. 4.1
Выходами всякой схемы называются такие выходы функциональных элементов в ней, которые не подаются на входы других функциональных элементов. Каждый выход схемы соответствует некоторой функции от переменных, приписанных входам схемы. Значение этой б.ф. на произвольном наборе значений переменных можно определить, если подать на входы схемы значения компонент этого набора и проследить значения поступающие на входах и выходах ф.э., входящих в схему, вплоть до получения значения на выбранном выходе схемы.
Например, нетрудно проверить, что приведенная ранее с.ф.э. вычисляет функцию, представляемую формулой: 
В дальнейшем будем рассматривать только такие с.ф.э., которые имеют ровно один выход.
Поскольку всякая б.ф. может быть представлена с помощью формулы над множеством функций {&, Ú,` }, то с помощью схем, составленных из функциональных элементов, можно вычислять любую б.ф.
Основная задача, относящаяся к с.ф.э., связана с отысканием для произвольной б.ф. f такой схемы S, которая вычисляет f и составлена с помощью минимального количества функциональных элементов.
Сложностью произвольной с.ф.э. S называется число входящих в нее элементов & и Ú. Сложность схемы S обозначается как L(S).
Пусть f(x1, . . . , xn) - некоторая б.ф. Предположим, что f отлична от тождественного нуля. Возьмем СДНФ для f, по которой построим с.ф.э., вычисляющую f, и определим сложность такой схемы.
f(x1, . . . , xn) = 
.
Представим СДНФ для f в виде K1 
. . . Kr, где r - число наборов, на которых f принимает значение 1, а K1, . . . , Kr - все различные конъюнкции ранга n, принимающие значение 1 на таких наборах.
Для каждой конъюнкции Ki= 
построим с.ф.э. Sk, вычисляющую эту конъюнкцию (рис. 4.2):
x1 x2 . . . xn
1 2 n
&
. . .
&
Рис.4.2
В приведенной схеме использовано специальное обозначение s , представляющее фрагмент схемы, имеющий вид:
, если s = 0
Здесь s =
, в противном случае.
То есть такое обозначение соответствует либо отрицанию, либо проводнику в схеме. Нетрудно видеть, что всякое вхождение такого фрагмента в с.ф.э. вычисляет функцию xs.
Схема, реализующая конъюнкцию Sk, имеет сложность, равную n - 1 .
Пусть построены схемы S1, . . ., Sk, вычисляющие все конъюнкции из СДНФ для f. Тогда f реализуется схемой Sf, представленной на рис.4.3:
x1 x2 xn
. . .
. . . . . . . . .
S1 S2. . .Sr
Ú
. . .
Ú
f
Рис 4.3
Определим число функциональных элементов & иÚ, входящих в Sf.
Понятно, что L(Sf) = 
+ r - 1 = (n - 1) r + r - 1.
В общем случае значение r может изменяться в пределах
от 1 до 2n. Если остановиться на “среднем“ случае, когда f принимает значение 1 на половине наборов значений переменных, то r = 2n - 1 .
Полученное значение сложности с.ф.э. оказывается слишком большим для того, чтобы схему для практически важных булевских функций можно было считать реализуемой. Например, уже для n = 16 значение L(Sf) имеет величину, близкую к 16 215 = 219. Последнее значение превосходит 500000.
Поэтому приведенный пример построения с.ф.э., реализующих произвольные б.ф., основанный на представлении функции в виде СДНФ, не применим на практике.
Следовательно, требуется разработка специальных методов построения или синтеза с.ф.э., приводящих к более простым схемам, чем схемы, получаемые по предложенному ранее простому методу синтеза схем.
В определении сложности с.ф.э. не учитывается количество элементов отрицания. Это связано с тем, что практические методы синтеза схем обычно основаны на реализации формул, подобных СДНФ. Поскольку в СДНФ функция отрицания применяется только к отдельным переменным, то для получения значений отрицаний n переменных достаточно включить в схему ровно n элементов, вычисляющих отрицание. Выходы таких элементов могут расщепляться и использоваться в качестве входов для схем вычисления элементарных конъюнкций, входящих в СДНФ.
| <== предыдущая страница | | | следующая страница ==> |
| ТЕОРЕМА 4.2 | | | МИНИМАЛЬНЫЕ ДНФ |
Дата добавления: 2014-11-15; просмотров: 336; Нарушение авторских прав
Мы поможем в написании ваших работ!