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

Содержание

1. МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ методом Л.Ф.Викентьева
2. 6.1 Метод поразрядного сравнения рабочих и запрещенных
3. 6.1 Метод поразрядного сравнения рабочих и запрещенных
4. 6.1 Метод поразрядного сравнения рабочих и запрещенных
5. Минимизация по кубу соседних чиселЧасто такую минимизацию
6. 6.2 Минимизация по кубу соседних чиселдвоичная переключательная
7. 6.2 Минимизация по кубу соседних чисел f(abc)=c
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 набора переменных
16. Метод Л.Ф. Викентьеваf8(х6х5х4х3х2х1)=56[26].Каждое рабочее число соответствует члену
17. Метод Л.Ф. ВикентьеваТаким образом, говорят, что ранг
18. Метод Л.Ф. ВикентьеваПолучаем: 06,16,26,36,46,66,76. Видим, что число
19. Метод Л.Ф. ВикентьеваРезультат анализа запишем следующим образом:
20. Метод Л.Ф. ВикентьеваМинимизируем функцию трех переменных f8 (х6х5х4)= 5[2] по кубу соседних чисел
21. Метод Л.Ф. ВикентьеваПолучаем возможное покрытие (1∨3∨5∨7) и импликанту (--1).Запишем это таким образом:
22. Метод Л.Ф. ВикентьеваЭта запись означает, что функцию,
23. Метод Л.Ф. Викентьеваf8(х6х5х4х3х2х1)=56[26].Теперь нужно аналогичным образом минимизировать
24. Метод Л.Ф. ВикентьеваЗапишем результат следующим образом:Здесь прочерк под цифрой 6 означает отсутствие запрещенных разрядов.где
25. Метод Л.Ф. ВикентьеваТаким образом, доопределили функцию до
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. Метод Л.Ф. ВикентьеваТеперь начнем минимизацию той же функции с младшего разряда:
30. Метод Л.Ф. ВикентьеваПолучили f8(х5х4х3 х2х1)= x5. f8(х5х4х3
31. Скачать презентанцию

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

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

Слайды и текст этой презентации

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

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

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

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

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

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

Здесь

отдельно записаны три рабочих (единичных) набора: 00, 01, 11. Набор

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

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

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

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

6.1 Метод поразрядного сравнения рабочих и запрещенных наборовТаким образом, импликация представлена в виде (0-)∨(-1), то есть x→y

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

например, на кубе соседних чисел, и объединять рабочие вершины в

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

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

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

Квадрат соответствует обобщенному коду – импликанте (--1).
Ребро соответствует обобщенному

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

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

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

использовании куба соседних чисел основан метод поразрядного сравнения рабочих и

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

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

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

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

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

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

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

остальные наборы – условные.

Метод Л.Ф. Викентьева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)=

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

Слайд 17Метод Л.Ф. Викентьева
Таким образом, говорят, что ранг такого представления =6.

f8(х6х5х4х3х2х1)=56[26].
Определим запрещенные числа для старшего разряда числа 56, т.е. для

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

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

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

в совокупности с ним второй разряд (6) приводит к получению

запрещенного набора 26.
f8(х6х5х4х3х2х1)=56[26].

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

Слайд 19Метод Л.Ф. Викентьева
Результат анализа запишем следующим образом:

Цифра 5, стоящая

над чертой указывает заданное значение старшего разряда рабочего числа, а

цифра 2, стоящая под чертой, – запрещенное значение этого разряда.

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

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

кубу соседних чисел

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

таким образом:

Слайд 22Метод Л.Ф. Викентьева

Эта запись означает, что функцию, заданную одним рабочим

числом 56, мы доопределили до четырех рабочих чисел: 16, 36,

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

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

Слайд 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) нет.

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

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

Здесь прочерк под цифрой 6

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

где

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

набор 26, естественно, не вошел в покрытие. Пользуясь кубом соседних

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

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

Слайд 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-)=

Здесь в первом

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

пяти переменных. Говорят, что старшая триада неполная.

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

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

разряда:

Слайд 30Метод Л.Ф. Викентьева
Получили f8(х5х4х3 х2х1)= x5.
f8(х5х4х3 х2х1)=37,22,31[00,16,10].
Очевидно, x5

покрывает все рабочие числа 37, 22, 31.
Видим, что данный вариант

дает самую минимальную форму.

Метод Л.Ф. ВикентьеваПолучили f8(х5х4х3 х2х1)= x5. f8(х5х4х3 х2х1)=37,22,31[00,16,10].Очевидно, x5 покрывает все рабочие числа 37, 22, 31.Видим, что

Скачать презентацию

Разделы презентаций

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

Содержание

Слайды и текст этой презентации

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

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

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

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

отдельно записаны три рабочих (единичных) набора: 00, 01, 11. Набор

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

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

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

например, на кубе соседних чисел, и объединять рабочие вершины в

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

Квадрат соответствует обобщенному коду – импликанте (--1). Ребро соответствует обобщенному

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

использовании куба соседних чисел основан метод поразрядного сравнения рабочих и

Слайд 86.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].Определим запрещенные числа для старшего разряда числа 56, т.е. для

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