О синтезе разделительных схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА №ХАИ1К0-И4ТЕМАТИЧЕСКЙЙ ФАКУЛЬТЕТ

Чэ правах рукописи УДК 519.7

Влхлннцев Игорь Анатольевич О СИНТЕЗЕ РАЗДЕЛИТЕЛЬНЫХ СХЕМ

01.С!.09 - математическая кибернетика •

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата Физико-математических . наук

МОСКВА-1992

Работа вуюлнена в Болгоградскоа госудзротьенне:л унавет)сцгете5на кафедре дискретной матештихи.

Ьаучный руководитель: доктор фи?"1ко-мате?латичесгаах

наук

Л.Е.Андреев

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

наук,профессор Н.П.Редькин

кандидат физико-матекатиче-склх • наук Н.&.Карпова

Ведущая организация: Московский энергетический . институт

Зы;ита гяссертацкя состоится 1992г.

в 16.05 г^сов на зе~едании специализированного совет" д.053.05.05 при МГУ по адресу: 119399, Москва, Ленинские горы МГУ, механико-математический факультет, аудитория 14-Ой.

С диссертацией к окно ознакомиться в библиотеке нега'ико-нвтематического Факультета МГУ (14 этаж).

Автореферат разослан *"_ о/сг&ЗРЯ 1992Г.

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

наук • В.Н.Чубарикоз

.1 ». ОБЩАЯ ХАРАКТЕРИСТИКА PAFOTU

Актуальность проблемы. При проектировании управляющих систем,то есть устройств,осуществляющих хранение,передачу и переработку информации,часто возникает оадачз реализации разбиений шожеств булевых наборов - разделения множества нл шпересрчажщотся подмножества. Этт задача,нощталер,встречается при разработке г.-шифраторов, то есть устройств,устанавливавших однозначное состветеп.чс кезду- входным дешифрируемая сигналом а сигналом ка соответствующем выходе. В ЭВМ дегеифратори преобразуют код операции в упраьляищай сигнал,кол адреса - в сигнал шборгс'и соответствующей пчейгш памяти. Зта задач" возникает также и при разработке састем распознавания образов. Пусть,например, вгсется t оСпсзов я п признаков,хоракт еризуждах даннкэ обрзэн. Тогда -вмеетса некоторое шсяестсо m (m s 2П) булевнх поборов д-wi п - ."опустиин? набороБ значений признаков, п каждому образу соответствует некоторое подшшкество данного ююжества,причем подакожества,соответствующие разным образам, пе пересекаются.

Для контактных схем задача реализации систем элементарных кгашоняцпй кокет бить сведена к задаче " реализации разбыет?йй булевнх наборов. Задачей реализация лреизволышх я элементарных коеьшкцей- одинакового ранга, зависящих от одних и тех же персменшг , кэгтистнкля схемами занимались в разное время К. Пеннон , C.B. Яблонский , О.Б. Лупанов , Э.И.Непипорук., Н.П.Редь-нш . Но всо-таш» для произвольного, достаточно большого "числа реализуемых конъюнкций задача че Сила решена.

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

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

Научная новизна. Задача реализации произвольной с хтемы m элементарных конъюнкций ранга п контактными схемами бчла впервые рассмотрена в 1949г. К.Шгнноном1'. Для данной задачи им была построена схема в виде контактного дерева сложности 2n:1 - 2 , где п - ранг конъюнкций. Долгов время счйталось , что понизить

оцени" 2n+1 - 2 нельзя. Яблонский C.B. высказал предполо-

2 )

жение о том что это не так. И уже в 1958г. О.Б.Лупаноа ' предложил конструкцию, которая экономнее контактного дерева

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

1 ^ Shannon С.Е. The . synthesis oi tvo~terminal switching circuits. - Bell Syst.Techr J., 1949, v.28,1! 1, P.59-98 [Рус.пер.: Шеннон К. Работы по теории информации и кибернетике. - И.: ИЛ, 1963. - С.59-1011.

Лупанов О.Б. О синтезе контактных схем . • Доклады ан ссср, 1<jb8, т. 114, м 1, г.г'3-26.

Ь" нч поперио непересекающихся ефгр единичного рад: тупа,

где г - некоторая степень дпой.т. Пользунгь этой конструкцией , (КБ. Лупанов кострскл схему' с числом контактов виь..!Птг.тич}С5й« равный 2°, Задача синтеза схемы для системы

m элекг-йтар:^;* коньйкю'йи ранга п, где in s '/} была впервые

11

рассмотрена в 1 ЛЯг. Э.Й.Иеноторухом При построении

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

• 'л' 26 U

куба Е на (-§-) декзртошх произведении сфер - единичного

радикса размеркости ô. С немощью эчой конструкции 3.11. Кечи-.

поруи показал , что при выполнении условия M 5 s п чис;«о

контактов а схеш релизующей искомые m конт.юнкцкй не

превосходит

min + (М• 1)-§-,М r-j + (M б2 -f 2tbMb+1 ).

Очевидно,что донкыЗ .'гетод синтеза валяется асимптотически

оптимальшн) дашь при ш » ц . Аналогичный результат нчтекает вепесредств«нно я'из конструкции О.В.Лупанова при удалении неяслольпуешх 2n - m выходные вершин схемы с зявддектнши ия ребрами. .'•* •'

1 ^ Нечипорук Э.И. О топологических пришд,лох самокорректирования. - Ио-сладн' АН СССР,ШбВ,т. 179,H 4,С.786-769...

Нечипорук Э.И.. О топологических принципам самокорректирования. - Проблемы квбернетвкм,195Э,вып.21jC.5-102.

Дальнейшее продвижение в решении згой задачи было поя5 •

1 \

чено в 1975г. Н.П.Редышным Ик установлены* следгощие ^кты:

1 .Члсдо контактов в схеме реализующей исковые га конъюнкций

не превосходит •

и1п { 2Г 1 ш - 2)1,

Ге<1,.,.,п) I Г" >

2.Если 1ой_го = о(п) и = оЦс^т), то существует схема

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

Для реализации систем конъюнкций контактными схеиами В П.Редькишм была предложена следующая конструкция: снъ«ла строк.ся двухполюсник,реализующий даэъюниржо всех копъиисцкй данной системы как функцию с заданным числом единиц, а затей выходной полис этого двухполюсник« отождествляется с входами полюсом разделительной схе»1в для кнсжсс1£'1 булевых кабориа, на которых конъюнкции дачной системы сбпзщгвтся в единиц?. Таким образом задача реализации системы ¡п произвольных элементарных конъюнкций ранга п. может быт» сведена к задаче реализации разбиений булевых наборов. В настоян,ей работе приведено асимптотически оптимальное решение задачи реализации системы . т элементарных конъюнкций ранга п при условии 1ой„ш■ ~ п .

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

Редышн Н.П. О реализации систем конъюнкций контактными схемами. - Проблемы кибернетики, 1975,вып.30,С.2615-276.

- г

Функциональны! элементов и контактных схем. Многие результату, нелучениие для контактных схем.могут быть перенесеич с незначительная изменениям:! и на бинарные программы , состоящие только из команд передачи управлении, [{эк частики случай разбиений решается задача реализации произвольн 1 система ¡а элементарных конъюнкций ранга п контактными схемами.

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

Методы, предлп*еннна в ценной работе,опираются на теорию А.Ь.Андреева 1^ декомпозиции частичных Нулевых функций.

Андреев А.Е. о синтезе самокорректирующихся управляющих систем. - Доклады' АН ССПР,19е4,т.277,Ы З.С.521-525.

Андреев А.Е. Универсальна принцип сакокорректирова-ная. - Математический сборник,1985,т.127(169),N6,С.147-172.

Андреев А.В, Метод бесповторной редукции синтеза сзиокорректирующгеся сгем. - Доклада АН Г1СР, 1985, т.¿83,

1] 2,С.265-269.

Андреев А.Е. О синтезе топологических функциональных сетей. - Препринт ¡'.:59 - ИПМ31 АН СССР и МГУ им.М.В.Ломоносова ,.1985,67с.

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

Апробация регультатов р.Иота. Результаты работы докладывались и обсуждались на Ш-ем Все-союзкок сеиин«ре по дискретно? математике и ее приложения« (Москва,1990),на ГК-й Всесогзнэй конференций "Проблем» теоретической кибернетики" (Волгоград, 1990), - на сердарах кафедра дискретной математики Волгоградского государственного университета под руководством д.ф.-ю.н. А.Б,Андреева (Волгоград, 1933-1'?91 ).

Публикации, структура л объем работ, По теме дассертгцга} «втори*?, 'овубкяковано 3 работы, список которых приводятся г к^Яч"1 Диссертация состоит и?. введения, дв}х глав к сьлет.з литературы, содержит 5 рисунков. Бибдиогрйфед гключа»! 32 наименования. Полный объем диссертации - 104 страницы машинописного текста.

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

Во введении указывается тс ^«те-

матической кибернетики,к которому -относится наотоядаи работа,устанавливается ео актуальность. Формулирус-си цель работы и основные результаты,указывается с.фора иг вдакоуного гфиивнеиш. Придадите» краткое изло^ете содерти.чли -рьс1 ¡ты.

В а г р 5 о а г л а з э вводятся сс;:свн«е определения и рассматривается эвдача рс-."л'?з.-цс:и раэбиени* множеств булевых наборов и систем коныогзкцей контакта .г.-л схемами.

^р83б!-:е';{;ем множества назовем разбиение данного ¡даоязствп на t подмножеств- (среди которых допускаются пустые), а (к^.пь,,..-^-разбиением . - разбиение данного' . множества не 1 ыдоножеств с пздзнньыр неотрицательными мощ-, иостя«л га1 ,Г12,.,

ОЗегпзчгм через :!(т,п>- - клнес в-ех множеств из га 'булеокх наСороз ддиш п, через -КдШ ( Р.^я,. .¡п^)) -класс всех 1;-раэбкений(соответсгвенно, ,, ..т^Ьра^бг-енкп) тюягствэ &.

Нудей говорить,что схеив реализует раэбигшю (А^... множества Л е а(т,п),есля. ока реализует частятнай (п,!;)-оператор Р - .. . (то есть некоторое его

доопределений) т.зкой, ч?о

| 1, если й А:, м (б) - \ 0. если 5 -.г А \ Л ,

1 ! ' ~ п

I если у А, 1 = 1,2,..., 1, 5 а Е".

Схему,реолкзукщую ш-ряз5::еняи множества, ¡п булевых наборов, нановзм раздэлй?ельиой.

Обозначим ч>г.рез ЗСНЕ"(а,Т) - класс вгях схем, реализую-ата раьбпе -ле Т »»нокествэ Л. Чьрез £Х{Г>)- будг-а обозначать сложность схемы Б ¿правята^еГ? с;:с?ега г.

Введем следующие функционалы сложности: 1г(ЛД') = т11г. I1 ;3),

а^сЕИлцлд)

(П!,п,1) - ¡пах шах Г,1(АД!),

Ьг(га,п,11) и> ) = шах шах ЬТ(А,^').

1 1 ' АЬ!((Ш,П) ЛсЯА(и ....га^

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

21ое'п

Теорема 1,1. Если га * Н 1 .то

Ь^ (ю,в,го) ~ т .

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

Контактная схема,реалиэущаы некоторую булеву функцию (систему булевых функций) корректирует замиканив Ь (размыканий а ) контактов,если эта схема реализует ту' ае самуа фушсцш(систему функций) при коротком замыкании/размыкании в ней не более чем Ь(соответственно а) р^.оиэволыих контактов.

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

Получен следуш'чий результат

Лемма 1.2.4. _

'Ь*^(и.п> г (а+1)(Ь+1 )ш.

л.

Отсэда,в силу теоремы. 1.1.следует вывод,что асиаптотически

оптимальней самокорректирующаяся разделительная схема может быть получена с помощью тривиального дублирования контактов асимптотически оптимальной некорректируккцей разделительной схемы (каждый контакт дублируется параллельно a f 1 ргп " последовательно b + 1 раз),то есть справедлива

Slogan

Тесре.ча 1.2. Если га s г г -, то

Ь* й(т,п) (а-И ) (Ь+1 )га.

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

Обозначим через 1'Чп, л ; - наим"кыг£.а число_ контактов, достаточное для реплнзацрги произвольной систем« m злемепгэр-них конъшкцкй ранга п с перегоняй».« х,х , а тзрез

(г '

i..' , 'm,a) -' наименьшее число хонтактоя". достаточное для реализация произвольной скстсзсы ri элементарных конъюнкций рзнга г. с перзксНннми х i-x .обеспечивЕ/чее корректирование а обрывов и-b замиканий.

"остроим схему, реализующую m элементарных конъюнкций ранга п следуй®,™ образом : сначала построим двухполюсник, п^нлизукдап дазъ-онкций все'х конъкекцрб данной система как функцию с задакгам числом единиц, а затеи ототдестгим выходной iio.t;Qc зтего дзухьэлгеиика с входным полисом разделптель1-:;o:i exe;«' для множества булевых наборов , на которых яонъгшгадяп данной системы ебрэиаются в единицу. Поэтом/ из теорекм 1-1 в силу того, что дизъюнкция всех m конъюнкций ьожет 'быть реализована. при Доя. я ~ п со сложностью о(п) ,

следует

Теорзма 1.3. Если ~ п , то

Ьк{т,п) " я.

Из леммы 1.2.4 и теораш 1.2 следует Теорема 1.4. Если Ю£гт " п , та

г||Ь{в,п) " (а + 1){Ь + 1) я

Также доказан в сяедуэщкй рзэультач

1о£>а п

Теорема 1.5. Если г. * 2 " и ^орпп = о(аЬ). то

~ (а + 1)(Ь.+ 1)

. ¿иозшм результатом четвертого параграфа яйлялтся

Теорема 1.6. Если 20(5*и =£ 1о£гт 4 п, то

к 1о£?г Ь*(т,Р,г) " и. при то!^" ^

т при щгд ~ 6. где б е (0,1),

. ■ * ' • ..

1г га 102 г -306,1: !

"* ~-щг§т при П * Зов^п.

Теорема 1.Т. Если 1о1„1ое,|11д(т ,...,т )| г и

Юг2г = 0(^г10£2 |КЛ(П1,... ;.т1) I), ТО

т^пп-п 105г|КА(т1.....У..

Ь.Цв.п.и,,...^) Т0371 |1^Г(гг) 1.........

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

В периога параграфе рассматриваемая вопрос реализации разделительных схем (систем конъюнкций} для кшхестп булевых наборов в а о/, лиг конечных базисах из Р^ , где .Р^ - множество всех двуместных булевых фунгадяя. Положим хт = х ® г .к 1 , где г ч {0,1). Основным результатом о того "араграфа яъляютсп

Теорема 2.1. Если п = о( п ) и в полном конечном

базисе В из Р* не существует ни одной функции типа X «= У ,где 11,г2 е (0,1), ТО

Г^(ш,п,га) ™ 2т.

Теорема 2.2. Если п.10£,п - о( «л ) и в. полном конечном базисе В из Р; существует функция типа

т х

х 1 & у , где 1,»т, г {0 >1Ъ то Г.Б(т,п,т) " ш.

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

( logJR.{ra )|. .

2,3, Бела n = o^-15g-fgg-^n_T^T1J и

t-of л '

к log (к ,.i.,ra )|

где р(Б) - минимум прквад^кнах весов элементов базиса Б,

Т^аорзиа 2.4. Если n lor^n = о (в) и t - о (гг.} , то

к Ш log„t

bfim,n,t> " pVo)-^-—- ,

где р(Б > - минимум приведенных весов элементов базиса В.

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

1. Еихлянцев 5!.А. О реализации систем конъюнкций контактными . схемами. - Дискретная математика, 1989s т. 1, вып.4,С.3-11.

2. Зихлянцев И.А. О сашкор^эктированш контактных раэ-делигельннх схем. - Дискретная математика, 1 ПО,т.2, вып.1, с.ео-86.

3. Вахлявцев И.А. О разделительна* схеа. - 1Х-я

Есесоюзьая конференция по проблемам теоретической ккбер-нетшл, Т03ИС21 докладог,- Волгоград,1990,ч.П.

' лоцпиетяо в печать 29.0б.92г. Фзряаг60'<84/16. Бумага типографская. Усл,пз-4-.л.0,93. ¿ч.-изц.л.1,0. Тираж ГООэкз. Заказ ^00$ Волгоградский государственный университет Отпечатано в НПО "ВНЯИГ.МА1Д" 100011,, Волгоград II, ул.Цимлянская, 2а.