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

А С

О-

-■с-г-,

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

ГОРБАТОВ Александр Вячеславович

УДК 681.3.02

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

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

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

Москва — 1997

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

Научный руководитель

академик МАИ, РАЕН, проф., докт. техн. наук С. Л. РЕДКОЗУБОВ.

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

академик МАИ, РАЕН, Лауреат Государственной премии РФ, проф., докт. техн. наук В. М. ЛОХИН,

доц., канд. техн. наук В. И. МЕТЕЧКО.

Ведущее предприятие — Московский государственный институт электроники и математики (технический университет).

Защита диссертации состоится « » декабря 1997 г.

в час. на заседании диссертационного совета Д.053.12.12 в Московском государственном горном университете по адресу: 117935, Москва, Ленинский проспект, 6.

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

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

» ноября 1997 г.

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

доц., канд. техн. наук М. А. РЕДКОЗУБОВ.

ОБЩАЯ ХАРАКТЕРИСТИКА. РАБОТЫ Актуальность темы. Перспективной технической базой сложных систем обработки информации накануне XXI века являются нейрокомпьютеры, нейроссти, позволяющие производить параллельную обработку информации и тем самым существенно повышать производительность вычислительных средств. В нейротехнологиях можно выделить два класса технологий: 'soft'-нейротехнологни н 'hard'-нейротехпологин. В технологиях первого класса основной проблемой является разработка стратегии обучения и самообучения нейронных сетей, включающих в себя синтез сценариев обучения. Эти технологии особенно важны при решении неформализованных задач при наличии зашумленной, противоречивой, неполной входной информации. Такими задачами являются распознавание, классификация, протезирование, краткосрочное предсказание, которыми изобилуют финансовая и оборонная области деятельности человека

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

функции /(*!•*!.....хт>) в визе декомпошции функций от 4-5 переменных.

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

В становлении, развитии и использовании нейротехнологий большой вклад внесли У. С. Мак-Каллок, В. Питтс, Ф. 1'озенблатт, И, М. Макаров, А. И. Галушкин, В. М. Лохин, IO. А. Маматов,С. А. Редкозубое, С. О. Мкртчан, Э. А. Малыкин, В. К. Левин, В. Д. Цыганков, Р. Хечт-Нильсен, Дж. Хопфилд, Т. Кохкнен.'). Д. Аведьян, А. Л. Стемпковский. А. Н. Нубепников и др.

Известная реализация нейронов в виде композиции множительных и суммирующею устройств является достаточно громоздкой, с точки зрения объема аппаратуры, конструкцией. Наиболее оптимальной реализацией нейрона является однородная структура тетрагонального (США, Япония) и гекса! опального (Россия) типа, настраиваемая на реализацию одной из булевых функций от четырех или пяти переменных. При этом перспективной, с точки зрения наибольшего использования площади кристалла, является i ексагональная структура нейрона.

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

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

/(xi,X2.....х„), • в виде декомпозиции булевой функций от четырех

переменных.

В решении проблемы декомпозиции булевых функций на протяжении последних пятидесяти лет большой вклад внесли ученые К.Шеннон (1945-1955 г.), А.Г.Лунц (1950 г.), М.А.Гаврилов (1950 г.), В.Беркхарт (1952 г.), Г.Н.Поваров (1954 г.), С.Окада (1955 г.), Р.Гоулд(1957 г.), С.Абхъянкер (1958 г.), А.В.Кузнецов (1958 г.), Р.Ашенхерст (1959 г.), Р.Карп (1963 г.), А.Кертис (1963 г.), Р.Миллер (1970 г.), Л.И.Волгин (1992 г.) и др.

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

Работа выполнялась в рамках федеральной научно-технической программы «Океантехника» и научно-технических программ кафедры «Высшая математика» МГГУ.

Цель работы состоит в разработке математического обеспечения н программной реализации инструментальной среды построения на базе ПЭВМ IBM PC и предназначенной для автоматизированного логического проектирования нейронных сетей.

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

Методы исследования базируются на использовании характеризационного анализа, теории графов и однородных ' электронных структур.

Основные научные Положения, разработанные лично соискателем, и их новизна

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

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

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

4. Предложены эффективные алгоритмы декомпозиции булевой функции через функции от четырех переменных, соответствующие элементам нейронных 'Ьагс1'-тсхнологий,используемых в России и США.

Степень обоснованности научных положен»!), выводов и рекомендаций, сформулированных в диссертации, подтверждается:

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

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

Практическая значимость работы состоит:

• в разработке программных средств автоматизированного логического проектирования нейронных сетей, состоящих из модулей КЕНИГ, СВЯЗНОСТЬ, РАСКРАСКА, РЕДУКЦИЯ, КОДИРОВАНИЕ, ДЕКОМПОЗИЦИЯ, ¡1НЙРОН, ДЕБАЛАНС образующих инструментальную среду в ПЭВМ IBM PC, позволивших проектировать тегырехсинаптические нейронные сети гсксоганалыюй структуры сложностью до 106 вентилей;

• во внедрении разработанной инструментальной среды в практику реального автоматизированного проектирования на промышленных предприятиях (НИИ цифровых систем (г. Челябинск), Быковский завод средств логическою управления и дрД о чем имеются соответствующие акты о внедрении. Эксплуатация этих средств показала уменьшение трудоемкости проектирования на два порядка и уменьшение сложности проекта на порядок по сравнению с известными алгебраическими и эвристическими подходами (метод каскадов с оптимальным исключением переменных, основанном на использовании аппарата булева дифференцирования; метод Кертиса и др.).

Апробация работы Основные результаты диссертационной работы докладывались и обсуждались на Международной конференции "Control systems and computer science" (Бухарест, 1991 г.), 14-м Международном симпозиуме "Логическое управление и интеллектуальные информационные технологии и стратегии" (Феодосия, 1991 г.), Всемирном конгрессе 11S-93 "Информационные коммуникации, сети, системы и технологии"(Москва, 1993 г.), Всемирном конгрессе 1PTS-94 "Информационные процессы, технологии, системы, коммуникации и сети" (Москва, 1994 г.); 17-м Международном симпозиуме "Логическое управление и интеллектуальные информационные технологии и стратегии" (Варна, 1994 г,), доклад удостоен Почетного диплома как лучшая работа по информатизации за 1994 г. среди молодых ученых; Всемирном Конгрессе 1PTS-95 «Информационные процессы, технологии, системы, коммуникации ц сети» (Москва, 1995 г.), доклад удостоен 1-й премии среди научных работ молодых ученых в конкурсе, посвященном 50-летию Великой

победи во Цюрой мировой войне; Всемирном конгрессе «Информатизация», посвященном намят А. Нобеля (Ижевск, 1995 г.) и Всемирном конгрессе 1МС11-96 «Информационная математика, кибернетика и искусственный интеллект в ниформациологии» (Москва, 1996 т.).

Публикации Основное содержание диссертационной работы отражено в оди ииадца ш ну бпикациях.

С'т|>ук-|> |>а н объем работы Диссертационная работа состоит из введения, четырех |лав, заключения, списка использованной литературы из 101 наименовании, в том числе 37 таблиц, 45 рисунков.

Содержание работы

Современные интеллектуальные средства вычислительной техники и управления все в большой степени реализуются на базе нейронной технологии, обеспечивающей высокую производительность проектируемых систем. В ведущих странах мира этой проблемой занимаются большое количество фирм: в США -61 фйрма, в том числе Rand Со; в Японии - свыше 10 фирм, в том числе TOSHIBA, HITACHI; в России - также более 10 организаций, в том числе ИАЭ им, И. В. Курчатова, Нейро-Ком (г. Красноярск), Научный центр нейрокомпьютеров, НИИ «Квант», АО «Ангстрем», МИРЭА; в ФРГ - более 5 фирм, в том числе Цен</> оборонных исследований. 'Hard'-нейротехнологии особенно интенсивно применяются в системах с искусственным интеллектом для обслуживания ядерных установок, в оборонных комплексах и горном деле; в экспертных системах прогнозирования месторождений и финансовом деле при проведении инвестиционной политики; в системах интеллектуального управления (И. М. Макаров, В. М. Лохин, Заде и др.).

Перспективной компонентой 'hard'-нейро иппологии является перепрограммируемая логическая интефальная среда (ПЛИС), представляющая собой переналаживаемую нейронную сеть, работающую в условиях субмикронной технологии.

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

Впервые формальная модель нейрона была предложена в 1943 г. американскими учеными У. Мак-Каллоком и У, Питгсом, которая была уточнена и развита С.Юшнн, Д.Калбертсоном, Й.фон Нейманом и др. Аналоговая реализация нейрона на основе множительных устройств и сумматора требует прецезионную точность изготовления компонент нейрона. По этой причине более эффективной является цифровая реализация на основе применения однородных структур. Западный вариант такой реализации основан на использовании однородных структур тетраидального типа (С.Мурога - 1979 г.), российский вариант - гексагонального типа (В.Л.Белявский, В.А.Горбатов -1970 г.). Гексагональная однородная структура является на два-три порядка более эффективной, по сравнению с тетраидальной в смысле объема аппаратурных затрат.

По Мак-Каллоку-Питтсу условия возбуждения нейрона описываются функцией (р(Х|,Х2,...,Х|,) вида

к

Г 1, если Xх М^Т ¡=1

ф(х1,хг.....ХкН

I О, в противном случае,

где х,=0,1^1- вес ¡-ого синапса Т - порог возбуждения нейрона.

Условия возбуждения нейрона гексагонального типа отличны от этих условий и описываются функцией ч>(Х|,Х1,—,Хь) вида к '

I 1, если ]Гх лу,=Т( ¡=1

ф(Х1,Х2,...,Хк)И

1о, в противном случае,

где х,=0, 1; - вес ¡-ого с...тиса (\и,*0);

^ - ]-ый квазипорог возбуждения нейрона, множество квазипорогов {Т/)=1,2.....э} моделирует порог возбуждения нейрона Т.

В качестве реализации нейрона будем рассматривать однородную Структуру гексагонального типа, при этом вес синапса р, моделируется количеством горизонтальных цепей, на которые подается переменная х„ значения квазипорогов {Г]} записываются в регистр порога Т, выхрдные каналы которого соединены с вертикальными цепями. Выходной канал вертикальных цепей соответствует аксону нейрона.

Синтезу нейрона, сводящийся к целочисленному решению системы линейных неравенств, посаящеко много исследований (В.И.Варшавсшй -1962, М.Дертоузос - 1967, Е.Н.Вавилов - 1970, С.В.Архангельский -1970, А.И.Галушкин - 1992 и др.). В диссертации рассматриваются нейронные технологии использующие четырехсинаптические нейроны. Следовательно, при определении весов синапсов и порога число неравенств,входящих в систему не превышает 16.

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

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

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

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

Представим заданное булево пространство Р(Х) в виде декартова произведения Р(Х,) * Р(ХЬ) пространств Р(Х.), Р(ХЬ), {Х,МХЬ}={Х}, {Х,)г\{Хь}=0.

Каждой точке пространства Р(Х,) взаимнооднозначно сопоставим вершину v,6V„ графа G,=<V,,0>1 а точке пространства Р(Хь) - вершину vbeVb, графа Gb=<V„,0>, тогда граф G = <V,uVb,U|,Uo>,

G = G, + Gb,

определит исходное пространство Р(Х), при этом если булева функция /(X) в этом пространстве принимает единичное значение в точке Xj, то вершины v.eV, и vbeVb, соответствующие этой точке, соединены неинверсным ребром (v„,vbij eUi; если - нулевое значение, то - соединены инверсным ребром {v,„vb,}eUo; если же функция /(X) в точке Xi=X„*Xb, (вектор Xi есть результат конкатенации векторов X,, и Xbl) не определена, то {vai, граф G является графом Кенига, имеющий два сорта ребер (неинверсные и инверсные). Очевидно, что каждая вершина v„e V, взаимнооднозначно соответствует остаточной булевой функции и вершина vbjeVb

- остаточной функции /(Х,,аук»1),0ь(к+5),-.-,<тьл) в разложении Шеннона булевой функции /(X) по строчным X, и столбцевым Хь переменным соответственно.

Для построения декомпозиции функции /(X) определим понятие графа противоречивости.

Строчным графом противоречивости Gnp(X,)=<V„U„p>, называется граф, каждая вершина v, которого взаимнооднозначно соответствует вектору X„i, XaoV„ U„pcVa2 и (v,a,v,r)je'Jnp<=>(3XbJ)(/(X1[„XbJ)*/(X|fi,Xbj)).

Столбцевым графоз противоречивости Gn!,(Xb)=<Vb,Urp> называется граф каждая вершина Vj которого взаимнооднозначно соответствует вектору Хщ, XboVb н {vjn,vj()} eUnbo(3X4)(/(X.J,XJa)f/(X,J)Xrf)).

Названия графоз противоречивости G„P(X«) и G.,P(Xb), соответственно "строчный" и "столбцевой", указывают на возможность задания графа Кенига

G=<y,uVb,Ui,Uo>, определяющего булеву функцию /(х,,xi.....хп), в виде

соответствующей двумерной таблицы Вейча, в которой каждая строка (столбец) • задает соответствующую остаточную функцию в разложении Шеннона.

УТВЕРЖДЕНИЕ 1.

Булева функция /(X) декомпозируема в виде F(ipi(X,),<p2(X.).....<f>k(X,),Xb)

тогда и только тогда, когда целое ближайшее двоичного логарифма хроматического числа h(G„p(X,)) графа противоречивости Gnp(X,)=<V„Unp> меньше мощности его носителя I V,|;

/(X)=F(4>,(X>),4i2(Xl),...,4,t(X1)^b)o[logih(G„p(XO)l<IV,|, (1)

где k=[log2 h(G„p(Xa))],[]-3Hax ближайшего целого.

УТВЕРЖДЕНИЕ 2. Булева функция /(X) декомпозируема в виде /(X)=F(X,,i)i(Xb),ri2(Xb),...,Tis(Xb)) тогда и только тогда, когда (Jog2 h(G„p(Xb))]< I Vi, I:

/(X)=F(X„ri ,(Хь),Л2(Хь).....tis(Xb))«.[log2 h(Gt,p(Xb))]<l Vbl; (2)

где s=[log2 h(G„p(Xb))];

У i ИЕРЖДЕНИЕ 3.

Булева функция /(X) декомпозируема в виде

/(X)=F((pi(Xa),(p2(Xa),...,<pk(X1),rii(Xb),n2(Xb),..-1ns(Xb)) тогда и только тогда, когда ([log2 h(Gnp(X,))]<l V,l)&([log2 h(G„p(Xb))3<l Vbl):

/(X)=F(<(),(X.),92(X,).....9k(Xi),H 1(Хь),Пг(Хь).....П.(Хь)>» ' (3)

([logjh(Gnp(X„))l<l V.l )&([|og2 h(Gnp(Xb))]<l Vbl); при раскраске графов Gnp(X,) и Gnp(Xb), при этом V,nVi,=0. . Утверждения (1)-(3) являются теоретико-графовым развитием теоремы Шеннона о разложении булевой функции по заданным переменным и определяют построение бесповторной, декомпозиции - случай, когда V/~iVb=0,-этот случай достаточно подробно был исследован различными учеными (А. Кертис, В. В. Копьев и др.).

Предложим стратегию построения повторных декомпозиций, т. е. когда V,nVь*0, для синтеза нейронных сетей, работающих в условиях субмикронной технологии. Следовательно, будем рассматривать построение повторных декомпозиций булевых функций /(хi,...,x„) через функции vj(x„xb,x{>x(i) от четырех переменных, удовлетворяющих условиям (3), при этом k+sS4.

Согласно характеризационному анализу запрещенными фигурами раскраски графа G в q красок являются квазиполный граф квазиплотности q+1.

Отсюда, учитывая ограничения, накладываемые на вид декомпозиции, будем раскрашивать графы Gnp(Xa) и Gnp(Xb), согласно выражению (3), не более чем в четыре цвета каждый (случай k=s=2) или в восемь и два цвета (случай k(s)=3,s(k)=l).

УТВЕРЖДЕНИЕ 4.

Запрещенными фигурами гостроения декомпозиции булево К функции /(X) вида

ЛХ)=Р(<р|(Х.).ч>2(Х.),ч,(Хь),Пг(Хь)) являются квазиполные графы 0(р„ к,)сО„,,(Х.),('>..Р(Хь) (р, • плотность, к, -порядок квазиполного графа 0): 0(5,0). <5(4.1 ),0(3, 2). 4(2,3).

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

Таблица 1.

Тип запрещенной фигуры СХ>0) Плотность I Порядок j Минимальная структура ОМ Минимальное значение

Мощности

Носителя Сигнатуры Степени вершины графа

0(5)-квази- 5 0 0(5,0) 5 10 4

полные графы А 1 <3(2,1)+-+0(2,0) 7 16 4

квазиплотности 3 2 0(2,2)+ +0(1,0) 12 31 4

пять Н=5 2 3 0(2,3) 23 71 4

УТВЕРЖДЕНИЕ 5. Запрещенными фигурами построения декомпозиции булевой функции /(X) вида

/(Х)=Г(ф,(Х,),(?2Си Ч>3(Х.),Ч1(ХЬ)) являются квазиполные графы квазиплотности 9

О(9)={О(9,0),0(8,1),О(7,2),О(6,3),О(5,4)О(4,5),О(3,6),О(2,7)} 0(9)с01Ч,(Х,) и квазиполные графы квазиплотности 3 0(3)» «3(3,0),<3(2,1)} 0(3)сОлр(Хь).

УТВЕРЖДЕНИЕ 6, Запрещенными фигурами построения декомпозиции булевой функции /<Х) вида

/(Х)=Р(<|>|(Х.),Т11(Хь),п2(Х1,),п)(Хь)) являются квазиполные графы квазиплотности 9, <3(9)сОг,р(Хь) и квазиполные графы квазиплотности 3, С?(3)сОпр(Х,). С целью построения оптимальных, в смысле трудоемкости, алгоритмов построения декомпозиции и качества проекта, как и для случая к=з=2 (утверждение 4), так н случая к($)=3, 5(к)=1 (утверждения 5, 6) были исследованы минимальные ресурсы, при наличии которых возможно существование запрещенных фигур в графах противоречивости Опр(Х,) и 0„р(Хь). Полученные результаты сведены в табл. 2.

Таблица 2.

Тип запрещенной фшуры ОСУ) Плотность 1 Порядок ) Минимальная структура Минимальное значение

Мощности Степени вершины графа

Носителя Сигнатуры

0(9)-квазиполные графы квази-плотностн девять ¡+3=9 9 0 <3(9.0) 9 36 8

8 I 0(2,1)+ +(3(6,0) И 50 8

7 2 0(2,2)+ +0(5.0) 16 85 8

0(2,1)+ +0(2,1)+ +0(3,0) 13 68 10^'

6 3 0(2,3)+ +0(4,0) 27 169 8

0(2,2)+ +0(2.1)+ +0(2,0) 18 ИЗ 10

0(2,1)+ +0(2.1)+ +0(2,1) 15 90 12

5 4 0(2,4)+ +0(3,0) 50 380 8

0(2,3)+ +0(2,1)+ +0(1,0) 29 507 10

0(2,2)+ +0(2,2)+ +0(1,0) 23 183 15

-1 5 0(2.5)+ +0(2,0) 97 946 8

0(2,4)+ +0(2,1) 52 476 10

0(2,3)+ +0(2,2) 34 344 15

3 6 0(2,6)+ +00,0) 192 2551 8

2 7 ... 0(2>7) 383 7271 8

Продолжеие таблицы 2.

(^-ква- 3 0 <3(3.0) 3 3 2

зиполные

графы ква-

зиплотно- 2 1 0(2.1) 5 5 2

сти три, ¡+}=3

На основе предложенного математического обеспечения разработана интеллектуальная технология и стратегия синтеза оптимальной декомпозиции булевой функции /(X):

1. Разбиваем исходное пространство Р(Х) на два подпространства Р(Х,), Р(Хь) таких, что

Р(Х)=Р(Х,)»Р(Хь),Х^Хь=0, |Х.|=(0,5|Х|],|ХьМХ|-[0,5|ХЛ,

где |Х|=п.

2. Оцениваем каждое из С (п, (0, 5п|) разбиений пространства Р(Х) суммой верхних оценок хроматических чисел Ь(С11р(Х,)), Ь(0„р(Х,))

Л,(Р)=МО„р(Х,))+Ь(С„р(Х,)), (4)

С(п, [0. 5п))-число сочетаний изппо (0, 5п], С„Р(Х,1 строчный граф противоречивости, С,Ф(Х,) - столбцевой граф противоречивости,

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

0=<У,и>

Ь(0)5](5И1„+1 +((5ГШ„+1 )5+8|иИ|УГ8П1„)"2У2[, где 5т.п - минимальная степень вершины графа б, ][ - целая часть.

3. Выбираем разбиение исходного пространства Р(Х) по минимальной оценке (4).

4. Линейно упорядочиваем рассматриваемые случаи декомпозиции вида

У ЛХ)=Г((?1(х.),фг(Х.).....Ф^ХО.пКХьМ^Хь).....П>(Хь))

1)к=5=2,

2) к=1,5=3,

3) к=3,

и поочередно их рассматриваем.

5. Строим граф противоречивости 0„Р(Х,).

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

- квазиплотности пяти или

- квашплот/шети 3 и 9 или

- квазиплотности 9 и 3.

Находим оптимальное покрытие соо1ветст»>ющен семат ичеекой таблицы, как результат нолуюем множество ребер, определяющих сужение cimiai)pu графа противоречивости.

7. Осуществляем найденное в п.6 сужение сигнатуры путем штриховки векторов, которыми сцеплены удаляемые ребра. Для штриховки векторов строим двумерную таблицу Q=|q,,i>). каждой строке которой взаимнооднозначно сот неге гвует сцепляющий вектор Xj пространства 1'(Х,). столбцу - переменная пространства 1'(Х,), которой отлнчшшея векторы Х„, Х,ь, находящиеся в отношении противоречивости в сня т с сушествшшшем вектора X,, и в клетке [u.(5 ¡находится 1, если векторы Х„, Х,ь. (Xia, X|b)eUllD - сцепленные вектором Х,„ отличаются |1-ой переменной, 0 - в прошвном случае, loi да переменные, пошедшие в покрытии строк столбцами, определяют расширение пространства l'iX,) и eciecmeimiiii способ реализации сужения сигнатуры графа нрошиорсчииоо и.

X Сужение cm шилрм i рафа противоречивости определяет редуцирование его хроматического числа до числа, соответствующей) рассматриваемому случаю (см. Н.4). Кодируем инеденные краски. С'оцнетные вершины склеиваем.

9, Paccuoipeu ли ног случай декомнотннии (см. и.4), с учетом флигноинронання разложения Р(Х|. 1:с.чи "нет", то переходит к п.10, в прошвном случае - к u.ll.

10. Транспонируем раиюженис i'iXH'fXJ'I'iXt,) (идентификаторы а и b HMiiMiKi иерсимснонмиамгся), получаем Р(Х)-1'(Хь)*Р(Х,,). Переходим к п.5.

11 l'accMoi репы ли все случаи декомпозиции (см. п.4). "Нет" -рассматриваем следующий случай декомпозиции, переходя к п.5. "Да" -переходим к п. 12.

12 Иошорием п и.1-11 для каждой полученной внутренней функции до ок-нишельнот получения всех внутренних и ниешних функций размерности чешре с учетом ич совместной реализации.

Полеченная декомпозиция заданной булевой функции определяет U'iiuTdHiio нроектр)емой нейронной сети.

1 lac 1 ройка каждою нейрона на реализацию соответствующей функции сно.ппея к- целочисленному решению снаемы m 16 уравнений (2", п=4). Каждое >равнение соошетощет точке четырехмерного булевого пространства, при лом сумма весов синапсов приравнивается разрешенному квазипорогу Т., если н -поп ючке функция равна 1 и - запрещенному квазппорогу 7-,, сели -фхнкиня равна 0 Единичная область булевой функции порождает систему

урапнений для определения разрешенных квашпорогов, нулевая область - для ■определения запрошенных квазниорогов. "'Условием решения этих систем уравнений, якляетс-я неравенство любой пары Т„ Р,: Ti*Pj. Функционал качества решения chciем определяется как сумма весов синапсов. Прн синтезе нейрона минимизируется его "функционал качества.

.Для уменьшения трудоемкости синтеза нейрона введено понятие графа неравенства Gh=,îVw.U>, каждая вершина которого ¡взаимнооднозначно ■ соответствует всцусннапса, и две вершины соединены ребром тогда и только •тогда, когда соответствующие веса синапсов линейными .'преобразованиями могут быть представлены в виде.одинаковых алгебраических.сумм,¡входящих в {различные енстемы уравнений: один вес - в.систему.разрешенных:квазипорогов, другой - запрещенных квазипорогов. На Базе введенного : графа неравенства

• предложен апоригм быстрого определения -весов и ^квазнпорогов ¡-каждого нейрона - алгоритм -индивидуализации нейрона. Сумма .весов синапсов

• определяет время задержки сигнала.

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

Предложенное математическое обеспечение .синтеза -нейронных сетей доведено до .разработки соответствующего программного инструментария, включающего в себя операционные модули: ,-КЕНИГ, ХАРАКТЕРИЗАЦИЯ, РАСКРАСКА. РЕДУКЦИЯ, -КОДИРОВАНИЕ. .ДЕКОМПОЗИЦИЯ, ¡НЕЙРОН, /ДЕБАЛАН1

■ Программные .средства разработаны для ПЭВМ :1ВМ !РС в NMS ,DOS с использованием языка Turbo С. позволяют синтезировать .нейронные лети .сложностью до 106 вентилей при среднем времени логического.ирое^тирования, отнесенного к одному вентилю - (0"гс.

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

Рез\ ,(^1агы практического.внедрения показаш:

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

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

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

Результаты диссертационных исследований были внедрены на. промышленных предприятиях (Быковский завод средств логического' управления, Челябинский НИИ цифровых снеток и др.) при автоматизированном проектировании цифровых споем. реальною- времен», в том' числе при логическом проектировании' нейронной МЛИС логическою вывода для гидрогео;№1 орачаедки месторождений желечисго-марганиевых конкреций,

Ocnouni.it' isuiuo ii.i н [iciy.ibia iu работьк

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

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

3. Найдены запрещенные фигуры, определяющие

« Характеризацию раскраски графа противоречивости булевой функции;

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

4 Предложены 'эффективные семантические алгоритмы проектирования нейронных сетей на основе синтеза декомпозиции булевой функции через функции от четырех переменных, соответствующие элементам нейронной «hard»-Texiiojiornn, используемой в России н США.

5. Введен граф неравенств, на основе которого разработан эффективный ялюритм синтеза 4-синалтического нейрона, реализуемого на однородной гексагональной структуре.

6. На основе предложенного математического обеспечения разработаны программные средства, образующие инструментальную среду для ПЭВМ Pentium, в которой успешно решена задача автоматизированного логического проектирования нейронных сетей, функционирующих в условиях субмикроиной технологии, сложностью до 10й вентилей со средней "реактивностью" обработки одного вентиля ¡0'гс.

7. Внедрение разработанных программных средств в практику промышленного проектирования нейронных секй (Ьыкоаский >в»од средств

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

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

1. Горбатов Л.В. Частотный алгоритм определения подобия матриц инцидентности. • в сб. "Логическое управление с использованием 'ЗИМ", ЛИ СССР, М-Феодосия. 1991, 39-42.

2. Gorbatov A.V. Mographs isomorphism, "Control systems and computer science", vol I, Bucurcsti. 1991. 118-120.

3. Горбатов A.li. Синтез цифровою нейрона. - в cG. Информационные коммуникации, сети, системы и техиолопш. НА. N1.. 1993. 237-238.

4. Горбагов А.В. Решение проблемы синтеза повторной декомпозиции булевой функции и нейронная технология. - в сб. Информационные процессы, технологии, системы, коммуникации и сети. НА, М.. 1995, 27-35.

5 Горбатов А.В.. Кузьменко B.C. Стратегия шперкотнровки при проведении валютных операций, - в сб. Информационные процессы, технодо! ми. системы, коммуникации н сети. Il.-V М.. 1995. 156-158.

6. Горбатов А.В. Автоматнтированное логическое проектирование сотовых пенросетсй. - В сб. Информационные процессы, технологии, системы, коммуникации и ссги. Международная академия информатизации. Санкт-Петербург. 1495.5-6.

1 Горбаюв А.В.. Горбатова М.В. Интеллектуальное проектирование и моделирование нейронных сетей, функционирующих в условиях субмикронной lexHO.Toiini - В сб. иПнформ.мишцня». посвященном памяти Л. Нобеля. Международная академия информатизации. Ижевск. llW5. 111-121

8. Горбатов А.В. Характертация проектирования структур согоьой нейронной технологии. Информационные технологии N 0. М.. Машиностроение, 1995. 38-40.

9. Горбатов А.В. Структура запрещенных фигур при проектировании 4-синаптических нейронных сетей, в сб. Информационная математика н искусственный интеллект в информациологнн, Терек. Владикавказ. 1997, 8-12.

Ю.Горбатов А.В. Автоматизированное проектирование нейронных сетей для экспертных систем реального времени, - в сб. Информационная математика и искусственный интеллект в информациологнн, Терек, Владикавказ, 1997, ¡316.

П.Горбатов А.В. Характеризационно-дскомпозициоиный подход к синтезу нейронных сетей, - в сб. Информационная математика в информациодогии, НА, М.-Ижевск, 1997,4-11.