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

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

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

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

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

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

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

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

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

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

Д. Улиг [7] для инверсных неисправностей на выходах элементов с вероятностью ошибки 8 доказал, что для любых, сколь угодно малых чисел с и b {с, b > 0) существует число е' (с' е (0, ½)) такое, что при любом 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, xvx2, х, g (x, x2, x3)}. Он предполагал, что элемент, г реализующий функцию голосования = vx2x^ абсолютно надежный, а конъюнктор, дизъюнктор и инвертор — ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше с. Им доказано, что для любого р > О существует алгоритм, который для каждой булевой функции j{x, Х2, ., хп) строит такую схему S, что P (S).

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- ½), реализует константу 0, то она называется неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, то такая неисправность называется неисправностью типа 1 на выходе элемента.

Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью 8б (0- ½) может превратиться в нуль, то она называется неисправностью типа 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,., х&bdquo-), если при поступлении на входы схемы набора, а = (а, а^, ., ап) при отсутствии неисправностей на выходе схемы появляется значение /(а). Предполагается, что все элементы схемы имеют не более двух входов, один выход и независимо друг от друга с вероятностью ве (0- ½) подвержены инверсным неисправностям на входах. Эти неисправности характеризуются тем, что поступающее на каждый вход элемента значение а, ае{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, х&bdquo-), назовем асимптотически оптимальной (асимптотически наилучшей) по надежности, если P{A) ~ Р£(/) при в —> 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 (c)x2}, В5 = {x-frx2, х{~х2}, В (, = {Х]ФХ2, Х8ОС2, 1}, В1 = {Х~Х2, XiVX2, 0}, Z? g = {Xi~X2, Х&Х2, JCI (c)X2}, By = {Xi~X2, X? VX2, Xi®X2}, Bio = {Xl~X2, Xi&X2, 0}, Bu = {Xi@X2, XVX2, 1},.

B2 = {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, xvx2, Xj}), можно получить переименованием переменных без отождествления, а также добавлением одной или нескольких функций из множества М (хь х2) к некоторому базису из указанного списка.

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

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

2) Если ee (0- d], то при реализации любой функции /(*, х2, ., х&bdquo-)? К (п) любой схемой 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, Х](c)Х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 в2 = {*1>к>} 2 -1 ¼ х,, 0.

Вз = {Х1->Х2,Х1-/>Х2} 2 -1 ¼ х-, 0, 1.

Вц = {Х1~>Х2, Х1(c)Х2} 2 -2 ¼ X,., 1 в5= 2 -2 ¼ *" 0.

2?6 = {*1(c)*2> Х (&Х2, 1} 2 -2 ¼ *" 0, 1.

В1 = {Х1~Х2, Х^Х2, 0} 2 -2 ¼ 0, 1.

В% = {х[~х2, х&х2, х!(c)х2} 2 -2 ¼ х,, 0.

В<) = {Х]~Х2, Х[УХ2, Х!(c)Х2} 2 -2 ¼ х, 1.

Во = {Х]~х2, х&х2, 0} 2 -2 ¼ х&bdquo- 0.

В и = {х!®х2, хчх2, 1} 2 -2 ¼ х&bdquo- 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,., х&bdquo-)).

Диссертация состоит из введения, четырех глав и списка литературы, содержащего 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.