автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Основы теории логического синтеза компонентов СБИС в линейных пространствах

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

Чернов Николай Иванович

УДК 681.325.65.053:519.713

ОСНОВЫ ТЕОРИИ ЛОГИЧЕСКОГО СИНТЕЗА КОМПОНЕНТОВ СБИС В ЛИНЕЙНЫХ ПРОСТРАНСТВАХ

Специальности

05.13.12 - Системы автоматизации проектирования

05.13.05 — Элементы и устройствавычислительной техники и систем управления

АВТОРЕФЕРАТ

диссертации на соисканиеученой степени доктора технических наук

ТАГАНРОГ-2004

Работа выполнена в Таганрогском Государственном радиотехническом университете.

Научный консультант - доктор технических наук,

профессор КУРЕЙЧИК В.М.

Официальные оппоненты: - Лауреат премии президента РФ,

доктор технических наук, профессор ВАГИН В.Н.

доктор технических наук, профессор ИВАНЧЕНКО В.Н.

доктор технических наук, профессор БЕРШТЕЙН Л. С.

Ведущая организация: Российский научно-исследовательский

институт информационных технологий и автоматизации проектирования Минпромнауки РФ.

Защита диссертации состоится «_»_2004 г. в 14 час. 00

мин. на заседании диссертационного Совета Д 212.259.03 в Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, ГСП-17А, пер. Некрасовский, 44.

С диссертацией можно ознакомиться в библиотеке Таганрогского государственного радиотехнического университета, г. Таганрог, ул. Чехова, 22.

Автореферат разослан

2004 г.

Ученый секретарь, диссертационного Совета, доктор технических наук, профессор

А.Н. Целых

Общая характеристика работы

Актуальность темы. Развитие теории и техники логического синтеза и реализации цифровых устройств определяется двумя основными и взаимосвязанными факторами:

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

- состоянием развития технологии изготовления таких устройств.

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

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

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

К настоящему времени в разработке БИС и СБИС сложилась ситуация, говорящая о том, что все успехи в повышении сложности и улучшении характеристик БИС и СБИС достигнуты за счет развития технологии и конст-рукторско-технологических технологических САПР. Функционально -логическое же проектирование развивается гораздо медленнее.

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

1. До 80% полезной площади кристалла современной БИС-занимают соединения между компонентами. Если на начальном этапе становления микроэлектроники кристалл ИС представлял собой множество элементов, соединенных линиями связи, то современный кристалл - это паутина проводов, в которую изредка вкраплены элементы. С ростом сложности эта доля может только увеличиваться.

2. До 75% потребляемой БИС мощности расходуется на перезаряд емкостей линий связи в кристалле. С ростом сложности кристалла эта доля также может только возрастать.

Поэтому представляет интерес исследование возможностей улучшения технических, технологических и эксплуатационных характеристик БИС и СБИС за счет совершенствования методологии логического проектирования и создание новых САПР функционально-логического проектирования на основе этих новых возможностей.

Основными проблемами улучшения характеристик БИС можно считать:

- уменьшение количества активных и пассивных элементов;

уменьшение количества связей;

ЮС. НАЦИОНАЛЬНАЯ]

сиелпотека слюр: 05 О^

1

- повышение технологичности;

- повышение эксплуатационной надежности.

Возможными решениями этих проблем могут быть соответственно:

- устранение функциональной нагруженности компонентов;

- многозначное внутреннее представление информации;

- уменьшение числа нетехнологичных компонентов;

- использование представлений логических функций, повышающих надежность функционирования БИС.

Средствами решения перечисленных проблем в настоящей работе выбраны:

- гибридный (т.е. состоящий не только из логических операций) базис логического проектирования;

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

- замена пассивных компонентов активными;

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

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

- неиспользование достижений современной технологии в отношении повышения точности и повторяемости параметров компонентов на кристалле для повышения показателей качества БИС;

- неадекватность логических операций функциональным операциям, используемым для реализации логической функции, реализуемой БИС;

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

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

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

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

Еще одно обстоятельство, определяющее ограниченность традиционного подхода к проблематике логического синтеза, состоит в замкнутости любой из используемых алгебраических структур. Это не позволяет рассматривать синтез логических схем с разной значностью, например, входа и выхода, либо внешнего и внутреннего представления информации, АЦП и т.д.

Таким образом, рассмотрение проблемы совершенствования функционально-логического проектирования цифровых структур приводит к необходимости создания САПР на основе новых алгебраических структур. Такие попытки предпринимались и ранее. Главной особенностью этих попыток было использование для реализации логических преобразований помимо булевых операций других, в частности, арифметических операций. Эта особенность отражает попытки использования достигнутых технологией точности и повторяемости параметров компонентов для уменьшения аппаратурных затрат на преобразование функциональных операций в логические: арифметические операции оперируют с количественными данными. Теоретическое единство обоих видов операций должно иметь место, видимо, в логическом синтезе формальных нейронов, хотя аппаратная их реализация еще далека от практического использования этого единства.

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

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

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

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

3. Проблема громоздкости процедур синтеза здесь может быть обойдена естественным образом путем использования аналитического представления закона функционирования синтезируемого устройства (например, с помощью численных методов). Дело в том, что представление логической функции в линейном пространстве естественно «ближе» к обдчной аналитической записи за счет того, что аддитивные операции являются в то же время и операциями линейного пространства. Еще одна возможность состоит в использовании представления закона функционирования в виде матрицы от матриц. Это, конечно, не уменьшает объема вычислений, но обеспечивает экономное исходное представление и стандартизацию процедур его обработки при проектировании не только компонентов (одновыходных цифровых структур), но и систем (многовыходных цифровых структур) .

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

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

6. Алгебраическое единство линейного и аффинного пространств является основой разработки методов линейного и порогового представления логических функций и порогового синтеза.

7. Еще одна проблема, решаемая путем использования предлагаемой алгебраической структуры - это проблема повышения надежности функционирования цифровых структур. Суть ее в том, что описание логической функции в виде вектора линейного пространства в некотором базисе:

где - суммы положительных и отрицательных термов,

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

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

Цель и задачи исследования. Целью исследования в настоящей диссертационной работе является разработка теории фунционально-логического проектирования компонентов СБИС и математического обеспечения электронных САПР (ЕСАО-систем) на основе математического аппарата линейных пространств.

Указанная цель достигается решением следующих проблем:

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

2. Разработка основ теории логического и структурного синтеза цифровых структур в линейных пространствах, в том числе:

- разработка алгебраической структуры «линейное пространство с булевыми компонентами на множестве Л-значных логических функций».

- разработка методов формирования классов монотонных и циклических векторов линейного пространства на множестве &-значных логических функций.

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

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

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

3. Разработка методологии функционально-логического проектирования компонентов БИС и СБИС в САПР на основе предлагаемой алгебраической структуры, в том числе:

- разработка методов синтеза комбинационных, последовательностных и аналогово-цифровых схем.

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

4. Разработка методологии схемотехнической реализации компонентов БИС и СБИС в САПР на основе предложенного математического аппарата.

5. Разработка в виде модуля САПР программы логических преобразований, выполняемых в предложенной алгебраической структуре в процессе . функционально-логического проектирования.

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

мирование, теория графов, алгебраические основы теории логического проектирования цифровых структур, теория вероятностей, методы системного и объектно-ориентированного анализа, теория линейных и аффинных пространств.

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

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

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

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

4. Разработана программа логических преобразований функций, реализующая теоретические результаты логического проектирования компонентов БИС.

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

1. Основы теории логического проектирования цифровых структур на основе новой алгебраической структур - линейного пространства с булевыми компонентами.

2. Методы логического синтеза цифровых структур в линейных пространствах.

3. Математическое обеспечение САПР на основе новой теории логического проектирования цифровых структур.

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

Практическая ценность. На основе результатов исследований, проведенных в диссертационной работе, разработана программа логических преобразований, выполняемых в процессе в процессе функционально-

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

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

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

Реализация результатов работы. Теоретические и практические результаты, полученные в диссертационной работы использованы в 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 авторских свидетельств на изобретения. Список основных работ по теме диссертации приведен в конце автореферата.

Объем и структура диссертационной работы. Диссертация состоит из введения, пяти глав и заключения. Она содержит 340 страниц, 148 рисунков и 28 таблиц. Список литературы насчитывает 186 наименований.

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

Во введении обосновывается актуальность работы, определяется объект исследования, формулируется цель исследования — разработка алгебраической системы для использования в качестве основы математического обеспечения САПР, которая:

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

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

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

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

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

В РАЗДЕЛЕ 1 рассмотрены некоторые особенности используемого в настоящее время для целей логического синтеза математического аппарата и основанных на нем методов логического синтеза цифровых структур. Это далеко не полное рассмотрение имеет целью указать на особенности алгебраических структур, положенных в основу современной теории логического синтеза, которые определяют (и ограничивают) возможности современных методов логического синтеза цифровых структур. На основе проведенного анализа делаются определенные выводы относительно свойств алгебраических структур, которые могли бы стать основой новой теории и методов логического синтеза цифровых структур, обладающих большей степенью универсальности по отношению к значности синтезируемых цифровых структур и способных улучшить технические параметры БИС.

Подраздел 1.1. посвящен постановке задачи исследования существующего математического аппарата теории логического синтеза цифровых устройств. Эти задачи формулируются следующим образом:

- рассмотрение исходных понятий абстрактной алгебры как математического аппарата теории логического проектирования;

- рассмотрение алгебраических моделей, наиболее часто применяемых в теории логического проектирования;

- методологические основы некоторых наиболее известных методов логического синтеза двузначных и многозначных цифровых структур.

Подраздел 1.2. — это краткий обзор развития методов логического проектирования цифровых устройств. Здесь упомянуты существующие подходы к синтезу, в том числе двузначная, £-значная, и пороговая логики.

Подраздел 13. посвящен рассмотрению математического аппарата существующей теории логического синтеза цифровых структур. Указывается, что в качестве таких моделей используются:

1. Ъулевы решетки - системы (А, э) с одним бинарным отношением' включения, удовлетворяющем условиям:

- рефлексивность

- антисимметричностьV(a,bеА)

- транзитивностьV(a,b,ceА)оэЬл4эе^аэс,

а также наличием для каждой пары элементов а,ЬеА точной верхней тах (а,Ь) (наименьший элемент хе.А, такой, что х гэ А) и точной нижней min (a,b) (наибольший элемент хеА, такой, что аз;с) граней.

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

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

Анализируя результаты ранних исследований по разработке многозначных алгебр (системы Россера-Тьюектта, Поста, Вебба), можно легко прийти к выводу о том, что предлагавшиеся функционально полные системы были основаны, главным образом, на использовании двухместных операторов тах от'" (х\,Х2) и одноместных операторов различных типов, в том числе:

- дополнения

а b

литерала

k -1 при а < х^ <Ь; О в противном случае.'

- циклического отрицания х = (\+х) mod к.

Дня двузначного случая эти операторы превращаются в операторы основной функционально полной системы И, ИЛИ, НЕ.

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

2. Булевы кольца — системы (А, +, •), используемые для представления логических функций в виде булевых полиномов. Использование булевых колец в логическом синтезе основано на том, что каждая булева решетка по отношению к операциям симметрического вычитания и булева умножения & образует коммутативное унитальное кольцо. В булевом кольце каждый элемент противоположен самому себе, т.е. 2-х = 0, где 2-х = х Ф je. Булево кольцо обладает также важным свойством идемпотентности: X1 —х (т.е. X &

Представления логических функций в булевых кольцах называются булевыми полиномами. В то же время булевы кольца можно рассматривать и как булевы решетки с использованием симметрической разности в качестве унарной операции. Примером булевой решетки, использующей в качестве унарной операции сумму по модулю 2, является алгебра Жегалкина — решетка А = (А, min, Ф), где А = jc^ Хз,..., 0,1}, je = jc©l.

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

Поскольку {К, Ф) - абелева группа (К - множество допустимых значений логики), то, использовав в качестве тела множество К с операциями Ф и &, а в качестве функции f, сопоставляющей элементам aeÄ" и aeÄ*1 элемент сш посредством покомпонентной конъюнкции aа = (СШ|, СШг,..., сш„ ), получим булево линейное пространство.

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

Аналогично, изоморфизм между булевым кольцом и булевой решеткой устанавливается следующими соотношениями:

тах{хи х2) -х\ Фх2Ф тт(хи х2)',

и т.д.

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

- декомпозиции логических функций (разделительная, неразделительная, неявная);

- проблемы время-структурной оптимизации логических схем БИС (минимизация логических функций, оптимальная реализация ее на элементах с ограниченным числом входов);

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

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

В подразделе 1.5. приведены основные выводы, сделанные на основе предыдущего анализа. Они сводятся к следующему:

1. Анализ развития теории логического синтеза показывает, что в основном она представляет собой развитие идей булевой алгебры. Определяющая булеву алгебру абстрактная алгебраическая структура — дистрибутивная решетка - была определена позже появления булевой алгебры как аппарата логического синтеза цифровых структур. Другие подходы к логическому синтезу - булевы линейные пространства, использование спектральных преобразований, - появились значительно позже. Это говорит, с одной стороны, о фундаментальности булевой алгебры как математического аппарата логического синтеза, а с другой — о наличии не прекращающихся попыток поиска альтернативных математических средств логического синтеза цифровых структур.

2. Основными алгебраическими структурами, положенными в основу существующих методов проектирования цифровых структур, являются:

- булевы решетки;

- булевы кольца и пространства;

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

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

4. Недостатки булевых структур как математического аппарата логического синтеза состоят в следующем:

- процедуры минимизации логических функций в этих структурах носят переборный характер;

- процедуры синтеза с увеличением числа аргументов становятся громоздкими, практически эти процедуры даже в двузначном случае становятся плохо обозримыми уже при п = 5,6;

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

5. Недостатки булевых структур как математического аппарата схемотехнической реализации цифровых структур состоят в следующем:

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

- операции алгебраических структур часто плохо "ложатся" на операции, реализуемые функциональными элементами, что увеличивает аппаратные затраты на реализацию цифровых структур;

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

- единство методологии логического и структурного синтеза в логиках любой значности;

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

Рассмотрена проблематика связи теории логического синтеза, схемотехники и технологии.*

В РАЗДЕЛЕ 2 рассмотрены методологические и математические основы предлагаемой теории логического синтеза цифровых структур над полем вещественных чисел.

В подразделе 2.1. определена общая постановка задачи и вопросы, подлежащие разработке.

В подразделе 2.2. рассмотрены четыре основных методологических принципа предлагаемой теории:

- принцип полноты использования значности логики;

- принцип гибридности набора операций, используемых для представления логических функций;

- принцип относительности формы представления результатов реализации логической функции

- принцип послойной реализации логических функций.

Сущность принципа полноты использования значности логики формулируется следующим образом:

- в теоретическом плане - логические операции могут выполняться только над переменными, имеющими одну и ту же область определения (существования);

- в комбинационных схемах - все входы и выходы схем равноценны в отношении использования значности переменных, то есть на любом входе и

любом выходе допустимы любые значения сигналов в пределах значности логики;

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

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

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

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

Суть принципа послойности реализации логических функций — в замене качественного (логического) описания значений аргументов и функций количественным. Это позволяет правомерно использовать операции min и /ЙОГ, сложения и вычитания и рассматривать значения аргументов и функций элементами натурального ряда. Он обеспечивает представление пространства логических функций данной значности подпространством логических функций большей или меньшей значности. Это позволяет предложить отличные от известных методы реализации логических функций.

В подразделе 2.3. вводится исследуемая математическая структура - линейное пространство с булевыми компонентами над полем вещественных чисел Это делается следующим образом. Вначале определяется

обычное линейное пространство, вектора которого представляются множеством координат, задаваемых кортежами натуральных чисел. Затем на элементах этого множества (т.е., на векторах) вводятся операции теории множеств как поэлементные операции на координатах векторов. Если х = {хо, *i>-,*m-i} е Z™ и у = {yo^b-.^m-i} 6 2™,то:

- пересечение

хпу = {min (x0,y0),min (xi,yi),..., min (Хт-ь^т-ОЬ

т.е. оно представляет собой покомпонентный min одноименных координат векторов и тогда (Z1" , Г») - нижняя полурешетка, т.е. частично упорядоченное множество, у которого определена только верхняя грань;

- объединение

xuy= {max (х0,у0), max (хьу,),..., max (*„.,,>Vi)},

т.е. оно представляет собой покомпонентный max одноименных координат векторов и тогда (2^ , и) - верхняя полурешетка, т.е. частично упорядоченное множество, у которого определена только нижняя грань;

Числовое представление значений координат позволяет использовать для их преобразования также операции линейного пространства:

- сумма

Х+у={ (х0+у0), (*,+;>!),..., (Xrn-1+Jn.-l)},

т.е. покомпонентная сумма одноименных координат; —разность

т.е. покомпонентная разность одноименных координат, причем при Х{ < yt разность Xj — у^ принимается равной 0;

- сумма по модулю,

кх®у=* { (х0©Уо), (*i©Л),-, (*m-i©Ло-i)},

т.е. покомпонентная сумма модулю к одноименных координат.

Поскольку операции линейного пространства могут быть выражены посредством операций на множествах:

х—у = max (x,y) - min (х, у) = max (х, -у) + min (х, -у);

то на множестве векторов линейного пространства наряду с классическими алгебрами (булевой алгеброй (Ä™; min, max), алгеброй Поста (Ä™; max ,0,1,..., k-1), алгеброй Вебба (Ä™; Ф, min , 0,! 1,... ,к-\) и т.д.) можно сформировать линейные булевы алгебры (Ä™; min (max), +, —, 0, 1,..., ft-J), являющиеся предметом дальнейшего рассмотрения.

Связи между операциями линейного пространства (Z™ , +, •) и операциями булевой алгебры (К"1, min, max) выражаются следующим образом. Поскольку соответствии со свойством совместимости

V(xj; еК™) max (х, у) =х=> min (х, у) —у,

то обозначив символом * одну из операций max или min, а символом # — другую из них, запишем следующие тождества:

Теорема 2.1. х*у = х+у-(х *у)=х+у +((-х)*(-у));

Теорема 2.2. x + (y*z) = (x+y)*(x+z),

Теорема 2 3. x — (y*z) = (x—y) *(x-z),

Теорема 2.4. (х+у)* z=x + (y* (z — x)) = x-(у *(z-x));

Теорема 2.5. (x — y)*z=x + (y * (z — x)) = x- (y*(z-x));

Теорема 2.6. (x,+y,) * (Х2+У2) = (*i * x2) + 0,* y2)

Далее рассматривается задача отображения линейных пространств. В рамках настоящего исследования рассмотрены отображения:

— отображение линейного пространства К" на другое линейное пространство;

— отображение линейного пространства НС на аффинное пространство;

— отображение линейного пространства 1С на некоторую другую алгебраическую структуру (алгебру).

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

В подразделе 2.5. приведены выводы по результатам формирования методологических принципов предлагаемой теории.

1. Результативность принципа полноты использования состоит в следующих двух факторах:

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

- он определяет единые структурные принципы построения цифровых структур любой значности.

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

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

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

5. Принцип послойной реализации позволяет обеспечить преемственность и единые правила получения представления логических функций большей значности путем «наращивания» представлений предыдущей знач-ности дополнительными компонентами данной значности.

РАЗДЕЛ 3 посвящен проблемам логического синтеза цифровых структур над полем вещественных чисел.

В подразделе 3.1. перечислены основные задачи, подлежащие решению:

- исследование класса циклических векторов специального булева линейного пространства для использования в качестве средства формирования базисов;

- разработка способов формирования наборов базисных векторов линейного пространства для представления логических функций посредством циклических векторов;

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

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

- формирование общей методологии логического синтеза в рассматриваемом линейном пространстве и разработку методов синтеза цифровых и цифроаналоговых схем.

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

- связь между базисом линейного пространства и логическим базисом;

- определение класса циклических векторов, являющихся основой для формирования базисных векторов линейного пространства -К™;

- разработка базовых конструкций базисных векторов - срезов циклических векторов и исследование их основных свойств;

- определение правил выполнения логических операций над срезами;

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

- определение итерационных процедур формирования базисных и обратных им матриц;

- разработка способов представлений логических функций в линейных и аффинных пространствах;

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

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

- получение порогового представления логических операций и векторов с использованием аппарата аффинных пространств.

Назовем циклом С последовательность вида {0, 1,-..,1, 2,...,2, к— 1,..., А—1}, в которой количества одинаковых значений элементов (т.е. нулей, единиц и т.д.) равны между собой. Группу одинаковых значений компонент последовательности (т.е. группу нулей, единиц и т.д.) назовем элементом цикла, а количество этих значений - длиной элемента.

Выделим в К* п векторов Х\, Хг ха , таких, что компоненты каждого из пихху,1=1,...,п,} = 1,...,т образуют последовательность из А1'"1 повторяющихся циклов с, состоящих из И элементов длиной А"'1 каждый:

Эти векторы будем называть циклическими.

Определение 3.1. Верхним срезом 1-го уровня вектора Х\ е Л"1 по значению / называется вектор Х\ — тах (х» Т), а. нижним срезом 1-го уровня -

вектор - вектор, все компоненты кото-

рого равныХ

Определение 3.2. Верхним срезом 2-го уровня вектора^ б Л™ называется вектор X" —Х1 —Х}'1 , а нижним срезом 2-го уровня— вектор дгвд ~Хщ)

Определение 3.3. Верхним срезом 3-го уровня векторае К* называется вектор а нижним срезом 3-го уровня -

вектор

В определениях 1-3 принято:

/ е [0, Лг-1], в е [1, / +1], г € [1, кЧ-Ц, ч е [1,4

Детерминированность структуры цикла С позволяет выявить структуры его преобразований на основе определений 1-3. Так, структуры верхних и нижних срезов 1-го уровня цикла выглядят следующим образом:

Структуры срезов 2-го уровня цикла определяются на основе структур соответствующих ^срезов первого уровня:

c'"s = с1 -с(м> = (0,-

t k~t t~s k~t+s

= {Q,...,0,0,1 ,„.¿-1 ;

t~s s k~t Ct-s = СГ C(t-s) = } - {f-j,/-5,f-5+1 } =

итд- t k-t t-s

Поскольку срезы циклических векторов принадлежат Er, то для них

должны быть справед!1(&ь1»Ш$яД»жф^аР}выше логические операции на векторах К". Однако их вЫполнеНие и^е^т некоторые особенности, определяемые их структурой. Дело в том, что, как уже было отмечено выше, элементы обычного множества представляют собой элементы одной природы -множества Xi — {0,1, ..., к— 1}, т.е. они имеют общую область определения, и операции min и max над ними - это операции над элементами с областью значений результата, совпадающей с областью определения элементов.

В линейном пространстве Ji"1 такое соотношение между областями определения элементов и операций над ними имеет место только при к = 2. При к > 2 рассматриваемые образования на основе элементов обычных множеств (срез - это «часть» обычного элемента!), имеют свою область определения, отличную от областей определения других элементов, поэтому по отношению к ним операции & и v непосредственно неприменимы. Использованию операций & и v над предлагаемыми элементами должно предшествовать предварительное «совмещение» областей определения элементов. Получение результата логической операции над совокупностями однотипных срезов производится в виде следующей последовательности действий:

1. Совмещение верхних граней комбинаций срезов с нижней нулевой гранью.

2. Сравнение совмещенной верхней грани с нижней гранью срезов группы 3.

3. Выполнение логической операции.

Последовательное применение перечисленных действий к произвольному сочетанию различных количеств срезов разных уровней приводит к следующему общему виду выражения для определения значений коэффициентов при срезах:

где

а =■ max(p¡,Apj,Aqs), а символом * обозначена одна из операций & или

Верхний вариант формулы используется при а > а нижний - при

а <, пип(д\). Полученное выражение использовано при формировании базисных матриц.

Далее рассмотрены монотонные векторы. Пусть имеем произвольный вектор а = {ао, вь— ат.\} е К". Перенумеруем компоненты вектора к-ичными «-разрядными числами.

Определение 3.4. Вектор ае К™ называется монотонно возрастающим (убывающим), если при поразрядном сравнении к-ичных кодов номеров компонент имеет место:

УОУе-К"1) г>у => а,>а,л1<]=>а,<ау

Поразрядное сравнение &-ичных кодов номеров компонент позволяет выделить последовательности неубывающих (невозрастающих) компонент. Смысл их заключается в том, что для установления монотонности вектора достаточно установить его монотонность в каждой последовательности таких компонент. Структуры последовательностей неубывающих компонент для k = 2, 3 и п =1, 2, 3 приведены в таблице на следующей странице. В таблице цифрами в кружках обозначены десятичные номера компонент вектора, а сама последовательность включает в себя некоторую вершину и связанные с ней ребрами ближайшие расположенные ниже вершины.

Свойство монотонности векторов из позволяет получить различные представления произвольного вектора посредством монотонных векторов. Рассмотрены такие представления в следующих трех вариантах:

- разностью двух монотонных векторов;

- алгебраической суммой монотонных векторов той же значности, что и исходный вектор;

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

Первая задача решается на основе следующей теоремы:

Теорема 3.1. Произвольный вектор а = {ао, а\,... ат.1} е может быть представлен в виде

а = Ъ-с, где Ъ ={Ь0, Ьх.....Ь^еЯ* и с= {с0, с,..., с^ 1} е Я™

Доказательством теоремы является следующий алгоритм:

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

Теорема 3.2. Произвольный вектор а е К™ может быть представлен конечной алгебраической суммой монотонных векторов а, вида

Задача представления произвольного вектора векторами меньшей знач-ности имеет множество вариантов решения. Рассмотренный в настоящем исследовании путь предполагает решение этой задачи в два этапа:

- получение представления произвольного вектора из Лт векторами меньшей значности;

- преобразование полученного представления к представлению посредством монотонных векторов.

Для первого этапа поставленной задачи предложено два решения:

- представление произвольного вектора из Л1™ взвешенной суммой век-

торов:

- представление произвольного вектора из унитарной суммой векторов: ° = >

о

где

Для второго этапа можно воспользоваться теоремой 3.2.

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

В подразделе 3 3. описаны предложенные методы логического синтеза цифровых структур над полем вещественных чисел, в том числе:

- матричный, т.е. синтез с использованием базисной и обратной ей матриц, при котором коэффициенты представления реализуемой функции в данном базисе определяются на основе разложения вектора ее значений по столбцам обратной матрицы;

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

- аналитический, т.е. синтез на основе математического описания закона функционирования реализуемой цифровой структуры

В подразделе 3.4. рассмотрен логический синтез последовательностных схем. Здесь предлагается новая реализация структурного классического синтеза автоматов с использованием аппарата линейных пространств. Суть его состоит в представлении многовыходной схемы произвольного автомата его многозначным аналогом с одним выходом, т.е. в виде предельно асинхронного автомата по Э.А. Якубайтису. Затем, используя отображение полученного описания схемы в исходном линейном пространстве в требуемое линейное пространство (например, в двузначное), можно получить его пред-

ставление множеством логических функций требуемой значности с заданными характеристиками.

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

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

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

Подразделы 3.7. и 3.8. посвящены оценке возможностей использования предлагаемого аппарата логического синтеза для синтеза аналогово-цифровых схем и систем соответственно.

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

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

В подразделе 3.9. приведены выводы, которые можно сделать на основе анализа полученных результатов. Они позволяют считать ее вполне перспективным математическим аппаратом для разработки методов синтеза таких структур по следующим факторам:

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

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

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

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

РАЗДЕЛ 4 посвящен структурному синтезу цифровых структур над полем вещественных чисел-

В подразделе 4.1. рассматривается постановка задачи структурного синтеза цифровых устройств над полем вещественных чисел. Отмечается, что она включает в себя решение следующих задач:

- рассмотрение совокупности операций над полем вещественных чисел и определение функционально полных наборов операций для различных технологических базисов;

- структурная реализация функционально полных наборов компонент логических базисов в различных технологических базисах;

- структурное проектирование цифровых устройств над полем вещественных чисел в различных технологических базисах;

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

Выводы полученные на основе результатов структурного синтеза, приведены в подразделе 4.3. Они сводятся к следующему:

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

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

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

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

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

5. Одной из важнейших особенностей предлагаемого подхода является то обстоятельство, что он открывает возможность реализации ^значных структур на функциональных элементах меньшей значности (в пределе - на двузначных элементах).

В РАЗДЕЛЕ 5 рассмотрены некоторые применения полученных теоретических результатов в логическом и схемотехническом проектировании и смежных областях.

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

В подразделе 5.2. и 53. рассмотрено схемотехническое проектирование цифровых структур в линейных пространствах с использованием ТТЛ- и ЭСЛ-технологий. Показано, что основным функциональным компонентом такой реализации является генератор тока. Сравнительный анализ получаемых и существующих схемотехнических решений доказывает высокую логическую эффективность полученных решений.

В подразделе 5.4. описана программа выполнения разработанных логических преобразований векторов в линейных пространствах. Эта программа позволяет получить прямую и обратную базисную матрицы для заданного набора срезов аргументов выбранной значности, получить вектор разложения логической функции по заданному базису, а также вычислить значения векторов представления логической функции в виде разных видов разложения ее в сумму монотонных функций. Она может быть использована в качестве программногоГмодуля любой из существующих САПР.

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

В заключении приведена сводка основных результатов, полученных в ходе проведения исследований. Основные из них приведены ниже:

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

2. Оценены недостатки булевого подхода к логическому синтезу. Основными из них являются:

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

- неиспользование точностных параметров функциональных элементов;

- неадекватность методов логического синтеза двузначных и многозначных цифровых структур;

- невозможность логического синтеза гибридных (аналогово-цифровых и цифро-аналоговых) структур.

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

- принцип полноты использования значности логики;

- принцип гибридности набора используемых операций;

- принцип относительности представления реализуемой функции;

- принцип послойности реализации логической функции.

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

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

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

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

8. Предложен метод синтеза последовательностных двузначных цифровых структур (триггеров), расширенный до синтеза многозначных последо-

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

9. Рассмотрен структурный синтез цифровых структур, реализуемых на основе предлагаемого подхода, в том числе логических операций, базисных векторов и логических функций. Его результаты позволяют проводить оптимальный выбор технологических решений для синтеза цифровых компонентов СБИС.

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

11. Предложены новые схемотехнические решения компонентов цифровых структур, обладающие в сравнении с существующим меньшими аппаратурными затратами и количеством связей между элементами, а также более высокими эксплуатационными характеристикам. Использование таких компонентов может улучшить технологические характеристики БИС и цифровых систем. В частности, они позволяют резко снизить требования к источникам питания (девиация напряжения питания в 20 - 30% вместо 5% в существующих СБИС), радиационной защите (до полной потери работоспособности активных компонентов схемы), температурному режиму и т.д.

Основные результаты диссертации опубликованы в следующих работах:

1. Корецкий А.А., Самойлов Л.К., Чернов Н.И. Минимизация временных переключательных функций. Материалы III Всесоюзной конференции по проблеме "Однородные вычислительные системы и среды", Таганрог, 1972.

2. Самойлов Л.К., Чернов Н.И. О числе временных переключательных алгебр //Сб. "Однородные цифровые вычислительные и интегрирующие структуры", вып.1, Таганрог, 1974.

3. Самойлов Л.К., Чернов Н.И. Минимизация логических функций с использованием алгебраической формы их представления //Сб. "Однородные цифровые интегрирующие структуры". Вып.9,1978.

4. Самойлов Л.К., Чернов Н.И. Об алгебраической форме представления логических функций. //Сб. "Однородные цифровые интегрирующие структуры". Вып.9, 1978.

5. Чернов Н.И. Об унификации подхода к синтезу логических элементов произвольной значности с использованием арифметического представления логических функций //Межвуз. сб. "Системы сбора и обработки измерительной информации", Таганрог, 1979.

6. Самойлов Л.К., Чернов Н.И. Арифметико-логические элементы как элементная база микроэлектроники. Материалы IX Всесоюзной научной конференции по микроэлектронике, Казань, 1980.

7. Чернов Н.И. Оптимизация многовыходных логических схем автоматики с использованием арифметической формы представления логических функций //Известия ВУЗов СССР "Электроника", №11, Новочеркасск, 1978, с. 1263.

. 8. Рогозов Ю.И., Чернов Н.И. Об использовании арифметических базисов для синтеза цифровых устройств систем сбора информации //Сб. "Системы сбора и обработки измерительной информации", вып.4, Таганрог, 1982.

9. Рогозов Ю.И., Чернов Н.И. Метод синтеза комбинационных устройств инжекционных БИС //Известия Северокавказского научного центра. Технические науки, №3,1984.

10. Рогозов Ю.И., Чернов Н.И. О влиянии логического базиса на оптимальность синтеза БИС. Материалы Всесоюзной конференции "Состояние и перспективы развития микроэлектронной техники", Минск, 1985, ч. III, с.73.

11. Рогозов Ю.И., Чернов Н.И. Оптимизация логического базиса для синтеза цифровых И2Л-схем // "Микроэлектроника", т. 16, вып.4,1987, с.352-356.

12. Рогозов Ю.И., Чернов Н.И. Многозначная реализация аппаратных средств параллельной обработки информации. Материалы седьмой Всесоюзной школы-семинара "Распараллеливание обработки информации" (РОИ-89), Львов, 1989,4.1, с.231-232.

13. Рогозов Ю.И., Чернов Н.И. Синтез последовательностных схем в логико-арифметическом базисе //"Микроэлектроника", т. 19, вып.4,1990, с.55-63.

14. Рогозов Ю.И., Чернов Н.И. Алгебраические методы синтеза цифровых устройств произвольной значности. Материалы 1-й Всесоюзной конференции "Однородные вычислительные среды и систолические структуры", Львов, 1990, т.2, с.84-90.

15. Рогозов Ю.И., Чернов Н.И. Алгоритм синтеза формального нейрона с постоянным порогом //Известия ВУЗов "Приборостроение", 1990, №5, с. 1216.

16. .Чернов Н.И. О синтезе цифровых структур произвольной значности над полем действительных чисел. Материалы Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места", Таганрог, 1995, С.208- 213.

17. Чернов Н.И. Метод синтеза сумматоров произвольной значности. Материалы Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места", Таганрог, 1995, с.201 -207.

18. Чернов Н.И. О нетрадиционных методах синтеза цифровых и циф-роаналоговых схем. Материалы Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места", Таганрог, 1996-97, с. 52 - 59.

32 € 3 660

19. Чернов Н.И. О монотонном представлении логических функций произвольной значности. Материалы Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места", Таганрог, 1998, с. 77 - 84.

20. Чернов Н.И. О разложении логических функций* произвольной знач-ности над полем действительных чисел. Материалы Всероссийской научно-технической конференции с международным участием "Персональные исследовательские комплексы и автоматизированные рабочие места", Таганрог, 1999, с. 109-113.

21. Чернов Н.И. Основы логического синтеза цифровых структур над полем вещественных чисел. Монография. Таганрог, ТРТУ, 2000,146 с.

22. Чернов Н.И. Синтез базисов для представления &-значных логических функций. Известия ТРТУ. Тематический выпуск Актуальные проблемы твердотельной электроники и микроэлектроники. Материалы Шестой международной научно-технической конференции «Актуальные проблемы твердотельной электроники и микроэлектроники - ПЭМ-99». Таганрог: ТРТУ,2000, №3 (17), с. 98-103.

23. Чернов Н.И. Логический синтез лдафровых устройств в булевом пространстве. Материалы международной научно-технической* конференции «СуперЭВМ и многопроцессорные вычислительные системы (МВС'2002)». Таганрог, 2002, с. 130-133.

24. Чернов Н.И. Линейное пространство как аппарат логического проектирования дискретных устройств. Материалы международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке, технике и экономике» «КЛИН-2003», Ульяновск, 2003, т.З, с. 150-152.

25. Чернов Н.И. Линейное пространство как математический аппарат порогового представления логических функций. Материалы международной конференции «Континуальные алгебраические логики, исчисления и нейро-информатика в науке, технике и экономике» «КЛИН-2003», Ульяновск, 2003, т.З, с. 153-155.

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты:

- [1 -4,6] - гибридное (арифметико-логическое) представление логических функций, [8 - 15] - математические основы реализации методов логического синтеза.

Типография Таганрогского государственного радиотехнического университета Заказ №44 Тираж 100 экз 2004 г