Синтез комбинационных схем

Июль 23, 2022

Главная
Информатика
Синтез комбинационных схем

Содержание

2. Задание. Построить комбинационные схемы в различных базисах, реализующие не полностью определенную булеву функцию f(Х) = f
4. Представление булевой функции в аналитическом виде
5. Минимизация булевой функции методом Квайна –Мак-Класки Нахождение простых импликант (максимальных кубов).
7. Составление импликантной таблицы. Импликантная таблица содержит 11 строк (по числу простых импликант) и 15 столбцов (по
8. Импликанта 4, не покрывающая ни одной вершины, вычеркивается из таблицы.
9. Определение существенных импликант. Импликанты 8 и 10 – существенные, так как они покрывают вершины 1 и
10. Определение минимального покрытия Метод Петрика. Выпишем булево выражение Y, определяющее условие покрытия всех 0-кубов (существенных вершин),
11. Применим закон поглощения к дизъюнктивным термам, в результате чего в выражении остаются только двухбуквенные термы Y=(B∨C)(B∨G)(G∨H)(C∨D)(D∨E)(E∨H)(A∨B)(A∨F)(E∨F)
12. Возможны следующие варианты покрытия:
14. Дальнейшее упрощение импликантной таблицы. К упрощенной импликантной таблице применим операцию удаления “лишних” столбцов (существенных вершин). В
15. Дальнейшие упрощения таблицы невозможны. Для определения минимального покрытия можно использовать метод Петрика. Исходное булево выражение Y,
16. Минимизация булевой функции на картах Карно. Определение МДНФ
17. Определение МКНФ ,,,
18. Преобразование минимальных форм булевой функции Факторное преобразование для МДНФ: (SQ=23) (SQ=20) (SQ=18) Решим задачу декомпозиции применительно
19. Реализация комбинационной схемы по этому выражению с учетом затрат на вспомогательную функцию ϕ и ее инверсию
20. Следует отметить, что вынесение x4 из первых двух термов МКНФ не дает уменьшения цены схемы: ΔSQ
21. Синтез комбинационных схем в булевом базисе Комбинационные схемы, реализующие заданную функцию по последней форме, в булевом
22. Задержка схемы с парафазными входами Т=4τ, цена схемы SQ=17. Для схемы с однофазными входами Т=5τ, цена
23. Синтез комбинационных схем в универсальных базисах Базис ИЛИ-НЕ а) Приведение последнего выражения к базису ИЛИ-НЕ осуществляется
24. Задержка схемы Т=4τ, цена схемы SQ=18. По сравнению с ценой схемы SQ, построенной в булевом базисе,
25. б) Преобразование схемы из булева базиса в универсальный. Заменим элементы булева базиса в соответствии с логическими
26. Исключим из схемы лишние инверторы. К ним относятся: входной инвертор для инверсии переменной x2 (логический эквивалент
27. Кроме того, пары последовательных инверторов составляют выходной инвертор логического эквивалента элемента 1, на котором реализуется вспомогательная
28. После удаления замыкающих инверторов обеих пар, на выходах которых реализуется инверсия ϕ, входы логических эквивалентов элементов
29. булева базиса на операцию штрих Шеффера (отрицание конъюнкции) путем использования законов двойственности. Цена схемы в базисе
30. Для построения схемы с меньшей ценой целесообразно использовать форму, полученную по МДНФ с ценой SQ=18 для
31. Задержка схемы Т=4τ, цена схемы SQ=18 совпадает с ценой для булева базиса. б) Преобразование схемы из
32. Синтез комбинационной схемы с учетом коэффициента объединения При построении схемы в универсальном базисе с учетом ограничения
33. Если в выражении для функции имеются трехмест-ные операции, то при I=2 для уменьшения задерж-ки синтезируемой схемы
34. Кроме того, при объединении скобок как элементов трехместной операции конъюнкции уединим среднюю скобку, как более сложный
35. Инверсии реализуются в схеме, построенной по этому выражению, на элементах ИЛИ-НЕ с запараллеленными входами.
36. Задержка схемы Т=6τ, цена схемы SQ=30. По сравнению со схемой в базисе ИЛИ-НЕ, построенной без ограничений
37. Замечание. Использование в качестве исходного выражения с последующей дополнительной факторизацией путем вынесения за скобки x4 из
38. Анализ комбинационных схем По таблице истинности булевой функции выберем наборы аргументов (входных переменных), на кото-рых функция
39. Синтез многовыходных комбинационных схем ПРИМЕР 2. Синтезировать комбинационную схему, выполняющую операцию сложения двух двухразрядных двоичных чисел:
40. 1. Составление таблицы истинности Таблица истинности системы булевых функций строится с учетом правил двоичного сложения и
51. Скачать презентацию

Слайд 2

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

булеву функцию
f(Х) = f (x1, x2, x3, x4, x5 ),
которая принимает значение 1 при условии:
2 ≤ ⎥ X4X5X1 - X2X3⎥ ≤ 5
и неопределенное значение на наборах, для которых X4 X5 = 0.

Слайд 3

Слайд 4

Представление булевой функции в аналитическом виде

Слайд 5

Минимизация булевой функции
методом Квайна –Мак-Класки
Нахождение простых импликант
(максимальных кубов).

Слайд 6

Слайд 7

Составление импликантной таблицы.
Импликантная таблица содержит 11 строк (по числу простых импликант)

и 15 столбцов (по числу существенных вершин).

Слайд 8

Импликанта 4, не покрывающая ни одной вершины, вычеркивается из таблицы.

Слайд 9

Определение существенных импликант.
Импликанты 8 и 10 – существенные, так как они

покрывают вершины 1 и 10 соответственно, не покрытые другими импликантами. Вычеркнем из таблицы строки, соответствующие этим импликантам, а также столбцы, соответствующие вершинам, покрываемым существенными импликантами.
Множество существенных импликант образует ядро покрытия как его обязательную часть:
Получаем упрощенную импликантную таблицу.

Слайд 10

Определение минимального покрытия
Метод Петрика. Выпишем булево выражение Y, определяющее условие покрытия

всех 0-кубов (существенных вершин), не покрываемых существенными импликантами, в соответствии с таблицей
Y=(B∨C)(B∨G)(G∨H)(C∨D)(D∨E)(E∨H)(A∨B∨C)(A∨B)
(A∨C∨D∨F)(D∨E∨F)(A∨F)(E∨F).

Слайд 11

Применим закон поглощения к дизъюнктивным термам, в результате чего в выражении

остаются только двухбуквенные термы
Y=(B∨C)(B∨G)(G∨H)(C∨D)(D∨E)(E∨H)(A∨B)(A∨F)(E∨F)
Выполняя операции попарного логического умножения применительно к термам, содержа-щим одинаковые буквы, с последующим примене-нием закона поглощения, приведем исходную конъюнктивную форму Y к дизъюнктивной
Y=ABDEG∨ACEG∨ABCEH∨ABDEH∨ACDFGH∨
∨BDEFG∨BCEFG∨BCEFH∨BDFH.

Слайд 12

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

Слайд 13

Слайд 14

Дальнейшее упрощение импликантной таблицы. К упрощенной импликантной таблице применим операцию удаления

“лишних” столбцов (существенных вершин).
В отношении “множество-подмножество“ находятся отметки следующих пар столбцов: g и a, g и h, k и d, k и m , l и e, l и n. Таким образом из таблицы можно удалить столбцы g, k и l, после чего получим новую таблицу.

Слайд 15

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

Петрика.
Исходное булево выражение Y, определяющее условие покрытия существенных вершин будет таким же.

Слайд 16

Минимизация булевой функции на картах Карно. Определение МДНФ

Слайд 17

Определение МКНФ
,,,

Слайд 18

Преобразование минимальных форм булевой функции
Факторное преобразование для МДНФ:
(SQ=23)
(SQ=20)
(SQ=18)
Решим

задачу декомпозиции применительно к полученной форме. Для этого введем вспомога-тельную функцию
Инверсия этой функции имеет вид
С учетом новой функции последнее выражение преобразуется к виду:

Слайд 19

Реализация комбинационной схемы по этому выражению с учетом затрат на вспомогательную

функцию ϕ и ее инверсию дает цену схемы SQ=18, такую же, как и для построенной схемы, но задержка схемы будет больше.
Факторное преобразование для МКНФ:
(SQ=22)
(SQ=19)

Слайд 20

Следует отметить, что вынесение x4 из первых двух термов МКНФ не

дает уменьшения цены схемы: ΔSQ = 0 (m=1, k=2, p=1, Δ=2), однако является целесообразным для дальнейшей декомпозиции за счет введения вспомогательной функции ϕ, такой же как и в предыдущем случае. Выражение после декомпозиции примет вид:
для которого цена схемы дает абсолютный минимум при условии, что синтезируемая схема строится на элементах булева базиса с парафазными входами.

Слайд 21

Синтез комбинационных схем в булевом базисе
Комбинационные схемы, реализующие заданную функцию по

последней форме, в булевом базисе с парафазными входами и с однофазными входами

Слайд 22

Задержка схемы с парафазными входами Т=4τ, цена схемы SQ=17. Для схемы

с однофазными входами Т=5τ, цена схемы SQ=21.

Слайд 23

Синтез комбинационных схем в универсальных базисах
Базис ИЛИ-НЕ
а) Приведение последнего выражения к

базису ИЛИ-НЕ осуществляется заменой операций булева базиса на операцию стрелка Пирса путем использования законов двойственности.

По полученному выражению строим схему с парафазными входами в базисе ИЛИ-НЕ

Слайд 24

Задержка схемы Т=4τ, цена схемы SQ=18. По сравнению с ценой схемы

SQ, построенной в булевом базисе, цена схемы увеличилась за счет того, что в качестве инвертора используется двухвходовой элемент ИЛИ-НЕ.

Слайд 25

б) Преобразование схемы из булева базиса в универсальный.
Заменим элементы булева базиса

в соответствии с логическими эквивалентами из таблицы. В результате получим следующую схему. Пунктирной линией на ней выделены логические эквиваленты элементов булева базиса.

Слайд 26

Исключим из схемы лишние инверторы. К ним относятся:
входной инвертор для инверсии

переменной x2 (логический эквивалент элемента 4);
пары последовательных инверторов на связях с выходов логических эквивалентов элементов 3, 5 и 6 на входы логического эквивалента элемента 7.

Слайд 27

Кроме того, пары последовательных инверторов составляют выходной инвертор логического эквивалента элемента

1, на котором реализуется вспомогательная функция ϕ, и входной инвертор логического эквивалента элемента 4, а также логический эквивалент элемента 2. Однако из двух последовательных инверторов обеих пар исключается только один, замыкающий пару, на котором реализуется инверсия вспомогательной функции ϕ. Лидирующий инвертор пары сохраняется для подачи значения ϕ на вход логического эквивалента элемента 3.

Слайд 28

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

ϕ, входы логических эквивалентов элементов 4 и 5, связанные с выходом удаляемых инверторов, переключаются к выходу первого элемента логи-ческого эквивалента 1, на котором формируется требуемое значение инверсии ϕ. После исклю-чения лишних инверторов получим окончательную схему в базисе ИЛИ-НЕ, аналогичную приведенной выше.
Базис И-НЕ
а) Приведение аналитического выражения к базису И-НЕ осуществляется заменой операций

Слайд 29

булева базиса на операцию штрих Шеффера (отрицание конъюнкции) путем использования законов

двойственности.
Цена схемы в базисе И-НЕ: SQ=20. Увеличение цены схемы на три по сравнению со схемой в булевом базисе связано, во-первых, с реализацией инверсии вспомогательной функции ϕ и, во-вторых, с использованием выходного инвертора.

Слайд 30

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

МДНФ с ценой SQ=18 для булева базиса.

Слайд 31

Задержка схемы Т=4τ, цена схемы SQ=18 совпадает с ценой для булева

базиса.
б) Преобразование схемы из булевого базиса в базис И-НЕ осуществляется так же как и для базиса ИЛИ-НЕ.

Слайд 32

Синтез комбинационной схемы с учетом коэффициента объединения
При построении схемы в универсальном

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

Слайд 33

Если в выражении для функции имеются трехмест-ные операции, то при I=2

для уменьшения задерж-ки синтезируемой схемы целесообразнее объеди-нять в пару более простые элементы операции, оставляя более сложные элементы уединенными.
Преобразуем полученное выражение для коэффи-циента объединения I = 2, вводя в нем дополни-тельные скобки. При этом в трехместной операции дизъюнкции в правой скобке объединим в пару входные переменные x2 и x5, уединив функцию ϕ, реализуемую отдельной подсхемой и следователь-но, являющуюся более сложным элементом этой скобки.

Слайд 34

Кроме того, при объединении скобок как элементов трехместной операции конъюнкции уединим

среднюю скобку, как более сложный элемент. В результате исходное выражение преобразуется к виду:
Преобразуем это выражение к базису ИЛИ-НЕ, заменяя операции булева базиса операцией стрелка Пирса подобно тому, как это делалось ранее, но с учетом скобок. Это означает, что каждая операция стрелка Пирса должна быть двухместной.

Слайд 35

Инверсии реализуются в схеме, построенной по этому выражению, на элементах ИЛИ-НЕ

с запараллеленными входами.

Слайд 36

Задержка схемы Т=6τ, цена схемы SQ=30. По сравнению со схемой в

базисе ИЛИ-НЕ, построенной без ограничений на число входов в элементы, задержка схемы и ее цена значительно увеличились.

Слайд 37

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

вынесения за скобки x4 из двух последних термов позволяет построить схему на двухвходо-вых элементах ИЛИ-НЕ с ценой SQ=22 и задержкой Т=7τ. Преобразованное к базису выражение имеет вид
Если использовать аналогичное преобразование для двухвходового базиса И-НЕ, то цена схемы и задержка схемы уменьшатся (SQ=20, Т=6τ) за счет отсутствия в ней выходного инвертора.

Слайд 38

Анализ комбинационных схем
По таблице истинности булевой функции выберем наборы аргументов (входных

переменных), на кото-рых функция принимает значения 0 и 1, например, 01101 и 10101, и определим реакцию построенных схем на эти наборы. Для этого на схеме отмечаются значения входных переменных и далее определяются значения выходных сигналов каждого из логических элементов с учетом функции, реализуемой им. Последовательно продвигаясь по схеме от ее входов к выходу, получим значение выходного сигнала схемы. Сравнив его со значением булевой функции для выбранного набора аргументов по таблице истинности, можно утверждать, что, по крайней мере, для этого набора схема функционирует правильно.
-

Слайд 39

Синтез многовыходных комбинационных схем
ПРИМЕР 2. Синтезировать комбинационную схему, выполняющую операцию сложения

двух двухразрядных двоичных чисел:
C=A+B, где A=(a1 , a2) B=(b1 , b2) C=(C0 , C1 , C2).
Закон функционирования синтезируемой схемы описывается системой булевых функций
аргументами которых являются значения двоич-ных разрядов операндов

Слайд 40

1. Составление таблицы истинности
Таблица истинности системы булевых функций строится с учетом

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

Слайд 41

Слайд 42

Слайд 43

Слайд 44

Слайд 45

Слайд 46

Слайд 47

Слайд 48

Слайд 49

Синтез комбинационных схем

Содержание

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

Представление булевой функции в аналитическом виде

Минимизация булевой функции методом Квайна –Мак-Класки Нахождение простых импликант (максимальных кубов).

Составление импликантной таблицы.Импликантная таблица содержит 11 строк (по числу простых импликант)