Содержание к диссертации
ВВЕДЕНИЕ 6
1. АНАЛИЗ АЛГЕБРАИЧЕСКИХ ОСНОВ СУЩЕСТВУЮЩЕЙ
ТЕОРИИ ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО
ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ СТРУКТУР 15
Последовательность изложения результатов 15
Определение области исследований 16
Краткий обзор развития теории и методов
логического проектирования цифровых устройств 19
1.4. Абстрактные алгебраические системы, используемые
для анализа и синтеза цифровых структур 25
Структура алгебраических систем 25
Булева решетка 26
Булево кольцо 33
Булево линейное пространство 33
Взаимосвязи между булевыми решетками, кольцами и пространствами 34
1.5. Определение требований к математическому аппарату
логического синтеза цифровых структур 35
1.6. Анализ особенностей существующих методов логического
проектирования компонентов СБИС 41
Общие положения 41
Декомпозиция логических функций 43
Время-структурная оптимизация логических схем . .46
Логический синтез цифровых устройств
на основе конструктивно-технологических элементов 48
1.7. Выводы 50
2. РАЗРАБОТКА МАТЕМАТИЧЕСКИХ ОСНОВ ТЕОРИИ
ЛОГИЧЕСКОГО СИНТЕЗА КОМПОНЕНТОВ БИС
В ЛИНЕЙНЫХ ПРОСТРАНСТВАХ 53
Последовательность изложения результатов 53
Разработка методологии логического синтеза
в линейных пространствах 55
Принцип полноты использования значности логики 55
Принцип гибридности набора операций представления логических функций 61
Принцип разностного представления
результатов синтеза 63
2.2.4. Принцип послойности реализации логических функций. . . .65
2.3. Исследование линейного пространства над полем
вещественных чисел 66
2.3.1. Определение линейного пространства
с булевыми компонентами 66
2.3.2. Отображения линейных подпространств 70
2.4. Исследование аффинного пространства над полем
вещественных чисел 81
2.5. Выводы 93
3. РАЗРАБОТКА МЕТОДОВ ЛОГИЧЕСКОГО
ПРОЕКТИРОВАНИЯ КОМПОНЕНТОВ БИС
В ЛИНЕЙНЫХ ПРОСТРАНСТВАХ 94
Последовательность изложения результатов 94
Разработка общих вопросов логического синтеза
цифровых структур в линейных пространствах 95
3.2.1. Исследование циклических векторов
в линейных пространствах 95
3.2.2. Разработка логических базисов
линейного пространства 119
3.2.3. Исследование монотонных векторов
4
линейного пространства 141
3.3. Разработка методов логического синтеза
цифровых структур в линейных пространствах 168
3.3.1. Матричный метод логического синтеза
цифровых структур 168
3.3.2. Табличный метод логического синтеза
цифровых структур 170
3.3.3. Аналитический метод логического синтеза
цифровых структур 177
Пороговое представление логических функций 179
Логический синтез последовательностных схем. 202
Логический синтез комбинационных схем 225
Логический синтез аналогово-цифровых схем 237
О синтезе систем 241
Выводы 242
4. СТРУКТУРНЫЙ СИНТЕЗ КОМПОНЕНТОВ БИС
В ЛИНЕЙНЫХ ПРОСТРАНСТВАХ 243
4.1. Последовательность изложения результатов 243
4.2. Структурный синтез двузначных цифровых структур 247
Общие положения 247
Разработка структурной реализации компонентов
БИС на основе линейного подхода 252
4.2.3. Разработка структурной реализации компонентов
БИС на основе порогового подхода 260
4.3. Выводы 267
5. ПРИМЕНЕНИЕ ПРЕДЛАГАЕМОЙ ТЕОРИИ ЛОГИЧЕСКОГО
СИНТЕЗА ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ПРОБЛЕМ 269
Последовательность изложения результатов 269
Схемотехническое проектирование ТТЛ-схем 271
Схемотехническое проектирование ЭСЛ-схем 284
Оценка эффективности получаемых
схемотехнических решений 287
Разработка программы автоматизации логических преобразований 290
Синтез канала связи с повышенной
достоверностью передачи 297
5.7. Выводы 306
ЗАКЛЮЧЕНИЕ 307
ЛИТЕРАТУРА 311
Введение к работе
Развитие теории и техники логического синтеза и реализации цифровых компонентов БИС и СБИС определяется состоянием развития теории, методов и средств проектирования цифровых устройств. Определяющими факторами этого развития являются логико-математические возможности алгебраических систем, положенных в основу разработки методов логического проектирования и систем проектирования на их основе.
К настоящему времени в разработке БИС и СБИС сложилась ситуация, говорящая о том, что все успехи в повышении сложности и улучшении характеристик БИС и СБИС достигнуты за счет развития технологии и технологических САПР. Функционально-логическое же проектирование развивается гораздо медленнее. Поэтому становится настоятельным исследование возможностей улучшения технических, технологических и эксплуатационных характеристик БИС и СБИС за счет совершенствования методологии логического проектирования и создания новых САПР функционально-логического проектирования на основе этих новых возможностей.
Математической основой реализации БИС и СБИС до настоящего времени является булева алгебра. Ее возможности как алгебраической основы функционально-логического проектирования, хорошо изучены и использованы в полном объеме. Следовательно, совершенствование функционально-логического проектирования цифровых структур возможно только путем создания функционально-логического обеспечения САПР на основе новых алгебраических структур. Поэтому исследование новых для целей логического синтеза алгебраических структур, разработка теории логического синтеза на их основе и создание математического обеспечения функционально-логического проектирования САПР БИС и СБИС является актуальной и важной задачей.
7 Целью исследования настоящей диссертационной работы является разработка нового научного направления в области логического проектирования -разработка математического обеспечения электронных САПР (ECAD-систем) на основе математического аппарата линейных пространств.
Указанная цель достигается решением следующих проблем: \J
Постановка проблемы дальнейшего повышения логической мощности и улучшения технологических и эксплуатационных характеристик БИС и СБИС.
Исследование линейного пространства с булевыми компонентами как абстрактной алгебраической структуры, в том числе:
разработка алгебраической структуры «линейное пространство с булевыми компонентами на множестве -значных логических функций».
разработка методов формирования классов монотонных и циклических векторов линейного пространства на множестве -значных логических функций.
разработка методов отображения логических векторов линейного пространства на множестве &-значных логических функций в алгебраическую сумму большей, данной и меньшей значности.
исследование аффинных пространств, связанных с линейными, и разработка методов порогового представления логических функций.
разработка методов формирования базисов линейного пространства на множестве А>значных логических функций в виде набора циклических срезов векторов и использование их для представления реализуемых логических функций.
3. Разработка методологии функционально-логического проектирования
компонентов БИС и СБИС в САПР на основе предлагаемой алгебраической
структуры, в том числе:
- разработка методов синтеза комбинационных, последовательностных и
аналогово-цифровых схем.
8 - разработка методов минимизации логических функций и структурного
синтеза автоматов с использованием преобразования значности.
Разработка методологии схемотехнической реализации компонентов БИС и СБИС в САПР на основе предложенного математического аппарата.
Разработка в виде модуля САПР программы логических преобразований, выполняемых в предложенной алгебраической структуре в процессе функционально-логического проектирования.
В качестве методов исследования в процессе выполнения исследований в диссертационной работе использованы теория множеств, математическое программирование, теория графов, алгебраические основы теории логического проектирования цифровых структур, теория вероятностей, методы системного и объектно-ориентированного анализа, теория линейных и аффинных пространств.
Научная новизна работы состоит в теоретическом обобщении и решении крупной научной проблемы, имеющей важное народнохозяйственное значение в области разработки математического обеспечения САПР и методов функционально-логического проектирования БИС и СБИС. В этом плане в процессе проведения исследований решены следующие проблемы:
Разработана прикладная математическая модель - линейное пространство на множестве &-значных логических функций. Определены зависимости, связывающие операции линейного пространства с логическими операциями. Исследованы свойства некоторых типов логических векторов, в частности, монотонных и циклических векторов и их срезов. Разработаны способы отображения логических векторов данной размерности (значности) в совокупность векторов другой (большей или меньшей) размерности.
Разработаны способы представления логических функций в предложенной структуре. Предложены методы структурного и логического синтеза комбинационных, последовательностных и аналогово-цифровых схем на основе предложенной алгебраической структуры.
3. Предложены схемотехнические решения цифровых структур в предло
женной структуре, обеспечивающие меньшие по сравнению с существующими
аппаратурные затраты и более высокую надежность функционирования в жест-
ф ких условиях эксплуатации.
4. Разработана программа логических преобразований функций, реали
зующая теоретические результаты логического проектирования компонентов
БИС.
Решение поставленных задач позволяет автору защищать следующие новые научные результаты:
1. Основы теории логического проектирования цифровых структур на ос
нове новой алгебраической структур - линейного пространства с булевыми
* компонентами.
Методы логического синтеза цифровых структур в линейных пространствах.
Математическое обеспечение САПР на основе новой теории логического проектирования цифровых структур.
Методологию схемотехнического проектирования цифровых структур на основе математического аппарата линейных пространств с булевыми компо-нентами.
Практическая ценность. На основе результатов исследований, проведенных в диссертационной работе, разработана программа логических преобразований, выполняемых в процессе в процессе функционально-логического проектирования. Она может быть использована в качестве функционального модуля любой из существующих САПР цифровых БИС и СБИС.
Получены схемные решения компонентов цифровых БИС. Предложенная методология функционально-логического проектирования обеспечивает полу-чение схемотехнических решений с улучшенными характеристиками по аппаратным затратам, технологичности, надежности и энергопотреблению.
10 Результаты работы могут также найти применение при решении любых
проблем, в которых в качестве инструмента используется аппарат математической логики. Например, на основе разложения произвольной функций в алгебраическую сумму монотонных предложен метод повышения достоверности передачи данных.
Реализация результатов работы. Теоретические и практические результаты, полученные в диссертационной работы использованы в 6 научно-исследовательских и опытно-конструкторских работах, выполненных в НКБ «Миус» ТРТУ в 1974 - 2002 г.г. для НПК «Энергия», г.Королев, и для ОКБ ТК, г. Тула, а также в ТФ ОАО НИИС, г. Таганрог, что подтверждено соответствующими актами внедрения и использования.
Апробация работы. Основные результаты диссертационной работы докладывались на III Всесоюзной конференции по проблеме "Однородные вычислительные системы и среды" (Таганрог, 1972), Всесоюзном совещании-семинаре "Математическое, программное и техническое обеспечение систем автоматизации проектирования радиоэлектронной аппаратуры" (Сочи, 1978), докладов I Всесоюзной конференции СУПЕР ЭВМ, Минск, 1978, IX Всесоюзной научной конференции по микроэлектронике (Казань, 1980), X Всесоюзной конференции по микроэлектронике (Таганрог, 1982), Всесоюзной конференции "Состояние и перспективы развития микроэлектронной техники" (Минск, 1985), VII Всесоюзной школе-семинаре "Распараллеливание обработки информации" (РОИ-89) (Львов, 1989), 1-й Всесоюзной конференции "Однородные вычислительные среды и систолические структуры" (Львов, 1990), Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места" (Таганрог, 1995 * 1999), международной, научно-технической конференции «СуперЭВМ и многопроцессорные вычислительные системы» (Таганрог, 2002), международной конференции «Континуальные алгебраические логики, исчис-
ления и нейроинформатика в науке, технике и экономике» «КЛИН-2003» (Ульяновск, 2003).
Публикации. По теме диссертации опубликовано 50 научных работ, в том числе одна монография и 18 авторских свидетельств на изобретения.
Объем и структура диссертационной работы. Диссертация состоит из введения, пяти глав и заключения. Она содержит 330 страниц, 148 рисунков и 28 таблиц. Список литературы насчитывает 186 наименований.
Изложение результатов проведенных исследований ведется в следующей последовательности.
В разделе 1 рассмотрены некоторые особенности используемого в настоящее время для целей логического синтеза математического аппарата и основанных на нем методов логического синтеза цифровых структур. Это далеко не полное рассмотрение имеет целью не столько рассмотреть современное состояние развития методов логического синтеза, сколько указать на особенности алгебраических структур, положенных в основу современной теории логического синтеза, определяющих (и ограничивающих) возможности современных методов логического синтеза цифровых структур. На основе проведенного анализа делаются выводы относительно свойств алгебраических структур, которые могли бы стать основой новой теории и методов логического синтеза цифровых структур, обладающих большей степенью универсальности по отношению к значности синтезируемых цифровых структур и способных улучшить технические параметры БИС. Рассмотрены также задачи логического проектирования, решаемые в современных ECAD.
В разделе 2 рассмотрены методологические принципы и математические основы построения предлагаемой структуры - линейного пространства с булевыми компонентами и связанного с ним аффинного пространства. Методология определяет предлагаемый вариант обобщения двузначных моделей и методы синтеза цифровых структур, положенные в основу разрабатываемого подхода.
12 Анализ этих принципов позволил сделать положительные выводы относительно их дальнейшего использования.
Затем рассмотрены свойства предлагаемой структуры и ее связи, как с обычным линейным пространством, так и с алгебраическими структурами типа булевых алгебр. Выделены два вида векторов этого пространства - монотонные и циклические, свойства которых позволили использовать их для последующей разработки методологии синтеза цифровых структур произвольной значности. Рассмотрено отображение булева линейного пространства на аффинное пространство и возможности использования этого отображения для представления одного из важных классов логических функций - пороговых. Установлены также связи между операциями предлагаемой структуры и известными алгебраическими структурами, используемыми для целей логического синтеза. На основе проведенного анализа делается вывод о целесообразности и перспективности использования линейного пространства в качестве исходной алгебраической структуры для создания теории и методов логического синтеза цифровых и цифроаналоговых структур.
В разделе 3 описывается методология и процедуры логического синтеза цифровых схем на основе предлагаемой структуры. В частности, рассмотрены:
проблема формирования базисов для логического синтеза и использования их для представления логических функций;
методы представления логических функций в виде, удобном для реализации с учетом логических и технологических особенностей реализации описываемых ими цифровых устройств, как известные - матричное, табличное и пороговое, так и специфичное для предлагаемого подхода - аналитическое на основе уравнения функционирования синтезируемого цифрового устройства;
реализация способов представления логических функций с произвольными сочетаниями значностей функции и аргументов, что дает возможность решать, например, задачу логического проектирования многозначных устройств на двузначной элементной базе.
13 - разработка методов логического синтеза цифровых и цифроаналоговых
схем на основе разработанного математического аппарата.
Полученные здесь результаты дают основание сделать выводы относительно логической эффективности предлагаемого подхода к созданию теории логического синтеза цифровых структур на основе линейного пространства.
