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

Размещено на http://www.allbest.ru/

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

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

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

Автореферат

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

Андреев Дмитрий Васильевич

Ульяновск 2010

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

Научный консультант:

доктор технических наук, профессор Волгин Леонид Иванович

Официальные оппоненты:

доктор технических наук, профессор Левин Виталий Ильич

доктор технических наук, профессор Масленников Валерий Викторович

доктор технических наук, доцент Негода Виктор Николаевич

Ведущая организация: Институт проблем управления им. В. А. Трапезникова РАН, г. Москва

Защита диссертации состоится 6 октября 2010 г. в 15 часов на заседании диссертационного совета Д212.277.01 в Ульяновском государственном техническом университете по адресу: 432027, г. Ульяновск, ул. Северный Венец, д. 32, главный корпус, аудитория 211.

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

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

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

мультиплексорный модуль логический схемотехника

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

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

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

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

Теории и схемотехнике многозначных логических (МЛ) модулей посвящены работы Иваськива Ю.Л., Поспелова Д.А., Ракова М.А., Кухарева Г.А., Шмерко В.П., Зайцевой Е.Н. Джейна А., Болтона Р., Дрехслера Р., Фиттинга М. и др.

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

Исследования математического аппарата и схемотехники бесконечнозначных логических (БЛ) модулей изложены в работах Мак-Нотона Р., Уилкинсона Г., Гинзбурга С.А., Кендела А., Еремеева И.С., Левина В.И., Золотовой Т.М., Волгина Л.И., Шимбирева П.Н. и др.

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

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

Актуальность диссертационного исследования подтверждается тем, что его тематика соответствует разделу «Технологии обработки, хранения, передачи и защиты информации» утвержденного Президентом РФ 21.05.2006 г. перечня критических технологий Российской Федерации.

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

Поставленная цель достигается решением следующих задач:

1. Анализ известной схемотехники мультиплексорных МЛ- и БЛ-модулей и разработка новых принципов их более простой структурной организации.

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

3. Разработка принципов реализации из настраиваемых элементов, воспроизводящих базовые бинарные операции бесконечнозначной логики и ПАВ, универсальных БЛ-модулей с распределенным кодовым управлением.

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

5. Разработка принципов организации универсальных логических модулей (УЛМ) с систолической структурой.

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

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

8. Анализ основных компонентов целевых УЛМ современных микросхем аналоговых компараторов и ключей, их использование в разработанных схемах универсальных средств логической обработки многозначных и континуальных данных.

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

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

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

В процессе исследований и разработок получены следующие новые научные результаты, выносимые на защиту:

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

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

3. Разработаны два метода построения мультиплексорных модулей, универсальных в классе всех n-арных БЛ_,-функций (, символы операций max, min), основанные на предложенных процедурах разложения произвольной БЛ_,-функции и при дающие более простые по сравнению с известными схемные решения. Показано, что при четном n мультиплексорные БЛ-модули могут быть использованы для реализации любой из всех БЛ-функций от 0,5n аргументов.

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

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

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

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

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

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

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

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

Практическая ценность результатов исследований заключается, в частности, в том, что

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

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

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

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

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

Внедрение полученных в диссертации результатов проводилось согласно договоров № Д121-УП от 06.09.2007 г., № Д135 от 26.09.2007 г. (исполнитель: ГОУ ВПО «Ульяновский государственный технический университет», заказчик: ЗАО «ИВЛА-ОПТ» г. Ульяновск) по созданию новых технических решений вторичных преобразователей для систем контроля концентрации метана и угарного газа в атмосфере категорийных помещений, под руководством автора как научного руководителя и при его непосредственном участии в разработках.

Кроме того, результаты диссертации использовались в учебном процессе УлГТУ при проведении курсового и дипломного проектирования.

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

«Методы и средства преобразования и обработки аналоговой информации» (г. Ульяновск, 1999 г.), «Interactive systems: the problems of human-computer interaction» (г. Ульяновск, 1999, 2001 г.г.), «Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике» (г. Ульяновск, 2000 г.), «Надежность и качество» (г. Пенза, 2001, 2002, 2003 г.г.), «Computer science and information technologies» (г. Уфа, 2001 г.), «Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике» (г. Ульяновск, 2001 г.), «SCM-2001» (международная конференция по мягким вычислениям и измерениям, г. Санкт-Петербург, 2001 г.), «Проблемы нейрокибернетики» (г. Ростов-на-Дону, 2002 г.), «Новые методологии проектирования изделий микроэлектроники» (г. Владимир, 2003 г.), «Фундаментальные проблемы радиоэлектронного приборостроения» (г. Москва, 2003 г.), «Оптические, радиоволновые и тепловые методы и средства контроля качества материалов, промышленных изделий и окружающей среды» (г. Ульяновск, 2004 г.), «Актуальные проблемы электронного приборостроения» (г. Саратов, 2004 г.);

на всероссийских конференциях:

«Нейроинформатика» (г. Москва, 2000, 2001 г.г.), «Динамика нелинейных дискретных электротехнических и электронных систем» (г. Чебоксары, 2001 г.), «Современные проблемы создания и эксплуатации радиотехнических систем» (г. Ульяновск, 2001 г.), «Информационные технологии в электротехнике и электроэнергетике» (г. Чебоксары, 2002 г.), «Актуальные проблемы радиоэлектроники» (г. Самара, 2003 г.), «Теоретические и прикладные вопросы современных информационных технологий» (г. Улан-Удэ, 2003 г.).

Универсальный логический модуль с импульсной настройкой (патент РФ 2284573) экспонировался на международной выставке изобретений «IENA-2007» (г. Нюрнберг, 2007 г.). Работа удостоена бронзовой медали.

Публикации. Основное содержание диссертации отражено в 104 публикациях, в числе которых монография, 8 статей в ведущих научных журналах РФ из перечня, определяемого ВАК, 11 статей в научных сборниках и прочих научных журналах, 55 запатентованных изобретений, а также труды, опубликованные в материалах международных и всероссийских научно-технических конференций.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 220 наименований, двух приложений, содержит 307 страниц машинописного текста, 115 рисунков и 37 таблиц.

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

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

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

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

, (1)

где ; и символы ДЛ-дизъюнкции и алгебраического умножения; нормированные характеристические функции вида

. (2)

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

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

, и .

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

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

, (3)

где ; , и символы, обозначающие ДЛ-конъюнкцию, ДЛ-дизъюнкцию и алгебраическое умножение; значение функции на i-ом неповторяющемся наборе значений ее аргументов ; вычисляемая по (2) нормированная характеристическая функция;

.

Рис.1

Поскольку некоторые произведения в выражении (3) имеют одинаковые левые сомножители, то его можно записать в виде

, (4)

где (m максимальное количество одинаковых левых сомножителей);

.

На основе (4) получено схемное решение (рис.2) однородного мультиплексорного МЛ-модуля, структура базисных элементов (рис.3) которого не зависит от значности воспроизводимых функций. При указанный модуль является универсальным в классе всех k-значных логических функций .

Рис.2

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

)

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

Рис.3

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

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

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

Среди разработанных схем имеются одноканальные итеративные сети, в частности, сеть, математическая модель i-й () ячейки которой определяется выражением , где настроечный сигнал; двоичные сигналы, задающие значения соответствующих разрядов n-разрядных двоичных переменных , ; # символ мажоритарной операции. Указанную сеть удобно использовать для распознавания ситуаций , () или , ().

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

; (5а)

, (5б)

где , и двухканальная итеративная сеть, i-я () ячейка которой формирует выходные сигналы согласно соотношений

, ,

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

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

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

;

;

,

где есть оператор двойственного преобразования; .

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

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

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

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

; ,

; ,



где есть номер такта ее работы; ; ; ;

; .

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

(, ).

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

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

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

Впервые предложена и теоретически обоснована процедура разложения произвольной БЛ_,-функции :

, (6)

(7)

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

(, ); .



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

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

Предложена и теоретически обоснована еще одна процедура разложения произвольной n-арной БЛ_,-функции:

,

где , характеристические функции, определяемые согласно (7).

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

,

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

Характеристическая функция реализуется выражением

,

содержащим неинверсных и инверсных характеристических функций

(), (8)

количество которых определяется числом упорядоченных континуальных переменных ( перестановка чисел Оператор преобразует произведение по правилу ().

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

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

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

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

, (9)

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

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

Рис.4

На основе выражения (9) и элементного базиса кодоуправляемых реляторных элементов (рис.4), воспроизводящих бинарные операции max, min, (в дальнейшем просто кодоуправляемых реляторных элементов) разработан принцип структурной организации (рис.5) селектора напряжений, реализующего путем кодовой настройки любую из всех n-арных симметричных БЛ_,-функций.

Рис. 5

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

,

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

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

Доказано, что второй селектор напряжений с кодовой настройкой является универсальным в классе всех n-арных симметричных БЛ_,-функций. Второй селектор напряжений (рис.6) имеет меньшее количество настроечных входов и базисных элементов, а первый дополнительно воспроизводит более широкий набор функций.

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

,

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

i
1
2
3
4
5

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

Рис. 6

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

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

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

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

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

; , (10)

где номер момента времени (рис.7б); и символы, обозначающие БЛ-конъюнкцию (min) и БЛ-дизъюнкцию (max); , входные аналоговые сигналы (напряжения).

Доказано, что данный систолический модуль

1) при , выполняет преобразование несортированного последовательного набора континуальных переменных в их сортированный параллельный набор ,…, (, );

2) при , выполняет преобразование несортированного параллельного набора континуальных переменных в сортированный последовательный набор ,…, этих переменных;

3) при одновременно выполняет сортировку последовательного набора ,…, и сортировку параллельного набора ,…, входных континуальных переменных и ;



4) при , () выполняет преобразование несортированного последовательного набора континуальных переменных в их сортированный параллельный набор ,…, ,;

5) при , , выполняет преобразование несортированного параллельного набора континуальных переменных в их сортированный последовательный набор ,…,;

6) при выполняет совместные преобразования и либо совместные преобразования и .

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

; ,

где номер такта вычислений; и входные аналоговые сигналы (напряжения).

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

,…,

.

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

, (11)

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

,…,.

В (11) () есть пространственная (временная) координата, , , .

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

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

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

, (12)

где , символы операций И, ИЛИ; , , .

Согласно (12) впервые разработаны принципы построения однородного высокоточного логического модуля, воспроизводящего путем кодовой настройки любую из симметричных БЛ_,-функций ,…, . Недостатком указанного модуля является значительное количество (n) настроечных входов.

Впервые разработаны принципы структурной организации более сложных неоднородных высокоточных УЛМ, настройка которых на реализацию заданной симметричной БЛ_,-функции осуществляется уровнем единственного настроечного сигнала. Базовые схемы этих модулей приведены на рис.8, а математические модели определяются выражениями (13), (14), где и континуальные и двоичная переменные (настроечные и информационный сигналы); e масштабный коэффициент (заданный квант напряжения); неопределенное значение .

(13)

(14)

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

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

,

где оператор выделения целой части; относительная погрешность коэффициента усиления операционного усилителя A;

, ; (15а)

, . (15б)

В (15)

;

;

;

,

где есть величина допуска номинального сопротивления R используемых резисторов; () есть сопротивление аналоговых ключей в замкнутом (разомкнутом) состоянии.

Рис.8

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

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

Выделен класс БЛ-функций, представителем которого является произвольная функция, заданная формулой из h букв и символов операций max, min и порождающая остальные функций своего класса с помощью соответствующей замены либо (). Функции выделенного класса названы изоморфными в силу идентичности структуры их формул, определяемой организацией суперпозиционных подстановок бинарных операций бесконечнозначной логики.

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

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

Разработаны принципы организации новых БЛ-модулей с кодовой настройкой, универсальных в заданном классе изоморфных БЛ-функций и занимающих среднее положение по аппаратурным затратам и схемной глубине. В качестве базисного элемента этих УЛМ предложен модуль, воспроизводящий путем кодовой настройки любую из трехбуквенных БЛ_,-формул и реализованный на трех кодоуправляемых реляторах по графу соответствующей предикатной формы.

В пятой главе дана характеристика некоторых современных микросхем аналоговых компараторов и ключей, которые выпускаются ведущими мировыми производителями (фирмами Advanced Linear Devices, Analog Devices, Maxim, Texas Instruments и др.) и могут быть использованы в полученных схемотехнических решениях универсальных логических модулей.

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

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

, (16)

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

Описан ряд апробированных принципиальных схем, которые разработаны на основе рассмотренных ИМС и предложенных принципов структурной организации универсальных БЛ-модулей.

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

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

В приложении 2 представлен акт, подтверждающий использование результатов диссертационной работы.

ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

11. Исследованы основные электронные компоненты целевых УЛМ современные микросхемы аналоговых компараторов и ключей, выпускаемые ведущими мировыми производителями и применимые в полученных схемотехнических решениях универсальных логических модулей. Разработаны и апробированы соответствующие принципиальные электрические схемы.

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

13. Разработанные базовые принципы организации структур обеспечивают построение универсальных логических модулей любой заданной размерности. Предложенные для некоторых УЛМ варианты схемной реализации позволяют в каждом конкретном случае выбрать наиболее подходящий вариант.

14. Результаты диссертации использовались в ЗАО «ИВЛА-ОПТ» г. Ульяновск при выполнении НИОКР «Разработка новых методов построения многоканальных газосигнализаторов», «Разработка универсальной системы газового контроля для вновь возводимого и реконструированного жилья» по государственным контрактам № 4703р/6886 от 15.01.2007г., № 6101р/8574 от 31.07.2008г. (заказчик: «Фонд содействия развитию малых форм предприятий в научно-технической сфере» г. Москва). Результаты диссертации представляют интерес для учреждений, занимающихся проектированием средств и систем автоматики, вычислительной техники и управления.

Дальнейшее развитие научных исследований, проведенных в диссертации, может быть связано, в частности, с созданием логических модулей, реализующих путем настройки набор заданных БЛ(МЛ)-функций, которые принадлежат в общем случае разным классам. Кроме того, весьма перспективной является разработка принципов построения аналого-цифровых преобразователей «напряжениевремянапряжение», универсальных в классе всех n-арных БЛ_,-функций.

ОСНОВНЫЕ ПУБЛИКАЦИИ

Монография

1. Андреев, Д.В. Универсальные логические модули для обработки многозначных и континуальных данных Д.В. Андреев. Ульяновск УлГТУ, 2010. 234 с.

Статьи в определяемых ВАК ведущих научных журналах РФ

2. Андреев, Д.В. Принципы организации реляторной комбинаторной сети с распределенным кодовым управлением Д.В. Андреев Информационные технологии. 2001. № 8. С. 17-20.

...