Исследование моделей МДП-схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

р' -

Академия наук Украины Ордена Ленина Институт кибернетики имени В. М. Глушкова

На правах рукописи

ПШЕННОВ Дмитрий Евгеньевич

УДК 519.21

ИССЛЕДОВАНИЕ МОДЕЛЕЙ МДП-СХЕМ

01.01.09 — математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Каев 1991

Работа выполнена в Московском государственном университете имени М. В. Ломоносова и Институте кибернетики имени В. М. Глушкова АН Украины.

Научные руководители: академик АН Украины, доктор

физико-математических наук, профессор СЕРГИЕНКО И. В.,

кандидат физико-математических наук САПОЖЕНКО А. А.

Официальные оппоненты: члсн-корреснондснт АН Украины,

доктор физико-математических наук, профессор ШОР Н. 3.,

доктор физико-математических наук ПЕРЕПЕЛИЦА В. А.

Ведущая организация: Киевский государственный университет имени Т. Г. Шевченко.

Защита состоится ---------19 г. в--

часов на заседании специализированного совета Д 016.45.01 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

С диссертацией можно ознакомиться в научно-техническом архиве института.

Автореферат разослан ■■■ 19 -^^гГ"

Ученый секретарь специализированного совета

СИНЯВСКИЙ В. Ф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. В последнее время разработано и производится много разновидностей полупроводниковых приборов, в основу действия которых положен эффект поля. Широкое распространение получили приборы со структурой ВДП ( металл-диэлектрик-полупроводник ). Интегральные схемы на ад-транзисторах конструктивно просты, технологичны, дают высокий процент выхода годных изделий, малоразмерны, что позволяет значительно повысить степень интеграции и снизить стоимость отдельной -схемы.

Но с ростом степени интеграции повышается и трудоемкость проектирования интегральных схем. Уже при числе транзисторов в схеме порядка сотен становится практически невозможно проектирование Больших Интегральных Схем ( БИС ) вручную, а современная технология позволяет создавать В>1С, состоящее из сотен тысяч полупроводниковых приборов. В связи с этим особую важность приобретают системы автоматизированного проектирования и расчета ( САПР ) БИС. Они призваны освободить человека от рутинной работы, ускорить выполнение работ, непосредственно не-свят занных с творческой деятельностью человеческого мозга. Такого рода функции вполне могут исполнять компьютеры.

• Проблемы функционирования схем на МДГЬтранаисторах предусматривают реализацию схемой, определенной логической функции, также прохождение сигнала по схеме во времени, переключение схемы при изменении ее входов и согласование нескольких сигналов. Различные подходы к этим вопросам уже расс-матрияались как в теоретической кибернетике, так и в радиотехнике.

Основным принципом. исследования переходных процессов в МДП-схемах является возможно более точное описание схемы с по-

„ о ,

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

В случае, когда число элементов в схеме невелико, существует возможность достаточно точного численного решения системы дифференциальных уравнений, описывающих схему. Суи&ствуот программы для компьютера, анализирующие схемы, состоящие из 1000'и-менее транзисторов. Для более сложных схем таких точных методов решения получено пока не было. Это связано как с усложнением опйсания схемы, гак и с недостаточным быстродействи- '■' ем и памятью существующих компьютеров. Кроме того, непрерывный подход не предполагает получения конкретных результатов по анализу схем исходя из вида дифференциальных уравнений, т. е. из топологической структуры схемь!. В этом аспекте представлял бы интерес более интуитивный подход к анализу БИС, позволяющий простыми средствами достигать значимых результатов.

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

Цель работы заключается в следующем:

- выявить тенденций развития исследований по вопросам анализа электрических схем со структурой'ЩП, . провести анализ существующих методов расчета переходных процессов в электрических схемйх; .

*- рассмотреть новый дискретный . подход к анализу

МДП-схем;

- предложить математическую модель МЩ-схемы, позволяющую , упростить рассмотрение переходных процессов в ВДП-схемах и задержек распространения электрического сигнала по схеме во времени;

- получить "качественные результаты по функционированию МДП-схем;

»»

- разработать алгоритм для анализа НС-схем и провести оценки его-сложности

- оценить задерж;' и предложить оптимальный по- быстродействию схем метод синтеза контактных схем;

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

Методика исследований. В основу' исследований связанных с анализом МДП-схем и макромоделированием, положены некоторые результаты из теории управляющих систем и теории анализа электрических схем. •

Научная новизна. Предложен дискретный подход к анализу МДП-схем, позволяющий упростить рассмотрение переходных процессов ■ в МДП-схемах и задержек распространения электрического сигнала, но схеме во .времени. Разработан алгоритм для анализа схем и проведены оценки его сложности. Доказаны теоремы, позволяющие оценить задержку и предложить оптимальный по быстродействию схем метод синтеза контактных схем. Предложено понятие макромодели и приближенной макромодели для ,произвольных управляющих систем и его приложение к классу рассматриваемых схем. Доказаны некоторые, теоремы о существовании макромоделей и приближенных макромоделей , а также'предложена макромодель

для одного класса схем.

Практическая ценность и актуальность результатов. Разработанные в диссертационной работе алгоритмы могут использоваться при анализе электрических схем со структурой МДП, а также при решении хозяйственных и научно-технических задач,до* пускаицих макромоделирование.

Апробация работы. Результаты диссертационной работы докладывались на конференциях молодых ученых Московского государственного университета им. И Б. Ломоносова. ( г. Москва, 1983, 1984; •1985 гг.), Всесоюзном семинаре по дискретной математике ( г. Москва, 198? г.), Республиканской конференции по вопросам конструировался электротехнических приборов ( г.Рига, 1988), Московской городской конференции молодых ученых и специалистов по проблемам кибернетики и вычислительной техники ( г. Москва, 1989 г. ), Всесоюзной школе по вопросам оптимизации вычислений С пос. Кацивели", 1991 г.), '

Публикации. Основные результаты диссертации отражены в четырех .работах.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы. Обший объем работы - 72 страницы, список литературы - 31 наименование. Изложение иллюстрируется 36 рисунками.

СОДЕРЖАНИЕ РАБОТЫ.'

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

•В первой главе рассматривается литература по данному воп-

росу и исследуются различные подходы к анализу МДП-схем.-

Приведенный анализ показал, что существующие методы анализа электрических схем основаны на составлении систем дифференциальных уравнений и их дальнейшем численном решении. В этой связи представляют интерес для исследования два следующих направления." ¿э-первых, дискретный подход к анализу схем на ЩЩ-транзисторах, позволяющий вообще отказаться от составления дифференциальных уравнений, и,во-вторых, упрощение схем и соответствующее упрощение систем дифференциальных уравнений. Этим двум направлениям посвящены соответственно вторая с третьей и четвертая главы диссертации.

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

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

• " Рис.1 •

В случае соединения нескольких транзисторов возникает понятие ЯС-схемы.

Введем ряд определений.

Цог>о/<?

Сто*

Ссгпоха

ОПРЕДЕЛЕНИЕ 1. КС-схемой называется граф, в котором реб-

рам приписаны веса - сопротивления, а вершинам - веса ~ емкости. Некоторым вершинам,- полюсам приписано постоянное напряжение питания £ ; это предполагает источник питания с бесконечной емкостью и нулевым сопротивлением.

Общим принципом исследования переходных процессов в БИО является следующей: фиксируется некоторая гипотеза о прохождении сигнала по схеме во времени, а далее на ее основе получаются результаты по функционированию схемы. Предлагается следующая гипотеза последовательного заряда. *

■ Вершина РС-схемы начинает заряжаться с того момента, когда в какой-либо смежной ей вершине устанавливается потенциал, не меньший некЬторого порогового значения 1/ц . С этого момента ' заряд осуществляется через-Я-подсхему, образованную заряженными до Ц-$ на каждый момент вершины.

Будучи принята в качестве базисной, эта гипотеза позволяет получить некоторые г;,тересные 'свойства ЩП-схем. Она подтверждается расчетом схем на основе дифференциальных уравнений для цепочки-одинаковых'транзисторов.

ОПРЕДЕЛЕНИЕ 2. Задержка 1[тг) вершины 7/ ИС-схемы есть время установления в данной вершине потенциала У* при условии, что все вершины, кроме полюсов, имели в начальный момент потенциал, равный нулю. ■

ОПРЕДЕЛЕНИЕ'3. ЗадержаТГ/^^схемы 21нс есть время установления во всех ее вершинах потенциала^ :

Т(^хс) -/77СХХ 7{Ъ-} . ш

2леллс

. Сопоставим контактной схеме 2 некоторую ¡?С-схему следующим образом. Зафиксируем набор входных переменных . Каждый откритый контакт схемы ¿Г 'заменим на элемент, состояний из со-

противления у 2*змкостей. Получившуюся КС-е:гэму позовем остаточной схемой схемы <2Г при наборе и обозначим ¿Г^ •

ОПРЕДЕЛЕНИЕ 4.

Заде ржа контактной схемы 2! при

наборе входных переменных оС есть задержка ее остаточной схемы

Ъ(2, Т.) - . (2)

ОПРЕДЕЛЕНИЕ 5. Задержка контактной схемы £ есть Т(*Е) ~та* 1(2■ ■ (3)

о? >

ОПРЕДЕЛЕНИЕ 6. Задержка функции ^ есть .2Гре&лиэ. ^

ОПРЕДЕЛЕНИЕ 7. Функция Шеннона -задержки Х{р) есть

ОПРЕДЕЛЕНИЕ 8, Функция Шеннона для" опреде- .

ленного метода синтезаесть

(%■)■•>- - ■ (6)

X

где максимум берется по всевозможном схемам , построенным , по данному методу синтеза для всевозможных функций £ от./7 переменных. •

■ ■ Определим' теперь остаточную схему для МДП-схемы. ¡Это определение отличается от определения д'ля контактной схемы, так

как в ЦДЛ- схеме могут существовать транзисторы с неопределенной проводимостью.

В начальный момент времени в ВДП-схеме могут быть открыты некоторые транзисторы. Заменим их на сопротивления, им соответствующие, и припишем вершинам, им инцидентным, суммарные емкости элементов тех транзисторов, которые им инцидентны ( включая емкости затворов транзисторов, управляющихся этой вершиной ). ''Определим задержу каждой вершины как задержку вершины в произвольной И>схеме. Некоторые вершины получившейся КС-схемы могут быть'управляющими для транзисторов МДП-схе-мы. Начиная с момента к получившейся КС-схеме добавляется НС-схема, 'образованная транзисторами, ч.;. управляющимися вершиной 1Г и открывшимися в соответствии с функционированием схемы. Продолжая эту процедуру, мы можем в любой момент времени определить остаточную схемуЫДП-схемы .

Доказаны еледуювд: теоремы. •

ТЕОРЕМА 1, Напряжение в вершинах И}-схемы не может быть отрицательным. '

ТЕОРЕМА 2. Напряжение в вершинах ИЗ-схемы не может превышать напряжение питания. .

ТЕОРЕМА 3. Если сопротивление источника Г бесконечно мало, а емкость С бесконечно велика, то напряжение источника

¿/шт - Е - с&т £.

В третьей главе описывается алгоритм исследования переходных процессов в ЦЦП-схемах,• анализируются существующие ме-• тоды синтеза схем и предлагается метод синтеза схем, удовлетворяющий некоторым условиям.

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

• Справедлива следующая теорема.

ТЕОРЕМА 4. Существует алгоритм для вычисления задержек в вершинах ГС-схемы со сложностью, по порядку не- превышающей 0(лг^(л)} > где/7 - число вершин !?С-схемы, а сложность решения системы линейных алгебраических уравнений с /7 неизвестными.

Доказательство.

Будем помечать каждую вершину временем заряда до, Это время заряда зависит от ?ого, через какие вершины происходит заряд емкости, соответствующей данной вершине, поэтому оно может корректироваться по ходу работы алгоритма. Будем называть просмотренной вершину, • время заряда которой скорректировать' .уже невозможно, это и будет задержка в ней.

На первом шаге рассматриваем полюс. Считаем его просмотренным и помечаем задержкой Т-0 .

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

Рассмотрим процесс заряда данной вершины. Он осуществляется через смежные ей просмотренные вершины. Пусть они имеют задержки , ( в порядке возрастания ). Тогда заряд

рассматриваемой вершины с момента Т/ до момента происходит через Н-подсхему, образованную заряженными до и% вершинами к моменту ¿/, с момента ¿г до момента 2} - заряженными к моменту Тг , •••> с'момента ¿с до момента заряженными к моменту (с учетом изменения для рассматриваемой вершины начального значения потенциала в ней) ( см. примеры 1 и 2 ). Находим таким образом время заряда рассматриваемой вершины до^Лс и помечаем ее этим временем заряда, после чего переходим к следующей вершине, смежной с просмотренными, для нее повторяем описанную процедуру.

- 10 - \

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

■ Алгоритм заканчивается, когда просмотрены все вершины исследуемой RC-ехемы.

Оценим сложность описанного алгоритма

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

превосходите . '

i

Для каждого шага и для каждой смежной * с просмотренными вершинами 'требуется определить время ее заряда до^ж. Для этого ' требуется рассчитать эквивалентное сопротивление для смежных с нею просмотренных вершин, то есть решить систему П линейных алгебраических уравнений с П неизвестными. Смежных с просмотренными ьерший может '"Ть не более/7 , смежных с ними просмо-тренных-тоже не более П , но искать эквивалентное сопротивле-

а

ние может быть придется/7 раз.- На определение времени заряда до Ut и пересчета начального Потенциала требуется постоянное число операций,.не вависящее от/7 .

В итоге получаем сложность алгоритма Ofn^ff/t)) , где f(п) - сложность решения системы линейных алгебраических уравнений с П неизвестными.

ЗАМЕЧАНИЕ. Сложность алгоритма для расчета задержек можно уменьшить в Л раз, -если хранить в памяти список смежных вершин с временами их заряда через различные заряженные вершины, т. е. если иметь память й(пг) . .

■ ПРИМЕР i. Найти задержку RC-схемы, изображенной на рис.2, если напряжение питания £-ÍB , а пороговое напряжениеЩ

- и -

Решение.

Воспользуемся алгоритмом из т. 4 и примером 1. Сначала рассмотрим вершины, смежные с полюсом:

=/Оьэ, (?)

[ггг) - г. м -'?еп ^ г гг '/о'^сем). (в)

Т. к. ^{у^ЦЩ,то считаем г^Ц^ задержкой 1 вершины Т/ц-), а вершину просмотренной.

Посчитаем теперь, насколько зарядится 2 вершина за время

ТМ:

иг(Щ))г фо}е * у 4<гв . (9)

Начиная с моментаТ(тг4^ 2 и 3 вершины заряжаются' через Я-подсхемы, образованные полюсом и \ вершиной. Время заряда 3 вершины через сопротивление ЗкОм есть

(щ) ^ з ¿сем)., по)

£(тгг)г/.го'з./о'^п) . (И)

Т. к. ~£{гГг)< . то считаем 'Ц^+Т^) задержкой 2

вершины, а вершину 2 - просмотренной. 2&.Ц2Гг)=£.1125*/0~3 сек 3 вершина зарядится ( учитываем, что зарядка начинается лишь с момента ■ ) до

0,263 . (12)

Начиная с момента 3 вершина варякается через Р-под-

схему, образованную полюсом, 2 и 1 вершинайи. Время ее заряда

через сопротивление( см. пример 1, "где /? возьмем равным • '

I

гг'юЪ^е»'^ ~ 3.6>/0~9сек . (13) /

Отсюда 'Е-^-Т^Щ^^^ог^-М3* это И'будет задержкой в целом.

Ответ: 9. 025 нсек. Доказан ряд теорем.

ТЕОРЕМА Задержка цепочки из /7 последовательно соединенных простейших элементов имеет квадратичный по П порядок.

Рассмотрим метод синтеза контактных схем с томошыо совершенной дизъюнктивной нормальной формы. Для него имеем следующее утверждение.

ТЕОРЕМА б. Функция Шгннона ^(¡н^П) по порядку равна П2"\

Тс%Аер(п)~гП-П .

Для синтеза схем с помощью "дерева" имеем следующее ут-' верждение.

ТЕОРЕМА 7. Функция Шеннона синтеза "контактных схем с помощью контактного дерева по порядку равна Тку(*>)•.

п.г».

"Учитывая результат теоремы б,имеем следующее утверждение.

ТЕОРЕМА 8. Существует метод синтеза ( обратного контактного дерева ),такой, что в схеме, построенной по нему, задержка сигнала есть (?/у> г).

Рассмотрим метод Шеннона синтеза контактных схем. Он базируется на представлении функции Л переменных в виде

= V //ЙГ...&-, (14)

С?...

ТЕОРЕМА 9. Для функции Шеннона Тмш(^) задержки схем, построенных по методу Шеннона,

Попутно доказана и следующая теорема ( для

ТЕОРЕМА 10. Для синтеза контактных схем с помощью метода Шеннона существует такое К , при котором достигается минимум задержки и сложности.

Получим теперь нижнюю оценку задержки для метода Шеннона и убедимся, что она совпадает с верхней.

ТЕОРЕМА 11. '5ункция Шэннона Т/чш/'м) задержки контактных схем, построенных по методу Шеннона, по порядку равна 2." \

Рассмотрим метод Лупанова синтеза контактных схем.

ТЕОРЕМА 12. Задержка ¿^ (и) схем, построенных по методу Лупанова, есть О^-П^&^п) при асимптотически оптимальном методе.

Рассмотрим реализацию контактными функциями элементарной

- и -

конъюнкции П переменных:

ТЕОРЕМА 13. Любая проводящая цепь в схеме . реализующей конъюнкцию /? переменных (22), имеет длину, не меньшую чем в П контактов.

Как уже отмечалось ( теорема б ), реализация элементарной конъюнкции П контактами имеет задержку, по порядку равную/?2. Попытаемся уменьшить задержку, построив другую схему для - реализации той же функции.

, ТЕОРЕМА 14. Существует, схема, реализующая элементарную конъюнкцию П переменных и имеющую задержку, по порядку равную

Покажем теперь, что нельзя получить задержки, меньшей по порядку, чем П ■

ТЕОРЕМА 15. Задержка элементарной конъюнкции П переменных имеет линейный по/7 порядок.

Рассмотрим теперь произвольную контактную схему.. ТЕОРЕМА 16. Существует метод синтеза контактных схем для функции П переменных, дающй линейную по П задержу.

Объединяя теоремы 15 и 16,получаем следующее утверждение: . ОСНОВНАЯ ТЕОРЕМА 1?. Функция Шэннона 1(ъ) в классе конта-' кгных схем имеет линейный порядок по П ',

ЛЕША 1. Если степень выхода параллельно-последовательной КС-схемы, составленной из одинаковых сопротивлений 1 , есть*, то ее сопротивление не может быть меньше, чем .

/7.

Т' (») СГ п .

(17)

Доказательство.

Проведем доказательство теоремы индукцией по степени выхода.

Для К:/ схема состоит из некоторой схемы, и соединенного с ней последовательно ребра и имеет очевидно сопротивление не меньше, чем сопротивление этого ребра.

Пусть схема 2. со степенью выхода к получена из двух схем и' склейкой. Пусть степени выхода схем 2Г, и £ к>7>, а их сопротивления -/?✓ и/?г соответственно.

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

л*=/?7 и Я* Яг+Яг^-Яг^'я; ?* (18)

В случае параллельной склейки имеем

Яг - с / Яг

/? " Ж Кг ~ С «

»

(20)

что и требовалось доказать.

СЛЕДСТВИЕ. В классе параллельно-последовательных схем задержка схемы, реализующей'конъюнкцию /7 переменных, имеет линейный по /7 порядок.

Доказательство.

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

вершины

Но сопротивление Н-подсхемы по лемме 1 не меньше^ довательно»

2/г^/.

Рассмотрим теперь алгоритм расчета задержек в комбинационных ( без обратной связи ) ВДД-схемах на'основании одной из их математической модели и гипотезы последовательного заряда. МДП-транзистору сопоставляемся помеченный граф иа трех вершин и одного ребра. Вершины соответствуют трем полюсам транзистора, а ребро соединяет вершины, соответствующие стоку и истоку. Вершина, соответствующая затвору, несет две пометки. Первая из них есть либо число, либо символ некоторой функции алгебры логики, а вторая, как-и пометки стока и истока, соответствует емкости соответствующего узла транзистора.

Ребро помечено символом р или Л ( по типу канала ),. пометкой затвора и значением сопротивления канала транзистора. Несколько транзисторов, соединенных вместе, образуют ЩП-схе-му»

функционирование схемы состоит в передаче нулевого и единичного потенциалов от входов к выходам. Для каждого набора значений входных переменных ,„ «¿„"¡^¿б {0,<} . для каж-

дой вершины"схемы 2" в казкдьй момент времени Ь^О . определим значение потенциала, равное О ( низкое ), 1 (высокое ) и ~ С неопределенное ). Для набора в каждый момент времени.

0 потенциалы входов 0 и 1 равны О и 1 соответственно, а

, еле-

С 22)

потенциалы входовXI, XI, ¿-^л?, равны ¿/ о£г . Потенциалы остальных вершин в момент £ -О не определены. Потенциалы вершин схемы в моменты определим по индукции.

МДП-схеме в каждый момент времени соответствует остаточная (?С-схема, образованная всеми вершинами МЦП-схемы и ребрами, соответствующими открытым в этот момент транзисторам. Транзистор р -типа считается открытым, если он управляется либо переменной, имеющей нулевое значение,-либо вершиной, имеющей потенциал, не превышающий порогового значенияТранзистор /7-типа считается открытым, если он управляется либо переменной, имеющей единичное значение, либо вершиной, имеющей потенциал, не меньший порогового значения Л У . Распространение сигнала по остаточной й>схеме аналогично уш описанному алгоритму.

Компьютерное моделирование позволяет подтвердить теорети-

*

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

Автором проведено компьютерное моделирование алгоритма вычисления задержек в соответствии с гип'отезой последовательного заряда

. В качестве входной информации для программы используется задание йС-схемы ее матрицей смежности для сопротивлений и массивом для емкостей. При этом, в качестве первой.вершины задается полке схемы, а 'в качестве последней - ее выход ( то есть вершина, в которой требуется рассчитать задержу ). Программа легко модифицируется для расчета задержек во всех вершинах ЯС-ехемы. Кроме указанной информации вводятся значения напряжения питания и порогового напряжения Мс.

В четвертой главе исследуются макромодели схем и доказываются некоторые утверждения о макромоделировании.

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

Ограничимся в дальнейшем рассмотрением макромоделей для схем с одним входом, в котором не существует емкости, и одним выходом.

Макромоделирование предполагает наличие;

1) некоторого класса Л' моделируемых схем;

2) некоторого подклассасхем, называемых моделирующими;

3) множества операций0-{0?1} над схемами из Н , ставящими в соответствие совокупности схем ^.„^.пч схему

из класса к ;

•4)' основной характеристики схемы 21 из )< , относительно которой ведется макромоделирование. В рассматриваемом нами ' случае роль 2"/2Г)играет время установления потенциала ¿/% в выходе ИС-схеш Е , т.е. задержка схемы 2 .

• ОПРЕДЕЛЕНИЕ 9. Макромоделью для четверки/А\м,0,Т) называется такое отображение , что выполняются следующие условия: • *

2) ?(Р{21)) = для всех £ £ Ы у

3) ... Z„i)) = rt(0?i(F(z<l.f/Z»L))) Ш всех

О^Е-О и всех совокупностей схем/Е-,.,, v&H , к. которым

применима операция Vi .

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

ЗАМЕЧАНИЕ. В определении макромодели для четверки^Л££?2^ предполагается, чтоMz-к? , т.е. что класс моделей не выходит . из класса моделирующих схем. Это обстоятельство позволяет рассматривать кратное моделирование в сочетании с применением операций к моделирующим схемам.

Условие 3) определения 9 в ряде случаев может оказаться слишком жестким и приводить к несуществованию макромоделей. Можно ослабить это условие, введя следующее понятие приближенной макромодели.

ОПРЕДЕЛЕНИЕ 9'. Приближенной макромоделью для четверга {М,М(Р, X) называется такое отображение , что вы-

полняются условия 1) и .2) из определения 9 и, кроме того, существуют такие положительные Константин// и cf[ , что выполняются следующие неравенства: ' •

3-) J' г. + c¡)

- т/orfrfz,),,, r/zml)» - 0fL-

ЗАМЕЧАРИЕ. В принципе аналогичная замена возможна и в

пункте . 2) определения 9. •

Определим операции над RC-схемами. Пусть даны двухполюсные схемы ¿í, и ¿Ег •

01РЕДЕЛЕНИ5 10. Схема Т- 0-${Ъ,Тг ^называется результатом последовательной склейки, схем 2Г, и 2Гг , если она получается отождествлением в«.лОда схемы ¿Г/ с входом схемы 'и припи-

снванием этой вершине емкости выхода схемы X/ • Входом схемы 2" является вход схемы , а выходом - выход схемы "Ег.

ОПРЕДЕЛЕНИЕ 11. Схема X -¿^/Доказывается результатом параллельной склейки схем 5?, и "£г , если она получается отв-.ждествлекием попарно входов и выходов схем и 2Гг (получавшемуся выходу схемы £ приписывается сумма емкостей . схем Г, и гг )•

'1Г иг)

ОПРЕДЕЛЕНИЕ 12. Схема Т.-Ц^ получается из схемы заменой ее ребра/г^ ш) на схему£"г , если ребро¿сУзаменя- ' ется на схему . вершине приписывается ее емкость в схеме^ , а вершине - сумма ее емкости в схеме 21 ( и емкости выхода схемы ¿Ег .

Рассмотрим макромоделиро^ание произвольных ЯС-схем НС-схемами, имеющими одно ребро, соединяющее вход и выход схемы. Назовем такие схемы двухузловыми и обозначим их класс через Т. класс всех двухполюсных схем обозначим через V.

Доказан ряд теорем по макромоделированию КС-схем.

ТЕОРЕМА 18. Не существует макромодели для четверки

Зададим теперь отношение порядка на множестве вершин (ад-схемы.

ОПРЕДЕЛЕНИЕ 13. Вершина V ЯС-схемы 2Г называется предшествующей вершине КГ (2/4 И/' ), если существует кратчайшая по числу ребер цепь, соединяющая вершину ЬУ с - входом схемы и проходявзя через 7/" ■

ОПРЕДЕЛЕНИЕ 14. Назовем КС-схему ¿Г ранжируемой, если'- на множестве ее вершин-можно задать целочисленную функцию 2{х)так, что ' ■ . ■

г)1(гг):0тот№ и только тогда, когда V- вход схемы 2";

2) если 1М и и не существует третьей вершины 2б^такой,

- 21 -

что тм ИГ И ЪСГ< и. то ¿/¿V-

ОПРЕДЕЛЕНИЕ 15. Назовем ЙС-схемы Е/ и изоморфными, если изоморфны их графы, причем пометки соответствующих вершин и ребер равны между собой, входам схемы 5/. соответствуют входы схемы • а выходам -' выходы.

ОПРЕДЕЛЕНИЕ 16. Назовем двухполюсную RC-cxeмyZ симметричной, если она ранжируема и,- кроме того, для любых двух зер-пин одного ранга существует автоморфизм схемы ЛГ , переводящий эти вершины друг в друга, причем максимальный ранг имеет только выход схемы .

Обозначим класс симметричных КС-схем, имеющих более одного ребра,через 2Г •

Верна следующая лемма.

ЛЕММА 2. Задержки вершин одного ранга симметричной Р.С-схемы ¿1 равны между собой.

Для симметричных 1?С-схем определим операции последовательной склейки двух схем И 2Гг : 2"г) • параллельной склейки А7 изоморфных схем ¿ЕГ : Ор(Е) и подстановки КС-схемы вместо всех ребер, соединяющих.вершины двух соседних фиксированных рангов I и 1+г схемы 2Г,: От,("¿.г)> сохраняющие свойство симметричности.

Рассмотрим макромоделирование РС-схем ИЗ-схемами, имеющими два последовательно соединенных ребра, соединяющих полюса схемы. Назовем такие схемы трехузловыми и обозначим их класс через Т'

ТЕОРЕМА 19. Существует макромодель для четверки

Перейдем теперь, к рассмотрению приближенной макромодели.

ТЕОРЕМА 20. Не существует приближенной 'макромодели для четверки (V, Г £>1, Т) •

- 22 -

В заключении анализируются результаты проведенного исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Выявлены тенденции развития исследований по вопросам анализа электрических схем со структурой МДП.

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

3. Обоснована возможность использования дискретного подхода к анализу ВДП-схем.

4. Определено, понятие НС-схемы, позволяющее упростить ' рассмотрение переходных процессов в ЩП-схемах и задержек

распространения электрического сигнала по схеме во времени.

5. Доказан ряд теорем, описьгзющих функционирование схем, рассматриваемых в диссертации.

6. На основании исследований ЙС-схем с простой структурой предложена моделд их" функционирования, позволяющая применить дискретные методы к анализу КС-схем, получающихся при моделировании ЩЩ-схем.

7. Разработан алгоритм для анализа ЙС-схем к - проведены оценки его сложности.

8. Проведен расчет задержек и функции Шеннона для . КС-схем, получающихся при синтезе контактных схем с помощью различных методов.

9. До:сазаны теоремы, позволяющие оценить снизу задержку и предложить оптимальный по.быстродействию схем метод синтеза контактных схем. ' .' ' . '. ■.

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

- 23 -

классу рассматриваемых КС-схем.

11. Доказаны некоторые теоремы о существовании макромоделей и приближенных макромоделей для НС-схем. •

12. Предложена макромодель для одного класса КС-схем.,

Основные положения диссертационной работы. отражены: в.слег. дующих работах:

1. Пшеннов Д.Е.Некоторые вопросы.эквивалентных.преобразований Й>схем//Прикладная математика и математическое ■•.обеспечение ЭВМ. -М.: Изд-во Моск. ун-та, 1985. -С. 49-50.

2. Пиеннов Д. Е. Мэдели для. анализа КЩШ-схем//Чис- . ленные методы математической физики. - М.: Изд-во. Моек, ун-та, 1986.-С. 118-120.

3. Шеннов Д.Е. Вопросы задержек в ЩП-схемах//Некоторые. вопросы вычислительной математики, математической физики и программного обеспечения ЭВМ. - М.; Изд-во Шек. ун-та, 1987. -С. 47-49.

4. Шеннов Д.Е. Модели МДП-схеы.-//Седьмая Моск. город, конф. молодых ученых и специалистов по пробл. кибернетики и вычисл. техники. - Е , НПО АСУ"Москва", 1989.-0.38-40.