Синтез логических схем

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

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

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

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

Пусть имеются наборы с номерами 0, 4, 8, 12 и 15, из которых наборы с номерами 8 и 15 отмечены звездочками.

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

Функции с доопределением можно обозначить через f₀, f₁, f₂ и f₃. Каждую такую функцию целесообразно представить на карте Карно, произвести минимизацию. В итоге найдется оптимальный вариант тупиковой формы f_тф.

Оказывается, есть алгоритм оптимального доопределения. Он связан с доопределением нулями (с функцией j₀), с доопределением единицами (с функцией j₁).

Алгоритм этот - следующий:

1) начало;

2) получение выражения j₀ без минимизации;

3) получение выражения j₁ с минимизацией;

4) выбор по импликантной таблице существенных простых импликант из j₁ для получения f_тф;

5) конец.

Выражение j₀ есть:

Для получения выражения j₁ целесообразно воспользоваться картой Карно (рис. 26). Видно, что

Реализация алгоритма оптимального доопределения для заданной функции представлена в табл. 37.

Как видно,

Таблица 37

ПИ j1	ИМП j0
	\/	\/	\/
x1x2x3x4

Р

Р

Р

Рис. 26

5.1.2. Синтез схем с двумя выходами с средней степенью связи

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

Данный синтез вначале рассматривается применительно к схеме с 2-мя выходами, а затем - к дешифратору с заданным количеством входов.

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

y₁= x₁ x₂ x₃+ x₁x₂ x₃+x₁x₂ x₃,

y₂= x₁x₂x₃+x₁x₂x₃+x₁x₂x₃.

Видно, что 1-я импликанта у выражений является общей. Её следует реализовать в одном из каналов, например, в первом. С учётом общей части

a =`x<sub>1</sub>`x₂ x₃

y₁= x₁x₂x₃+x₁x₂x₃+x₁x₂x₃,

y₂= a +x₁x₂x₃+x₁x₂x₃.

Стоимость по Квайну 1-го выражения будет равна 15, а 2-го выражения – 9. Учтена и слабая связь (инверторы отнесены к 1- му каналу). Исходные

выражения без учёта каких- либо связей “стоили” 30.

Синтезированную схему требуется изобразить с учётом булевого базиса элементов.

В качестве примера учёта частей импликант, дающего большой эффект, можно рассмотреть синтез дешифратора с n входами. Эффект начинает получаться при n, равном 4. С увеличением числа входов растет сложность дешифратора и эффект минимизации. С учетом увеличения сложности следует ограничиться количеством входов, равным четырем (табл. 38).

Таблица 38

Условия работы дешифратора

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

_ _ _ _ _ _ _

y₀ = x₁x₂x₃x₄ , у₈= х₁х₂х₃х₄ ,

_ _ _ _ _

у₁= х₁х₂х₃х₄ , у₉= х₁х₂х₃х₄ ,

_ _ _ _ _

у₂= х₁х₂х₃х_{4 ,} у₁₀= х₁х₂х₃х₄ ,

_ _ _

у₃= х₁х₂х₃х₄ , у₁₁= х₁х₂х₃х₄ ,

_ _ _ _ _

у₄= х₁х₂х₃х₄ , у₁₂= х₁х₂х₃х₄ ,

_ _ _

у₅ = х₁х₂х₃х₄ , у₁₃= х₁х₂х₃х₄ ,

_ _ _

у₆= х₁х₂х₃х₄ у₁₄= х₁х₂х₃х₄ ,

_

у₇= х₁х₂х₃х₄ у₁₅= х₁х₂х₃х₄ .

При синтезе дешифраторов принято считать, что входные сигналы по-

Даются как без инверсии, так и с инверсией. Количество входов при этом удваивается. Однако число входов указывается без удвоения. Рассматриваемый дешифратор – это дешифратор на 4 входа, хотя их – 8.

Без учёта общих частей (видно, что они применительно к х₁х₂ и х₃х₄

имеются) стоимость любого канала c_i =4 (в общем случае, стоимость равнa

n). Известно, что число каналов у дешифратора равно 2 ⁿ (при n=2 число каналов будет равно 2⁴). Общая стоимость всех каналов c_исх составит 2ⁿ_* n. При n =4 c⁴ = 64, а при n =10 c¹⁰ = 10240 (много).

Учёт общих частей позволяет резко снизить общую стоимость. Общие части можно обозначить так:

_ _ _ _

e₀=х₁х₂ , f₀=x₃x₄ ,

_ _

e₁=x₁x₂, f₁=x₃x₄ ,

_ _

e₂=x₁x₂, f₂=x₃x₄ ,

e₃=x₁x₂, f₃=x₃x₄.

Получились выражения для двух дешифраторов на 2 входа (n/2 входа ) со стоимостями:

c_e²=2_*2²=8, c_f²=2_*2²=8,

общая стоимость составляет:

c_ef²=16.

В общем случае получаются стоимости :

c_e^n/2=n/2_*2^n/2, c_f^n/2=n/2_*2^n/2, c_ef^n/2=n_*2^n/2.

При n=4 c_ef²=4_*2²=16, при n=10 c_ef⁵=10_*2⁵=320.

Если n не делится на 2, то тогда

c_e^(n-1)/2 = (n-1)/2) _*2 ^(n-1)/2, c_f^(n+1)/2 = (n+1)/2) _*2 ^(n+1)/2 и

c_ef = (n-1)/2 ^2(n-1)/2 + (n+1)/2 ^2(n+1)/2.

Рассмотренные дешифраторы составляют первую ступень итогового дешифратора, для второй (выходной) ступени выражения будут равны:

y₀=e₀f₀, y₄=e₁f₀, y₈=e₂f₀, y₁₂=e₃f₀,

y₁=e₀f₁, y₅=e₁f₁, y₉=e₂f₁, y₁₃=e₃f₁,

y₂=e₀f₂, y₆=e₁f₂, y₁₀=e₂f₂, y₁₄=e₃f₂,

y₃=e₀f₃, y₇=e₁f₃, y₁₁=e₂f₃, y₁₅=e₃f₃.

Стоимость любого выражения второй ступени в любом случае составляет 2.

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

при n=4 c_вых⁴=2⁴_*2=32, при n=10 c_вых¹⁰=2¹⁰_*2=2048.

Итоговые стоимости дешифратора равны:

cⁿ=n_*2^n/2+2_*2ⁿ; cⁿ=(n-1)/2^2(n-1)/2+(n+1)/2^2(n+1)/2+2_*2ⁿ;

c⁴=4_*2²+2_*2⁴=16+32=48; c¹⁰=10_*2⁵+2_*2¹⁰=320+2048=2368.

Видно, что при учёте общих частей импликант удаётся достичь существенного снижения стоимости схемы. С увеличением числа входов снижение стоимости становится более существенным.

5.1.3. Синтез схем с двумя выходами с сильной степенью связи

Условно можно рассмотреть три степени связи: отсутствие связи, слабую связь и сильную связь.

Оказывается, эти три степени связи можно иметь в виду при синтезе любой схемы с несколькими выходами. Если, например, нет никаких сведений о связи между выходами, то синтез логической схемы можно провести как для схемы с отсутствием связи между выходами.

При работе со схемой должны появиться сведения о связи, которая фактически всегда есть. Именно такой подход и применяется.

В качестве примера пусть будут заданы две функции, представленные в табл. 39. Как видно, в качестве обозначений выходов (функций) выбраны обозначения u₁ и u₂. Фактические обозначения каждый исполнитель может выбрать самостоятельно.

Таблица имеет дополнительные столбцы, используемые при синтезе.

По табл. 39 получаются следующие выражения:

Таблица 39

			u1	u2	m	s	u2*=Øu1	u2	u2**
0

Стоимость каждого выражения составляет 19. Общая стоимость равна 38. Так дело обстоит без установления связей.

Оказывается, у этих выходов имеются общие инверторы. Выражения эк-

вивалентны по сложности, инверторы можно оставить в канале u₁, тогда

стоимость второго канала окажется равной только 16. Итоговая стоимость составит 35. Такой подход можно представить как учет слабой связи.

При любом синтезе требуется минимизация (рис.27 и 28). Стоимости 1-

го и 2-го каналов составляют 8 и 12 соответственно. Общая стоимость равна 20. Если учесть общие инверторы, то стоимость второго канала будет равна

Рис. 27 Рис. 28

Для другой схемы ситуация может быть иной.

В табл. 39 видна сильная связь: выражение u₂ на шести строках является

инверсией выражения u₁. Если реализовать канал для u₁, то с помощью ин-

вертора можно получить выражение, почти эквивалентное u₂, как и наоборот тоже справедливо.

Возникает проблема выбора основного выражения. Естественно, что за основу следует взять более дешевое (u₁):

тогда u₂*=Øu₁. В таблице имеется столбец для этого выражения. Правее его скопирован столбец для u₂ для упрощения сравнения. Из этих соседних столбцов хорошо видно, что выражения на двух наборах дают разные результаты. На нулевом наборе вместо нуля получается 1, а на соседнем наборе вместо 1 получается 0. Требуется за счет вспомогательных функций m и s, зависящих от переменных выражение u₂* изменить, чтобы получить выражение, соответствующее u₂.

Делается это последовательно. Вначале следует учесть преобразование 1 в 0. Это преобразование возможно за счет множителя m, равного нулю только для нужного (нулевого) набора, что зафиксировано в табл. 39. В результате этого преобразования u₂**=u₂*×m=Øu₁×m. Очевидно, что

Видно, что осталось еще расхождение при наборе 001. Преобразование 0

в 1 возможно за счет слагаемого s, равного 1 на указанном наборе (зафикси-

ровано в табл. 39), следовательно, +x₁x₂x₃.

Итак, синтез следует вести по выражениям

+ x₁x₂x₃.

Инверторы переменных, как и раньше, приписываются выражению u₁. Для реализации выражения u₂ требуется добавить инвертор для u₁, конъюнктор и дизъюнктор на три переменные, конъюнктор и дизъюнктор на две переменные. Добавочная стоимость составляет 11, что следует писать как +11. Суммарная стоимость оказывается равной 19. Как видно, попытка использовать сильную связь к эффекту для заданного варианта не привела.

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

Рекомендуется сведения о стоимостях свести в отдельную таблицу (табл. 40).

Таблица 40

Дата добавления: 2015-07-26; просмотров: 257; Нарушение авторских прав

Мы поможем в написании ваших работ!