|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Каскадный метод минимизации функционального представления ⇐ ПредыдущаяСтр 5 из 5
Основанием для метода является теор. Шиннона, исходя из которой произв. Функция может быть представлена в следующем виде: f(x1, …, xn) = =
Эту функцию можно реализовать следующей схемой:
& xi 1 f & f0 Это устройство – каскадный элемент, который на схемах обозначают в следующем виде:
1
f0 С помощью данного каскада получено представление от n аргументов, через остаточныеные функции f0 и f1 для функций от n-1 аргумент, с помощью искл. хi перемен. На втором шаге каскада реализуется исключаемая следующая переменная. Это – каскадный метод – при этом каждый каскад соответствует исключению некоторой переменной. Для одной и той же функции можно получить несколько реализаций. Число реализаций равно: N ( N - 1)( N – 2) - … = n! Отсюда следует, что найти самую эффективную реализацию простым перебором весьма затруднительно. Поэтому для метода должна быть найдена эффективная стратегия. Это позволяет сделать аппарат производных от булевых функций. Производная от функции n-аргументов.
Пример: Найти производную от функции двух переменных f (x1, x2) = x1 + x2
Повторные производные определяются следующим образом:
Производная от булевой функции определяет условия при которых функция зависит от хi f (x1, …, xi-1, Æ, xi+1, …, xn) ¹ f (x1, …, xi-1, 1, xi+1, …, xn) т.е. при изменении хi меняется значение функции. ( функция зависит от перем.) Если производная равна 0, то функция от хi не зависит, т.е. при изменении хi значение функции не меняется. Пример: Определить при каких условиях функция зависит от переменной х3. f (x1, x2, x3, x4) = x1x2x3 + Найдем соответствующую производную:
= х4 Ответом на поставленную задачу будут значения х1, х2 , х4 при которых
На этих наборах функция зависит от переменной х3. Первый шаг каскадной реализации.
х4 &
f0 f0 ( x1, x3, x4 ) = Весом производной функции называется количество возможных наборов, при которых производная равна 1. Исходя из предыдущего примера сложность производной по х3 ( Чем больше состояний имеет функция, прикоторых она зависит от xi, тем сильнее она зависит от этой переменной. Для примера выясним от какой переменной функция зависит сильнее. f ( x1, x2, x3, x4 ) = x1x2x3 + W (
W (
W (
W ( Оказалось, что сильнее всего функция зависит от переменной х4. При этом видно, что чем сильнее зависимость функции, тем меньше сложность остаточнной функции при ее исключении. Для функции заданной таблично удобно использовать табличный метод определения веса производной. Пример: Функция от четырех переменных задана таблицей истинности
Для заданной функции определить веса производных по х1, х2, х3, х4.
Cтолбцы 1 и 0 заполняются следующим образом. Вместо исключаемой переменной в каждый набор подставляются значения 1 или 0 и выписывают соответствующие стболбцы значений функции из исходной таблицы. Столбец d получается сложением по mod 2 соответствующих значений столбцов 1 и 0. W1 = 5 x2:
W2 = 3 x3:
W3 = 3 x4 :
W4 = 5 Анализ производных показал, что для данного примера первыми исключаемыми переменными будут х1 и х4. Рассмотрим более сложную задачу для которой функция задана аналитически ( от 5-и переменных ). f ( x1, x2, x3, x4, x5 ) = x1 Для данного примера на картах Карно определим веса производных и первую исключаемую переменную.
X1X2 X3X4X5 001 011 010 110 111 101 100
W1 = 7; W2 = 5; W3 = 9; W4 = 5; W5 = 7; Первая искл. переменная х3
ВАРИАНТЫ ЗАДАНИЙ Номер варианта индивидуального задания определяется номером по списку студента в журнале преподавателя!
Таблица 7.1 Варианты определения логической функции I задачи для гр.ИВТб-11д
Таблица 7.2 Варианты определения логической функции I задачи для гр.ИВТб-12д
Таблица 7.3 Варианты определения логической функции I задачи для гр.ИВТб-13д
Таблица 7.4 Варианты задания для определения исключаемой переменной в каскадном методе минимизации функционального представления схемы
Для построения таблицы истинности для II задачи курсовой работы номер варианта (в десятичной системе счисления) преобразовуется в двоичный пятизначный код N=a1a2a3a4a5. Например, вариант номер 7 преобразовуется в N=00111 Булева функция пяти переменных задается таблицей истинности, путем подстановки в таблицу 7.5 значений a1, a2, a3, a4, a5, соответствующих двоичному представлению номера варианта. Таблица 7.5 Таблица истинности исходной функции для II задачи
Таблица 7.6 Варианты задания представления функции и логического базиса
Популярное:
|
Последнее изменение этой страницы: 2016-03-17; Просмотров: 3227; Нарушение авторского права страницы
i f(x1, …, xi-1, Æ, xi+1, …, xn)+f (x1, …, xi-1, 1, xi+1, …, xn ) =
f1
f1 & 
x1 & f
=f (x1, …, xi-1, Æ, xi+1, …, xn)Å f (x1, …, xi-1, 1, xi+1, …, xn)
= x2 Å (1 + x2) = 
= 
( 
) и т. д.
= ( 
х1 & & 1
= ( x4 +x2x3 ) Å (x2x3 + 
= ( 
=(x1x2x3 + x2x3)Å (x1x2x3 + 
