Покрытие логической схемы двухвходовыми элементами

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

1) «2И», «2ИЛИ», «НЕ» (классический базис);

2) «2И-НЕ»;

3) «2ИЛИ-НЕ».

Наибольший практический интерес может представлять базис, состоящий из двухвходвых элементов «И-НЕ» либо «ИЛИ-НЕ» («2И-НЕ», «2ИЛИ-НЕ»), поскольку в этом случае вся проектируемая схема будет состоять из одинаковых логических элементов. Структуру, состоящую из однотипных элементов проще изготовить в интегральном исполнении на полупроводниковом кристалле.

Кроме того, в современных интегральных схемах двухвходовые элементы «И-НЕ» и «ИЛИ-НЕ» могут быть реализованны в виде базовых матричных кристаллов (БМК) или программируемых пользователем вентильных матриц (ППВМ или FPGA – Field Programmable Gate Arrays). Один из вариантов конфигурируемых логических блоков (КЛБ) ППВМ представляет собой регулярные топологические структуры на основе последовательно соединённых МОП-транзисторов с каналами и -типа (SLC – Simple Logic Cells). Между цепочками таких транзисторов расположены трассировочные каналы, в которых реализуются необходимые межсоединения транзисторов.

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

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

Рассмотрим основные принципы преобразования числовых последовательностей логических элементов, используемые при покрытии схем. Для простоты изложения будем рассматривать только двухвходовые элементы и блоки. Вообще, для двух входов (аргументов) можно определить 16 типов различных логических элементов (блоков) и соответствующих им числовых (логических) последовательностей (), которые представлены в табл. 3.2.

Таблица 3.2

Логические последовательности двухвходовых элементов и блоков

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

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

– функция «», не зависящая от аргументов;

– функция «», не зависящая от аргументов;

– функция тождества, значение которой совпадает со значением аргумента ;

– функция тождества, значение которой совпадает со значением аргумента ;

– функция отрицания аргумента (функция «НЕ»);

– функция отрицания аргумента (функция «НЕ»).

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

1. Э лементы (функции) типа «И» – содержат в собственных числовых последовательностях одну единицу:

– функция «И» (значение функции равно «1», если оба её аргумента и также равны «1»);

– функция «ЗАПРЕТ» ( запрещает , значение функции равно «0», если запрещающий аргумент равен «1», если равен «0», то значение функции равно аргументу );

– функция «ЗАПРЕТ» ( запрещает );

– функция «СТРЕЛКА ПИРСА», «ИЛИ-НЕ» (значение функции равно «1» только в том случае, когда оба её аргумента и равны «0»).

2. Элементы (функции) типа «М2» – содержат в собственных числовых последовательностях две единицы:

(или ) – функция «НЕРАВНОЗНАЧНОСТЬ», «НЕЭКВИВАЛЕНТНОСТЬ», «ИСКЛЮЧАЮЩЕЕ ИЛИ» (значение функции равно «1», если значения её аргументов и не равны между собой);

– функция «РАВНОЗНАЧНОСТЬ», «ЭКВИВАЛЕНТНОСТЬ» (значение функции равно «1», если значения её аргументов и принимают одинаковые значения).

3. Элементы (функции) типа «ИЛИ» – содержат в собственных числовых последовательностях три единицы:

– функция «ИЛИ» (значение функции равно «1», если равен «1» хотя бы один из её аргументов или );

– функция «ИМПЛИКАЦИЯ», «СЛЕДОВАНИЕ» (из следует , значение функции равно «0», если посылка равняется «1», а следствие равно «0»);

– функция «ИМПЛИКАЦИЯ», «СЛЕДОВАНИЕ» (из следует );

– функция «ШТРИХ ШЕФФЕРА», «И-НЕ» (значение функции равно «0» только в том случае, когда оба её аргумента и равны «1»).

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

Утверждение 3.2. Инвертирование выходной числовой последовательности логических элементов позволяет из элементов типа «И» получить элементы типа «ИЛИ».

Доказательство. Числовая последовательность двухвходового логического элемента содержит 4 символа (). Для элементов типа «И» – это три символа «0» и один символ «1». При инвертировании выходной последовательности три символа «0» превращаются в три символа «1», а один символ «1» – в «0». Таким образом тип элемента меняется с «И» на «ИЛИ». И наоборот, при инвертировании числовой последовательности, содержащей три символа «1» тип элемента меняется с «ИЛИ» на «И».

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

Утверждение 3.3. Инвертирование входной числовой последовательности с весом приводит к взаимной перестановке групп из символов в числовой последовательности элемента.

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

Таким образом, для двухвходовых логических элементов можно сформулировать две леммы.

Лемма 3.1. Инвертирование входного сигнала старшего входа соответствующего входной переменной с весовым коэффициентом 2, приводит к взаимной перестановке пар символов числовой последовательности логического элемента:

Лемма 3.2. Инвертирование входного сигнала младшего входа , соответствующего входной переменной с весовым коэффициентом 1, приводит к взаимной перестановке чётных и нечётных символов числовой последовательности логического элемента:

Аналогичные леммы можно сформулировать и для элементов с большим числом входов. Например, для трёхвходового логического элемента старшим будет вход с весовым коэффициентом 4 и, следовательно, при его инвертировании будут меняться местами четвёрки символов в его числовой последовательности.

Лемма 3.3. При инвертировании двух и более входных числовых последовательностей применяется принцип суперпозиции – перестановки символов в выходной последовательности производятся группами в соответствии с весовыми коэффициентами инвертированных входов:

3.2.2. Реализация двухвходовых логических блоков на элементах «2И-НЕ».

Используя сформулированные и доказанные выше утверждения, можно построить реализацию представленных в табл. 3.2 нетривиальных логических блоков и соответствующих им функций на двухвходовых элементах «И-НЕ», представляющих собой функционально полный логический базис.

1. Инвертор. Если на оба входа элемента «2И-НЕ» подать одинаковые числовые последовательности и выполнить над ними логическую операцию «И-НЕ», то выходная последовательность окажется равной инвертированной входной последовательности:

Реализация инвертора на рассматриваемых элементах приведена на рис. 3.12.

Рис. 3.12

2. Блок «И» (). Для его реализации числовую последовательность элемента «2И-НЕ» необходимо проинвертировать на выходе (рис. 3.13):

Рис. 3.13.

3. Блок «ИЛИ» () относится к тому же типу, что и покрывающий элемент. Для его реализации необходимо проинвертировать обе последовательности и , подаваемые на входы элемента «2И-НЕ» (рис. 3.14):

Рис. 3.14

4. Блок «ИЛИ-НЕ» () можно получить из элемента «ИЛИ», добавив инвертор на выходе его схемы (рис.3.15).

Рис. 3.15

5. Блоки «ИМПЛИКАЦИЯ», имеющие логические последовательности и , относящиеся к типу «ИЛИ» можно реализовать, проинвертировав входные переменные или соответственно (рис. 3.16 и 3.17).

Рис. 3.16

Рис. 3.17

6. Блоки «ЗАПРЕТ», имеющие логические последовательности и , относящиеся к типу «И», можно реализовать путём добавления инверторов на выходах схем, изображённых соответственно на рис. 3.16 и 3.17.

7. Блок «ИСКЛЮЧАЮЩЕЕ ИЛИ». Реализацию логической последовательности можно получить, выполнив операцию «И-НЕ» над двумя определёнными последовательностями и типа «ИЛИ», соответствующими типу покрывающих элементов (для простоты дальнейшей реализации):

Схемы, реализующие последовательности и могут быть получены путём инвертирования одной из входных последовательностей логического элемента «2И-НЕ» (рис. 3.16 и 3.17). Реализация рассматриваемой схемы представлена на рис. 3.18.

Рис. 3.18

Для реализации последовательностей и в общем случае в схему необходимо добавить ещё два инвертора, каждый из которых представляет собой элемент «2И-НЕ» с объединёнными входами. Однако этого можно избежать, если провести процедуру оптимизации, которая будет описана ниже в разделе 3.3.2. А пока на рис. 3.19 приведём окончательную схему реализации блока «ИСКЛЮЧАЮЩЕЕ ИЛИ» на элементах «2И-НЕ» без промежуточных построений.

Рис. 3.19

8. Блок «ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ» () можно получить из блока «ИСКЛЮЧАЮЩЕЕ ИЛИ» путём добавления инвертора на выходе схемы рис. 3.19 либо выполнив операцию «И-НЕ» над двумя определёнными последовательностями типа «ИЛИ»:

Полученная таким образом реализация схемы блока «ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ» представлена на рис. 3.20.

Рис. 3.20

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

3.2.3. Реализация двухвходовых логических блоков на элементах «2ИЛИ-НЕ».

Реализация рассмотренных выше нетривиальных логических блоков и соответствующих им функций (см. табл. 3.2) на двухвходовых элементах «ИЛИ-НЕ», также представляющих собой функционально полный логический базис, выполняется аналогично.

В качестве примера приведём реализацию наиболее сложного блока «ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ». Последовательность может быть получена путём выполнения операции «ИЛИ-НЕ» над двумя определёнными последовательностями типа «И», поскольку в данном случае покрывающие элементы относятся к этому же типу:

В свою очередь последовательности и могут быть получены путём инвертирования числовой последовательности одного из входов логического элемента «2ИЛИ-НЕ». Реализация рассматриваемой схемы приведена на рис. 3.21.

Рис. 3.21

Для реализации последовательностей и в общем случае в схему также необходимо добавить ещё два инвертора, каждый из которых представляет собой элемент «2ИЛИ-НЕ» с объединёнными входами. Однако проведение процедуры оптимизации позволяет свести схему к виду, представленному на рис. 3.22.

Рис. 3.22

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