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

о

V, ')

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОГОНОССВА

№( АНИКО-МАТЕМАТИЧЕС КИЙ ФАКУЛЬТЕТ

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

Алехина Марина Анатольевна

УДК 519.718

СИНТЕЗ НАДШЫХ СХЕМ ИЗ НЕНАДЕЕНЫХ ДВУХВХОДОВЬК ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

01.01.09 - математическая кибернетика

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

МОСКВА - 1952

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

•Научный руководитель - доктор физико-математических наук, ■

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

профессор Л.А.Поломов,

- кандидат физико-математических наук,, доцент С.А.Ложкин.

Ведущая организация - Вычислительный центр РАН.

в 16 час. С6 мин. на заседании специализированного совета Д.053.05.05 при МГУ по адресу: 119899, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

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

Защита диссертации состоится

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

Автореферат разослан "Ж" 1993 г.

7

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

В,Н.Чубариков

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

Актуальность темы

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

Цель работы

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

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

Научная новизна

I. Разработаны методы синтеза надежных схем из ненадежных элементов в базисах {®/у] , {«&* ^ . -{XV«., х] , ПРИ неисправностях типа 0 и

типа I.

2. Получены верхние оценки ненадежности схем в каждом из перечисленных базисов.

3. Получены нижние оценки ненадежности схем в перечисленных базисах.

4. Показано, что представленные методы оинтеза позволяют реализовать почти все функции в базисах £ Л /^ , СХ * УЗ ' [^^У' ' прИ неисправностях типа 0 и типа I, в базисе ЗС.^} при неисправностях типа 0 и в базисе £ ^^^ ^З "Р0 неисправностях типа I схемами, асимптотически наилучшими с точки зрения надежности функционирования.

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

• Теоретическая и практическая ценность

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

Методика исследования

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

налыюго анализа, математического анализа.

Апробация результатов

Материалы диссертации докладывались на Ломоносовских .чтениях ( Москва, 1951 ), а также на семинарах С.В.Яблонского "Математические вопросы кибернетики", О.Б.Лучанова "Синтез управляющих систем" и других в МГУ имени М.В.Ломоносова.

Публикации

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

Объем и структура работы

Диссертация состоит из введения, четырех глав и списка литературы, включающего 14 наименований. Общий объем работы состовляет 92 страницы. Изложение материала иллюстрируется 56 рисунками.

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

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

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисах £ 5С / .

^зеуу.х^, . Схема реализует функцию .....^и-) •

лед/

, если при поступлении на входы схемы набора = ($"«,..., при отсутствии неисправностей в схеме на

ее Еыходе появляется значение • Все элементы схемы

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

Сложность 1(5) схемы 5 определяется как число входящих в нее элементов.

Пусть Р- ч ( «•) вероятность появления значения К*) 4

fff) на выходе схемы 5 , реализующей функцию , при

входном наборе г . Ненадежность Р(6) схемы 5 определяется как максимальное из чисел Р- . (

К«) 4 •

при всевозможных входных наборах ? . Надежность схемы S , следовательно, равна i~P(S) .

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

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

Определение. Два функциональных элемента Е и , Е подверженных неисправностям разного типа, называются двойственными, если двойственны реализуемые ими функции У (я-,у) и *f*fap), то есть Ч"(х, f) •

Определение. Две схемы 5 и S* двойственны,

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

Лета 1.3 утверждает, что'для двойственных схем на противоположных входных наборах вероятности ошибок равны. Следовательно (Следствие 1.1), равны ненадежности двойственных схем. Поэтому утверждение о надежности, доказанное для функции 4 в данном базисе и при данном типе неисправностей, верно для двойственной функции £ * в двойственном базисе и противоположном типе неисправностей.

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

О, , $ , с 1. определяются базисом и типом неисправностей, О.е^.2, зJ . Нижние оценки-надежности схем получаются из верхних оценок ненадежности с учетом определения надежности. . Для базиса £ X, > у^ и неисправностей типа О

а. = 2 , £ = 8. , с = , г ' /во

Для базиса [Я"' и неисправностей типа I

а = 1 , $ = 2 , с = 35 , ъ = < /во ■

Для базиса £ ^ и неисправностей типа О

а. = I , 2 ' , с = 35 , 4 = ''/ •

Для базиса [^^у] и неисправностей типа Ь

а. - 2 , # - <Р , с = 45У , -2 = '/50

Для базиса ^Л^, 5.J . и неисправностей типа 0 ,

а - 3 , /5 , С = 3/0 , 4 = '/У5£> •

Для базиса и неисправностей типа I

£2. = 2 , 1С = 5-00 , £ = .

- Б -

Для базиса £ X V у, зс^ и неисправностей типа О , 12 , с - 500 , .

Для базиса ^ 3 и неисправностей типа I

а. = 3 , ё - , , г ж 1/{50 .

Для базиса £ сс уу, ¿С 1/у, и неисправностей типа о и типа I а ■= * , , с * ¿о , г-**/а .

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

В третьей главе доказаны нижние оценки ненадежности схем. Показано, что почти все функции нельзя реализовать схемами, ненадежность которых менее й.у + при ^е (о, ¿) . Классы Р этих функций и константы £ , в , и Л приведены ниже.

Для базиса £ X / ^^ и неисправностей типа О

Р-[К*-<...../(а)*«г и^аО, ¿ф.....п,} %

для реализации функда^ ^ требуется не менее трех элементов^,

к = г , е = - з , /я. -1 , £. */ ъ .

Для базиса 11 неисправностей типа I

Для базиса и неисправностей типа О

, с-1, е- *п-о ,

Для базиса ^ и неисправностей типа I р = .....ом1 , /(х) К-^а). ¿е£*.....Й,] .

для реализации функции ^ требуется не менее трех элементов|.

К » 2 , е ' -ъ , т,. 1 , Уъ .

Для базиса £ Ж- и неисправностей типа О

/? = [/(х,,... хО .• ¿(30 * ъ , {(£) * ЩТЦЕ) ,

í./ejV..«}} , ic. = Ъ , ¿=-9 , m- = 9 , i - Vi50.

Для 'базиса [лку. 2.] и неисправностей типа I

P-[í '• , z -1 , е. т -О , i - 1.

Для базиса 1/^, xj и неисправностей типа О

P-{f :f, b - i , г - м - о , i -1.

Для базиса [xv^, х j и неисправностей типа I

......Иж, и^сг;, / ж,- иад,

6 {'<.-. . К- - з . -9 , т.- 9 , i - </<50.

Для базиса xt'y, 5с J и неисправностей типа О

и типа I F-[f : -f^conlij , к. - i , £ = m-= О , á - -f.

Доказательство каждой из теорем о нижних оценках -ненадежности схем состоит в том, что в схеме 6 , реализующей функцию из класса Р , выделяется подсхема, содержащая выход схемы и обладающая тем свойством, что ее ненадежность не больше ненадежности схемы £> и не меньше е+ при yg(o,s).

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

Из верхних и нижних оценок ненадежности', доказанных во второй и третьей\лавах, для базисов / yj '{^^i/j '

X vy, 5Í.J при неисправностях типа 0 и типа I, для базиса £ х Vy, xj при неисправностях типа 0 и для базиса 2.J при неисправностях типа I следует возможность реализации почти всех футавдй схемами, ненадежность которых асимптотически равна ft-j- при ^ О . Константа Q, описана и приведена выше.

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

кой, что ¿(s)= 0(г*/*>). PCь) ¿a*

при X ~ ^ • К°нстанты & ж В описаны и приведены выше, константы £ и {. зависят от базиса и типа неисправностей. Доказательства теорем этой главы конструктивны.

Из результатов третьей и четвертой глав для базисов [я-'у] ' {^^У- "У» * J при неисправнос-

тях типа 0 и типа I, для базиса ^сс-Уу, х^ при неисправностях типа 0 и для базиса ® J при неисправностях типа I следует возможность реализации почти всех функций схемами, асимптотически наилучшими с точки зрения надежности и без существенного увеличения сложности.

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

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

1. Алехина М.А. 0 синтезе надежных схем из функциональных элементов ос- / ^ при однотипных константных неисправностях на выходах элементов //Вестн. Моск. ун-та. Матем. Механ. 1991. Л 5. 80-33.

2. Алехина М.А. О сложности надежных схем из функциональных элементов при однотипных константных неисправностях на выходах элементов//Вестн. Моск. ун-та. Матем. Механ. 1992. № 5. 79-31.

3. Алехина М.А.,0 надежности схем в базисе

при однотипных константных неисправностях на выходах элемен-тов//Ве~.тн. Моск. ун-та. Матем. Механ. 1992. № 6. 3-6 -я

АЛЕХИНА МАРШ АНАТОЛЬЕВНА

СИНИВ НАДЕЖНЫХ СХШ ИЗ НЕНАДЕЖНЫХ ДВУХВХОДОВЫХ ОУНКЩЭНАШШХ ЭЛЕМЕНТОВ

/Автореферат/

Подписано к печати 07.12.92 Оорлат 60x90 I/I6 п.л. 0,8

Уч.год.л.0,6 Тираж 100 Заказ 482 МП ТАРАНТ"_

Ротапринт MACW-ВТТЗ-ЗИТ/ ,1092 80 .Москва, Автозаводская, 16