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

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

принципы построения

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

для обработки многозначных

и континуальных данных

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

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

Автореферат

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

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

Ульяновск – 2010

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

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

Официальные оппоненты: доктор технических наук, профессор

доктор технических наук, профессор

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

Ведущая организация: Институт проблем управления

им. РАН, г. Москва

Защита диссертации состоится 6 октября 2010 г. в 15 часов на заседании диссертационного совета Д212.277.01 в Ульяновском государственном техническом университете , главный корпус, аудитория 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. Разработаны принципы построения однородных и регулярных многоразрядных цифровых компараторов и компараторных устройств, образующих эффективную основу однокристального элементного базиса модулей, универсальных в классах функций многозначной логики, аргументы и значения которых представлены многоразрядными двоичными переменными.

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

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

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

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

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

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

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

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

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

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

«Методы и средства преобразования и обработки аналоговой информации» (г. Ульяновск, 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), основанный на применении доказанного тождества ) с целью уменьшения количества функций при сохранении числа функций . Однако, такое упрощение нарушает однородность элементного базиса.

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

Рис.3.

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

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

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

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

; (5а)

, (5б)

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

, ,

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

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

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

;

; ,

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

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

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

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

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

; ,

; ,

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

; .

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

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

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

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

, (6)

где

(7)

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