Каскадный метод минимизации функционального представления
Лекции.ИНФО


Каскадный метод минимизации функционального представления



Основанием для метода является теор. Шиннона, исходя из которой произв. Функция может быть представлена в следующем виде :

f(x1, … , xn) = i f(x1, …, xi-1,Æ,xi+1, …, xn)+f (x1, …,xi-1,1,xi+1,…, xn ) =

= i f ( Æ ) + xi f( 1 )

 

Эту функцию можно реализовать следующей схемой :

f1

&

xi

1 f

&

f0

Это устройство – каскадный элемент, который на схемах обозначают в следующем виде:

f1 &

1

x1 & f

f0

С помощью данного каскада получено представление от n аргументов, через остаточныеные функции f0 и f1 для функций от n-1 аргумент, с помощью искл. хi перемен. На втором шаге каскада реализуется исключаемая следующая переменная. Это – каскадный метод – при этом каждый каскад соответствует исключению некоторой переменной. Для одной и той же функции можно получить несколько реализаций. Число реализаций равно :

N ( N - 1)( N – 2) - … = n!

Отсюда следует, что найти самую эффективную реализацию простым перебором весьма затруднительно.

Поэтому для метода должна быть найдена эффективная стратегия. Это позволяет сделать аппарат производных от булевых функций.

Производная от функции n-аргументов.

=f (x1,…, xi-1,Æ,xi+1,…, xn)Åf (x1, …, xi-1,1,xi+1, …, xn)

Пример : Найти производную от функции двух переменных

f (x1,x2) = x1 + x2

= x2 Å (1 + x2) = 2

Повторные производные определяются следующим образом :

= ( ) и т. д.

Производная от булевой функции определяет условия при которых функция зависит от х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 + 1х4 + x2x3 + x1 3x4

Найдем соответствующую производную :

= ( 1х4 1х4) Å (х1х2 + 1х42) = х4 Å ( х2+ 1х4) =

= х4 2 1х4 + 4 ( х2+ 1х4 ) = х4 21+ 4) + 4х2 = 4х2 + х4 2х1

Ответом на поставленную задачу будут значения х1, х2 , х4 при которых

= 1. Составим соответствующую таблицу:

х1 х2 х4

 

х1 х2 х4

 

На этих наборах функция зависит от переменной х3.

Первый шаг каскадной реализации.

х1 & & 1

х4

&

 

f0

f0 ( x1,x3,x4 ) = 1 + 3 4 + x3x4 = 1 +

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

Чем больше состояний имеет функция, прикоторых она зависит от xi, тем сильнее она зависит от этой переменной.

Для примера выясним от какой переменной функция зависит сильнее.

f ( x1, x2, x3,x4 ) = x1x2x3 + 1x4 + x2x3 + x1 3x4

W ( ) = 3

= ( x4 +x2x3 ) Å (x2x3 + 3x4 )

х1 х2 х4

W ( ) = 1

= ( 1x4 + x1 3x4 ) Å (x1x3 + 1x4 + x3 + x1 3x4)=(x4 1 + x4 3) Å (x3 + x4)

х1 х2 х4

W ( ) = 3

=(x1x2x3 + x2x3)Å(x1x2x3 + 1 + x2x3 + x1 3) = x2x3Å(x2 + 1 + 3 )

х1 х2 х4

W ( ) = 5

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

Для функции заданной таблично удобно использовать табличный метод определения веса производной.

Пример: Функция от четырех переменных задана таблицей истинности

х1 х2 x3 x4 f

 

Для заданной функции определить веса производных по х1, х2, х3, х4.

x2 x3 x4 d

 

Cтолбцы 1 и 0 заполняются следующим образом. Вместо исключаемой переменной в каждый набор подставляются значения 1 или 0 и выписывают соответствующие стболбцы значений функции из исходной таблицы. Столбец d получается сложением по mod 2 соответствующих значений столбцов 1 и 0.

W1 = 5

x2 :

x1 x3 x4 d

W2 = 3

x3 :

x1 x2 x4 d

W3 = 3

x4 :

x1 x2 x3 d

W4 = 5

Анализ производных показал, что для данного примера первыми исключаемыми переменными будут х1 и х4.

Рассмотрим более сложную задачу для которой функция задана аналитически ( от 5 переменных ).

f ( x1, x2, x3, x4, x5 ) = x1 2x3 + 1 3x4 + x1x3 5 + x1x2x4 + 2x3x5 + 3 4x5

Для данного примера на картах Карно определим веса производных и первую исключаемую переменную.

X1X2 X3X4X5 001 011 010 110 111 101 100

     
         
   
     

 

W1 = 7 ; W2 = 5 ; W3 = 9 ; W4 = 5 ; W5 = 7 ;

Первая искл. переменная х3

 


ВАРИАНТЫ ЗАДАНИЙ

Номер варианта индивидуального задания определяется номером по списку студента в журнале преподавателя!

 

Таблица 7.1

Варианты определения логической функции I задачи для гр.ИВТб-11д

 

№ в-та Функция № в-та Функция
1. 16.
2. 17.
3. 18.
4. 19.
5. 20.
6. 21.
7. 22.
8. 23.
9. 24.
10. 25.
11. 26.
12. 27.
13. 28.
14. 29.
15. 30.

 


 

Таблица 7.2

Варианты определения логической функции I задачи для гр.ИВТб-12д

 

№ в-та Функция № в-та Функция
1. 16.
2. 17.
3. 18.
4. 19.
5. 20.
6. 21.
7. 22.
8. 23.
9. 24.
10. 25.
11. 26.
12. 27.
13. 28.
14. 29.
15. 30.

 


 

Таблица 7.3

Варианты определения логической функции I задачи для гр.ИВТб-13д

 

№ в-та Функция № в-та Функция
1. 16.
2. 17.
3. 18.
4. 19.
5. 20.
6. 21.
7. 22.
8. 23.
9. 24.
10. 25.
11. 26.
12. 27.
13. 28.
14. 29.
15. 30.

 


 

Таблица 7.4

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

№ в-та Метод исключения переменных № в-та Метод исключения переменных
1. визуальный метод опреледеления веса производной 16. визуальный метод опреледеления веса производной
2. табличный метод опреледеления веса производной 17. табличный метод опреледеления веса производной
3. метод опреледеления веса производной на картах Карно 18. метод опреледеления веса производной на картах Карно
4. визуальный метод опреледеления веса производной 19. визуальный метод опреледеления веса производной
5. табличный метод опреледеления веса производной 20. табличный метод опреледеления веса производной
6. метод опреледеления веса производной на картах Карно 21. метод опреледеления веса производной на картах Карно
7. визуальный метод опреледеления веса производной 22. визуальный метод опреледеления веса производной
8. табличный метод опреледеления веса производной 23. табличный метод опреледеления веса производной
9. метод опреледеления веса производной на картах Карно 24. метод опреледеления веса производной на картах Карно
10. визуальный метод опреледеления веса производной 25. визуальный метод опреледеления веса производной
11. табличный метод опреледеления веса производной 26. табличный метод опреледеления веса производной
12. метод опреледеления веса производной на картах Карно 27. метод опреледеления веса производной на картах Карно
13. визуальный метод опреледеления веса производной 28. визуальный метод опреледеления веса производной
14. табличный метод опреледеления веса производной 29. табличный метод опреледеления веса производной
15. метод опреледеления веса производной на картах Карно 30. метод опреледеления веса производной на картах Карно

 

Для построения таблицы истинности для II задачи курсовой работы номер варианта (в десятичной системе счисления) преобразовуется в двоичный пятизначный код N=a1a2a3a4a5.

Например, вариант номер 7 преобразовуется в N=00111
(a1=0, a2=0, a3=1, a4=1, a5=1).

Булева функция пяти переменных задается таблицей истинности, путем подстановки в таблицу 7.5 значений a1, a2, a3, a4, a5, соответствующих двоичному представлению номера варианта.

Таблица 7.5

Таблица истинности исходной функции для II задачи

 

x1 x2 x3 x4 x5
a1
a1
a2
a2
a3
a4
a5
a3
a4
a5
a3
a2
a1
a2
a4

Таблица 7.6

Варианты задания представления функции и логического базиса
для II задачи

 

№ в-та Тип пред-ния исх. функции Тип пред-ния min функции Заданный базис № в-та Тип пред-ния исх. функции Тип пред-ния min функции Заданный базис
1. СДНФ ДНФ И-НЕ 16. СКНФ КНФ И-НЕ
2. СКНФ КНФ ИЛИ-НЕ 17. СДНФ ДНФ И-НЕ
3. СДНФ ДНФ ИЛИ-НЕ 18. СКНФ КНФ ИЛИ-НЕ
4. СКНФ КНФ И-НЕ 19. СДНФ ДНФ ИЛИ-НЕ
5. СДНФ ДНФ И-НЕ 20. СКНФ КНФ И-НЕ
6. СКНФ КНФ ИЛИ-НЕ 21. СДНФ ДНФ И-НЕ
7. СДНФ ДНФ ИЛИ-НЕ 22. СКНФ КНФ ИЛИ-НЕ
8. СКНФ КНФ И-НЕ 23. СДНФ ДНФ ИЛИ-НЕ
9. СДНФ ДНФ И-НЕ 24. СКНФ КНФ И-НЕ
10. СКНФ КНФ ИЛИ-НЕ 25. СДНФ ДНФ И-НЕ
11. СДНФ ДНФ ИЛИ-НЕ 26. СКНФ КНФ ИЛИ-НЕ
12. СКНФ КНФ И-НЕ 27. СДНФ ДНФ ИЛИ-НЕ
13. СДНФ ДНФ И-НЕ 28. СКНФ КНФ И-НЕ
14. СКНФ КНФ ИЛИ-НЕ 29. СДНФ ДНФ И-НЕ
15. СДНФ ДНФ ИЛИ-НЕ 30. СКНФ КНФ ИЛИ-НЕ

 









Читайте также:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 288;


lektsia.info 2017 год. Все права принадлежат их авторам! Главная