МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ методом Л.Ф.Викентьева

Сентябрь 3, 2022

Главная
Алгебра
МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ методом Л.Ф.Викентьева

Содержание

2. 6.1 Метод поразрядного сравнения рабочих и запрещенных наборов Несложные функции удобно минимизировать путем сравнения рабочих и
3. 6.1 Метод поразрядного сравнения рабочих и запрещенных наборов Таблица импликации Здесь отдельно записаны три рабочих (единичных)
4. 6.1 Метод поразрядного сравнения рабочих и запрещенных наборов Таким образом, импликация представлена в виде (0-)∨(-1), то
5. Минимизация по кубу соседних чисел Часто такую минимизацию удобно выполнять графически, например, на кубе соседних чисел,
6. 6.2 Минимизация по кубу соседних чисел двоичная переключательная функция (ПФ) №17410 Квадрат соответствует обобщенному коду –
7. 6.2 Минимизация по кубу соседних чисел f(abc)=c ∨a b. На использовании куба соседних чисел основан метод
8. 6.3 Минимизация переключательных функций на основе поразрядного сравнения рабочих и запрещенных восьмеричных наборов. (Метод Л.Ф. Викентьева
9. Метод Л.Ф. Викентьева В свою очередь, для упрощения эти отдельные функции минимизируются по кубу соседних чисел,
10. Метод Л.Ф. Викентьева Тогда для каждого разряда восьмеричного рабочего числа функции определяются запрещенные цифры, то есть
11. Метод Л.Ф. Викентьева Затем, используя куб соседних чисел, следует минимизировать функцию трех переменных (определить покрытие данного
12. Метод Л.Ф. Викентьева По полученным обобщенным кодам для каждого восьмеричного разряда определяется ДНФ для всего рабочего
13. Метод Л.Ф. Викентьева Числа, покрытые полученной импликантой, удаляют. Оставшиеся числа вновь подвергают минимизации – пока не
14. Метод Л.Ф. Викентьева ПРИМЕР. Задана функция в восьмеричной системе счисления: f8(х6х5х4х3х2х1)=56[26].
15. Метод Л.Ф. Викентьева f8(х6х5х4х3х2х1)=56[26]. Всего существует 64 набора переменных для функции 6 переменных. Как видно, используется
16. Метод Л.Ф. Викентьева f8(х6х5х4х3х2х1)=56[26]. Каждое рабочее число соответствует члену СДНФ. Восьмеричная система позволяет очень легко переходить
17. Метод Л.Ф. Викентьева Таким образом, говорят, что ранг такого представления =6. f8(х6х5х4х3х2х1)=56[26]. Определим запрещенные числа для
18. Метод Л.Ф. Викентьева Получаем: 06,16,26,36,46,66,76. Видим, что число 2 – запрещенное, в совокупности с ним второй
19. Метод Л.Ф. Викентьева Результат анализа запишем следующим образом: Цифра 5, стоящая над чертой указывает заданное значение
20. Метод Л.Ф. Викентьева Минимизируем функцию трех переменных f8 (х6х5х4)= 5[2] по кубу соседних чисел
21. Метод Л.Ф. Викентьева Получаем возможное покрытие (1∨3∨5∨7) и импликанту (--1). Запишем это таким образом:
22. Метод Л.Ф. Викентьева Эта запись означает, что функцию, заданную одним рабочим числом 56, мы доопределили до
23. Метод Л.Ф. Викентьева f8(х6х5х4х3х2х1)=56[26]. Теперь нужно аналогичным образом минимизировать младший разряд рабочего числа. Определим возможные наборы,
24. Метод Л.Ф. Викентьева Запишем результат следующим образом: Здесь прочерк под цифрой 6 означает отсутствие запрещенных разрядов.
25. Метод Л.Ф. Викентьева Таким образом, доопределили функцию до 32 наборов, но набор 26, естественно, не вошел
26. Метод Л.Ф. Викентьева Получено одно из возможных решений, представляющее собой простую импликанту переключательной функции, покрывающую рассмотренное
27. Метод Л.Ф. Викентьева ПРИМЕР 2. f8(х5х4х3 х2х1)=37,22,31[00,16,10].
28. Метод Л.Ф. Викентьева ПРИМЕР 2. f8(х5х4х3 х2х1)=37,22,31[00,16,10]. Итак, f8(х5х4х3х2х1)=(--)(--1)∨(--)(01-)= Здесь в первом разряде обобщенных кодов два
29. Метод Л.Ф. Викентьева Теперь начнем минимизацию той же функции с младшего разряда:
31. Скачать презентацию

Слайд 2

6.1 Метод поразрядного сравнения рабочих и запрещенных наборов
Несложные функции удобно

минимизировать путем сравнения рабочих и запрещенных наборов. Задача заключается в том, чтобы в каждом рабочем наборе оставить минимальное количество переменных, позволяющих отличить этот набор от всех запрещенных наборов.
Покажем это на примере минимизации функции «импликация х в y»:

Слайд 3

6.1 Метод поразрядного сравнения рабочих и запрещенных наборов
Таблица импликации
Здесь отдельно

записаны три рабочих (единичных) набора: 00, 01, 11. Набор 10 запрещенный (нулевой). Видно, что в наборе 00 достаточно оставить переменную x, поскольку значение этой переменной в одном – единственном запрещенном наборе равно 1. Таким образом, получили импликанту (0-). Эта же импликанта покрывает и набор 01. Тогда для набора 11 необходимо оставить переменную y, то есть, получили импликанту (-1).

Слайд 4

6.1 Метод поразрядного сравнения рабочих и запрещенных наборов
Таким образом, импликация представлена

в виде (0-)∨(-1), то есть x→y =x∨y.

Слайд 5

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

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

Слайд 6

6.2 Минимизация по кубу соседних чисел
двоичная переключательная функция (ПФ) №17410
Квадрат

соответствует обобщенному коду – импликанте (--1).
Ребро соответствует обобщенному коду – импликанте (01–)
Таким образом, ДНФ ПФ имеет вид

Слайд 7

6.2 Минимизация по кубу соседних чисел
f(abc)=c ∨a b.
На использовании

куба соседних чисел основан метод поразрядного сравнения рабочих и запрещенных восьмеричных наборов – метод Л.Ф. Викентьева

Слайд 8

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

восьмеричных наборов.

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

Слайд 9

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

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

Слайд 10

Метод Л.Ф. Викентьева
Тогда для каждого разряда восьмеричного рабочего числа функции определяются

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

Слайд 11

Метод Л.Ф. Викентьева
Затем, используя куб соседних чисел, следует минимизировать функцию трех

переменных (определить покрытие данного разряда). Так минимизируются все разряды.

Слайд 12

Метод Л.Ф. Викентьева
По полученным обобщенным кодам для каждого восьмеричного разряда определяется

ДНФ для всего рабочего числа. По полученному покрытию определяют, какие рабочие числа покрывает дополнительно полученная импликанта (кроме данного числа).

Слайд 13

Метод Л.Ф. Викентьева
Числа, покрытые полученной импликантой, удаляют.
Оставшиеся числа вновь подвергают

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

Слайд 14

Метод Л.Ф. Викентьева
ПРИМЕР.
Задана функция в восьмеричной системе счисления:
f8(х6х5х4х3х2х1)=56[26].

Слайд 15

Метод Л.Ф. Викентьева
f8(х6х5х4х3х2х1)=56[26].
Всего существует 64 набора переменных для функции 6 переменных.

Как видно, используется только один рабочий и один запрещенный, остальные наборы – условные.

Слайд 16

Метод Л.Ф. Викентьева
f8(х6х5х4х3х2х1)=56[26].
Каждое рабочее число соответствует члену СДНФ. Восьмеричная система позволяет

очень легко переходить к СДНФ. Каждый разряд восьмеричного числа – это 3 разряда двоичного числа. В данном примере 6 переменных:
f8(х6х5х4х3х2х1)=(101110)=

Слайд 17

Метод Л.Ф. Викентьева
Таким образом, говорят, что ранг такого представления =6.
f8(х6х5х4х3х2х1)=56[26].
Определим

запрещенные числа для старшего разряда числа 56, т.е. для 5. Будем подставлять вместо первого разряда возможные числа, а их всего 7 – система-то восьмеричная!

Слайд 18

Метод Л.Ф. Викентьева
Получаем: 06,16,26,36,46,66,76. Видим, что число 2 – запрещенное, в

совокупности с ним второй разряд (6) приводит к получению запрещенного набора 26.
f8(х6х5х4х3х2х1)=56[26].

Слайд 19

Метод Л.Ф. Викентьева
Результат анализа запишем следующим образом:
Цифра 5, стоящая над

чертой указывает заданное значение старшего разряда рабочего числа, а цифра 2, стоящая под чертой, – запрещенное значение этого разряда.

Слайд 20

Метод Л.Ф. Викентьева
Минимизируем функцию трех переменных f8 (х6х5х4)= 5[2] по кубу

соседних чисел

Слайд 21

Метод Л.Ф. Викентьева
Получаем возможное покрытие (1∨3∨5∨7) и импликанту (--1).
Запишем это таким

образом:

Слайд 22

Метод Л.Ф. Викентьева
Эта запись означает, что функцию, заданную одним рабочим числом

56, мы доопределили до четырех рабочих чисел: 16, 36, 56, 76. Число 56 – рабочее – вошло в покрытие, а вот запрещенное – 26 – нет.

Слайд 23

Метод Л.Ф. Викентьева
f8(х6х5х4х3х2х1)=56[26].
Теперь нужно аналогичным образом минимизировать младший разряд рабочего числа.

Определим возможные наборы, которые могут получиться путем соединения покрытия (1∨3∨5∨7) и второго разряда, который может принимать значения 0,…,7: 10,…,17,30,…,37,50,…,57,70,…,77. Очевидно, что ни в одном случае мы не получим запрещенного набора 26, а значит, запрещенных чисел для второго разряда 6 рабочего числа 56 нет, поскольку запрещенный набор начинается на число 2, а двойки в покрытии (1∨3∨5∨7) нет.

Слайд 24

Метод Л.Ф. Викентьева
Запишем результат следующим образом:
Здесь прочерк под цифрой 6 означает

отсутствие запрещенных разрядов.
где

Слайд 25

Метод Л.Ф. Викентьева
Таким образом, доопределили функцию до 32 наборов, но набор

26, естественно, не вошел в покрытие. Пользуясь кубом соседних чисел, минимизируем второй разряд: f8(х3х2х1)=6.
Здесь нет запрещенных чисел, поэтому получаем импликанту (---), которая соответствует объединению всех вершин куба (полный куб): f8(х3х2х1)=(---).
Тогда f8(х6х5х4х3 х2х1)=(--1)(---)=х1

Слайд 26

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

переключательной функции, покрывающую рассмотренное восьмеричное рабочее число.
Минимизация методом поразрядного сравнения не однозначна, возможны различные варианты решений. Можно было при минимизации первого разряда взять другие квадраты (4∨5∨6∨7), (0∨1∨4∨5), тогда ответ был бы другим, но все равно ранг его был бы равен 1.

Слайд 27

Метод Л.Ф. Викентьева
ПРИМЕР 2.
f8(х5х4х3 х2х1)=37,22,31[00,16,10].

Слайд 28

Метод Л.Ф. Викентьева
ПРИМЕР 2.
f8(х5х4х3 х2х1)=37,22,31[00,16,10].
Итак, f8(х5х4х3х2х1)=(--)(--1)∨(--)(01-)=
Здесь в первом разряде

обобщенных кодов два (символов «тире»), т.к. функция зависит от пяти переменных. Говорят, что старшая триада неполная.

Слайд 29

МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ методом Л.Ф.Викентьева

Содержание

6.1 Метод поразрядного сравнения рабочих и запрещенных наборов Несложные функции удобно

6.1 Метод поразрядного сравнения рабочих и запрещенных наборовТаблица импликации Здесь отдельно

6.1 Метод поразрядного сравнения рабочих и запрещенных наборовТаким образом, импликация представлена

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

6.2 Минимизация по кубу соседних чиселдвоичная переключательная функция (ПФ) №17410 Квадрат

6.2 Минимизация по кубу соседних чисел f(abc)=c ∨a b. На использовании

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

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

Метод Л.Ф. ВикентьеваТогда для каждого разряда восьмеричного рабочего числа функции определяются

Метод Л.Ф. ВикентьеваЗатем, используя куб соседних чисел, следует минимизировать функцию трех

Метод Л.Ф. ВикентьеваПо полученным обобщенным кодам для каждого восьмеричного разряда определяется

Метод Л.Ф. ВикентьеваЧисла, покрытые полученной импликантой, удаляют. Оставшиеся числа вновь подвергают

Метод Л.Ф. ВикентьеваПРИМЕР.Задана функция в восьмеричной системе счисления:f8(х6х5х4х3х2х1)=56[26].

Метод Л.Ф. Викентьеваf8(х6х5х4х3х2х1)=56[26].Всего существует 64 набора переменных для функции 6 переменных.

Метод Л.Ф. Викентьеваf8(х6х5х4х3х2х1)=56[26].Каждое рабочее число соответствует члену СДНФ. Восьмеричная система позволяет

Метод Л.Ф. ВикентьеваТаким образом, говорят, что ранг такого представления =6. f8(х6х5х4х3х2х1)=56[26].Определим

Метод Л.Ф. ВикентьеваПолучаем: 06,16,26,36,46,66,76. Видим, что число 2 – запрещенное, в

Метод Л.Ф. ВикентьеваРезультат анализа запишем следующим образом: Цифра 5, стоящая над

Метод Л.Ф. ВикентьеваМинимизируем функцию трех переменных f8 (х6х5х4)= 5[2] по кубу

Метод Л.Ф. ВикентьеваПолучаем возможное покрытие (1∨3∨5∨7) и импликанту (--1).Запишем это таким

Метод Л.Ф. ВикентьеваЭта запись означает, что функцию, заданную одним рабочим числом

Метод Л.Ф. Викентьеваf8(х6х5х4х3х2х1)=56[26].Теперь нужно аналогичным образом минимизировать младший разряд рабочего числа.

Метод Л.Ф. ВикентьеваЗапишем результат следующим образом:Здесь прочерк под цифрой 6 означает

Метод Л.Ф. ВикентьеваТаким образом, доопределили функцию до 32 наборов, но набор

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

Метод Л.Ф. ВикентьеваПРИМЕР 2. f8(х5х4х3 х2х1)=37,22,31[00,16,10].

Метод Л.Ф. ВикентьеваПРИМЕР 2. f8(х5х4х3 х2х1)=37,22,31[00,16,10].Итак, f8(х5х4х3х2х1)=(--)(--1)∨(--)(01-)= Здесь в первом разряде

Метод Л.Ф. ВикентьеваТеперь начнем минимизацию той же функции с младшего разряда:

Похожие презентации