Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Конспект лекции по дискретной математике от 08.11.2004 для А5
Метод каскадов позволяет минимизировать трудоемкость синтеза логической схемы за счет снижения размерности синтезируемой функции и за счет использования специального структурного модуля – модуля исключения переменной.
В основе метода лежит теорема Шеннона:
Теорема Шеннона: Любая, отличная от тождественного нуля логическая функция f(x1,…,xn) представима в виде
Функции f(x1,…,xi-1,1,xi+1…,xn) и f(x1,…,xi-1,1,xi+1…,xn) получаются подстановкой в f(x1,…,xn) вместо переменной xi значений 1 и 0, соответственно. Размерность этих функций на 1 меньше исходной. Функции f(x1,…,xi-1,1,xi+1…,xn) и f(x1,…,xi-1,1,xi+1…,xn) называют остаточными функциями при разложении f(x1,…,xn) по переменной xi единичной и нулевой, соответственно. В дальнейшем, эти функции для краткости будут обозначаться как и , соответственно.
В общем виде теорема Шеннона формулируется следующим образом:
Это означает, что при разложении функции по k-переменным получается 2k остаточных функций, каждая из которых зависит от n-k переменных.
Следствие из теоремы Шеннона: Предельное разложение функции по n-переменным является совершенная дизъюнктивная нормальная форма (СовДНФ).
Действительно, разложение Шеннона будет представлено дизъюнкцией конституент, каждая из которых конъюнктивно связана с остаточной функцией-константой. Функция константа принимает имеет значение 1, если соответствующая ей конституента является единичной, и 0 – в противном случае.
Для краткости разложение Шеннона по одной переменной представляется как . Если предположить, что имеется конструктивный блок, реализующий это представление (блок исключения переменной - БИП), его внутренняю структура в классическом базисе должна иметь следующий вид:
Метод каскадов можно представить как процедуру последовательного исключения переменных:
на первом шаге – из исходной функции исключается некоторая переменная, которая подается к левому входу БИПа, а к нижним соответствующим входам БИПа подключаются единичная и нулевая остаточные функции по этой переменной;
далее к каждой остаточной функции применяется указанная в предыдущем шаге последовательность действий.
Указанная процедура применяется до тех пор, пока размерность остаточных функций не будет превышать 2. Такие простые функции целесообразно синтезировать не методом каскадов, а методом непосредственного моделирования в заданном логическом базисе.
Замечания:
Исходная функция для метода каскадов может быть задана в любом виде (ее минимизация или приведение к какому-либо стандартному виду не требуется)
На каждом шаге надо решать вопрос о том, какую переменную следует исключать первой.
Основным структурным элементом в логической схеме по методу каскадов является БИП. Если задан логический базис, то логическая схема БИПа получается с помощью метода непосредственного моделирования элементов классического базиса в заданном базисе.
Константные остаточные функции или остаточные функции, зависящие от одной или двух переменных целесообразно синтезировать методом непосредственного моделирования элементов классического базиса в заданном базисе.
Для решения вопроса, какую переменную следует исключать первой, введем в рассмотрение понятия производной логической функции и веса производной.
По определению, производная функции f(x1,…,xn) по xi -
, т.е. производная по переменной есть сложение по модулю два соответствующих остаточных функций.
Вес производной – P() , по определению, – число конституент в производной. Значение веса производной определяет степень влияния переменной xi на значение функции при изменении значения этой переменной с 0 на 1 либо с 1 на 0. Общая рекомендация состоит в том, что первой следует исключать ту переменную, вес производной для которой – максимален. Эта рекомендация должна выполнятся на каждом шаге применения метода каскадов.
Рассмотрим задаче синтеза структуры логической схемы методом каскадов на следующем примере.
Дано:
f(x1, x2, x3, x4)=
базис Шеффера
Решение:
Определяем, какую переменную следует исключить первой
Значения производной вычислим по таблице
|
x2 |
x3 |
x4 |
F1 |
F0 |
F1ÅF2 |
|
0 |
0 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
0 |
Таким образом вес производной
Значения производной вычислим по таблице
|
x1 |
x3 |
x4 |
F1 |
F0 |
F1ÅF2 |
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
0 |
Таким образом вес производной
Значения производной вычислим по таблице
|
x1 |
x2 |
x4 |
F1 |
F0 |
F1ÅF2 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
1 |
Таким образом вес производной
Значения производной вычислим по таблице
|
x1 |
x2 |
x3 |
F1 |
F0 |
F1ÅF2 |
|
0 |
0 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
0 |
Таким образом вес производной
Как следует из проведенных расчетов производных, первой следует исключать либо переменную x2, либо x3. Для построения схемы принимается «волевое» решение об исключении переменной x2. В результате получаем схему:
Единичная остаточная функция = x3 и не подлежит дальнейшему разложению. Нулевая остаточная функция зависит от трех переменных. Для нее необходимо выделить переменную, которая должна быть исключена первой. Для этого необходимо вычислить веса производных по x1 ,x3 ,x3. Проделав это, можно убедиться, что максимальный вес имеет производная по x1. Исключая ее получаем схему:
Теперь остаточные функции зависят не более чем от двух переменных и для завершения схемы в заданном базис необходимо синтезировать остаточные функции в заданном базисе и показать структуру БИПа в заданном базисе.
Самостоятельно реализуйте в базисе Шеффера две остаточные функции. Логическая схема БИПа в базисе Шеффера приведена ниже:
БИП
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3