книги / Синтез принципиальных схем цифровых элементов на МДП-транзисторах
..pdf(AJA'j; Aï Aj; Ag AJ; A» AJ AJ; AJ AJ Ag; Ag Ag Ag; AJ. AJ Ag Ag;
AJ Ag AJ Ag; Al AJ Ag AJ; AJ AJ AJ AJ Ag; AJ AJ AJ Ag Ag ;
AJ AJ A| AJ AJ AJ).
10. |
Перемножаем |
найденные в п. 9 множества покрытий {К\} |
||
и {/<0} и исключим равнозначные комбинации. 6 результате полу |
||||
чим множество покрытий, состоящее из 16 элементов, |
||||
{А\ А\ А\ A J ; |
А\ А\ А] Л | ; |
А\ А\ А\ А\\ А\ А\ А\ А\ А\; |
||
А\ А\ А\ А\ A l |
А\ А\ А\ А\ A l А\ А\ А\ А\ А\ А\ ; |
|||
А\ А\ А\ A l A l A l А\ А\ А\ А\ А\ А\\ А\ А\ А\ А\ А\ А\ A l |
||||
А\ А\ А\ А\ А\ А\ A l |
А\ А\ А* А\ А\ А\ А\ А}; А{ А\ А\ А\\ |
|||
А\ A l А\ А\ A l |
A l А \ |
A l |
А\ А\ А\ A l) . |
11. Находим комплексы, соответствующие полученным в п. 10 покрытиям, и проверим комплексы на равнозначность. Результаты! полученные для каждого покрытия, приведены в табл. 2.16. Срав нивая комплексы, нетрудно обнаружить, что комплексы 4 и 15 равнозначны. Следовательно,.имеется только пятнадцать покрытий* соответствующих квазиполному каноническому набору логической функции (КНЛФ), и пятнадцать схемотехнических решений.
12. Записываем РЛФ, соответствующие КНЛФ:
2 , |
(F) |
= |
(IJ |
(Х ,Х 2 + |
Х ,Х 2) + |
[0] ( Х , Х , + |
% X J ; |
|
|
|||
Z2 (F) |
= |
[1] |
(X^X2+ T 1X 1) + |
[0] |
X xX2+ |
[XJX* |
|
|
||||
2 3 [F) |
= 14 (XjX , + |
X ,X 2) A- |
IX 2]X2-|- [X,]X2; |
|
|
|||||||
^4 |
(F) |
= |
[1] |
( X j / \ , + |
л , Х 2) + |
[0] |
( X t X |
2 + |
^ 1X 2) ■ +■ |
[ X I JA |
2; |
|
Z6 |
(F) |
= [1] |
( X { X 2 + ~ Х хХ а) + |
[0] |
X xX 2 |
+ |
[ X J Ï X J + |
I X , ! Х ц |
||||
2e (F) |
= [1] (X jX 2-f- |
X xX 2) + |
[Х2]Хх -j- [Х2]Х2-f~ [Х2]Х2; |
|
||||||||
2 , |
(F) |
= J 1 ] |
( Х , Х 2 + |
X x X 2) |
+ |
[0] |
( X xX 2+ |
В Д ) + |
[ X J X |
. + |
||
+ i x 2\xi; |
|
|
|
|
|
|
|
|
|
|||
2 , |
(F) |
= |
[1] ( X xX 2 + |
% X 2) |
+ |
[0] |
X , X 2 + |
[X2] X, + IX J |
X 2+ , |
+[ X 2] X i ;
Z, (F) = |
[1] (X fx, + |
X xX 2) + |
[XDX, + |
[ X jx 3 + |
IX J7 » + |
||
+ |
[X JX ,; |
_ |
|
|
|
|
|
z io |
(F) ~ |
[1] ( X , X 2 + |
X i ^ a ) + |
[0] ( X ^ a |
+ X ^ X T ) |
; + |
[ X ^ X , + |
+ |
[ X J X 2 + [ X 2] X i; |
|
|
|
|
|
|
Zn (F)j= |
[1] (X,Xe + |
XxX2) + |
[0]X ix2 + |
[X2]X, + |
[XiJXa + |
+ U 2]X, + [X^Xa;
|
К, |
|
/<0 |
Kl |
|
|
К о ' |
К 1 |
|
к* |
|
К, |
||
Импли- |
|
CI |
|
С» |
|
|
|
|
|
CI |
«J \< |
|
*•1 |
|
капты |
|
|
|
|
|
|
|
|
||||||
Ч‘ |
\'< |
* |
1* |
1* |
Ч |
* |
1* |
1* |
Ч |
|||||
|
* |
1* |
>< |
i* |
•*4 |
Г**' |
ч~Г |
1* |
|
|
|
|
||
а \ |
1 |
1 |
|
|
1 |
1 |
|
|
1 |
I |
|
|
1 |
1 |
а \ |
|
|
|
|
|
|
1 |
1 |
|
|
||||
А\ |
|
\ |
|
|
|
|
|
! |
|
1 |
|
|
||
А\ |
|
|
|
|
1 |
|
|
! |
|
|
1 |
|
||
giro |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А\ |
|
|
1 |
|
|
|
1 |
|
|
|
|
|
|
|
А\ |
|
|
1 |
|
|
|
|
|
|
|
|
|
||
■ Al |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Комплекс |
1, 1, |
1, |
1 |
2,, |
1, |
1. |
1 |
3,, |
1, |
к |
1 |
2, |
1, |
|
Номер |
|
|
1 |
|
|
2 |
|
|
|
3 |
|
|
*4 |
|
комплек |
|
|
|
|
|
|
|
|
|
|||||
са |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Al |
1 |
1 |
|
|
1 |
1 |
|
|
1 |
1 |
|
|
I |
1 |
А\ |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
|
1 |
||||
А% |
|
|
|
|
|
|
|
|||||||
Al |
1 |
|
|
1 |
1 |
|
|
1 |
1 |
|
|
1 |
1 |
|
А\ |
|
I |
1 |
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
А\ |
|
1 |
|
|
|
1 |
|
|
1 |
1 |
|
|
1 |
|
А) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
■А\ |
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
Комплекс |
с |
3, |
2, |
21 |
3,, |
2, |
:2, 3 |
3, |
3, |
2, |
3 |
3, |
3, |
|
Номер |
|
|
J? |
|
|
10 |
|
|
11 |
|
|
12 |
||
комплек |
|
|
|
|
|
|
|
|
са
Ко |
К, |
к„ |
|
к 1 |
К„ |
К, |
К . |
|
Ki |
К 0 |
||
>< |
N |
ч |
ei |
CI |
»< |
CI |
«1 |
04 |
Ч |
м |
*4 |
и : |
I*, |
>< |
1* |
* |
к |
>< |
И |
>< |
|||||
|
1* |
4 |
1^ |
* |
и |
1* |
* |
>< |>г |
4 |
|
|
|4 |
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
|
|
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
I |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
|
1 |
|
|
1 |
1 |
|
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
|
- |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
1 |
1, 2 |
2 , 2 , |
1, 2 |
з , 2 | |
1, 2 |
2 , 2 , |
1, 3 |
|
3, 2 , к 3 |
|
|||
|
|
|
5 |
|
6 |
|
|
7 |
|
|
8 |
|
|
|
! |
|
|
|
|
|
|
|
|
|
|
' 1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
|
1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
I |
|
1 |
|
|
1 |
|
|
|
|
1 |
1 |
|
|
|
1 |
1 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
3 3 |
3 1 |
1 2 |
2 |
2 , 3 2 |
2, 1 |
1. 2 |
|
2 , 2 . 2 , 2 |
|
13 |
14 |
15 |
.16 |
+ |
l x jx 2 + [X2lx; + 17,1X*; |
|
|
|
||||
Zis(F) = Ш (Х,Г2 + [X2]X, + [X,1X2 + |
[X2]X-; |
|||||||
Zu |
(F) |
= |
[ 0 ] X , X 2 + |
T 7 J X , |
+ |
[ X j X , |
+ |
[ X j X i + Г Х , ] Х г ; |
Z 15 |
(F) |
= |
[ X 2] X , + |
[ X , J X 2 |
+ |
[ X 2] X , + |
[ X , ] X 2. |
|
|
Напомним, что приведенные Р Л Ф |
соответствую т неравнознач |
ным комплексам. Одному и тому же ком плексу может соответство вать несколько различны х по форме Р Л Ф .
Трудоемкость отыскания полного набора в несколько раз выше, чем квазиполного, поэтому для большинства прак тических случаев достаточно ограничить анализ схемных вариантов квазиполными наборами. Некоторые из элемен тов квазиполного набора не покрывают всех конституент. В этом случае их следует дополнить таким образом, чтобы их комплексы не совпадали с комплексами других покрытий квазиполного набора. Например, покрытия А \ А \ , А \ A l , А \ А 2 А $ не покрывают конституенты из { К 0}. Поэтому их следует дополнить минимальным числом импликант, обес печивающих недостающие покрытия.
2.8. Комплекс программ генерации канонического набора расширенных логических формул и их оптимизации по схемотехническим критериям
Цель комплекса программ — автоматизировать процесс генерации множества РЛФ различных вариантов принци пиальных схем ЛЭ (канонический набор) и процесс их опти мизации по схемотехническим критериям. Созданная про грамма имеет блочную структуру и включает следующие самостоятельные подпрограммы (рис. 2.17): ввод логиче ской функции и определение ее значений на всех наборах аргументов; определение простых импликант трех групп; •формирование импликантной матрицы; определение кано нического набора комплексов; определение канонического набора РЛФ; упорядоченный вывод конечной информа ции на печать: печать канонического набора комплексов; печать РЛФ.
В блоке 1 допускается ввод функции в виде набора кон ституент К и Ко или импликант, покрывающих К х или /(„. Диагностическим сообщением является распечатка табли цы истинности.
Рнс. 2.17. Схема программы генерации канонического набора РЛФ
В блоке 2 методом Квайна—Мак-Класки определяются импликанты первой и второй групп для конституент Ki и К 0- Импликанты третьей группы определяются на основе соотношений (1.29).
В блоке 3 формируется импликантная матрица. Диаг ностическим сообщением является распечатка матрицы.
Вблоке 4 определяется канонический набор комплек сов (КНК). Проблема, существующая на этом этапе, обусловлена ростом числа различных комплексов при уве личении числа входных переменных. Как следует из приве денного в § 2.7 алгоритма, процесс поиска КНК представ ляет собой последовательную процедуру, требующую боль шого машинного времени. Поэтому на практике целёсообразно вводить ограничения, чтобы исключить генерацию вариантов, обладающих большой избыточностью. В блоке 4 возможно введение ограничений: на число покрытий одной конституенты импликантами; на число импликант, покры вающих все конституенты из K i и Ко', на использование им пликант только первой и второй групп.
Внастоящее время в микросхемах используются логиче ские функции, как правило, не более чем от четырех пере менных. Число входов ограничено электрическими характе ристиками ЛЭ [54]. Диагностическим сообщением являет ся распечатка канонического набора комплексов.
Вблоке 5 определяется канонический набор РЛФ. В бло ке 6 информация преобразуется для вывода на печать РЛФ в наглядном естественном виде (рис. 2.18). На основе
программы создан каталог [26] канонического набора РЛФ функций двух и трех логических переменных.
Программа оптимизации предназначена для работы в двух режимах: автономном и совместно с программой гене рации канонического набора РЛФ. Программа имеет блоч ную структуру и состоит из двух подпрограмм: образования РЛФ по заданной логической функции и определения ти пов транзисторов для реализации каждой импликанты; оп тимизации принципиальной схемы.
ОПРЕДЕЛЕНИЕ |
КАНОНИЧЕСКОГО |
НАБОРА |
|||
РАСШИРЕННЫХ |
ЛОГИЧЕСКИХ ФОРМУЛ |
||||
NLV= |
|
3 |
|
|
|
ИСХОДНАЯ |
ФУНКЦИЯ |
|
|||
FsAB+BC+AC+ABC |
|
||||
ТАБЛИЦА |
ИСТИННОСТИ |
|
|||
0 |
А в |
с |
F |
|
|
0 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
0 |
|
2 |
0 |
1 |
0 |
а |
|
3 |
0 |
1 |
1 |
1 |
|
Ц |
1 |
0 |
0 |
0 |
|
5 |
1 |
0 |
1 |
1 |
|
6 |
1 |
1 |
0 |
1 |
|
7 |
1 |
1 |
1 |
1 |
|
PRa2HAXI=10HAXF* 10 |
_ |
1F=C13<BC)+CC3AB+tA3BCttC3AS
2FrCl3(BC+AC)+C0J(A8C)+CB3AC+CBJAC 3 F=CU <Be+AC)+CC3A0+CB3AC+tB3AC
A Fa ИЗ <BC)+t03 CABC) + [ CJAB+ U3BC+ СC3AB 5 Fs ИЗ (BC>*CC3AB+tB3AC+CA3BC*CB3AC
6FstUCBC) + tC3AB+tB3AC+CA3BC+tC3AB
7F s И J(BC+AC+AB)+t0)(ABC+ABC)+CA3BC
8F =t13(BC+AC+AB)+t03(ABC>+C83AC+CA3BC'
9F*C13 (BC+AC+AB)+tC3AB+CB3AC+CA30C
0 Fst13(BCtAC+AB!+CC3AB+tB3AC+tC3AB ИСПОЛЬЗОВАНИЕ. ИМПЛИКД.НТ ТОЛЬКО 1 И 2 ГРУПП
1 Fï И 3 (ВС+ACtAB+ABC) + 103(ABC + ABC+ABС)
Рис. 2.18. Иллю страция результата работы программы
Рис. 2.19. Схема программы синтеза СФ
Для неискаженной передачи логических уровней при синтезе схем, содержащих переменные в качестве информа ционных сигналов, используются двунаправленные ключи.
Выполнение первой подпрограммы (рис. 2.19) делится на следующие этапы: сортировка импликант первой и второй групп на два множества, каждое из которых реализуется на п- и р-канальных транзисторах; исключение из списка конституент, покрываемых импликантами первой и второй групп; покрытие оставшихся конституент импликантами третьей .группы, выбор типа транзисторов для реализации этих импликант, который зависит от того, в каком множест ве K i или Ко находятся покрываемые конституенты; распре деление неиспользованных импликант с целью выравнива ния числа п- и р-канальных транзисторов в элементах и сим метрирования схемы. После завершения работы подпрограм мы формируются массивы импликант, реализуемых на п- и р-канальных транзисторах и импликант, реализуемых дву направленными ключами. На основе полученной информа ции строится СФ.
Вторая подпрограмма реализует алгоритм оптимизации. Сущность процедуры в минимизации числа транзисторов
в элементе, оптимизации схемы по быстродействию, площа ди и потопологическим критериям за счет симметрирования П- и p-частей по отношению к входным сигналам.
Процесс оптимизации делится на два цикла: оптимиза цию части схемы, реализуемой импликантами первой и вто рой групп, и оптимизацию части схемы, реализуемой импли кантами третьей группы. Такое разделение необходимо для передачи всех информационных сигналов без искажений, ис ключения состязаний уровней 0 и 1, исключения образова
ния ложных путей передачи информационных сигналов, искажающих логическую функцию. Структура подпрограм мы оптимизации показана на рис. 2.20. Выполнение подпро граммы делится на этапы: формирование матрицы инци дентности (МИ); оптимизация покрытия МИ с целью сокра щения числа транзисторов в п- и p-частях схемы и умень-
Рис. 2.20. Схема программы оптимизации РЛФ по схемотехническим критериям
СХЕМА: |
ЛО Г. ЭЛЕМЕНТ |
9. |
|
|
|
|
ч и с л о |
: п е р е м е н н ы х * 4, - |
и м л л и к а н т 111 г |
а ; |
и н п л и х а н т с о з * |
в |
|
ИМПЛ. |
tA3 Р-ТИПА* |
о ; ' и м п л . с а з Н-ТИПА= |
о; |
ДВУНАПР КЛЮЧЕП= |
о |
|
СХЕМОТЕХНИЧЕСКАЯ |
ФОРМУЛА |
|
|
|
-F-P-P P |
F-P P р |
F* С1 3 СA B € D + A 8 C D * |
|
N N -X N-3 N |
N-IM-N N |
С D 4 А В С 0 ♦ А В |
♦ о о |
-F-? Р-Р |
F-F-F-P -? F-7-? |
Р Р Г-Р -? Р Г P |
P F- ? Р |
и N-W-N -W N N-M |
у и |
A B C D * A B C D * A B ' C 0 + A B C D + A B C D + A B C D ; + |
г 0 3 (А В С D 4 А В С D ♦ А а |
||||
-N -N IH N |
И -N К- У -N-N-N-N |
|
|
|
|
А В С О 4 А В С D 4 А В С D ) |
|
|
|
|
ХОД: 1 -1 2 -2,
3 |
ю |
* |
1 |
•1
F - P Ï |
1 |
2 |
3 |
к |
5 |
é |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 15 16 17 18 19 20 21 22 23 |
24 |
|
|
|
|
|
|
|
|||||||||
СТОК: |
9 |
9 |
11 |
11 |
10 |
======:== === ===•==== = ===IIIIIIиIIIIIilиIIIII |
====== =:=== |
20 |
=== |
|
НОМЕР |
в ы х о д н о г о |
УЗЛ*= |
9 |
|||||||||||||||||
10 |
13 |
12 |
13 |
12 |
14 |
13 |
9 |
9 |
17 |
17 |
16 |
16 |
19 |
18 |
19 |
18 |
21 |
|
НОМЕР |
УЗЛА |
ШИНЫ |
П И Т .=-1 |
|||||||||
ИСТ. : |
11 |
10 |
13 |
12 |
12 |
13 |
14 |
14 |
13 |
15 |
-1 |
-1 |
17 |
16 |
19 |
18 |
18 |
19 |
20 |
20 |
21 |
21 |
0 |
0 |
|
НОМЕР |
УЗЛА |
НУЛ. |
ШИНЫ* |
0 |
|
J A T .: |
А |
3 |
2 |
1 |
2 |
1 |
7 |
а |
В |
7 |
6 |
5 |
3 |
4 |
1 |
2 |
1 |
2 |
8 |
7 • 7 |
8 |
6 |
5 |
|
ч и с л о |
ВНУТР..УЗЛОВ =12 |
|||||
ТИП : |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
-1 |
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
СПИСОК |
ВЕТВЕЙ |
СХЕМЫ |
по |
ТРАНЗИСТОРАМ И |
УЗЛАМ |
N-ЧАСТЬ |
|
|
|
|
|
|
|
|
|
||||||||||
Ч. |
11 |
7 |
9 |
1 |
Р-ЧАСТЬ |
-1 |
14 |
13 |
1 1 |
9 |
|
|
|
1 . |
23 |
19 |
15 |
13 |
0 |
20 |
19 |
17 |
9 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
2. |
11 |
7 |
6 |
2 |
|
|
-1 |
14 |
13 |
1.0 |
9 |
|
|
|
2. |
|
23 |
19 |
18 |
14 |
|
|
0 |
20 |
19 |
16 |
9 |
|
|
|
|
3 . |
11 |
8 |
к |
1 |
|
|
-1 |
14 |
12 |
11 |
9 |
|
|
|
3 . |
23 |
20 |
16 |
13 |
|
|
0 |
20 |
18 |
17 |
9 |
|
|
|
|
|
к ; |
11 |
б |
5 |
2 |
|
|
-1 |
14 |
12 |
10 |
9 |
|
|
|
4 . |
23 |
20 |
17 |
14 |
|
|
0 |
20 |
18 |
16 |
9 |
|
|
|
|
|
5. |
12 |
9 |
3 |
1 |
|
|
-1 |
13 |
13 |
11 |
9 |
|
|
|
5 . |
24 |
21 |
15 |
13 |
|
|
0 |
21 |
19 |
17 |
9 |
|
|
|
|
|
6. |
12 |
9 |
6 |
2 |
|
|
-1 |
15 |
13 |
10 |
9 |
|
|
|
6. |
|
24 |
21 |
18 |
14 |
|
|
0 |
21 |
19 |
16 |
9 |
|
|
|
|
7. |
12 |
10 |
к |
1 |
|
|
-1 |
15 |
12 |
11 |
9 |
|
|
|
7 . |
24 |
22 |
16 |
13 |
|
|
0 |
21 |
18 |
17 |
9 |
|
|
|
|
|
В. |
12 |
10 |
5 |
2 |
|
|
-1 |
15 |
12 |
10 |
9 |
|
|
|
8. |
|
24 |
22 |
17 |
14 |
|
|
0 |
21 |
18 |
16 - 9 |
|
|
|
|
со
о)
со
Рис. 2.21. Выходная Хг информация после оп тимизации РЛФ (а)
и синтезированная принципиальная схе ма (б)
Вы*
б)
шения выходной емкости элемента; формирование началь ного графа схемы — списка координат подключения тран зисторов; объединение импликант с целью сокращения чис ла транзисторов; формирование окончательного графа схе мы. Конечной информацией является описание принци пиальной схемы в виде списков вершин графа и инцидент ных им ребер, каждое из которых взвешено входной пере мени ой.
На рис. 2.21 , а приведен фрагмент выходной информации о схеме, на рис. 2.21, 6 — принципиальная схема синтези
рованного и оптимизированного элемента.
Совокупность программ позволяет генерировать множе ство оптимальных принципиальных схем ЛЭ на МДПтранзисторах, ряд из которых являются охраноспособными.
2.9. Методы синтеза и оптимизации как средство повышения эффективности логических элементов
Оценим эффективность предложенных методов по срав нению с другими способами реализации ЛЭ. В качестве примера на рис. 2.22 и 2.23 приведены четыре способа реа лизации функции
Первый вариант — схема 1 (рис. 2.22, а) представлена
вбазисе И—НЕ, схемы 2 и 3 (рис. 2.22, б, в) представлены
вуниверсальных базисах И—ИЛИ—И ... —НЕ, ИЛИ—И— ИЛИ— ... — НЕ, предложенных А. Г. Алексенко [28] и