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

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

ЧУГУНОВА Варвара Валерьевна

СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМ ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ НА ВХОДАХ ЭЛЕМЕНТОВ

Специальность 01.01.09-дискретная математика

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

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

Нижний Новгород - 2007

003056694

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» на кафедре «Дискретная математика».

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

доцент Алехина М. А.

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

профессор Мошков М. Ю.; доктор физико-математических наук, доцент Жильцова Л. П.

Ведущая организация - Московский государственный университет

им. М. В. Ломоносова (механико-математический факультет).

Защита диссертации состоится « /У» иаХсЬ 2007 г., в /¿Г часов, на заседании диссертационного совета Д 212.166.06 в Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, конференц-зал ННГУ, корп. 2.

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

Автореферат разослан иСРС/ЦУг-О— 2007 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент \JKXJ Лукьянов В. И.

Общая характеристика работы

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

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

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

переходит с вероятностью е (ее(0; 1/2)), реализует функцию /(х). С помощью итерационного метода Дж. фон Нейман установил, что при с (ее(0; 1/6)) произвольную булеву функцию можно реализовать схемой, на выходе которой вероятность ошибки при любом входном наборе значений переменных не превосходит се (с - некоторая абсолютная константа). Однако сложность такой схемы с ростом числа итераций увеличивается экспоненциально (примерно в Зк раз, где к - число итераций).

Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах Р. Л. Добрушина, С. И. Орткжова, Д. Улига и некоторых других авторов, причем главное внимание уделялось сложности таких схем (задача синтеза схем наилучших по надежности не ставилась).

' von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies, edited by Shannon C., Mc. Carthy J. Princeton University Press, 1956 (русский перевод: Автоматы. - M.: ИЛ, 1956. - С. 68-139.)

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в произвольном конечном полном базисе В = {е,, е2, —,ет}, т е N (множество всех функциональных элементов функции которых е, принадлежат базису 2?, будем также называть базисом В1). Каждому элементу базиса приписано положительное число v(E!) - вес данного элемента. Пусть сложность L(S) схемы S из ненадежных элементов3, реализующей булеву функцию f(x), определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимым образом с вероятностью е переходят в неисправные состояния. Ненадежность P(S) схемы S определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах, т. е. P(S) = ma.xPj{S)(S,a), где Pf{S)(S,a) — вероятность появления значения

/(а) на выходе схемы S при входном наборе а, а максимум берется по всем возможным входным наборам а. Надежность схемы S равна 1 - P(S).

Вводится функция Шеннона Lpc(n) = maxminL(S), характеризующая

f s

сложность схем, реализующих функции от п переменных в базисе В, где минимум берется по всем схемам S из ненадежных элементов, реализующим функцию J[xlt х2, ..., хг) с ненадежностью P(S)< р, а максимум - по всем булевым функциям /от п переменных.

Пусть р = min(v(£'( )/(«(£i) -1)), где минимум берется по всем элементам Е: базиса, для которых «(£,) > 1, «(£,) - число существенных переменных функции е„ реализуемой элементом Е„ a v(E,) - вес функционального элемента Еi = 1, ...,т.

О. Б. Лупанов4 показал, что для схем, реализующих булевы функции от п переменных и состоящих только из надежных элементов (т. е. при е = О up = 0), выполняется соотношение L0Р(и)~р ■ 2" /п.

С. И. Ортюков5 для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0<e<s0, p>q{s)Lg, где Lg- минимальное число надежных элементов, необходимое для реализации функции

2 Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984.

3 Редькин Н. П. Надежность и диагностика схем. - М.: Изд-во МГУ, 1992.

4 Лупанов О. Б. Об одном методе синтеза схем // Изв. вузов. Радиофизика. - 1958. -Т. 1. -№ 1.-С. 120-140.

5 Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике к ее приложениям (Москва,27-29января 1987г.).-М.: Изд-во Моск. гос. ун-та, 1989.-С. 166-168.

голосования g(xl,x2,xJ) = xtx2 v x,x3 v x2x} в базисе В, q(z) - некоторая функция такая, что q(z) = е + Зе2 + о(е2) при е -> 0. Тогда существует такая функция р(е) —> р при в -» 0, что Lp е(и)йр(е)-2"/и.

Д. Улиг6 для инверсных неисправностей на выходах элементов с вероятностью ошибки в показал, что для любых, сколь угодно малых чисел с и Ъ {с, b > 0) существует число г' (е'е(0, 1/2)) такое, что при любом е (eg(0, е')) и любом р, удовлетворяющем условию p>(\ + b)z L,, (точнее

р > q(z) Lg), справедливо соотношение Lp r (n) á (1 + с)р -2" I п.

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

Из результатов Н. Пиппенджера7 следует, что при инверсных неисправностях на выходах элементов с вероятностью ошибки ее(0, 1/200] любую булеву функцию от п переменных в базисе {&, v, } можно реализовать такой схемой S, что P(S) < ISz,L(S) s 170-2"/и.

С. В. Яблонский8 рассматривал задачу синтеза надежных схем в базисе В = {X|&X2, X)VX2, x¡, g(x,,x2,xj)}. Он предполагал, что элемент, реализующий функцию голосования g(x,,.*2,x3) = х,х, v х2х, v х,х3, абсолютно надежный, а конъюнктор, дизыонктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше е. Им доказано, что для любого р > 0 существует алгоритм, который для каждой булевой функции j{x\, х2, ..., х„) строят такую схему S, что P(S)<p,L(S) á2n-'/п.

В. В. Тарасов9 рассматривал задачу построения схем сколь угодно высокой надежности (когда P(S) —> 0). Для базисов из ненадежных функ-

6 Uhlig D. Reliable networks from unreliable gates with almost minimal comlexity // Fundamentals of Computation Theory. Intern, conf. FCT'87 (Kazan, June 1987). Proc. Berlin: Springer-Verl., 1987. - P. 462-469 (Lecture Notes in Comput. Sci.; V. 278) (русский перевод: Автоматы. - M.: ИЛ, 1956. С. 68-139).

7 Pippenger N. On networks of Noisy Gates // 26 Symposium on Foundation on Computer science, 21 -23.10.1985, Portland, 30 - 38.

8 Яблонский С. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center.-1982. 7. - P. 11 - 19.

9 Тарасов В.В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. - 1976. - Т. 20. - № 3. - С. 391-400.

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

С. И. Аксеновым10 получена оценка ненадежности схем в произвольном полном базисе В при инверсных неисправностях на выходах элементов. Он доказал, что в произвольном полном базисе В при ее(0; Бо) любую булеву функцию можно реализовать такой схемой б1, что Р(5) < к€ + се2, где к (к < 5) - минимальное число надежных элементов, необходимое для реализации какой-либо из функций вида £,(.*], х2, х3) = х°'х22 v х"'хп,г v х2*х"', 82(х1,х2,х],х1) = х",хг2' Vх^х*',(х,,х2,х3,х,) = (х"1 ух"1)^1 Vха4<), сг,е{0,1}, /е{1, 2, 3, 4), а е - ненадежность базисного элемента. Константы к, с, ео положительны и зависят от базиса В. Таким образом, в произвольном полном базисе любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше 5с при с —> 0. Вопрос о возможности снижения мультипликативной константы 5 в оценке ненадежности для произвольного базиса пока остается открытым.

М. А. Алехина11 решала задачу построения асимптотически оптимальных (асимптотически наилучших) по надежности схем при однотипных константных неисправностях только на входах или только на выходах элементов. Чтобы сформулировать полученные М. А. Алехиной результаты, введем необходимые определения.

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

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

,0 Аксенов С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. -№ б (21). -2005. - С. 42-55.

11 Алехина М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных функциональных элементов. - Пенза: Инф.-издат. центр Пенз. гос. ун-та, 2006.

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

Понятие ненадежности P(S) схемы S в случае однотипных константных неисправностей определяется так же, как для инверсных неисправностей на выходах элементов.

Пусть Pe(f) = inf P(S), где инфимум берется по всем схемам S из ненадежных элементов, реализующим функцию Дхь х2, ..., х„). Схема А из ненадежных элементов, реализующая функцию /, называется асимптотически оптимальной (асимптотически наилучшей) по надежности, если

Р (Я

Р(А) ~ Pt(f) при е -> 0, т. е. lim_si£i = 1.

s->o Р(А)

М. А. Алехиной доказано, что во всех неприводимых полных базисах (исключая три случая), содержащих функции не более чем двух переменных, почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью, асимптотически равной ас' при в —> О, константы а и t зависят от базиса и типа неисправностей, ае{ 1, 2, 3}, te{l, 2}. Сложность таких схем по порядку равна сложности схем, построенных только из надежных элементов (т. е. увеличивается несущественно).

Также М. А. Алехина12 рассматривала инверсные неисправности на входах элементов и доказала, что при инверсных неисправностях на входах элементов в базисах {х\ \х2} и {.тДл-2} почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью, асимптотически равной 2е при в 0. Сложность этих схем по порядку равна сложности минимальных схем, состоящих только из надежных элементов.

Вопрос о возможности построения асимптотически наилучших по надежности схем в других, отличных от {xi |х2}, {ху1х2} базисах из двухвхо-довых функциональных элементов при инверсных неисправностях на входах, оставался открытым. Ответ на него для всех остальных неприводимых полных базисов из двухвходовых функциональных элементов получен в данной диссертационной работе. Существенное внимание уделяется сложности асимптотически оптимальных по надежности схем.

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

12 Алехина М. А. О надежности и сложности схем в базисе {х\у} при инверсных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. -№ 6 (21). -2005. - С. 36-41.

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались на XIV Международной конференции «Проблемы теоретической кибернетики» (г. Пенза, 2005), на VII Международной конференции «Дискретные модели в теории управляющих систем» (Моск. обл., с. Покровское, 2006), Международном симпозиуме «Надежность и качество», (г. Пенза, 2006), XVI Международной школе-семинаре «Синтез и сложность управ-

ляющих систем» (г. Санкт-Петербург, 2006), на семинаре «Математические вопросы кибернетики» под руководством профессора О. М. Касим-Заде в МГУ им. М. В. Ломоносова, на семинаре «Надежность и диагностика управляющих систем» под руководством профессора Н. П. Редькина в МГУ им. М. В. Ломоносова, на городском семинаре по дискретной математике под руководством профессора В. Н. Шевченко в Нижегородском государственном университете им. Н. И. Лобачевского.

Публикации. Результаты диссертации опубликованы в 9 работах автора, список которых приведен в конце автореферата; среди них 4 основные работы опубликованы в журналах, рекомендуемых ВАК для публикации результатов диссертаций. Три работы из 9 написаны в соавторстве с научным руководителем М. А. Алехиной (опубликованные результаты являются собственными, М. А. Алехиной принадлежат постановка задачи и идея доказательства).

Структура диссертации. Диссертация состоит из введения, четырех глав, списка литературы и приложения. Объем диссертации составляет 110 страниц, включая 5 таблиц и 28 рисунков. Список литературы содержит 25 наименований.

Содержание диссертации

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

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

Схема реализует функцию _/(х), х2, ..., х„), если при поступлении на входы схемы набора а = (аь а2, ..., а„) при отсутствии неисправностей на выходе схемы появляется значение /(а). Предполагается, что все входы элементов схемы независимо друг от друга с вероятностью е (ее(0; 1/2)) подвержены инверсным неисправностям. Эти неисправности характеризуются тем, что поступающее на вход элемента значение а, ав{0, 1}, с вероятностью е может превратиться в значение а.

Ненадежность Р(5) схемы 5, реализующей функцию /(х), и понятие асимптотически оптимальной по надежности схемы при инверсных неисправностях на входах элементов определяются так же, как и при однотипных константных неисправностях. Веса всех элементов равны единице, поэтому сложность ¿(Б) схемы 5 равна числу функциональных элементов в ней.

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

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

М(х\, х2) = {Х]&Х2, х\\,х2, х\ \х2, х\1-х2, х]-^х2, х\ ~Ьх2, х\~х2, х\@х2, хг , О, 1}.

Определение. Множество В с М(х\, х2) назовем неприводимым полным базисом (в Р2), если множество В полно и никакое его собственное подмножество полным не является.

Введем в рассмотрение неприводимые полные базисы: В\ ~{х] |х2}, В2 = Вг = {х1->х2, X] -/>х2}, В\ = {х,->хь х|фх2}, В5 = {х| -/>х2, Х1~Х2},

В6 = {х[Фх2, Х[&Х2, 1}, В1 = {х1~х2, Х|ух2, 0}, Вц ~ {х!~х2, х\&х2, х|©х2}, В9 = {х\~х2, х]\/х2, х|фх2}, В10 = {х!~х2, х1&х2, 0}, Вп = {х!©х2, х1чх2, 1}, В12 = {х\фх2, X, }, В\3 = {х,->х2, X, }, Ви = !}. #15 = {х\->х2, 0},

Вы = {х,&х2, х, }, Вп = {х\чхъ х, }.

В Р2 существует ровно 17 (с точностью до переименования переменных) неприводимых полных базисов, содержащих функции не более чем двух переменных. Любой другой базис, отличный от базисов В\ — Вп (например, В\% = {х!&х2. х^х2, х, }), можно получить переименованием переменных без отождествления, а также добавлением одной или нескольких функций из множества М(хь х2) к некоторому базису из указанного списка.

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

Пусть в схеме Я, реализующей булеву функцию /, отличную от константы, выделена подсхема В, имеющая один вход, содержащая выход схемы 5 и реализующая инверсию. Обозначим через С подсхему, получаемую из схемы 5 удалением подсхемы В. Очевидно, что схема С реализует /. Если выполнено неравенство Р(5!) > Р(С), то будем говорить, что схема С надежнее схемы 5 и получается из 5 удалением подсхемы В.

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

Теорема 1.1. Пусть схема 5", ненадежность которой равна Р{5), реализует функцию /и является с-схемой. Если в £ можно выделить подсхему В, имеющую один вход, содержащую выход схемы и реализующую инверс-

ную функцию с вероятностями ошибок /?о и р 1 такими, что 0 <р0 +р\ < 1, то

верно неравенство гшгн———, ———I < Р(Б).

[Р0+Р1 Ро+Р,}

Теорема 1.1 устанавливает соотношение между надежностными характеристиками схемы и ее подсхемы специального вида и используется для получения нижних оценок ненадежности схем.

Функционирование двухвходового базисного элемента Е с приписанной ему функцией е можно задать таблицей 1, в которой Ро, Р\ - вероятности появления 0 и 1 соответственно на выходе элемента (р\,рг,рг,р4 - 0).

Определение. Элемент Е* с приписанной ему функцией е*, двойственной функции е, назовем двойственным к элементу Е, если он функционирует согласно таблице 2.

Таблица 1__Таблица 2 _ _

XI Х2 е{х\, хг) Ро Л

0 0 е(0, 0) Р\ 1-р.

0 1 е(0. 1) Р2 1 -Р2

1 0 е(1, 0) Рз 1 -Рз

1 1 1) Р4 1 -р4

Х\ Х2 е*( хи х2) Ро Р\

0 0 ё(1,1) 1 -р4 р4

0 1 ё(1,0) 1 -Рз Рз

1 0 ё(0,1) 1 ~Р2 Р2

1 1 ё(0,0) 1 "р. Р\

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

Теорема 1.213. Для любых двойственных схем 5 и и любого входного набора а верно равенство Ру(г)(5, й) = Р-(-)(5'*, а), где а = (а,, аг,..., а„),

х2, ..., л-„),/*(х|, х2, ..., хп) - функции, реализуемые схемами 5 и 5* соответственно.

Следствие 1.1й. Для любых двойственных схем 5 и 5* верно равенство Р(Б) =

Теорема 1.2 утверждает, что для двойственных схем на противоположных входных наборах вероятности ошибок равны. Поэтому (следствие 1.1) равны ненадежности двойственных схем. Следовательно, утверждение о надежности, доказанное для функции / в базисе В при инверсных неисправностях на входах элементов, верно для двойственной функции/" в двойственном базисе В* при тех же неисправностях элементов. В диссертационной работе свойства двойственных схем используются следующим образом: получив результат в базисе В для функции / переносим его в двойственный базис В* на функцию/", сокращая тем самым объем исследовательской работы.

13 Алехина М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных функциональных элементов: Монография. - Пенза: Инф.-издат. центр Пенз. гос. ун-та, 2006.

Теорема 1.2 и следствие 1.1 доказаны М. А. Алехиной для произвольных неисправностей функциональных элементов. Нами эти утверждения используются для случая инверсных неисправностей на входах элементов.

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

Лемма 1.912. Пусть f - произвольная булева функция, отличная от константы, и S - любая схема, ее реализующая. Пусть подсхема В схемы S содержит выход схемы S и реализует булеву функцию /' с ненадежностью Р(В) < 1/2. Обозначим /?' - минимум вероятностей ошибок на выходе схемы В по таким входным наборам b , что f'(b) = 0. Аналогично р° — минимум вероятностей ошибок на выходе схемы В по таким входным наборам Ь , что f'(b) = 1. Тогда вероятности ошибок на выходе схемы S удовлетворяют неравенствам P^S, а)>р\ если / (а) = 0; P0(S, а)>р°, если f(a) = 1.

Замечание 1.112. Из леммы 1.10 следует, что P(S) > тах{р°,/з!}.

Лемма 1.9 и замечание 1.1, доказанные М.А. Алехиной для произвольных неисправностей функциональных элементов, используются нами далее для случая инверсных неисправностей на входах элементов.

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

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

Сначала описывается общий метод синтеза надежных схем в произвольном полном конечном базисе, который позволяет найти оценку ненадежности схемы S, реализующей булеву функцию f. Для этого построим схему S/„ реализующую функцию Х\ I х2, и обозначим вероятности ошибок на выходе схемы S¡, следующим образом: /7* (00) = а, р'й (01) = ß, /5* (10) = 5, р*(11) = т. Найдем оценку ненадежности схемы S, реализующей булеву функцию^ используя теорему 2.2.

Обозначим (.1 = max{a, ß, 6, т} - ненадежность схемы Sh.

Теорема 2.2. Если це(0; 1/50], то любую булеву функцию / можно реализовать схемой S, такой, что P(S) < 4ц.

Полученный результат конкретизируется для каждого из базисов Вь В2, Вц — ¿¡п, В\б - ßi8. Иначе получены оценки ненадежности схем в базисах Въ, В ¡2, В и, В и, В\5- Здесь в качестве схемы S/, берем схему, реализующую функцию хДхг, двойственную функции Х\ I х2. Вычисляем вероятности оши-

бок />'(11). р\ (Ю)' Р, (01), р'й (00) на выходе этой схемы. Полагая р*(11) = а, р* (10) = Р, р\ (01) = у, />¿(00) = т, воспользуемся теоремой 2.2 и получим оценку ненадежности схемы 5, реализующей произвольную функцию/

Затем строятся схемы более надежные, чем схемы 5. В базисах В\, В2, В16, и В17 для повышения надежности схемы 5 использовалась схема ф(5), построенная следующим образом: возьмем два экземпляра схемы 5, реализующей булеву функцию /(х,, х2,..., х„), соединим их выходы с входами схемы 5/„ реализующей функцию Х\ | х2; затем возьмем два экземпляра этой схемы и соединим их выходы с входами еще одной схемы 5/,. Схема ф(5) построена.

В базисах В3) Вп, Вп, В\$ для повышения надежности используется схема ф(5), в которой в качестве схемы 5/, рассматривается схема, реализующая функцию х]4х2.

Очевидно, что в результате применения (возможно, неоднократного) операции ф к схеме 5, ре&чизующей функцию/ получаются схемы, реализующие ту же функцию/

В базисах В4 и для повышения надежности использовалась схема 4/1(5, 5'): возьмем один экземпляр схемы 5, реализующей функцию/ два экземпляра схемы 5', реализующей функцию /, и соединим выходы схем 5,5", 5 соответственно с первым, вторым и третьим входами схемы Sg, реализующей функцию g(xl, х2, х}) = х1х2\г xix}v х2х}. Очевидно, что в результате применения (возможно, неоднократного) операции к схемам 5 и 5, реализующим функции/и / соответственно, получаются схемы, реализующие/.

В базисах В в, Вт, и В? для повышения надежности использовалась схема Ц/(5): возьмем три экземпляра схемы 5, реализующей булеву функцию /, и соединим их выходы с входами схемы Sg, реализующей функцию голосования g(x],x2,xз) = х,х2 V х,х, Vх,х3. Очевидно, что в результате применения (возможно, неоднократного) операции \|/ к схеме 5, реализующей булеву функцию/, получаются схемы, реализующие функцию/

В базисах Вщ и В и для повышения надежности использовалась схема \|/2(5, 5'): возьмем два экземпляра схемы 5, реализующей функцию /, один экземпляр схемы 5', реализующей функцию /, и соединим выходы схем 5, 5', 5 соответственно с первым, вторым и третьим входами схемы Sg, реализующей функцию g(xl, х2, х3) = х, х2 Vх,х3 V х2х3. Очевидно, что в результате применения (возможно, неоднократного) операции 4/2 к схемам 5 и 5', реализующим булевы функции /и / соответственно, получаются схемы, реализующие функцию/

В базисе ¿?18 для повышения надежности использовалась следующая схема ф(5): возьмем два экземпляра схемы 5, реализующей булеву функцию /, и соединим их выходы с входами конъюцктора, затем выходы двух экземпляров таких схем соединим с входами дизъюнктора. Очевидно, что в результате применения (возможно, неоднократного) операции ф к схеме 5, реализующей функцию/ получаются схемы, реализующие ту же функцию/

Таким образом, во второй главе доказано, что каждому из базисов В\ - ¿?18 можно поставить в соответствие константы а, Ь, с1 (таблица 3), такие, что при ее(0; с!\ произвольную булеву функцию /(*,, х2,..., хп) можно реализовать схемой 51, ненадежность которой Р(!$) < ас + Ье2.

Таблица 3

В а Ъ d Ь К(п)

Si = {x,|x2} 2 19 1/100 - 1 1/4 xh 1

Вг = {xiix2} 2 19 1/100 -1 1/4 xh 0

Вз = {х¡-^х2, xi-^x2} 2 51 1/300 - 1 1/4 х,-, 0, 1

В4= {xi-»x2,xi©x2} 2 66 1/200 -2 1/4 *„ 1

£5= {x\-1>xi,x\~x2} 2 66 1/200 -2 1/4 xh 0

Be ~ {х](эх2, х1&х2, 1} 2 67 1/200 -2 1/4 xh 0, 1

В7 = {х\~х2, x\vx2, 0} 2 67 1/200 -2 1/4 x/, 0, 1

Вг = Х1&Х2, Xl©X2} 2 62 1/300 -2 1/4 х/, 0

В') = {Xl~*2, x\wx2, xi®x2} 2 62 1/300 -2 1/4 X,; 1

В]0 = {xi~x2, х\&х2, 0} 2 66 1/200 -2 1/4 x,-, 0

В11= {*1®Х2, х\vxz, 1} 2 66 1/200 _2 1/4 1

в12 = {х\ х2, Л*! ; 3 41 1/150 -6 1/6 xf&h(x), 1

в 13 = {х\-+х2, х\ } 3 41 1/150 -6 1/6 xf v h{x), 0

= {x\-f>x2, 1} 4 59 1/200 -8 1/11 (x? &.h{x)f

В\Ь = {xi-Мг, 0} 4 59 1/200 -8 1/11 (xf&/r(x)f

В\6 = {х\&х2, x1 } 4 83 1/200 - 12 1/10

В17 = {XlV*2, хх } 4 83 1/200 - 12 1/10 (xf & h(x)f

В\ц = {.Х1&Л2, xivx2, л-| } 2 19 1/150 -2 1/6 xf, 0, 1

Используемые в таблице 3 обозначения: г = 1 ,п, 6, це{0,1}, /г(х) -произвольная булева функция от п переменных (х = (х|, х2> ..., х„)).

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

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

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

Для получения нижних оценок ненадежности схем в базисе В используются следующие методы:

1) в произвольной схеме S, реализующей функцию / £ К(п), выделяется некоторая связная подсхема, содержащая выход схемы S, и по некоторым вероятностям ошибок подсхемы оценивается ненадежность схемы S;

2) в произвольной схеме S, реализующей функцию / g К(п), выделяется связная подсхема специального вида (с-схема), содержащая выход схемы S, по некоторым вероятностям ошибок которой можно оценить ненадежность всей схемы S;

3) для схемы S, реализующей функцию / g К(п), доказывается существование набора значений входных переменных, на котором вероятность ошибки на выходе схемы не меньше az + be2, если ее(0; d ] (см. таблицу 3).

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

Доказано, что каждому из базисов В\-В\% можно поставить в соответствие константы a, b, d и классы булевых функций К(п) (см. таблицу 3) такие, что при се(0; d ] любая схема S реализует булеву функцию /(.г,, х2,..., хп),

f g К{п), с ненадежностью P(S) > az + bz2. Константа а здесь га же, что и во второй главе.

Классы К(п) содержат почти все булевы функции.

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

V. Четвертая глава диссертации посвящена сложности асимптотически наилучших по надежности схем. Доказано, что сложность асимптотически наилучших по надежности схем в рассматриваемых базисах В\ — Bts по порядку равна сложности схем, построенных только из надежных элементов.

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

Теорема 4.1. Пусть В - произвольный полный базис, к - сложность минимальной схемы S/,, реализующей функцию х, |х2 с вероятностями ошибок на выходе /?д00) = а, />о(01)= ß> Ро(Ю)= А О1) = т и И = max{a, ß>

5, т}. Тогда при це(0; l/600i] произвольную булеву функцию f от п переменных можно реализовать такой схемой S, что L(S) й 56-к-2"/п и P(S) < 7р..

Теорема 4.213. Пусть S - схема, реализующая произвольную булеву функцию / в базисе В, Sg - схема, реализующая функцию голосования g(x 1, х2, Х3) = х,х2 v Х|Х3 v х2хз в том же базисе. Тогда можно построить схему \)/(5), реализующую функцию f, для которой < 3P2(S) + P(Sg),

L(4l(S)) = 3L(S) + L(Sg)^3L(S).

Теоремы 4.1 и 4.2, доказанные М. А. Алехиной для произвольных неисправностей функциональных элементов, далее используются нами для случая инверсных неисправностей на входах элементов.

Пусть В - один из базисов В\ — В\%, а в схемах возникают инверсные неисправности на входах элементов.

Теорема. Пусть константы а, Ъ', с', d (таблица 4) соответствуют базису В и ее(0; d'\. Тогда любую булеву функцию /(х,, х2,...,х„) в базисе В

можно реализовать такой схемой S, что P(S) <as + Ь'г2, L(S) й с ■ 2" / и. Таблица 4 ___

В а V d c' b" c"

ßi = {xi|х2} ¿. 605 1/1200 168 36 504

В 2 = {Xlix2} 2 607 1/1200 168 38 504

Вз = {*]->х2, Ч>Х2} 2 2403 1/2500 336 ' 78 1008

Bs, = {Х\^>Х2,Х\®Х2} 2 2418 1/2500 336 93 1008

В5 = {xi-/>x2,x,~x2} 2 2418 1/2500 336 93 1008

Bf, = {х[Фх2, х{&хг, 1} 2 2419 1/2500 504 94 1512

Bj ~ {X\~X2, Xj VX2, 0} 2 2419 1/2500 504 94 1512

Bs {Xl~X2, X\&X2, xiffixj} 2 5354 1/5500 504 89 1512

В9 = {Х\~Х2, X\VX2, Х\®хг) 2 5354 1/5500 504 89 1512

й|0 = {*1~Х2, Х1&Х2, 0} 2 2418 1/2500 504 93 1512

В п = {XI©XJ. X1VX2, 1} 2 2418 1/2500 504 93 1512

B)2={Xl4>X2, } 3 1364 1/1400 336 89 1008

в 13 = {xi-»x2, Х\ } 3 1364 1/1400 336 89 1008

В14= {Х\Ч>Х2, 1} 4 2411 1/2500 504 133 1512

B\i = {X1-W2, 0} 4 2411 1/2500 504 133 1512

Bif, = {X1&X2, X, } 4 1406 1/1500 336 157 1008

В17 = {x ¡VX2, X] } 4 1406 1/1500 336 157 1008

В18 = {X1&X2, X1VX2, Xj } 2 1342 1/1400 336 46 1008

Оценки теоремы установлены конструктивно, т. е. представлены методы синтеза схем удовлетворяющих указанным оценкам по надежности и сложности.

Константы b' и с' не являются единственной парой значений, для которой справедлива теорема. Теорема справедлива, например, для значений Ь" и с" соответственно. Однако уменьшение одной из констант влечет увеличение другой, т. е., «улучшая» одну характеристику схемы (например, повышая надежность), «ухудшаем» другую (сложность).

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

Выводы

Показано, что в базисах В\ - Вк при инверсных неисправностях на входах функциональных элементов (е - вероятность неисправности):

1) все булевы функции можно реализовать схемами, ненадежность которых асимптотически не больше as при г -> 0 (константа а зависит от базиса, а е {2, 3,4});

2) в каждом из рассматриваемых базисов В\ - В]& явно найден класс булевых функций, такой, что при реализации любой функции из этого класса любой схемой S, ненадежность схемы S будет асимптотически не меньше аг при е —> 0 (константа а та же, что и в пункте 1).

Найденные классы функций содержат почти все булевы функции;

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

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

Публикации но теме диссертации

1. Чугунова, В. В. Оценка ненадежности при инверсных неисправностях на входах элементов / В. В. Чугунова // Инновации в науке, образовании, бизнесе: материалы III науч.-метод. конф. (11-12 мая 2005 г., г. Пенза). -Пенза: Изд-во Пенз. ин-та эконом, развития и антикризисного управления, 2005.-С. 14-16.

2. Чугунова, В. В. Верхняя оценка ненадежности схем в базисе {л- V у, х) при инверсных неисправностях на входах элементов / В. В. Чугунова, М. А. Алехина // Проблемы теоретической кибернетики: тез. докладов XI V Междунар. конф. (г. Пенза, 23-28 мая 2005 г.). - М.: Изд-во механико-математического факультета МГУ, 2005. - С. 10.

3. Чугунова, В. В. Об асимптотически наилучших по надежности схемах в базисах {-/», } и {->, } при инверсных неисправностях на входах элементов / В. В. Чугунова, М. А. Алехина // Известия высших учебных заведений. Поволжский регион. Естественные науки. - № 6 (21). — 2005. - С. 16-25.

4. Чугунова, В.В. Об асимптотически наилучших по надежности схемах в базисах {—>, }, {-/>, 1} и {-», 0} при инверсных неисправностях на входах элементов / В. В. Чугунова // Известия высших учебных заведений. Поволжский регион. Естественные науки. - № 6 (21). - 2005. - С. 26-35.

5. Чугунова, В. В. Об асимптотически наилучших по надежности схемах в базисе {&, v, } при инверсных неисправностях на входах элементов / В. В. Чугунова, М. А. Алехина // Дискретный анализ и исследование операций. - Новосибирск: Изд-во ин-та математики. - Октябрь-декабрь 2006 г.-Сер. 1.-Т. 13.-№4.-С. 3-17.

6. Чугунова, В. В. Об асимптотически наилучших по надежности схемах в базисах {©, &, 1}, v, 0},{®, &, ~} и {Ф, v, при инверсных неисправностях на входах элементов / В. В. Чугунова // Дискретные модели в теории управляющих систем: тр. VII Междунар. конф. (Покровское, 4-6 марта 2006 г.). - М.: МАКС Пресс, 2006. - С. 419-425.

7. Чугунова, В. В. О сложности асимптотически наилучших по надежности схем в базисах {©, &, 1}, v, 0}, (ffi, &, и {©, v, ~} при инверсных неисправностях на входах элементов / В. В. Чугунова // Надежность и качество: тр. Междунар. симп. (г. Пенза, 25-31 мая 2006 г.). - Пенза: Изд-во Пенз. гос. ун-та, 2006. - Т. 1. - С. 303-306.

8. Чугунова, В. В. Об асимптотически наилучших по надежности схемах в базисах {—©} и {-/>, ~} при инверсных неисправностях на входах элементов / В. В. Чугунова // Синтез и сложность управляющих систем: материалы XVI Междунар. школы-семинара (Санкт-Петербург, 26-30 июня 2006 г.) / под ред. О. Б. Лупанова. - М.: Изд-во механико-математического факультета МГУ, 2006. - С. 122-126.

9. Чугунова, В. В. Об асимптотически наилучших по надежности схемах в базисах {v, } и {&, } при инверсных неисправностях на входах элементов / В. В. Чугунова // Известия высших учебных заведений. Поволжский регион. Естественные науки. - 2006. - № 5 (26). - С. 141-152.

ЧУГУНОВА Варвара Валерьевна

СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМ ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ НА ВХОДАХ ЭЛЕМЕНТОВ

Специальность 01.01.09-дискретная математика

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

Редактор Т. Н. Судовчихшш Технический редактор //. А. Вьяякова

Корректор Ж. А. Лубепцова Компьютерная верстка М. Б. Жучковой

ИД № 06494 от 26.12.01 Сдано в производство 23.03.2007. Формат 60х841/1б. Бумага писчая. Печать офсетная. Печ. л. 1,0. Заказ № 156. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40.

Введение.

I. Некоторые свойства схем из ненадежных элементов.

II. Верхние оценки ненадежности схем при инверсных неисправностях на входах элементов.

III. Нижние оценки ненадежности схем при инверсных неисправностях на входах элементов

IV. Сложность асимптотически наилучших по надежности схем при инверсных неисправностях на входах элементов

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

Впервые задачу синтеза надежных схем из ненадежных элементов рассматривал Дж. фон Нейман [1]. Он рассматривал инверсные неисправности на выходах элементов, когда функциональный элемент с приписанной ему булевой функцией f(x)=flx\, хг,., хп) в неисправном состоянии, в которое переходит с вероятностью s (ее(0; 1/2)), реализует функцию У(5с). С помощью итерационного метода Дж. фон Нейман установил, что при se(0; 1/6) произвольную булеву функцию можно реализовать схемой, вероятность ошибки, на выходе которой при любом входном наборе значений переменных не превосходит c\Z (c¡ - некоторая абсолютная константа). Однако сложность такой схемы с ростом числа итераций увеличивается экспоненциально (примерно, в Зк раз, где А: - число итераций).

Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах Р.Л. Добрушина, С.И. Ортюкова, Д. Улига [2 - 7] и некоторых других авторов, причем главное внимание уделялось сложности схем (задача синтеза схем наилучших по надежности не ставилась). а

Сформулируем результаты названных авторов. Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в произвольном конечном полном базисе В = {е1, е2, .,ет), т е N [8]. (Множество всех функциональных элементов Ефункции которых е1 принадлежат базису В, будем также называть базисом В [9].) Каждому элементу базиса Е1 приписано положительное число у(£,) - вес данного элемента. Пусть сложность ¿(5) схемы £ из ненадежных элементов [8], реализующей булеву функцию /(х), определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимым образом с вероятностью 8 переходят в неисправные состояния. Ненадежность Р(Б) схемы определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах. Вводится функция Шеннона ¿р г {п) = гпах 1ТИП 1(5), характеризующая сложность схем, реализующих функции от п переменных в базисе В, где минимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию Дхь хг,., д:„) с ненадежностью РЦШ) < р, а максимум - по всем булевым функциям / от п переменных.

Пусть р = тт(у(£;)/(л(£()-1)), где минимум берется по всем эле

Е, ментам Е> базиса, для которых п(Е{) > 1, п(Е,) - число существенных переменных функции еь реализуемой элементом Еь а у(Е,) - вес функционального элемента Е{, г = 1,., т.

О.Б. Лупанов [10] показал, что для схем, реализующих булевы функции от п переменных и состоящих только из надежных элементов (т. е. при 8 = 0 ир = 0), выполняется соотношение Ь0 0(п)~р• 2" /п.

С. И. Ортюков [6] для инверсных неисправностей на выходах элементов получил следующий результат: пусть 0<e<s0, p>q(s)Lg, где

L - минимальное число надежных элементов, необходимое для реализации функции голосования g(x,,jc2,jt3) = дг,д:2 vjcjjc3 vx2x} в рассматриваемом базисе, q(s) - некоторая функция такая, что g(s) = e + 3&2 +о(г2) при е -» 0. Тогда существует такая функция р(с) -> р при s -» 0, что LJn)ïp(s)-2n/n.

Д. Улиг [7] для инверсных неисправностей на выходах элементов с вероятностью ошибки 8 доказал, что для любых, сколь угодно малых чисел с и b {с, b > 0) существует число е' (с' е(0, 1/2)) такое, что при любом s (ее(0, s')), и любом р, удовлетворяющем условиюр > (1 + Ь) 8 Lg (точнее р> q(s) Lg), справедливо соотношение Ьрг(гг)^(1 + с)р-2" /п.

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

Из результатов Н. Пиппенджера [11] следует, что при инверсных неисправностях на выходах элементов с вероятностью ошибки ее(0, 1/200] любую булеву функцию от п переменных в базисе {&, v, } можно реализовать такой схемой S, что P(S) < 18s, L(S) £ 170 • Т / п.

C.B. Яблонский [12] рассматривал задачу синтеза надежных схем в базисе В = {х\8сх2, x\vx2, х,, g(x,,x2,x3)}. Он предполагал, что элемент, г реализующий функцию голосования = vx2x^ абсолютно надежный, а конъюнктор, дизъюнктор и инвертор - ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше с. Им доказано, что для любого р > О существует алгоритм, который для каждой булевой функции j{x\, Х2, ., хп) строит такую схему S, что P(S)<p,L(S)z2nA/n.

B.В. Тарасов [13] рассматривал задачу построения схем сколь угодно высокой надежности (когда P(S) -> 0). Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом В.В. Тарасовым выявлены необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных им результатов следует невозможность построения сколь угодно надежных схем для произвольных функций при инверсных неисправностях только на входах элементов или только на выходах в базисах из двухвходовых функциональных элементов.

C.И. Аксеновым [14] получена оценка ненадежности схем в произвольном полном базисе В при инверсных неисправностях на выходах элементов. Он доказал, что в произвольном полном базисе В при se(0; Со) любую булеву функцию можно реализовать такой схемой S, что P(S) < ке + + се , где к (к < 5) - минимальное число надежных элементов, необходимое для реализации какой-либо из функций вида: gi(x,, х2, х3) = Xj Xj V X, Xj V Х2 хз , £2 (Х|, Х2, Xj, Х4 ) Х| Xj V х3 х4 , (Х|, Xj, Xj, Хд ) (х,0' vx°2Xx°' vx°4)> {0, 1}, /е{1, 2, 3, 4}, a s - ненадежность базисного элемента. Константы к, с, So положительны и зависят от базиса В. Таким образом, в произвольном полном базисе любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше 5s при 8 -» 0. Вопрос о возможности снижения мультипликативной константы 5 в оценке ненадежности для произвольного базиса пока остается открытым.

М.А. Алехина [15] решала задачу построения асимптотически оптимальных (асимптотически наилучших) по надежности схем при однотипных константных неисправностях только на входах или только на выходах элементов. Чтобы сформулировать полученные М.А. Алехиной результаты, введем необходимые определения.

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

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

Ненадежность P(S) схемы S определяется также как для инверсных неисправностей на выходах элементов, и равна максимальной вероятности ошибки на выходе схемы S. Надежность схемы S равна 1 - P(S).

Пусть Ръ (/) = inf P(S), где инфимум берется по всем схемам S из неS надежных элементов, реализующим функцию ßx\, х2, ., хп). Схема А из ненадежных элементов, реализующая функцию f, называется асимптотически наилучшей (асимптотически оптимальной) по надежности, если

Р{А) ~ Pz (/) при 8 -> 0, т. е. lim ^ = 1. е-»0 Р{А)

М.А. Алехиной [15] доказано, что во всех неприводимых полных базисах (исключая три случая), содержащих функции не более чем двух переменных, почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью асимптотически равной ad при с 0, константы а и t зависят от базиса и типа неисправностей, ае{ 1, 2, 3}, /е{1, 2}. Сложность таких схем по порядку равна сложности схем, построенных только из надежных элементов (т. е. увеличивается несущественно).

В работе [16] М.А. Алехина рассматривала инверсные неисправности на входах элементов и доказала, что при инверсных неисправностях на входах элементов в базисах {xi | л:2} и {лг^лгг} почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью, асимптотически равной 2s при е -» 0. Асимптотически наилучшие по надежности схемы можно строить со сложностью, по порядку равной сложности минимальных схем, состоящих только из надежных элементов.

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

Введем основные понятия и определения.

Будем считать, что схема реализует функциюßx\, Х2,., х„), если при поступлении на входы схемы набора а = (а\, а^, ., ап) при отсутствии неисправностей на выходе схемы появляется значение /(а). Предполагается, что все элементы схемы имеют не более двух входов, один выход и независимо друг от друга с вероятностью ве(0; 1/2) подвержены инверсным неисправностям на входах. Эти неисправности характеризуются тем, что поступающее на каждый вход элемента значение а, ае{0, 1}, с вероятностью £ может превратиться в значение а .

Ненадежность P(S) схемы S, реализующей функцию f(x), при инверсных неисправностях на входах элементов определяется так же, как и при инверсных неисправностях на выходах, т.е.

P(S) = maxP/(3)(S,a), где P-f(d){S,a) - вероятность появления значения f(a) на выходе схемы S при входном наборе а, а максимум берется по всем возможным входным наборам а. Надежность схемы S равна 1 - P(S).

Понятие асимптотически оптимальной по надежности схемы вводится, как и раньше. Обозначим Ре(/) = inf P(S), где S- схема из ненадежных S элементов, реализующая булеву функцию Дхь jt2, хп). Схему А из ненаI дежных элементов, реализующую булеву функциюßxh х2, х„), назовем асимптотически оптимальной (асимптотически наилучшей) по надежности, если P{Ä) ~ Р£(/) при в —> 0, т.е. б->0 Р(А)

Напомним, что веса всех элементов равны единице, поэтому сложность L(S) схемы S равна числу функциональных элементов в ней.

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

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

М{х\, Х2) = {XI&JC2J X1VX2, Х\ 1*2, X\-f>Xi, , 0, 1}.

При перечислении функций использованы следующие обозначения:

Х^Х2 = Xl VX2 , Х{ 4 Х2 = Х{ & Х2 , Х\ ~ Х2 = X1&X2VX1 &Х2 , Х{ -> Х2 = Х{ V Х2,

Х\ -А х2 = Xi &х2 , Х{ Ф х2 = xl & x2 V Xj & х2.

Определение. Множество В с М(х\, д:2) назовем неприводимым полным базисом (в Р2), если множество В полно и никакое его собственное подмножество полным не является.

Введем в рассмотрение неприводимые полные базисы: В\ ={xi|x2}, В2 = {xi¿x2}, В3 = {xi->x2, xi-f>x2}, В4 = {*i->x2, Xi©x2}, В5 = {x\-frx2, х{~х2}, В(, = {Х]ФХ2, Х\8ОС2, 1}, В1 = {Х\~Х2, XiVX2, 0}, Z?g = {Xi~X2, Х\&Х2, JCI©X2}, By = {Xi~X2, X¡VX2, Xi®X2}, Bio = {Xl~X2, Xi&X2, 0}, Bu = {Xi@X2, X\VX2, 1},

B\2 = {x\-frx2, x{}, Bu = {xi->*2, }, BH = {x{-frx2, 1}, B]5 = {x,->x2, 0}, #16 = {xi&x2, xl }, B„ = {XiVX2, xx }.

В P2 существует ровно 17 (с точностью до переименования переменных) неприводимых полных базисов, содержащих функции не более чем двух переменных. Любой другой базис, отличный от базисов В\ - Вц (например, В\8 = {X1&JC2, x\vx2, Xj}), можно получить переименованием переменных без отождествления, а также добавлением одной или нескольких функций из множества М(хь х2) к некоторому базису из указанного списка.

В диссертационной работе доказано: для каждого базиса В из введенных выше базисов В\ - В\g при инверсных неисправностях на входах элементов существуют такие константы a, b, d, b, d, d', с' и класс булевых функций К(п) (см. табл. 1 - 3), что справедливы следующие утверждения.

1) Если se(0; d\, то любую булеву функцию Дхр х2,.,хп) можно реализовать схемой S с ненадежностью P(S) < яе + Ъгг.

2) Если ee(0; d], то при реализации любой функции /(*,, х2, .,х„) £ К(п) любой схемой S верно неравенство P(S) > аг + Ьг2.

3) Если ее(0; </], то сложность асимптотически наилучших по надежности схем £ по порядку равна сложности схем, построенных только из надежных элементов: 1(5) &с'-2п /п.

Полученные результаты сформулируем в виде теорем. Пусть В - один из базисов В\ - В\%, а в схемах возникают инверсные неисправности на входах элементов.

Теорема 1. Пусть константы а, Ь', с', (X (см. табл. 1) соответствуют базису В и се(0; </]. Тогда любую булеву функцию /(х,, х2,.,х„) в базисе В можно реализовать такой схемой 5, что Р(5) <аг + Ь'г2,1(5) £ с' • 2" / п.

Таблица 1.

В а V а с' Ь" с"

В\ = {х, х2} 2 605 1/1200 168 36 504

Вг={хМг} 2 607 1/1200 168 38 504

Вз = {х\^х2, XI 4>х2} 2 2403 1/2500 336 78 1008

ВА = {х]—>х2, Х1Фх2} 2 2418 1/2500 336 93 1008

В5= {Х1-АХ2,Х1~ДГ2} 2 2418 1/2500 336 93 1008

В6 = {х]Фх2, х1&х2,1} 2 2419 1/2500 504 94 1512

В-] = {Х]~Х2, Х\ЧХ2, 0} 2 2419 1/2500 504 94 1512

В$ = {*1~х2, Х1&Х2, Х]©Х2} 2 5354 1/5500 504 89 1512

Вд = {Х]~Х2, Х1УХ2, Х1ФХ2} 2 5354 1/5500 504 89 1512

ВЮ = {Х\~Х2, Х]&Х2, 0} 2 2418 1/2500 504 93 1512

В\] = {Х]ФХ2, Х1УХ2, 1} 2 2418 1/2500 504 93 1512

В\2= {х\Ч>х2, х, } 3 1364 1/1400 336 89 1008

Вхг= —х{} 3 1364 1/1400 336 89 1008

Вц= {х, 1} 4 2411 1/2500 504 133 1512

В\ь = {х,-»х2, 0} 4 2411 1/2500 504 133 1512

16 = {Х1&Х2, х, } 4 1406 1/1500 336 157 . 1008

В\1 = {Х,УХ2, х} } 4 1406 1/1500 336 157 1008

В18 = {Х!&Х2, х^х2, х,} 2 1342 1/1400 336 46 1008

Заметим, что результат С.И. Аксенова [14] можно перенести на случай инверсных неисправностей на входах элементов (в этом случае ненадежность базисного элемента не больше 2е) следующим образом: при ге(0; Со) произвольную булеву функцию можно реализовать такой схемой S, что 2 2

P(S) < 2кг + сб < 10е + се , то есть множитель при в не больше 10. В то время как у нас этот множитель принимает значения 2,3 и 4.

Оценки теоремы 1 установлены конструктивно, т.е. представлены методы синтеза схем S, удовлетворяющих указанным оценкам по надежности и сложности.

Константы Ъ' и с' (см. табл. 1) не являются единственной парой значений, для которой справедлива теорема 1. Теорема 1 справедлива, например, для значений Ъ" и с" соответственно. Однако, уменьшение одной из констант влечет увеличение другой, т.е. «улучшая» одну характеристику схемы (например, повышая надежность) «ухудшаем» другую (сложность).

Теорема 2. Пусть константы a,b, d и класс булевых функций К(п) (см. табл. 2) соответствуют базису В. Тогда для любой булевой функции /(х,, х2,.,хп),/£ К{п), и любой схемы S, реализующей/в базисе В, при ее(0; d] верно неравенство: P(S)>az + bг2, причем а - та же константа, что и в теореме 1.

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

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

Таблица 2.

В а Ъ 2 К(п)

В\= {*11*2} 2 -1 1/4 х,, 1 в2 = {*1>к>} 2 -1 1/4 х, , 0

Вз = {Х1->Х2,Х1-/>Х2} 2 -1 1/4 х;, 0, 1

Вц = {Х1~>Х2, Х1©Х2} 2 -2 1/4 X,., 1 в5= 2 -2 1/4 *„ 0

2?6 = {*1©*2> Х(&Х2, 1} 2 -2 1/4 *„ 0, 1

В1 = {Х1~Х2, Х^Х2, 0} 2 -2 1/4 0, 1

В% = {х[~х2, х\&х2, х!©х2} 2 -2 1/4 х, , 0

В<) = {Х]~Х2, Х[УХ2, Х!©Х2} 2 -2 1/4 х,, 1

В\о = {Х]~х2, х\&х2, 0} 2 -2 1/4 х„ 0

В и = {х!®х2, х\чх2, 1} 2 -2 1/4 х„ 1

В\2= {х^-/>х2, х] } 3 -6 1/6 х,5&/г(х), 1

В\3 = } 3 -6 1/6 х(8 V И(х), 0

Вц = {Х1-Дх2,1} 4 -8 1/11 (Х,5&/2 (Х)У

15 = {*1-»*2, 0} 4 -8 1/11 (х*&к(х)У

В16 = {х!&х2, х{} 4 -12 1/10 (х,5&/г(х))ц

В17 = {х,УХ2, X, } 4 -12 1/10 (х(8 & И(х)У

18 = {Х1&Х2, Х[\/Х2, х1 } 2 -2 1/6 Х-, 0, 1

Используемые в таблице 2 обозначения: / = 1 ,п, 8, це{0,1}, к{х) -произвольная булева функция от п переменных (х = (хь х2,., х„)).

Диссертация состоит из введения, четырех глав и списка литературы, содержащего 25 названий. Общий объем работы - 110 страниц, в работе содержится 28 рисунков и 5 таблиц. Нумерация таблиц и рисунков сквозная в пределах главы.

1. von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies, edited by Shannon C., Mc. Carthy J. Princeton University Press, 1956. (Русский перевод: Автоматы. M.: ИЛ, 1956. С. 68 - 139.)

2. Добрушин Р.Л., Ортюков С.И. О нижней оценке для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 1. С. 82 89.

3. Добрушин Р.Л., Ортюков С.И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 3. С. 56 76.

4. Ортюков С.И. К вопросу о синтезе асимптотически безызбыточных самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ. 1977. Т. 13, N 4. С. 3 8.

5. Ортюков С.И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок // Проблемы передачи информации. 1981. Т. 17, вып. 4. \\ С. 84 97.

6. Ортюков С.И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и ее приложениям (Москва, 27 29 января 1987 г.). М.: Изд-во Моск. ун-та, 1989. С. 166-168.

7. Редькин Н.П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.

8. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

9. Лупанов О.Б. Об одном методе синтеза схем. Изв. ВУЗов, Радиофизика, 1958. Т. 1, N 1. С. 120-140.

10. Pippenger N. On networks of Noisy Gates. 26 Symposium on Foundation on Computer science, 21 - 23.10.1985, Portland, 30 - 38.

11. Яблонский C.B. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center. 1982. N 7. \\ P. 11 -19.

12. Тарасов В.В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. 1976. Т. 20, N 3. С. 391 400.

13. Аксенов С.И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. №6(21) 2005. С. 42 55.

14. Алехина М.А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов. Монография. Пенза: Информационно издательский центр ПТУ, 2006.

15. Алехина М.А. О надежности и сложности схем в базисе {х Ijv} при инверсных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. №6(21) 2005. С. 36-41.

16. Чугунова В.В. Об асимптотически наилучших по надежности схемах в базисах {->, -f>}, {-/>, 1} и {-», 0} при инверсных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. №6 (21) 2005. С. 26 35.

17. Чугунова В.В. Об асимптотически наилучших по надежности схемах в базисах {v, } и {&, } при инверсных неисправностях на входах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. 2006. №5 (26). С. 141 152.