Синтез, надежность и сложность схем из ненадежных функциональных элементов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Алехина, Марина Анатольевна
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Пенза
МЕСТО ЗАЩИТЫ
|
||||
|
2004
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. Ломоносова Механико-математический факультет
На правах рукописи УДК 519.718
АЛЕХИНА Марина Анатольевна
СИНТЕЗ, НАДЕЖНОСТЬ И СЛОЖНОСТЬ СХЕМ ИЗ НЕНАДЕЖНЫХ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
Специальность 01.01.09 — Дискретная математика и математическая кибернетика
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
МОСКВА 2004
Работа выполнена в Пензенском государственном университете.
Научный консультант: доктор физико-математических наук,
профессор Н. П. Редькин.
Официальные оппоненты: доктор физико-математических наук,
профессор В. А. Буевич; доктор физико-математических наук, профессор М. Ю. Мошков;
доктор физико-математических наук, профессор Л. А. Шоломов.
Ведущая организация — Казанский государственный
университет им. Н. И. Лобачевского.
Защита диссертации состоится «_»_2004 г.,
в 16 ч 15 мин, на заседании диссертационного совета Д 501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.
С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (14 этаж).
Автореферат разослан «_»_2004 г.
Ученый секретарь
диссертационного совета Д 501.001.84 в МГУ / I
доктор физико-математических
наук, профессор / Ч/ В. Н. Чубариков
ГЦ^
Общая характеристика работы
Актуальность темы. Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники.
К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Проблема построения оптимальных по критериям надежности и сложности схем из ненадежных элементов является одной из наиболее важных и в то же время трудных в теории синтеза управляющих систем. Разработка специальных методов синтеза схем из ненадежных функциональных элементов связана, главным образом, с выбранной математической моделью неисправностей. Одна из основных моделей определяется константными неисправностями на выходах или на входах элементов. В диссертации рассматривается задача построения асимптотически наилучших по надежности схем в предположении, что функциональные элементы подвержены однотипным константным неисправностям либо только на выходах, либо только на входах элементов. Решение этой задачи усложняется при дополнительном требовании к сложности схем, которое состоит в том, чтобы сложность асимптотически оптимальных по надежности схем по порядку равнялась сложности схем, построенных только из надежных элементов. Задача решается в базисах, содержащих функции не более чем двух переменных.
Исторически сложилось так, что сначала исследовались инверсные неисправности. Первые существенные математические результаты, касающиеся синтеза надежных схем из ненадежных элементов получил Дж. Нейман Он предполагал, что элементы подвержены инверсным неисправностям, когда функциональный элемент Е с приписанной ему булевой функцией в неисправном состоянии, в которое переходит с
'топ Neuman, J. Probabilistic logics and the synthesis of reliable organisms from unreliable components [Text] / J. Neuman // Automata studies, edited by C. Shannon, Mc. J. Carthy. -Princeton University Press, 1956.
(Русский перевод: Автоматы. - M.: ИЛ, 1956. - С. 68 - 139.)
РОС UALIMOHAJIЪЫАЯ вНЬД «ОТЕКА
вероятностью е (0 < £ < 1/6), реализует функцию С помощью итерационного метода Дж. Неймана произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се (с - некоторая, зависящая лишь от базиса константа), т. е. ненадежность схемы сравнима с ненадежностью одного элемента (такие схемы в теории надежности управляющих систем принято называть надежными). С ростом числа итераций сложность схемы увеличивается экспоненциально.
Любой метод синтеза схем из ненадежных элементов характеризуется двумя важными параметрами: вероятностью ошибки на выходе схемы (ненадежностью) и сложностью схемы. Именно оптимизации сложности схем уделялось главное внимание в работах Р. Л. Добрушина, С. И. Ортюкова, Д. Улига и некоторых других авторов. Задача построения асимптотически наилучших по надежности схем из ненадежных элементов, подверженных тем или иным неисправностям, ни Дж. Нейманом, ни другими исследователями не рассматривалась. Речь идет о реализации булевых функций схемами из ненадежных элементов в произвольном конечном базисе Б = {е1,...,ет}, т Е N. (Множество всех функциональных элементов /:'„ функции которых е, принадлежат базису Б, будем также называть базисом Б. 2) Каждому элементу Е1 базиса приписано положительное число - вес данного элемента Сложность схемы .У определяется как сумма весов всех входящих в нее элементов и обозначается Предполагается, что все элементы схемы независимо друг от друга с вероятностью е подвержены инверсным неисправностям. Пусть Рд3)(5,а) - вероятность появления значения /(а) на выходе схемы Л', реализующей булеву функцию /(ж), при входном наборе а = (ах,...,а„). Пусть - максимальное из чисел Рда)(5,а) при всевозможных входных наборах Назовем величину ненадежностью схемы 5. Вводится функция Шеннона
ЬрЛп) ~ пуп М5)>
где минимум берется по всем схемам Л' из ненадежных элементов, реализующим функцию с ненадежностью а макси-
2Лупанов, О. Б. Асимптотические оценки сложности управляющих систем [Текст] / О. Б. Лупавов. - М.: Изд-во МГУ, 1984. г . - -
мум - по всем булевым функциям / от п переменных. Нетрудно проверить, что для любой схемы 5, содержащей хотя бы один элемент, при е <1/2 верно неравенство P(S) > е.
Пусть р = mint)(Bi)/(n(£j) — 1), где минимум берется по всем элементам Ei базиса, для которых п(Е{) > 1, а п(Е{) - число существенных переменных функции е,-, реализуемой элементом Д, i — 1,2,..., т. Для схем, реализующих булевы функции и состоящих только из надежных элементов (т.е. е — 0,р = 0), О. Б. Л уланов 3 показал, что
Ьо,о(п) ~ р-2п/п.
С. И. Ортюков 4 доказал, что асимптотика функции Шеннона сохраняется для схем из ненадежных элементов при степенном убывании вероятности сбоев с ростом п, а именно, если последовательности рп и еп таковы, что QLgen < р„ < 1/2, 0 < е„ < 1/2 и еп = о(1/п2), где Q > 1, Lg - минимальная сложность схемы из надежных элементов в рассматриваемом базисе, реализующей функцию голосования д(х 1,Х2)Зз) = xix2 Vxixj Vx2x3, то
Позднее С. И. Ортюкову 5 удалось усилить этот результат, заменив требование еп = о(1/п2) условием еп < £0, где £о - некоторая константа. Сформулируем полученный, им результат: если 0 < е < ео, q(e) Lg < р < 1/2, где g(e) = е + Зе2 + о(е2) при е 0, то существует такая функция р(е) р при е 0, что LPie(n) ~ р(е) • 2п/п.
Д. Улиг6для инверсных неисправностей с вероятностью ошибки не более е показал, что для любых с, Ъ (с, Ь > 0) существует £' 6 (0, 1/2)) такое, что при любых е, 0 < е < е1, и р,
'Лупанов, О. Б. Об одпом методе синтеза схем [Текст] / О. Б. Лупанов // Изв. вузов, Радиофизика. - 1958. - Т. 1. - 1. - С. 120 - 140.
'Ортюков, С. И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок [Текст] / С. И. Ортюков // Проблемы передача информации. -1981. - Т.17. - Вып. 4. - С. 84 - 97.
'Ортюков, С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов [Текст]: тр. семинара по дискретной математике и ее приложениям (Москва, 27 -29 января 1987 г.). - М.: Изд-во МГУ, 1989. - С. 166 - 168.
sUhlig, D. Reliable networks from unreliable gates with almost minimal comlexity [Text] / D. Uhlig // Fundamentals of Computation Theory. Intern, conf. FCT'87 (Kazan, June 1987). -Proc. Berlin: Springer-Verl., 1987. - P. 462 - 469. (Lecture Note» in Comput. Sei.; V. 278).
(1 + Ь)еЬд < р <1/2 (точнее при любом р, < р <1/2),
выполнено соотношение
^рЛп) ~ (1 + с)р • 2"/п.
С. И. Ортюков и Д. Улиг для инверсных неисправностей нашли методы синтеза оптимальных по сложности схем, функционирующих с некоторым уровнем надежности.
Инверсные неисправности, о которых до сих пор шла речь, достаточно удобны для использования математического аппарата теории вероятностей. Однако реальные неисправности элементов более точно отражают другие математические модели неисправностей. Основной из них являются однотипные константные неисправности на выходах и на входах элементов.
Впервые однотипные константные неисправности на выходах элементов исследовались в кандидатской диссертации , а также в статьях автора 8. Там же впервые был получен ответ на вопрос "Какова максимальная надежность схем, построенных из ненадежных элементов?" Тогда задачу построения схем, асимптотически наилучших по надежности, удалось решить лишь в четырех базисах из двухвходовых элементов.
Вопрос о возможности построения схем, асимптотически наилучших по надежности, в других базисах, а также при других неисправностях элементов (опять-таки однотипных константных неисправностях, но уже на входах элементов) оставался открытым.
'Алехина, М. А. Синтез надежных схем из ненадежных двухвхоаовых функциональных элементов [Текст]: дис. ... канд. физ.-мат. наук / Алехина Марина Анатольевна. - М., 1992.
'Алехина, М. А. О синтезе надежных схем из функциональных элементов х/у при однотипных константных неисправностях на выходах элементов [Текст] / М. А. Алехина // Веста. Моск. ун-та. Матем. Механ. - 1991. -№-5.- С. 80 - 83;
Алехина, М. А. О сложности надежных схем из функциональных элементов при однотипных константных неисправностях на выходах элементов [Текст] / М. А. Алехина // Вестн. Моск. ун-та. Матем. Механ. - 1992. - №■ 5. - С. 79 - 81;
Алехина, М. А. О надежности схем в базисе {&, v,"} при однотипных константных неисправностях на выходах элементов [Текст] / М. А. Алехина // Вестн. Моск. ун-та. Матем. Механ. -1992. -N-6.- С. 56-58;
Алехина, М. А. О надежности схем из ненадежных функциональных элементов при однотипных константных неисправностях на выходах элементов [Текст] / М. А. Алехина // Дискретная математика. - 1993. - Т. 5. - Вып. 2. - С. 59 - 74.
Цель работы — разработать методы синтеза асимптотически наилучших по надежности схем из ненадежных функциональных элементов при однотипных константных неисправностях только на выходах элементов или только на входах элементов. Кроме того, требовалось, чтобы сложность асимптотически наилучших по надежности схем по порядку равнялась сложности схем, построенных только из надежных элементов.
Методы исследований. В работе использованы методы дискретной математики и математической кибернетики, теории вероятностей, математического анализа, функционального анализа. Кроме того, исследование схем, асимптотически наилучших по надежности, потребовало формирования новых методов и подходов получения как верхних, так и нижних оценок ненадежности схем.
Научная новизна. Основные результаты диссертации являются новыми. Укажем наиболее важные из них.
1. Разработаны методы построения асимптотически наилучших по надежности схем из ненадежных элементов для большинства базисов из двухвходовых функциональных элементов.
2. Предложен специальный метод синтеза асимптотически наилучших по надежности схем над базисом при неисправностях на входах элементов.
3. Для всех булевых функций получены верхние оценки ненадежности схем в случае неисправностей на выходах элементов и в случае неисправностей на входах элементов.
4. Усовершенствованы ранее известные (и принадлежащие автору), а также разработаны новые методы и подходы получения нетривиальных нижних оценок ненадежности схем.
5. Доказана асимптотическая точность полученных верхних оценок в большинстве рассматриваемых базисов. При этом найден класс булевых функций К (зависящий от базиса) такой, что при реализации любой функции из К любой схемой нижняя оценка ненадежности этой схемы будет асимптотически равна полученной ранее верхней оценке ненадежности. Классы К найдены явно и в большинстве базисов содержат почти все булевы функции.
6. Конструктивно доказано, что сложность асимптотически наилучших по надежности схем для почти всех булевых функций в большин-
стве базисов по порядку равна сложности схем, построенных только из надежных элементов.
Теоретическая и практическая ценность работы
Полученные в работе результаты носят теоретический характер. Они могут быть использованы в дальнейших исследованиях надежности и сложности схем из ненадежных функциональных элементов в различных базисах. Предложенные методы синтеза схем, асимптотически наилучших по надежности, могут найти применение при проектировании технических систем для повышения их надежности.
Апробация работы. Результаты диссертационной работы докладывались на Международных конференциях по проблемам теоретической кибернетики (Нижний Новгород, 1999; Казань, 2002), на Международных семинарах "Дискретная математика и ее приложения" (Москва, 2001; 2004), на Международной конференции "Дискретные модели в теории управляющих систем" (Красновидово Моск. обл., 2000), на Международной научно-технической конференции "Методы и средства измерения в системах контроля и управления" (Пенза, 2002), на Межгосударственных и Международных школах-семинарах "Синтез и сложность управляющих систем" (Нижний Новгород 2000; 2003; Пенза, 2001; 2002), на Международной школе-семинаре "Дискретная математика и математическая кибернетика" (Ратмино Моск. обл., 2001), на Четвертой и Пятой молодежных школах по дискретной математике и ее приложениям (Москва, 2000; 2001), на семинарах О. Б. Лупанова "Математические вопросы кибернетики", "Синтез и сложность управляющих систем" и на семинаре Н. П. Редькина "Надежность и диагностика управляющих систем" в МГУ им. М. В. Ломоносова.
Публикации. Основные результаты диссертации опубликованы в 24 работах автора, список которых приведен в конце автореферата; среди них работ, написанных в соавторстве, нет.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, приложения и списка литературы. Объем диссертации составляет 169 страниц, включая 5 таблиц и 11 рисунков. Рисунки вынесены в приложение. Список литературы содержит 44 наименования.
Содержание диссертации
Во введении приводятся обзор результатов, связанных с темой диссертации, постановка задачи, дается характеристика работы и формулируются в общем виде полученные в ней результаты.
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в конечном базисе Б 9. Схема реализует функцию если она реализует ее при отсутствии неисправ-
ностей в схеме. Предполагается, что каждый элемент схемы независимо от состояний других элементов может перейти в неисправное состояние.
Определим однотипные константные неисправности на выходах элементов и на входах элементов.
Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью 7 (7 < 1/2), реализует константу О, будем называть ее неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, будем называть эту неисправность неисправностью типа 1 на выходе элемента.
Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью может превратиться в нуль, будем называть ее неисправностью типа 0 на входе элемента. Если же неисправность элемента такова, что поступающая на его вход единица не искажается, а нуль с вероятностью 7 может превратиться в единицу, будем называть ее неисправностью типа 1 на входе элемента.
Ненадежность P(S) схемы S, реализующей /(ж), для указанных неисправностей определяется так же, как и для инверсных неисправнос-
P(S)=maxP/(5)(S,ó),
где Py(¿)(5,а) - вероятность появления значе h/(5i)н а выходе схемы S при входном (произвольном) наборе а.
Надежность схемы равна
'Реяькин, Н. П. Надежность и диагностика схем [Текст] / Н. П. Редысин. - М.: Изд-во МГУ, 1992.
Обозначим P(f) = inf P(S), где S - схема из ненадежных элементов, реализующая булеву функцию /(xj, ...,х„).
Схему А из ненадежных элементов, реализующую булеву функцию f(zi, ...,хп), назовем асимптотически наилучшей (асимптотически оптимальной) по надежности, если P(Â) ~ P(f) при у —0.
Будем считать веса всех функциональных элементов равными единице, и тогда сложность L(S) схемы S есть число функциональных элементов в ней.
В первой главе диссертации развита некоторая техника, используемая в дальнейшем для получения верхней и нижней оценок надежности схем. Отметим наиболее важные утверждения.
Определение. Схему, реализующую булеву функцию, отличную от константы, будем называть а-схемой, если для любых входных наборов из равенства следует равенство
Из этого определения, ясно, что вероятность ошибки, на выходе а-схемы одинакова для всех нулевых (единичных) входных наборов схемы.
Теорема 1.1. Если подсхема А, содержащая выход схемы 5, реализующей функцию, отличную от константы, является а-схемой с вероятностями ошибок
Сформулированное в теореме 1.1 утверждение есть частный случай утверждения теоремы 1.2. При получении нижних оценок ненадежности схем удобно применять обе теоремы.
Пусть / - произвольная булева функция, отличная от константы, S - любая схема, ее реализующая. Пусть подсхема А схемы 5 содержит выход схемы 5 и реализует булеву функцию д с ненадежностью Р{А) < 1/2. Обозначим р1 - минимум вероятностей ошибок на выходе подсхемы А по таким входным наборам Ь, что g(b) = 0. Аналогично р° - минимум вероятностей ошибок на выходе подсхемы А при таких входных наборах что
Теорема 1.2: Вероятности ошибок на выходе схемы S удовлетво-творяют неравенствам
Pi (S,5) > р1, если /(а) = 0;
Следствие 1.1. P(S) > maxfp0,?1}.
В теореме 1.1 установлена возможность оценки надежности схемы
по надежности ее связной подсхемы, содержащей выход схемы.
В теореме 1.2 и следствии 1.1 установлена возможность оценки надежности схемы по некоторым вероятностям ошибок ее связной подсхемы, содержащей выход схемы.
Пусть в схеме 5, реализующей булеву функцию, отличную от константы, выделена подсхема В, имеющая один вход, содержащая выход схемы и реализующая тождественную функцию. Обозначим через А подсхему, получаемую из схемы 5 удалением подсхемы В. Если выполнено неравенство Р(8) > Р(А), то будем говорить, что схема А надежнее схемы 5 и получается из 5 удалением подсхемы В.
Определение. Схема 8, реализующая булеву функцию ^ отличную от константы, является ^схемой, если из нее нельзя получить более надежную схему удалением подсхемы, реализующей тождественную функцию.
Теорема 1.3. Пусть схема S, ненадежность которой равна Р(8), реализует функцию f и является ^схемой. Если в 5 можно выделить подсхему B, имеющую один вход, содержащую выход схемы и реализующую тождественную функцию с вероятностями ошибок ро и р\ такими, что то верно неравенство
Теорема 1.3 устанавливает соотношение между надежностными характеристиками схемы и ее подсхемы специального вида.
Функционирование базисного элемента Е с приписанной ему функцией е{х,у) можно задать табл. 1, в которой ро и рх - вероятности появления 0 и 1 на выходе элемента (а,/3,6,т > 0).
Определение. Элемент Е* с приписанной ему функцией е*, двойственной функции е, назовем двойственным элементу Е, если он функционирует согласно табл. 2.
Таблица 1 Таблица 2
X У Ро Р1 X У е'(х,у) Ро Р1
0 0 е(0,0) а 1 — а 0 0 5(1,1) 1 -т т
0 1 е(0,1) Р 1-/3 0 1 5(1,0) 1-5 6
1 0 е(1,0) 6 1-5 1 0 ё(0,1) 1 -р Р
1 1 е(1,1) т 1 — т 1 1 ё(0,0) 1 — а а
Определение. Две схемы S и S* двойственны, если одна получается из другой заменой всех элементов на двойственные им элементы соответственно.
Теорема 1.4. Для любых двойственных схем S, S' и любого входного набора а верно равенство Pf^(S,â) = Pf.^(S',a), где S = {âi,...,ân),f(xu...,xn), f*(xi,...,xn) - функции, реализуемые схемами S и S* соответственно.
Доказывается индукцией по числу элементов схемы.
Следствие 1.2. Для любых двойственных схем S и 5* верно равенство P(S) = P(S').
Таким образом, для двойственных схем на противоположных входных наборах вероятности ошибок равны. Следовательно, равны ненадежности двойственных схем. Поэтому утверждение о надежности, доказанное для функции f в базисе Б, верно для двойственной функции /* в двойственном базисе Б', а значит, результаты, полученные в базисе Б, можно переносить в базис Б*.
Поскольку функциональный элемент Е при неисправностях типа 0 на выходе является двойственным элементу Е* при неисправностях типа 1 на выходе, далее будем исследовать только неисправности типа 0 на выходах элементов.
Так как функциональный элемент Е при неисправностях типа 0 на входах является двойственным элементу Е* при неисправностях типа 1 на входах, далее будем рассматривать только неисправности типа 0 на входах элементов.
Итак, можно исследовать лишь неисправности типа 0 на входах или на выходах элементов, а полученные результаты очевидным образом перенести на неисправности типа 1.
Во второй главе диссертации описываются методы синтеза надежных схем, из которых получены верхние оценки ненадежности схем.
Вводятся базисы
Бг = {/},Б2 = Ш, Б3 = Ба = {АЛ. Бь = {->,/>}, Б6 = (&Л,
Б7 = Es = {/М},Д> = {е,&,1},£ю = {~,<М}, Бп = {-»,},
Бп = {->,0}, Бп = {-*,©}, БЦ = {V,-}, Fis = V,0}, Б16 = V,©}, £17= {©,V,1}.
При перечислении базисов использованы обозначения:
х/у = XV Уу X 4-у — Х&у, X ~ у = х&су V Х&у, X ф у = V х&у, х у = хУ у, х -)Ьу — хку.
Известно, что любой другой базис в Р2, содержащий функции не более чем двух переменных, например, базис получается
добавлением одной или нескольких функций к одному из базисов
В разделе 2.1 описывается метод синтеза надежных схем в базисе х/у. Базисный элемент является ненадежным, функционирует с вероятностями ошибок а,/3,5,г (0 < а,/3,5,т < 1/2) согласно табл. 3.
Базис Б = {х/у} играет основополагающую роль, поскольку полученные для него результаты при подходящем выборе значений переносятся в другие базисы из двухвходовых функциональных элементов.
Таблица 3
При синтезе схем, асимптотически наилучших по надежности, особое место занимают операции над схемами.
Операция ф по произвольной схеме Б, реализующей булеву функцию £ строит схему ^(5) следующим образом: возьмем два экземпляра схемы 5, соединим их выходы со входами базисного элемента; полученную схему обозначим Построим еще один экземпляр схемы С}. Выходы схем соединим со входами еще одного базисного элемента. Схема построена.
Очевидно, в результате применения (возможно, неоднократного) операции ф к схеме S, реализующей булеву функцию £ получаются схемы, реализующие туже функцию £ Кроме того, применение этой операции к некоторым схемам 5 (при некоторых условиях на приводит к
схемам, имеющим более высокую надежность, чем исходная схема S.
Теорема 2.1.1. Пусть Г - произвольная функция, Л' - схема, реализующая ее с ненадежностью Р(5). Тогда схема ^(5) реализует функцию f с ненадежностью
Р(ф{Б)) < тах{2а + т + 2(/3 + 5)Р(в) + 2Р2(5),
а + (/? + 5)(г + 2 Р(5)) + (г + 2Р(5))2}.
Доказывается непосредственным вычислением вероятностей ошибок.
Обозначим р. = тах{а, /3,8, г} - ненадежность базисного элемента.
Теорема 2.1.2. Если ц < 1/160, то любую функцию f можно реализовать схемой ненадежность которой
Доказательство проводится индукцией по числу существенных переменных функций.
Из результатов раздела 2.1 получаем метод построения надежных схем, которые, как будет показано в третьей главе, являются не просто надежными, а асимптотически наилучшими по надежности. Предлагаемый метод, при применении которого получим верхние оценки ненадежности схем как при неисправностях на выходах элементов, так и при неисправностях на входах элементов, состоит в следующем:
В базисе Б строим схему, реализующую функцию
1) х/у, вычисляем для нее вероятности ошибок а, ¡3,5, т и, применяя теоремы 2.1.2 и 2.1.1, получаем верхнюю оценку ненадежности схем;
2) г 4 Уу вычисляем для нее вероятности ошибок Р1(11) = а, Р1(10) = = /?, Р1(01) = 5, Ро(00) = т (теорема 1.4). Затем, применяем теоремы 2.1.2, 2.1.1 и снова находим верхнюю оценку ненадежности схем.
Из двух верхних оценок ненадежности выбираем лучшую.
Таким способом получены верхние оценки ненадежности схем в разделах 2.2 и 2.3. Исключение составляет базис ¿>1в = {&,\Л"}, здесь для повышения надежности использовалась иная схема.
В разделе 2.2 описаны методы синтеза надежных схем при неисправностях на выходах элементов. Доказаны верхние оценки ненадежности схем. Нижние оценки надежности схем получаются из верхних оценок ненадежности по определению надежности.
Пусть Б - один из базисов — £18, а в схемах возникают неисправности на выходах элементов.
Теорема 2.2. Если 7 < то любую булеву функцию /(®1,..., хп)
можно реализовать схемой S над Б, для которой Р(5) < 07 + Ь"72, где а, Ь", <И - некоторые, зависящие лишь от базиса Б константы, а £ {1,2,3,4}.
Доказательство теоремы 2.2 - конструктивное. Константы, фигурирующие в формулировке теоремы, приведены в табл. 4.
В разделе 2.3 описаны методы синтеза надежных схем при неисправностях на входах элементов. Доказаны верхние оценки ненадежности схем. Нижние оценки надежности схем получаются из верхних оценок ненадежности по определению надежности.
Пусть Б — один из базисов Б\ — Б-^у а в схемах возникают неисправности на входах элементов.
Теорема 2.3. Если 7 < то любую булеву функцию /(хх,... ,хп)
можно реализоватв схемой 5 над Б, для которой Р(5) < а7' + 6"7'+1,
гле а. Ь". ¿2'. £ - некоторв1е, зависящие лишв от базиса Б константв1, а €{1,2,4}, I 6 {1,2}.
Доказательство теоремы 2.3 - конструктивное. Константы, фигурирующие в формулировке теоремы, приведены в табл. 5.
Третья глава диссертации посвящается нижним оценкам ненадежности схем. Доказано, что надежные схемы, построенные во второй главе, во всех базисах, кроме при неисправностях на выходах элементов и при неисправностях на входах элементов, являются асимптотически наилучшими по надежности.
Для получения нижних оценок ненадежности схем в базисе Б как при неисправностях на выходах элементов, так и при неисправностях на входах элементов используются следующие методы:
1) в произволвной схеме 5, реализующей функцию / £ К, ввщеля-ется связная подсхема с ненадежностью не меньше
которая содержит выход схемы и является а-схемой, т. е. ее ненадеж-ноств не болвше ненадежности схемв1 8;
2) в произвольной схеме реализующей функцию / 6 К, выделяется связная подсхема, содержащая выход схемы, по некоторым вероятностям ошибок которой можно оценить ненадежность всей схемы.
Оценки для вероятностей ошибок на выходе схем и подсхем получены с помощью лемм 1.1 - 1.18 и теорем 1.1 - 1.3 первой главы;
3) для схемы реализующей функцию / 6 .К", доказывается сущест-
вование набора значений входных переменных, на котором вероятность ошибки на выходе схемы не меньше к^ + Л7*+1 при 7 <г.
Это свойство является решающим в выборе класса функций К.
Таблица 4 Таблица 5
В разделе 3.1 доказаны нижние оценки ненадежности схем в случае неисправностей на выходах элементов.
Пусть Б - один из базисов Б, — Б,, а в схемах возникают неисправности на выходах элементов.
Теорема 3.1. Базису Б можно сопоставить класс К{п) булевых функций от переменных xi,...,xn и константы к, h такие, что для любой функции f из К и для любой схемы 5, реализующей f, при 7 < г выполняется неравенство
Константы к, Л, г (к Е {1,2,3}) приведены в табл. 6. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других - еще и от схемы. В последнем случае
соответствующее ей место в таблице содержит прочерк. Классы К(п) булевых функций f(xi,...,xn) явно найдены и описаны далее. Эти классы, исключая Кз(п) и при больших п содержат почти все булевы функции.
Установлено, что для всех базисов, за исключением и
константы равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически наилучшие по надежности схемы для почти всех булевых функций в базисах Б\ — Eit Б$, Бз, Бц, Бц, Бц — Бц и Б^ и для некоторых классов булевых функций в базисах
Верхние оценки надежности схем получаются из нижних оценок ненадежности по определению надежности.
В разделе 3.2 доказаны нижние оценки ненадежности схем в случае неисправностей на входах элементов.
Пусть Б - один из базисов Б\ — Sjg, а в схемах возникают неисправности на входах элементов.
Теорема 3.2. Базису Б можно сопоставить класс К булевых функций от переменных и константы такие, что для любой функции f из К и для любой схемы S, реализующей f, при 7 < г выполняется неравенство Р(5) > ky* + h-yt+1.
Классы булевых функций явно найдены и описаны
ниже. Константы к, h, t, г (k,t£ {1,2}) приведены в табл. 7. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других - еще и от схемы. В последнем случае соответствующее ей место в таблице содержит прочерк.
Установлено, что для всех базисов, за исключением константы равны. Это означает, что соответствующие методы
синтеза позволяют строить асимптотически наилучшие по надежности схемы для почти всех булевых функций.
Верхние оценки надежности схем получаются из нижних оценок ненадежности по определению надежности.
Опишим фигурирующие в теоремах 3.1 и 3.2 классы К(п) булевых функций.
ВД = Р2(п)\({0,1}и(иГ=1х<));
К2(п) = {/(xi,... ,х„): / нельзя представить в виде / = (г<&д(ж1,...,1п))°};
Щп) = Цп) \ ({0,1} и (и?=1 х<) и (иг=1 «0)5
Щп) = {/(21,..., х„): / нельзя представить в виде / = («?У «„))•};
Щп) = {/(хь... ,х„) : / линейная функция, существенно зависящая не менее чем от трех переменных };
К$(п) = {/(хь..., хп): / нельзя представить в виде /»«V...«?)«};
Ку{п) = {/(жь. • •, хп): / нельзя представить в виде / = V $(*!,... ,*„))•};
ВД = Р2(п) \ ({0,1} и (иГ=1 *<) и (Ц?=1 «0)5
ЛГд(п) = {/(хх,..., хп) : / нельзя представить ни в одном из видов
.V х<„ V х<„ V х<, V V х^, V х; V V а*,, V в* V V хч V V х^;
]=1 )=1 ' р=1 " ' р=1 «=1 7=1 ' р=1
*ю(т») = {/(хь..., х„): / нельзя представить ни в виде / = х* У д(х 1,... ,х„), ни в виде / = х< V д{хи... ,х„)};
Кф) = {/(хь..., хп): / нельзя представить в виде / = ((*п ~ Уп) V... V (х4 ~ у{„))-, где 2/,т 6 К.,0,1};
Кц(п) = {/(хь..., хп): / нельзя представить в виде / = ((*<, ~ Ю,)"" V ... V (»4 ~ Угк)^)а, где 6 {*ц„0,1}.
Используемые обозначения, имеют следующий. смысл: / - булева функция от п переменных х1,...,х„; Рг(п) - множество всех булевых функций от п переменных; Ь{п) - множество всех линейных булевых функций от п переменных; д — произвольная булева функция от п переменных; г,/,я,г,V,г'х,г*, г'/,гр,г( 6 {1,...,п}; а,а!,...,сц - булевы константы.
При достаточно больших п классы К\(п) — К\ъ(п), исключая К%[п) и Кь(п), содержат почти все булевы функции.
Четвертая глава диссертации посвящена сложности асимптотически наилучших по надежности схем. Доказано, что сложность асимптотически наилучших по надежности схем как при неисправностях на выходах, так и при неисправностях на входах элементов по порядку равна сложности схем, построенных только из надежных элементов.
В разделе 4.1 излагается метод синтеза надежных схем в базисе x/у, причем главное внимание уделяется сложности построенных схем. Базисный элемент является ненадежным, функционирует с вероятностями ошибок а, ¡3, т согласно табл. 3 (0 < а, /3, 8, т < 1/2,
играет основополагающую роль, поскольку полученные для него результаты переносятся в другие базисы из двухвходовых функциональных элементов. Основным результатом раздела 4.1 является теорема.
Теорема 4.1.1. При ц < 1/600 произвольную булеву функцию от п переменных можно реализовать схемой ненадежность и сложность которой удовлетворяют неравенствам
Р(5) < 7ц, ¿(5) ^ 56-27«.
Доказательство теоремы 4.1.1 - конструктивное.
Теорема 4.1.1 легко обобщается на случай произвольного конечного базиса, если в качестве элемента х/у использовать соответствующий блок из элементов нового базиса.
Теорема- 4.1.2. Пусть Б = {ех,...,е;} - произвольный базис, (л = тах{/^1, ...,(ц}> где - ненадежность базисного элемента Ер которому приписана функция гх (г = 1,...,{). Пусть к - сложность минимальной схемы, реализующей функцию х/у, а ц < 1/600/г. Тогда произвольную булеву функцию от п переменных можно реализовать такой схемой 51, что Р{Б) < 7кц, Щ) ~ 56к ■ 2п/п.
С помощью этих результатов в рассматриваемых базисах при однотипных константных неисправностях на выходах или на входах элементов будем строить асимптотически наилучшие по надежности схемы, сложность которых по порядку равна сложности схем, построенных только из надежных элементов.
В разделе 4.2 описываются методы синтеза схем, асимптотически наилучших по надежности, при неисправностях на выходах элементов. Доказаны оценки ненадежности и сложности построенных схем.
Пусть Б - один из базисов Б, — Бю а в схемах возникают неисправности на выходах элементов.
Теорема 4.2. Если 7 < ¿, то любую булеву функцию /(ж1,...,г„) можно реализовать схемой Л' над Б, для которой Р(3) < ау + Ьу2, Ь(Б) ~ с • 2п/п, где а, Ь, с, с1 - некоторые, зависящие лишь от базиса Б константы,
Оценки теоремы 4.2 установлены конструктивно, т. е. представлены методы схем удовлетворяющих указанным оценкам по надежности и сложности. Константы, фигурирующие в формулировке теоремы, приведены в табл. 6.
Б а Ь с в. 6' е к Л г л:
* = {/} 2 98 224 1/600 11 672 2 -3 1/4
1 98 224 1/600 4 672 1 0 1/2 Кх
1 122 448 1/600 6 1344 1 0 1/2 Кг
п * 2 391 448 1/1200 12 1344 2 -3 1/4 К2
1?5 = {-*,/>} 2 392 448 1/1200 12 1344 2 - - К3
Б6 = {&,-} 3 390 448 1/1200 22 1344 3 -9 1/8 К2
Бг = {~,&,ф} 3 390 672 1/1800 22 2016 1 0 1/2 Кг
£8 = ЬМ} 3 880 672 1/1800 26 2016 3 -9 1/8 К2
Бэ = {Ф,&,1} 3 966 672 1/1800 44 2016 1 0 1/2 Кг
£го = {~,&,0} 3 390 672 1/1200 22 2016 1 0 1/2 Кг
Бп = {-*Л 2 476 448 1/1200 28 1344 2 -4 1/6 к4
Бп = {->,0} 2 476 672 1/1200 28 2016 2 -4 1/6 Кг
£« = {->, Ф} 2 476 448 1/1200 28 1344 2 - - Къ
Би = {V,-} 2 506 448 1/1200 34 1344 2 - 1/4 к6
2 506 672 1/1200 34 2016 2 - - Кгг
2 506 672 1/1200 34 2016 2 - - К12
4 1137 672 1/1800 107 2016 1 0 1/2 Кг
518 = {&,У,-) 1 7 40 1/125 - - 1 0 1/2 Кг
Константы Ь и с из теоремы 4.2 определяются неоднозначно. Их можно заменить константами Ь' и с* соответственно. Заметим, что "улучшая" одну из констант (например, Ь', что соответствует повышению надежности схемы), "ухудшаем" другую - с! (увеличивая сложность схемы).
Установлено, что для всех базисов, за исключением Б^, Бт, Б$, Бга, Бц и Бп, предлагаемые методы синтеза позволяют строить для почти всех функций (при растущем п) асимптотически (по 7) наилучшие по надежности схемы со сложностью, по порядку равной сложности схем, построенных только из надежных элементов.
В разделе 4.3 описываются методы синтеза схем, асимптотически наилучших по надежности, при неисправностях на входах элементов. Получены оценки ненадежности и сложности построенных схем.
Пусть Б - один из базисов Бг — Бц, а в схемах возникают неисправности на входах элементов.
Теорема 4.3. Если 7 < ¿, то любую булеву функцию /(11,...,х„) можно реализовать схемой 5 над Б, для которой Р(5) < а71 + Ь7<+1) 2/(5) ~ с-2п/п, где а, Ь, с, с?, £ - некоторые, зависящие лишь от базиса Б константы, о € {1,2,4}, f 6 {1,2}.
Оценки теоремы 4.3 установлены конструктивно, т. е. представлены методы схем 5, удовлетворяющих указанным оценкам по надежности и сложности. Константы, фигурирующие в формулировке теоремы, приведены в табл. 7.
Б а b t с d У d к h T К
Бг = {/} 2 392 1 224 1/1200 13 672 2 -1 1/4 Kx
Бг = {4-} 2 9 2 2016 1/600 - - 2 -3 1/6 K7
1 144 1 448 1/600 15 1344 1 0 1/4 Кг
■Сь II * 1 128 1 448 1/600 11 1344 1 0 1/2 Ki
= 1 480 1 448 1/1200 18 1344 1 0 1/2 Кг
£6 = {&,"} 2 967 1 448 1/1800 28 1344 2 -1 1/6 Kt
£7 = {~>&,е} 2 449 1 896 1/1200 24 2688 2 -5 - Kl
£8 = {тМ} 2 449 1 672 1/1200 24 2016 2 -3 1/4 K2
Бд = {ф,&,1} 4 1794 1 672 1/2400 93 2016 1 0 1/2 Кг
£10 = {~,&,0} 2 967 1 672 1/1800 28 2016 2 -4 - K7
Би = НЛ 2 420 1 448 1/1200 18 1344 2 -4 1/6 к7
Бп = Н,0} 2 420 1 672 1/1200 18 2016 2 -4 1/8 К ю
£13 = {->,©} 2 923 1 448 1/1800 20 1344 1 0 1/2 Кг
Бг* = {V,-} 2 506 1 448 1/1200 34 1344 2 - 1/2 к9
5is = {~,V,0} 2 447 1 672 1/1200 22 2016 2 - - кэ
5i6 = {~,V,®} 2 1680 1 672 1/2400 31 2016 2 - - к9
£n = {e,v,i} 4 1050 1 672 1/1800 85 2016 1 0 1/2 Кг
J5i8 = {&,v,-} 1 3.13 2 504 1/450 - - 1 0 1/2 Кг
Константы Ь и с из теоремы 4.3 определяются неоднозначно. Их можно заменить константами Und соответственно. Заметим, что "улучшая" одну из констант (например, Ь\ что соответствует повышению надежности схемы), "ухудшаем" другую - d (увеличивая сложность схемы).
Установлено, что для всех базисов, за исключением Б$,Бц и £17, предлагаемые методы синтеза позволяют строить для почти всех функ-
ций (при растущем п) асимптотически (по 7) наилучшие по надежности схемы со сложностью, по порядку равной сложности схем, построенных только из надежных элементов.
Выводы
Во всех базисах, содержащих функции не более чем двух переменных, при однотипных константных неисправностях только на выходах или только на входах функциональных элементов - вероятность неисправности) показано, что
1) все булевы функции можно реализовать схемами, ненадежность которых асимптотически не больше (константы зависят от базиса и типа неисправностей,
2) во всех базисах, кроме Бт,Бд,Бю и Б^ при неисправностях на выходах элементов, при неисправностях на входах элементов, явно найден класс булевых функций К, такой, что при реализации любой функции из К любой схемой Л' ненадежность этой схемы будет асимптотически не меньше 07* при 7 О (константы а и t те же, что и в пункте 1).
Классы К, исключая ^з(п) и ^(п), которые соответствуют базисам Б5 и Б3 при неисправностях на выходах элементов, содержат почти все булевы функции;
3) в большинстве рассмотренных базисов сложность асимптотически наилучших по надежности схем для почти всех булевых функций по порядку равна сложности схем, построенных только из надежных элементов.
Пользуясь случаем, выражаю глубокую благодарность профессору Н. П. Редькину за постановку задачи, поддержку и постоянное внимание к работе.
Публикации по теме диссертации
1. Алехина, М. А. К вопросу надежности управляющих систем [Текст]: материалы Междунар. науч.-техн. конф. "Точность автоматизированных производств" (Пенза, 5-6 июня 1997 г.) / М. А. Алехина. - Пенза: типография № 1 АОЗТ "Нисса-Поволжье", 1997. - № 3. - С. 69 - 70.
2. Алехина, М. А. О сложности надежных схем в базисе {&, V,-} при однотипных константных неисправностях на выходах элементов [Текст]: межвуз. сб. науч. тр. "Вычислительная техника в автоматизированных системах контроля и управления" / М. А. Алехина. -Вып. 26. - Пенза: Изд-во Пенз. гос. ун-та, 1999. - С. 143 - 149.
3. Алехина, М. А. Синтез надежных схем в базисах {/}, {4.} при однотипных константных неисправностях на входах элементов [Текст]: тр. IV Междунар. конф. "Дискретные модели в теории управляющих систем" (Красновидово Моск. обл., 19 - 25 июня 2000 г.) / М. А. Алехина. -М.: МАКС Пресс, 2000. - С. 10 - 12.
4. Алехина, М. А. Верхние оценки ненадежности схем в базисах из двухвходовых функциональных элементов при однотипных константных неисправностях на выходах элементов [Текст]: материалы IV Молодежной школы по дискретной математике и ее приложениям (Москва, 18 - 23 сентября 2000 г.) / М. А. Алехина. - М.: Изд-во мех.-мат. ф-та МГУ, 2000. - С. 12 - 20.
5. Алехина, М. А. О надежности двойственных схем [Текст]: материалы XI Межгос. школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 20 - 25 ноября 2000 г.). Ч. 1. / М. А. Алехина. - М.: Изд-во центра прикл. исслед. при мех.-мат. ф-те МГУ, 2001. -С. 6-8.
6. Алехина, М. А. О надежности схем из ненадежных элементов х/у [Текст]: материалы XI Межгос. школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 20 - 25 ноября 2000 г.). Ч. 1. / М. А. Алехина. - М.: Изд-во центра прикл. исслед. при мех.-мат. ф-те МГУ, 2001. - С. 9 - 14.
7. Алехина, М. А. Верхние оценки ненадежности схем при однотипных константных неисправностях на входах элементов [Текст]: материалы VII Междунар. семинара "Дискретная математика и ее приложения" (Москва, 29 января - 2 февраля 2001 г.). Ч. 1. / М. А. Алехина. -М.: Изд-во центра прикл. исслед. при мех.-мат. ф-те МГУ, 2001. -С. 49 - 52.
8. Алехина, М. А. О надежности схем в базисах при однотипных константных неисправностях на входах элементов [Текст] / М. А. Алехина // Дискретный анализ и исследование операций. Сер. 1. -2001. - Т. 8. - № 2. - С. 3 - 14.
9. Алехина, М. А. О надежности схем в базисе {&, V,-} при однотипных константных неисправностях на входах элементов [Текст] / М. А. Алехина // Дискретная математика. - 2001. - Т. 13. - Вып. 3. -С. 75 - 80.
10. Алехина, М. А. О надежности схем в базисах при неисправностях типа 0 на выходах элементов [Текст]: материалы XII Междунар. школы-семинара "Синтез и сложность управляющих систем" (Пенза, 15 - 21 октября 2001 г.). Ч. 1. / М. А. Алехина. - М.: Изд-во центра прикл. исслед. при мех.-мат. ф-те МГУ, 2001. - С. 9 - 13.
11. Алехина, М. А. О надежной реализации функций специального вида в некоторых базисах при неисправностях типа 0 на выходах элементов [Текст]: материалы пятой Молодежной научной школы по дискретной математике и ее приложениям (Москва, 11-17 ноября 2001 г.) / М. А. Алехина. - М.: Изд-во мех.-мат. ф-та МГУ, 2002. -С. 5 - 9.
12. Алехина, М. А. Нижние оценки ненадежности схем в некоторых базисах при однотипных константных неисправностях на входах элементов [Текст] / М. А. Алехина // Дискретный анализ и исследование операций. Сер. 1. - 2002. - Т. 9. - № 3. - С. 3 - 28.
13. Алехина, М. А. О сложности надежных схем из ненадежных элементов [Текст]: тез. докл. XIII Междунар. конф. "Проблемы теоретической кибернетики" (Казань, 27 - 31 мая 2002 г.). Ч. 1. / М. А. Алехина. -М.: Изд-во центра прикл. исслед. при мех.-мат. ф-те МГУ, 2002. - С. 8.
14. Алехина, М. А. О надежности схем в базисе 1} при неисправ; ностях типа 0 на выходах элементов [Текст]: тр. Междунар. науч.-техн. конф. "Методы и средства измерения в системах контроля и управления" (Пенза, 9-10 сентября 2002 г.). - Пенза.: ИИЦ Пенз. гос. ун-та, 2002. - С. 193 - 197.
15. Алехина, М. А. Синтез и сложность надежных схем из ненадежных элементов [Текст] / М. А. Алехина // Математические вопросы кибернетики. - 2002. - Вып. 11. - С. 193 - 218.
16. Алехина, М. А. О сложности надежных схем в базисе при однотипных константных неисправностях на входах элементов [Текст] / М. А. Алехина // Дискретная математика. - 2003. - Т. 15. - Вып. 1. -С. 98 - 109.
17. Алехина, М. А. О надежности схем в базисах {->,"}, {~*»0} при неисправностях типа 0 на выходах элементов [Текст] / М. А. Алехина // Дискретный анализ и исследование операций. Сер. 1. - 2003. - Т. 10. -№ 1. - С. 3 - 13.
18. Алехина, М. А. О надежности схем в базисе при неисправностях типа 0 на выходах элементов [Текст]: тр. V Междунар. конф. "Дискретные модели в теории управляющих систем" (Ратмино Моск. обл., 26 - 29 мая 2003 г.) / М. А. Алехина. - М.: Изд. отдел ф-та ВМиК МГУ им. М. В. Ломоносова, 2003. - С. 9 - 10.
19. Алехина, М. А. О надежности схем в базисах
у, 0} при однотипных константных неисправностях на входах элементов [Текст]: тр. Междунар. юбилейного симпозиума "Актуальные проблемы образования и науки" / М. А. Алехина. - Пенза: ИИЦ Пенз. гос. ун-та,
2003. - Т. 1. - С. 13 - 17.
20. Алехина, М. А. О надежности схем в базисе при неисправностях типа 0 на выходах элементов [Текст] / М. А. Алехина // Известия высших учебных заведений. Поволжский регион. Естественные науки. - 2003. - № 6 (9). - С. 50 - 56.
21. Алехина, М. А. О надежности схем в базисе
[Текст]: материалы XIV Междунар. школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 27 октября -1 ноября 2003 г.).-Н. Новгород: Изд-во Нижегород. гос. пед. ун-та, 2003. -С. 9-11.
22. Алехина, М. А. О надежности схем в базисах при неисправностях типа 0 на выходах элементов [Текст] / М. А. Алехина // Дискретный анализ и исследование операций. Сер. 1. - 2004. - Т. 11. -№1. - С. 3 - 12.
23. Алехина, М. А. О верхних оценках ненадежности схем [Текст]: материалы VIII Междунар. семинара "Дискретная математика и ее приложения" (Москва, 2-6 февраля 2004 г.). Ч. 1. / М. А. Алехина. -М.: Изд-во мех.-мат. ф-та МГУ, 2004. - С. 53 - 56.
24. Алехина, М. А. О сложности надежных схем из ненадежных элементов при однотипных константных неисправностях [Текст] / М. А. Алехина // Дискретный анализ и исследование операций. Сер. 1. -
2004. - Т. 11. - № 2. - С. 3 - 17.
АЛЕХИНАМаринаАнатольевна
СИНТЕЗ, НАДЕЖНОСТЬ И СЛОЖНОСТЬ СХЕМ ИЗ НЕНАДЕЖНЫХ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
Специальность 01.01.09 - Дискретная математика и математическая кибернетика
Редактор В. В. Чувашова
Технический редактор Я А. Вьялкова Корректор Я. В. Степочкина
Компьютерный набор и верстка автора
ИД № 06494 от 26.12.01
Сдано в производство 10.08.2004. Формат 60x84/76. Бумага писчая. Печать офсетная. Усл. печ. л. 1,39. Заказ № 533. Тираж 120.
Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40. Отпечатано в типографии III У
04-15273
Введение
Глава 1. Некоторые свойства схем из ненадежных элементов
Глава 2. Верхние оценки ненадежности схем
2.1. Верхние оценки ненадежности схем из ненадежных элементов х/у
2.2. Верхние оценки ненадежности схем при неисправностях на выходах элементов
2.2.1. Базис {/}
2.2.2. Базис {|}
2.2.3. Базис
2.2.4. Базис {т^,-}
2.2.5. Базис {-»,/>•}
2.2.6. Базис {&,"}
2.2.7. Базис {~,&,Ф}
2.2.8. Базис {7^,1}
2.2.9. Базис {е,&,1}
2.2.10. Базис 0}
2.2.11. Базис {->,"}
2.2.12. Базис {—>,0}
2.2.13. Базис {-», ф}
2.2.14. Базис {V/}
2.2.15. Базис V, 0}
2.2.16. Базис V, ф}
2.2.17. Базис {ф, V, 1}
2.2.18. Базис {&, V,-}
2.3. Верхние оценки ненадежности схем при неисправностях на входах элементов
2.3.1. Базис {/}
2.3.2. Базис {+}
2.3.3. Базис
2.3.4. Базис {/>,"}
2.3.5. Базис {-»,/>}
2.3.6. Базис {&,"}
2.3.7. Базис {~,&,Ф}
2.3.8. Базис {/>, 1}
2.3.9. Базис {ф,&,1}
2.3.10. Базис &, 0}
2.3.11. Базис {->•,-}
2.3.12. Базис {—>,0}
2.3.13. Базис {—>,ф}
2.3.14. Базис {V,-}
2.3.15. Базис V, 0}
2.3.16. Базис V, ф}
2.3.17. Базис {ф, V, 1}
2.3.18. Базис {&, V,"}
Глава 3. Нижние оценки ненадежности схем
3.1. Нижние оценки ненадежности схем при неисправностях на выходах элементов
3.1.1. Базис {/}
3.1.2. Базис {1}
3.1.3. Базис
3.1.4. Базис {-/>,-}
3.1.5. Базис
3.1.6. Базис {&,"}
3.1.7. Базис {~,&,ф}
3.1.8. Базис {т^, 1}
3.1.9. Базис {ф,&,1}
3.1.10. Базис {~,&,0}
3.1.11. Базис {->•,-}
3.1.12. Базис {—>,0}
3.1.13. Базис {—ЬФ}
3.1.14. Базис {V/}
3.1.15. Базис {~,У,0}
3.1.16. Базис V, Ф}
3.1.17. Базис {ф,У,1}
3.1.18. Базис {&, V"}
3.2. Нижние оценки ненадежности схем при неисправностях на выходах элементов
3.2.1. Базис {/}
3.2.2. Базис {1}
3.2.3. Базис
3.2.4. Базис {/>,-}
3.2.5. Базис {-»,
3.2.6. Базис {&,-}
3.2.7. Базис {~,&,ф}
3.2.8. Базис 1}
3.2.9. Базис {ф,&,1}
3.2.10. Базис {~,&,0}
3.2.11. Базис {-»,"}
3.2.12. Базис {—>,0}
3.2.13. Базис {-»,$}
3.2.14. Базис {V,í
3.2.15. Базис {~,V,0}
3.2.16. Базис {~,V,e}
3.2.17. Базис {©, V, 1}
3.2.18. Базис {&,V,~}
Глава 4. Сложность надежных схем
4.1. Синтез и сложность надежных схем из ненадежных элементов х/у
4.2. Сложность надежных схем при однотипных константных неисправностях на выходах элементов
4.2.1. Базис {/}
4.2.2. Базис Щ
4.2.3. Базис
4.2.4. Базис
4.2.5. Базис {—>,/»}
4.2.6. Базис {&,"}
4.2.7. Базис {~,&,ф}
4.2.8. Базис 1}
4.2.9. Базис {ф,&, 1}
4.2.10. Базис {~,&,0}
4.2.11. Базис {->,"}
4.2.12. Базис {—>,0}
4.2.13. Базис {-»,$}
4.2.14. Базис {V,-}
4.2.15. Базис {~,V,0}
4.2.16. Базис {~,V,e}
4.2.17. Базис {ф, V, 1}
4.2.18. Базис {&, V,-}
4.3. Сложность надежных схем при однотипных константных неисправностях на входах элементов
4.3.1. Базис {/}
4.3.2. Базис {1}
4.3.3. Базис
4.3.4. Базис {>,"}
4.3.5. Базис {
4.3.6. Базис {&,"}
4.3.7. Базис {~,&,0}
4.3.8. Базис {>,1}
4.3.9. Базис {ф,&, 1}
4.3.10. Базис 0}
4.3.11. Базис
4.3.12. Базис ->,0}
4.3.13. Базис
4.3.14. Базис V,!
4.3.15. Базис N/,0}
4.3.16. Базис
4.3.17. Базис
4.3.18. Базис
Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники.
К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Проблема построения схем наилучших (асимптотически наилучших) по надежности из ненадежных элементов является одной из наиболее важных и в то же время трудных в теории надежности управляющих систем. Тем более значимым представляется ее решение с дополнительным требованием к сложности таких схем, которое состоит в том, чтобы сложность оптимальных (асимптотически оптимальных) по надежности схем по порядку равнялась сложности схем, построенных только из надежных элементов. Эта задача в предположении, что функциональные элементы подвержены однотипным константным неисправностям либо только на выходах, либо только на входах элементов, рассматривается в диссертации.
Исторически сложилось так, что сначала исследовались инверсные неисправности. Первые существенные математические результаты, касающиеся синтеза надежных схем из ненадежных элементов получил Дж. Нейман [42]. Он предполагал, что элементы подвержены инверсным неисправностям, когда функциональный элемент Е с приписанной ему булевой функцией е{х) в неисправном состоянии реализует ё(ж). Эти же неисправности рассматривались затем в работах Р. Л. Добрушина, С. И. Ортюкова, Д. Улига и некоторых других авторов [30, 31,35,36,37,43,44], причем главное внимание уделялось сложности схем (задача синтеза схем, наилучших или асимптотически наилучших по надежности, не ставилась). Речь идет о реализации булевых функций схемами из ненадежных элементов в произвольном конечном базисе Б = {б1,., ет}, га £ N [38]. Множество всех функциональных элементов Ефункции которых е, принадлежат базису будем также называть базисом Б [34]. Каждому элементу Е{ базиса приписано положительное число у(Е{) - вес данного элемента Е¿. Сложность схемы 5 определяется как сумма весов всех входящих в нее элементов и обозначается 1/(5). Предполагается, что все элементы схемы независимо друг от друга с вероятностью е подвержены инверсным неисправностям. Пусть а) - вероятность появления значения /(а) на выходе схемы 5, реализующей булеву функцию /(£), при входном наборе а = (ах, .,ап). Пусть Р(5) - максимальное из чисел Pf(a)(S, а) при всевозможных входных наборах а. Назовем величину Р(5) ненадежностью схемы 5. Вводится функция Шеннона
Ьр^{п) = тах ттХ(5), 5 где минимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию /(жх, .,хп) с ненадежностью Р{Б) < р, а максимум - по всем булевым функциям / от п переменных. Нетрудно проверить, что для любой схемы 5, содержащей хотя бы один элемент, при е < 1/2 верно неравенство >
Пусть = липь(Е{)/(п(Е^ — 1), где минимум берется по всем элементам базиса, для которых п(Е{) > 1, а п{Е¿) - число существенных переменных функции е,-, реализуемой элементом г = 1,2,., т. Для схем, реализующих булевы функции и состоящих только из надежных элементов (т.е. е = О,р = 0), О. Б. Лупанов [33] показал, что о,о(п) ~ р2п/п.
Для построения надежных схем из ненадежных элементов, подверженных инверсным неисправностям с вероятностью е (0 < е < 1/6), Дж. Нейман [42] предложил итерационный метод реализации булевых функций. С помощью этого метода произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит с • е (с - некоторая, зависящая лишь от базиса Б1 константа), т. е. ненадежность схемы по порядку равна ненадежности одного элемента (такие схемы в теории надежности управляющих систем принято называть надежными). Сложность схемы с ростом числа итераций увеличивается экспоненциально.
Любой метод синтеза схем из ненадежных элементов характеризуется двумя важными параметрами: вероятностью ошибки на выходе схемы (ненадежностью) и сложностью схемы. Оптимизация этих величин, т. е. построение наилучших по надежности и (или) сложности схем - цель исследований в теории синтеза, надежности и сложности управляющих систем. Поэтому наряду со сложностью надежных схем, которой уделялось главное внимание в работах ряда авторов, важным представляется ответ на вопрос: какова максимальная надежность схем, построенных из ненадежных элементов, подверженных тем или иным неисправностям?
Задача синтеза схем, максимально высокой надежности, или схем, надежность которых близка к максимальной надежности, ни Дж. Нейманом, ни другими исследователями не рассматривалась.
С. И. Ортюков [36] показал, что асимптотика функции Шеннона сохраняется для схем из ненадежных элементов при степенном убывании вероятности сбоев с ростом п, а именно, если последовательности рп и еп таковы, что С}Ьд£п < Рп < 1/2, 0 < еп < 1/2 и еп = о(1/п2), где > 1, Ьд- минимальная сложность схемы из надежных элементов в рассматриваемом базисе, реализующей функцию голосования д(х 1,22,23) = Х\Х2 V Х\Хз V Х2Х3, то
Ьря,ея(п) - Р2п/п.
Из результатов Н. Пиппенджера [43] следует, что при инверсных неисправностях с вероятностью ошибки е < 1/200 любую булеву функцию от п переменных в базисе {&, V,"} можно реализовать такой схемой 5, что Р(5) < 18с,. Ь(5) ~ 170 • 2п/п.
С. И. Ортюкову [37] удалось заменить требование еп = о(1/п2) условием еп < 50) где его — некоторая константа. Сформулируем полученный им результат: если 0 < е < £о, <р < 1/2, где = е+Зе2 + о(е2) при е —у 0, то существует такая функция р{е) —> р при е —у 0, что Ьр,£(п)*>р(е).2п/п.
Д. Улиг [44] для инверсных неисправностей с вероятностью ошибки не более £ доказал, что для любых с, Ь (с, Ь > 0) существует е' (е' Е (0,1/2)) такое, что при любом е, 0 < е < е', и любом р, (1 + Ъ)еЬд < р < 1/2 (точнее при любом р, я(е)Ьд <р< 1/2), выполнено соотношение
Ьр,е(п)£(1 + с)р2п/п.
С. И. Ортюков и Д. Улиг для инверсных неисправностей нашли методы синтеза схем оптимальных по сложности схем, функционирующих с некоторым уровнем надежности.
Инверсные неисправности, о которых до сих пор шла речь, достаточно удобны для использования математического аппарата теории вероятностей. Однако реальные неисправности элементов более точно отражают другие математические модели неисправностей. Основной из них являются однотипные константные неисправности на выходах и на входах элементов.
Однотипные константные неисправности на выходах элементов впервые исследовались в кандидатской диссертации автора [4].Там же впервые был получен ответ на вопрос о надежности асимптотически наилучших (по надежности) схем, построенных из ненадежных элементов. Тогда задачу построения схем, асимптотически наилучших по надежности, удалось решить лишь в четырех базисах из двухвходовых элементов.
Вопрос о возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов) оставался открытым.
Прежде чем перейти к изложению материала настоящей диссертации, отметим еще две важные задачи из теории синтеза, надежности и сложности управляющих систем.
С. В. Яблонский [41] рассматривал задачу синтеза надежных схем для случая, когда наряду с ненадежными конъюнктором, дизъюнктором, инвертором (е - максимум вероятностей их повреждений, 0 < е < 1/2) базис Б содержит абсолютно надежный элемент, реализующий функцию голосования д(х\,х2, £3) = х\хг V х\х^ V х^х^. Им доказано, что для любого р > 0 существует алгоритм, который для каждой булевой функции /(®1,., хп) строит схему 5 так, что •Р(З') < р и Ь(З') ~ 2п-1/п (сложность схемы здесь и далее - число функциональных элементов в ней).
Задача построения схем сколь угодно высокой надежности (когда Р(5) —> 0) рассматривалась В. В. Тарасовым [39]. Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом выявлены необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных Тарасовым результатов для базисов из двухвходовых функциональных элементов следует невозможность построения сколь угодно надежных схем для произвольных функций как при инверсных неисправностях, так и при однотипных константных неисправностях, которые определены ниже.
В настоящей диссертации решается задача реализации булевых функций асимптотически наилучшими по надежности схемами во всех базисах из двухвходовых функциональных элементов при однотипных константных неисправностях только на выходах или только на входах элементов. Существенное внимание уделяется сложности схем. Введем необходимые понятия и определения»
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в конечном базисе Б [38]. Схема реализует функцию /(х\,. .,яп), если она реализует ее при отсутствии неисправностей в схеме. Предполагается, что каждый элемент схемы независимо от состояний других элементов может перейти в неисправное состояние.
Определим однотипные константные неисправности на выходах элементов и на входах элементов.
Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью у (у < 1/2), реализует константу 0, будем называть ее неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, будем называть эту неисправность неисправностью типа 1 на выходе элемента.
Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью 7 (7 < 1/2) может превратиться в нуль, будем называть ее неисправностью типа 0 на входе элемента. Если же неисправность элемента такова, что поступающая на его вход единица не искажается, а - нуль с вероятностью 7 может превратиться в единицу, будем называть ее неисправностью типа 1 на входе элемента.
Ненадежность P(S) схемы S, реализующей /(£), для указанных неисправностей определяется так же, как и для инверсных неисправностей, т. е.
P(S)=m¡xPm(Stá), где Pf^(Sjâ) - вероятность появления значения /(а) на выходе схемы S при входном (произвольном) наборе ¿L
Надежность схемы равна 1 — P(S).
Обозначим P(f) = inf P(S)j где S - схема из ненадежных элементов, реализующая булеву функцию f(xi,.,xn).
Схему А из ненадежных элементов, реализующую булеву функцию /(¿с), будем называть асимптотически наилучшей (асимптотически оптимальной) по надежности, если Р(А) ~ Р(/) при у —> 0, т. е.
7-Ю P(f)
Будем считать веса всех элементов равными единице, и тогда сложность L(S) схемы S - число функциональных элементов в ней.
Введем базисы
Бг = {/},Б2 = Ш, Б3 = {/>,-}, Ба = {/>,-}, Бъ = {->,/>}, Д» = {&,"}, Б7 = &,©},.Д8 = {/>,1}, Бд = {ф,&,1}, Б10 = {~,&,0}, Бп = {-+Л, Бп = {->,0}, £>1з = {->,©}, БЦ = {V,-}, Б15 = {~,V,0}, Би = V,®}, i7 = {e,V,l}.
При перечислении базисов использованы обозначения: х/у = xV у, х 1у = х&су, х ~ у = x$zy V xSzy, х ф у = х&у V x$¿y, х —> у = х V уу х у = х&у.
Известно, что любой другой базис в Рг> содержащий функции не более чем двух переменных, например, базис Б\$ = {&, V,"}, получается добавлением одной или нескольких функций к одному из базисов Б\ -Б17.
Впервые задача синтеза схем, обладающих асимптотически (по 7) наилучшей надежностью, рассматривалась и была решена в кандидатской диссертации [4] и статьях автора [1, 3, 5] лишь для четырех базисов Б\у Б2, Бъ, Б\$ при однотипных константных неисправностях на выходах элементов. В дальнейших исследованиях автора выяснялись возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов). Существенное внимание в этих исследованиях уделялось и сложности надежных схем. Ответы на вопросы "Какова цена (стоимость) реализации функции схемой, асимптотически оптимальной по надежности? Как увеличится сложность такой схемы по сравнению со сложностью схемы, построенной только из надежных элементов?" были также впервые получены в статье [2] и кандидатской диссертации [4] автора для четырех вышеназванных базисов. Оказалось, что построение асимптотически наилучших по надежности схем возможно со сложностью, по порядку равной сложности схем, построенных только из надежных элементов.
В настоящей диссертации задача синтеза схем, асимптотически наилучших по надежности, решена во всех базисах из двухвходовых функциональных элементов, за исключением £7, £9, Бю и Бп, при однотипных константных неисправностях на выходах элементов, и во всех базисах из двухвходовых функциональных элементов, за исключением Бд, Б13 и Бп, при однотипных константных неисправностях на входах элементов.
Поскольку ненадежности двойственных схем равны (теорема 1.4, следствие 1.2), утверждения, доказанные в данном базисе Б для функции / при неисправностях типа 0 на выходах (входах) элементов, справедливы в двойственном базисе Б* для двойственной функции /* при неисправностях типа 1 на выходах (входах) элементов. Поэтому далее будем рассматривать только неисправности типа 0.
Пусть Б - один из базисов Б\ - Б\&, а в схемах возникают неисправности на выходах элементов.
Теорема 1. Если 7 < с?, то любую булеву функцию /(£1,, я„) можно реализовать схемой £ над Б, для которой -Р(5) < ау + Ьу2, 1/(5) ~ с • 2п/п, где а, Ь, с, й - некоторые, зависящие лишь от базиса
Б, константы, а £ {1,2,3,4}.
Оценки теоремы 1 установлены конструктивно, т. е. представлены методы синтеза схем 5, удовлетворяющих указанным оценкам по надежности и сложности.
Теорема 2. Базису Б можно сопоставить некоторый класс К булевых функций от переменных ., хп и константы к, к такие, что для любой функции / из К и для любой схемы 5, реализующей /, при 7 < г выполняется неравенство Р(5) > ку + /172.
Отвечающие базисам £1 — Б\$ константы а, Ь, с, Л, Л, г и классы X приведены в таблице 1. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других — еще и от схемы. В последнем случае соответствующее ей место в таблице содержит прочерк.
Таблица 1
Б а Ь с а У с' к к г К = {/} 2 98 224 1/600 11 672 2 -3 1/4 к2
2 = Ш 1 98 224 1/600 4 672 1 0 1/2 Кг з = {/>,-} 1 122 448 1/600 6 1344 1 0 1/2 Кг
Б, = {/>,1 2 391 448 1/1200 12 1344 2 -3 1/4 к2
Д> = {->,/>} 2 392 448 1/1200 12 1344 2 — — Кг
Д> = {&,"} 3 390 448 1/1200 22 1344 3 -9 1/8 к2
7 = {~,&,е} 3 390 672 1/1800 22 2016 1 0 1/2 Кг
8 = {тМ} 3 880 672 1/1800 26 2016 3 -9 1/8 к2
59 = {Ф,&:,1} 3 966 672 1/1800 44 2016 1 0 1/2 Кг
Бю = {~,&, 0} 3 390 672 1/1200 22 2016 1 0 1/2 Кг {->/} 2 476 448 1/1200 28 1344 2 -4 1/6 кА
Б12 = {->,0} 2 476 672 1/1200 28 2016 2 -4 1/6 к2
13 = {->>$} 2 476 448 1/1200 28 1344 2 — — Кь
14 = {V,"} 2 506 448 1/1200 34 1344 2 — 1/4 К6
2 506 672 1/1200 34 2016 2 — — Кгг
2 506 672 1/1200 34 2016 2 — — К12
4 1137 672 1/1800 107 2016 1 0 1/2 Кг
Б« = {&, V,! 1 7 40 1/125 — ■ — 1 0 1/2 Кг
Установлено, что при неисправностях на выходах элементов для всех базисов Б\ — .£>18, исключая £7, £9, £>10 и £17, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически (по 7) наилучшие по надежности схемы для почти всех булевых функций (при растущем п) в базисах Б\ — £4, .£>6, -£>8) -£>11» -£>12 > £>14 —-£>16 и £>18 со сложностью, по порядку равной сложности схем, построенных только из надежных элементов, и для некоторых классов булевых функций в базисах £5 и .£>13. Таким образом, из теорем 1 и 2 следует
Теорема 3. Схемы, построенные в теореме 1, являются асимптотически наилучшими по надежности для почти всех функций в базисах Б\ — ¿>4, 2?6j £>8) 5ц, Б\2, Б14 — ¿>16 и Бщ (сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов) и для некоторых функций в базисах £5 и ¿>13.
Константы Ь и с не являются единственной парой, для которой теорема 1 справедлива. Их можно заменить константами Ъ' и V соответственно. Заметим, что "улучшая" одну из констант (например, b', что соответствует повьпнению надежности схемы), "ухудшаем" другую — с' (увеличивая сложность схемы).
Опишим фигурирующие в таблицах 1 и 2 классы К\(п) — Ä"i2(n). tfi(n) = р2(п) \ ({0,1} и (u?=1 Xi));
К2(п) = {f(x 1,., хп) : / нельзя представить в виде / = (xikgixi,., яп))а};
Kz(n) = L(n) \ ({0,1} U (U?=1 xí) U (U?=i *<));
K±{n) = {/(®i,.,arn) : / нельзя представить в виде f = (x?Vg{x i,.,xn))a};
-Ks(rc) = {/(^l) • • • > xn) • /линейная функция, существенно зависящая не менее чем от трех переменных };
К&{п) = {/(xi,.,a;n) : / нельзя представить в виде / = (*?V. *?)«};.
Kj(n) = {f(x 1,., хп) : / нельзя представить в виде / = (zt- V^(a;b.,a;n))a};
К8(п) = P2(n) \ ({0,1} U (U?=1 х{) U (U?=1 Si));
Кд(п) = {/(я 1,., жп) : / нельзя представить ни в одном из видов
V xip V xin V xí, V V я;р, V а*, V V xí , V я,-, V V хч V V я;р; j=1 j=i j=i p=i j=1 p=i t=i j=i p=i
Tio(n) = {/(я1,., xn) : f нельзя представить ни в виде / = xfV д(хi, — ни в виде / = х{ V ^(zi,., zn)};
-Kn(n) = {/(яь.,яп) : / нельзя представить в виде / = ((®н - У,ч) V . V (xik ~ 2/¿fc))a, где yim £ {яг-га,0,1};
I2(n) = {/(яь., жп) : / нельзя представить в виде = ((яй -2/г1)а'^.У(^к ~2Л-к)а'*)а, ™ yi,. G {я1т,0,1}.
Используемые обозначения имеют следующий смысл: / - булева функция от п переменных х\,. ,хп; -Рг(гс) (L(n)) - множество всех (соответственно всех линейных) булевых функций от п переменных; д - произвольная булева функция от п переменных; г,j,/, s,r,¿i,¿jfe,z'j,г'/,ip,¿t Е
1,.,п}; а, ах,., а/ - булевы константы.
При достаточно больших п классы К\(п) — К^ть), исключая Кз(п) и К^п), содержат почти все булевы функции.
Пусть теперь Б - опять же один из базисов Б\ — но в схемах возникают однотипные константные неисправности на входах элементов.
Теорема 4. Если 7 < с£, то любую булеву функцию /(жь., хп) можно реализовать схемой 5 над Б, для которой Р(5) < <27* + &7<+1, Ь{Б) ~ с • 2п/п, где а, Ь, с, 4 — некоторые, зависящие лишь от базиса Б, константы, а е {1,2,4}, £ £ {1,2}.
Доказательство теоремы 4, также как и теоремы 1 - конструктивное.
Теорема 5. Базису Б можно сопоставить некоторый класс К булевых функций от переменных х11.1хп и константы к, К, £ такие, что для любой функции / из К и для любой схемы 5, реализующей /, при 7 < г выполняется неравенство > ку* + /гу<+1.
Фигурирующие в теоремах 4 и 5 константы и классы К приведены в таблице 2.
Таблица 2
Б а Ь £ с <1 V ё к К г К
Б, = {/} 2 392 1 224 1/1200 13 672 2 -1 1/4 Кг
Б2 = {1} 2 9 2 2016 1/600 — — 2 -3 1/6 К7
1 144 1 448 1/600 15 1344 1 0 1/4 Кг
Б4 = {/>,"} 1 11 1 1344 1/600 — — 1 0 1/2
5 = {-*,/>} 1 480 1 448 1/1200 18 1344 1 0 1/2 Кг
Б, = {&,-} 2 967 1 448 1/1800 28 1344 2 -1 1/6 к8
7 = {~,&,ф} 2 449 1 896 1/1200 24 2688 2 -5 — к8
Д> = {/Ы} 2 449 1 672 1/1200 24 2016 2 -3 1/4 к2
Д) = {е,&,1} 4 1794 1 672 1/2400 93 2016 1 0 1/2 Кг ю = {~,&,0} 2 967 1 672 1/1800 28 2016 2 -4 — к7
Бп = {->,-} 2 420 1 448 1/1200 18 1344 2 -4 1/6 к7
12 = {->, 0> 2 420 1 672 1/1200 18 2016 2 -4 1/8 К ю
13 = {->,е} 2 923 1 448 1/1800 20 1344 1 0 1/2 Кг
Бы = {V,-} 2 506 1 448 1/1200 34 1344 2 — 1/2 Кд
15 = {~,У,0} 2 447 1 672 1/1200 22 2016 2 — — Кд
2 1680 1 672 1/2400 31 2016 2 — — Кд
4 1050 1 672 1/1800 85 2016 1 0 1/2 Кг
Б18 = {&,У,"} 1 3.13 2 504 1/450 — — 1 0 1/2 Кг
В каждом базисе константа £ в теоремах 4 и 5 одна и та же. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других - еще и от схемы. В последнем случае соответствующее ей место в таблице содержит прочерк. Теорема 4 будет справедлива, если константы Ъ и с заменить константами Ь' и с' соответственно.
Установлено, что для всех базисов Б\ — Б\$, исключая Б$,Бц и £17, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить схемы, асимптотически (по 7) наилучшие по надежности, для почти всех булевых функций (при растущем п) в названных базисах, причем сложность предлагаемых схем по порядку равна сложности схем, построенных только из надежных элементов. Таким образом, из теорем 4 и 5 следует
Теорема 6. Схемы, построенные в теореме 4, являются асимптотически наилучшими по надежности для почти всех функций в базисах Б\ — Б$, Б10 — Бу Б14 — Z>i6 и i>i8, причем сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов.
Напомним, что константа t равна двум только в базисах Бч и ^18 и единице в остальных случаях.
При t = 1 ненадежность схемы сверху и снизу оценивается функцией, по порядку равной 7 при 7 —> 0. Точнее, произвольную функцию можно реализовать схемой (см. теоремы 1 и 4), ненадежность которой асимптотически не больше ау (7 —> 0). Если же функция / G К, то ненадежность любой схемы, ее реализующей (см. теоремы 2 и 5), асимптотически не меньше ку (7 —> 0). В том случае, когда а = к, схема S (см. табл. 1 и 2) для функции / G К имеет ненадежность, асимптотически равную ау (7 —> 0), и является асимптотически наилучшей.
При t = 2 имеем качественно другой результат. Ненадежность схемы оценивается (сверху и снизу) функцией, по порядку равной у2 при 7 —> 0. Точнее, в базисе произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше 2у2 (7 —у 0). Если же функция / G.-KV» то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше 2у2 (7 0). Следовательно, схема 5, удовлетворяющая условиям теоремы 4, для функции / G Ki имеет ненадежность, асимптотически равную 272 (7 —> 0), и является асимптотически наилучшей по надежности. Аналогично, в базисе Б\$ произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше у2 (у —> 0). Если же функция / G ifi, то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше у2 (у 0). Следовательно, схема, удовлетворяющая условиям теоремы 4, для функции / G К\ имеет ненадежность, асимптотически равную у2 (у 0), и является асимптотически наилучшей по надежности.
Диссертация состоит из введения, четырех глав и списка литературы, содержащего 44 названия. Общий объем работы - 169 страниц, в работе содержатся 11 рисунков (они приведены в приложении) и 5 таблиц. Нумерация таблиц и рисунков — сквозная.
1. Алехина М.А. О синтезе надежных схем из функциональных элементов х/у при однотипных константных неисправностях на выходах элементов // Вестн. Моск. ун-та. Матем. Механ. 1991. N 5.С. 80-83.
2. Алехина М.А. О сложности надежных схем из функциональных элементов при однотипных константных неисправностях на выходах элементов // Вестн. Моск. ун-та. Матем. Механ. 1992. N 5.С. 79 81.
3. Алехина М.А. О надежности схем в базисе {&, V,"} при однотипных константных неисправностях на выходах элементов // Вестн. Моск. ун-та. Матем. Механ. 1992. N 6. С. 56 58.
4. Алехина М. А. Синтез надежных схем из ненадежных двухвходовых функциональных элементов // Канд. дисс. М., 1992.
5. Алехина М. А. О надежности схем из ненадежных функциональных элементов при однотипных константных неисправностях на выходах элементов // Дискретная математика. 1993. Т. 5, вып. 2. С. 59 74.
6. Алехина М. А. К вопросу надежности управляющих систем // Материалы Международной научно-технической конференции "Точность автоматизированных производств" (Пенза, 5-6 июня 1997 г.). N 3. Пенза: Типография N 1 АОЗТ "Нисса-Поволжье", 1997. С. 69 70.
7. Алехина М.А. О надежности схем в базисах {ж/у}, {я I у} при однотипных константных неисправностях на входах элементов / / Дискретный анализ и исследование операций. Сер. 1. 2001. Т. 8, N 2. С. 3 14.
8. Алехина М. А. О надежности схем в базисе {&, V,"} при однотипных константных неисправностях на входах элементов// Дискретная математика. 2001. Т. 13, вып. 3. С. 75 80.
9. Алехина М. А. Нижние оценки ненадежности схем в некоторых базисах при однотипных константных неисправностях на входах элементов // Дискретный анализ и исследование операций. Сер. 1. 2002. Т. 9, N 3. С. 3-28.
10. Алехина М. А. Синтез и сложность надежных схем из ненадежных элементов // Математические вопросы кибернетики. 2002. Вып. 11. С. 193-218.
11. Алехина М. А. О сложности надежных схем в базисе {&, V,"} при однотипных константных неисправностях на входах элементов // Дискретная математика. 2003. Т. 15, вып. 1. С. 98 109.
12. Алехина М. А. О надежности схем в базисах {—>,"}, {->,0} при неисправностях типа 0 на выходах элементов / / Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10, N 1. С. 3 13.
13. Алехина М. А. О надежности схем в базисе {а: V у, х ф у, 1} при неисправностях типа 0 на выходах элементов // Известия высших учебных заведений. Поволжский регион. Естественные науки. 2003. N6(9). С. 50- 56.
14. Алехина М. А. О надежности схем в базисах {/»,—>}, {-*,ф} при неисправностях типа 0 на выходах элементов // Дискретный анализ и исследование операций. Сер. 1. 2004. Т. 11, N 1. С. 3 12.
15. Алехина М. А. О верхних оценках ненадежности схем // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (Москва, 2-6 февраля 2004 г.). М.: Изд-во мех.-мат. ф-та МГУ, 2004. С. 53 56.
16. Алехина М. А. О сложности надежных схем из ненадежных элементов при однотипных константных неисправностях // Дискретный анализ и исследование операций. Сер. 1. 2004. Т. 11, N 2. С. 3 17.
17. Добрушин Р.Л., Ортюков С.И. О нижней оценке для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 1. С. 82 89.
18. Добрушин Р. Л., Ортюков С. И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ., 1977. Т. 13, N 3. С. 56 76.
19. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: Наука, 1976.
20. Лупанов О. Б. Об одном методе синтеза схем. Изв. ВУЗов, Радиофизика, 1958. Т. 1, N 1. С. 120 - 140.
21. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
22. Ортюков С. И. К вопросу о синтезе асимптотически безызбыточных самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ. 1977. Т. 13, N 4. С. 3 8.
23. Ортюков С. И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок // Проблемы передачи информации. 1981. Т. 17, вып. 4.С. 84 97.
24. Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и ее приложениям (Москва, 27 29 января 1987 г.). М.: Изд-во Моск. ун-та, 1989. С. 166 - 168.
25. Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
26. Тарасов В.В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. 1976. Т. 20, N 3. С. 391 400.
27. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
28. Pippenger N. On networks of Noisy Gates.- 26 Symposium on Foundation on Computer science, 21-23.10.1985, Portland, 30 38.
29. 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).
