3. Реализация комбинационных устройств на простых логических элементах
В результате выполнения процедуры декомпозиции проектируемое устройство представляется в виде соединения некоторых блоков и на этом этапе никак не учитывается то, из каких логических элементов будет построена окончательная схема.
Определение
3.1. Логическим
блоком
будем считать некоторую неделимую часть
комбинационной схемы с
входами и
выходами, полученную в результате её
декомпозиции и обладающую известной
числовой последовательностью.
Определение
3.2. Логическим
элементом будем
считать некоторое неделимое комбинационное
устройство, имеющее
входов и
выходов и обладающее собственной
числовой последовательностью длины
.
Определение 3.3. Простым логическим элементом будем считать некоторое неделимое комбинационное устройство, имеющее два входа и один выход.
Для покрытия синтезируемого комбинационного устройства простыми логическими элементами полученную в результате декомпозиции схему, как правило, необходимо делить на ещё более мелкие части, соизмеримые по сложности с элементами, заданными для покрытия. Поскольку элементная база в настоящее время постоянно обновляется, повышается степень интеграции БИС, процедуру логического синтеза цифровых схем следует рассматривать в общем виде, без привязки к какому-либо конкретному базису.
Покрытие схемы логическими элементами заключается в формальном замещении получившихся в результате декомпозиции блоков заданными логическими элементами. Элемент может покрыть и несколько блоков, если он достаточно крупный (мультиплексор, ПЛМ, ПЗУ и т. д.).
Число выходов у покрываемого блока и у логического элемента, должно быть одинаковым. Если это не так, то их следует уравнять. При этом может потребоваться уменьшение числа выходов либо блока, либо элемента. Это можно сделать с помощью принудительной параллельной декомпозиции того или другого.
Несомненный интерес представляет покрытие простыми логическими элементами, и в особенности двухвходовыми элементами «И-НЕ» и «ИЛИ-НЕ». Эти элементы являются наиболее простыми и одновременно образуют функционально полный логический базис, с использованием которого можно реализовать любое, сколь угодно сложное комбинационное устройство.
3.1. Детализация схем до уровня двухвходовых блоков
Процедура разделения схемы до уровня двухвходовых блоков, сложность которых соизмерима со сложностью заданных для покрытия схемы двухвходовых логических элементов, носит название детализации. При выполнении детализации используются алгоритмы параллельной и последовательной декомпозиции, но при этом не требуется уменьшения сложности синтезируемой схемы. Процесс детализации включает выполнение трёх этапов:
1) принудительная параллельная декомпозиция блоков;
2) последовательная декомпозиция одновыходовых блоков;
3) разделение трёхвходовых блоков на двухвходовые.
Рассмотрим более подробно выполнение указанных этапов.
3.1.1. Принудительная параллельная декомпозиция блоков.
На первом этапе детализации логический блок с входами и выходами представляется в виде параллельного соединения одновыходовых блоков (рис. 3.1).
Рис. 3.1. Разделение блоков на первом этапе детализации
Определение 3.4. Разделение комбинационного устройства на параллельные блоки, содержащие все входные переменные исходной схемы, носит название принудительной параллельной декомпозиции.
Утверждение 3.1. Принудительная параллельная декомпозиция не приводит к уменьшению общей сложности описания синтезируемой схемы, не смотря на то, что каждый из выделенных блоков имеет меньшую сложность.
Доказательство. Пусть мы имеем комбинационное устройство с входами и выходами. Сложность описания исходной схемы
(бит).
Проведём
принудительную параллельную декомпозицию
рассматриваемого устройства на два
блока, содержащих соответственно
и
выходов и имеющих сложность
и
(бит).
Поскольку
,
сложность схемы после разделения
остаётся неизменной, что вытекает из
следующего соотношения:
.
Для определения числовых последовательностей получаемых при декомпозиции одновыходовых блоков используется алгоритм разделения исходной числовой последовательности на старшую и младшую части (см. раздел 2.2.9).
3.1.2. Последовательная декомпозиция одновыходовых блоков.
Полученные на первом этапе детализации одновыходовые блоки могут оказаться декомпозабельными и для каждого из них необходимо провести процедуру последовательной декомпозиции.
Для недекомпозабельных блоков будем проводить дальнейшее разделение на более мелкие части, не требуя при этом уменьшения сложности схемы. Пусть мы имеем блок с входами и одним выходом (рис. 3.2).
Рис. 3.2
С точки зрения
уменьшения сложности блок является
недекомпозабельным. Последовательность
блока содержит
элементов. Разложим эту последовательность
в матрицу по входной переменной с весом
:
.
(3.1)
В матрице (3.1) могут
присутствовать и не все, перечисленные
выше столбцы, но она не может содержать
никаких других столбцов, поскольку
число возможных сочетаний из двух
элементов равно 4 (
).
Если рассматриваемая числовая
последовательность является
недоопределённой и содержит звёздочки,
то в матрице могут присутствовать
недоопределённые столбцы, которые
следует доопределить до одного из
столбцов матрицы (3.1).
Минимальное количество различных столбцов в матрице (3.1) – три. Если в матрице окажется два различных столбца, то исследуемый блок является декомпозабельным, что противоречит исходным условиям.
В соответствии с
построенной выше матрицей разложения
(3.1) можно принудительно разделить
рассматриваемое комбинационное
устройство на два последовательных
блока, младший из которых имеет три
входа и один выход, а старший – (
)
входов и два выхода (рис. 3.3). Для простоты
дальнейшего изложения старший блок на
рис. 3.3 сразу представлен в виде
параллельного соединения двух
одновыходовых блоков
и
.
Определение 3.5. Разделение комбинационного устройства, выполненное в соответствии со схемой рис. 3.3 путём разложения его числовой последовательности в матрицу вида (3.1), носит название принудительной последовательной декомпозиции.
Такое разложение соответствует двукратной разделительной декомпозиции логических схем.
Рис. 3.3
Последовательность
блока
содержит
элементов и представляет собой первую
строку матрицы (3.1), а блока
– вторую строку указанной матрицы. Для
определения логической последовательности
младшего блока
строится обобщённая матрица, в которой
в лексикографическом порядке располагаются
столбцы, содержащиеся в матрице (3.1):
.
Последовательность
блока
получается в результате развёртывания
обобщённой матрицы по весу 4 (т. е. по
строкам) –
,
поскольку выделенная входная переменная
соответствует входной переменной
рассматриваемого блока.
Такое разделение
схемы с точки зрения уменьшения сложности
оказывается нецелесообразным, но оно
позволяет из
-входового
блока выделить трёхвходовый блок
.
Оставшиеся
-входовые
блоки
и
можно проверить на возможность выделения
последовательных блоков, т. е.
-входовые
блоки
и
могут оказаться декомпозабельными. В
противном случае их можно подвергнуть
дальнейшему выделению трёхвходовых
блоков и т. д.
Таким образом,
используя приведённые выше алгоритмы,
всю схему можно разделить на блоки,
содержащие в общем случае не более трёх
входов. Если в исходной матрице разложения
по входной переменной
содержатся три различных столбца, то в
обобщённой матрице вместо отсутствующего
столбца ставится столбец
.
При этом можно выделить пять вариантов
реализации выходного блока
,
которые представлены в табл. 3.1.
Таблица 3.1
Трёхвходовые логические блоки
Тип блока |
Обобщённая матрица |
Логическая последовательность блока |
1. |
|
|
2. |
|
|
Продолжение таблицы 3.1
3. |
|
|
4. |
|
|
5. |
|
|
3.1.3. Разделение трёхвходовых блоков на двухвходовые.
На третьем этапе детализации производится разделение блоков, указанных в табл. 3.1, на двухвходовые.
Возьмём блок 3-го типа с последовательностью и попытаемся провести его последовательную декомпозицию. Для этого построим матрицы разложения по всем входным переменным и подсчитаем количество содержащихся в них различных столбцов:
– 3 различных
столбца;
– 2 различных
столбца в случае доопределения «*» до
«1»;
– 2 различных
столбца в случае доопределения «*» до
«0».
Следовательно, возможны два варианта декомпозиции рассматриваемого блока, представленные на рис. 3.4.
Выбор одного из вариантов определяется с учётом элементного базиса, заданного для покрытия схемы. Следует выбирать тот вариант, выходной блок которого совпадает по типу (по количеству единиц в последовательности) с элементами логического базиса. Более подробно это будет рассмотрено ниже в разделе 3.2.
а)
б)
Рис. 3.4
Рассмотрим варианты последовательной декомпозиции блока 2-го типа с последовательностью :
– 3 различных
столбца;
– 2 различных
столбца в случае доопределения «*» до
«0»;
– 2 различных
столбца в случае доопределения «*» до
«1».
Следовательно, возможны два варианта декомпозиции рассматриваемого блока, представленные на рис 3.5.
Как уже было сказано выше, выбор одного из вариантов определяется с учётом элементного базиса, заданного для покрытия схемы.
а)
б)
Рис. 3.5
Для блока 5-го типа с последовательностью матрицы разложения по входным переменным имеют следующий вид:
– 4 различных
столбца;
– 3 различных
столбца;
– 3 различных
столбца.
В этом случае можно использовать второй и третий варианты разложения, которые позволяют выделить на выходе схемы трёхвходовый блок 3-го типа, имеющий наиболее простую схемотехническую реализацию (рис. 3.6).
а)
б)
Рис. 3.6
В свою очередь, блок с последовательностью , рассмотренный выше, также имеет два варианта реализации (см. рис. 3.4 а и 3.4 б), что в конечном итоге позволяет построить четыре варианта схем для блока 5-го типа (рис. 3.7 а – г).
а)
б)
в)
г)
Рис. 3.7
Варианты декомпозиции блока 1-го типа с последовательностью могут быть получены при рассмотрении следующих матриц:
– 3 различных
столбца;
– 3 различных
столбца;
– 3 различных
столбца.
В этом случае также
можно использовать второй и третий
варианты разложения, которые позволяют
в случае доопределения одной из звёздочек
до «0» в верхних строках обеих матриц
обеспечить отсутствие столбца
и выделить на выходе схемы трёхвходовый
блок 3-го типа (рис. 3.8).
а)
б)
Рис. 3.8
Как и в предыдущем случае это позволяет построить четыре варианта схем для блока 1-го типа (рис. 3.9 а – г).
а)
б)
в)
г)
Рис. 3.9
Аналогично для блока 4-го типа с последовательностью :
– 3 различных
столбца;
– 3 различных
столбца;
– 3 различных
столбца.
В рассматриваемом случае также можно использовать второй и третий варианты разложения, которые позволяют в случае доопределения одной из звёздочек до «1» в нижних строках обеих матриц обеспечить отсутствие столбца и выделить на выходе схемы трёхвходовый блок 3-го типа (рис. 3.10).
а)
б)
Рис. 3.10
Как и в двух предыдущих случаях это позволяет построить четыре варианта схем для блока 4-го типа (рис. 3.11 а – г).
а)
б)
в)
г)
Рис. 3.11
Таким образом, используя изложенные выше алгоритмы, сколь угодно сложную схему можно разделить на простые (двухвходовые) логические блоки.
В заключение следует заметить, что общий случай трёхвходового блока с последовательностью есть не что иное, как мультиплексор 2/1 (MUX 2/1), который в совокупности с константами «0» и «1» также может образовывать функционально полный базис для реализации любой, сколь угодно сложной, логической схемы.