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

• Автор: Чугунова, Варвара Валерьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Пенза
• Количество страниц: 110 с. : ил.

I. Некоторые свойства схем из ненадежных элементов
II. Верхние оценки ненадежности схем при инверсных неисправностях на входах элементов
III. Нижние оценки ненадежности схем при инверсных неисправностях на входах элементов
IV. Сложность асимптотически наилучших по надежности схем при инверсных неисправностях на входах элементов
Литература

К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Разработка специальных методов синтеза схем из ненадежных функциональных элементов связана, главным образом, с выбранной математической моделью неисправностей. Одна из основных моделей определяется инверсными неисправностями на входах или на выходах элементов. В диссертации рассматривается задача построения асимптотически оптимальных (асимптотически наилучших) по надежности схем в предположении, что функциональные элементы подвержены инверсным неисправностям только на входах элементов. Решение этой задачи усложняется дополнительным требованием к сложности схем, которое состоит в том, чтобы сложность асимптотически оптимальных по надежности схем по порядку равнялась сложности минимальных схем, построенных только из надежных элементов. Задача решается в неприводимых полных базисах, содержащих функции не более чем двух переменных.
Впервые задачу синтеза надежных схем из ненадежных элементов рассматривал Дж. фон Нейман [1]. Он рассматривал инверсные неисправности на выходах элементов, когда функциональный элемент с приписанной ему булевой функцией /(Зс)=ДХ1, *2, Хп) в неисправном состоянии, в которое переходит с вероятностью 8 (ее(0; 1/2)), реализует функцию /(х). С помощью итерационного метода Дж. фон Нейман установил, что при ее(0; 1/6) произвольную булеву функцию можно реализовать схемой, вероятность ошибки, на выходе которой при любом входном наборе значений переменных не превосходит СЕ (с — некоторая абсолютная константа). Однако сложность такой схемы с ростом числа итераций увеличивается экспоненциально (примерно, в Ък раз, где к-число итераций).

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

функции от п переменных в базисе В, где минимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию х2, —, *п) с ненадежностью Р(5) < р, а максимум - по всем булевым функциям /от п переменных.
Пусть р = ш1п(у(£’/)/(«(£,• )-1)), где минимум берется по всем элементам Е1 базиса, для которых п(Е,) > 1, п(Е,) - число существенных переменных функции реализуемой элементом Еи а у(Е,) - вес функционального элемента Е[, / = 1,
О.Б. Лупанов [10] показал, что для схем, реализующих булевы функции от п переменных и состоящих только из надежных элементов (т. е. при 8 = 0 и р = 0), выполняется соотношение 10 0(я) ~р • 2" / п.

/ с ненадежностью Р(£") в базисе {~, &, 0}. Тогда по схемам 5 и 5' в базисе {х1~х2, Х|&*2, 0} можно построить схему угОй /?'), реализующую функцию / для которой Р(у2(5, 5')) < 2е + 7е2 + 18еР(5) + 3 Р2(5), где Р(5) = шах{Р(5), Р(£')}, при ее(0; 1/200].
Доказательство. Пусть /- произвольная булева функция. По теоремам 2.2 при ее(0; 1/200] ее можно реализовать схемой 5 с ненадежностью Р(5) < 16в. Для повышения надежности схемы 5 будем использовать схему Д реализующую функцию £(х1,Х2,Х3) = Х,Х2 ух,х3 ух2х3, Нетрудно проверить, ЧТО Х[Х2 V Х^з V Х2Х3 = (Х1 ~ х2)&(х2 ~ х3) ~ х2. Моделируя формулу в правой части последнего равенства, построим схему £) из четырех элементов (рис. 2.9). Вероятности ошибок на выходе этой схемы таковы: Л(000) < 8е, Р0(001) < 58, /»,(010) < 2е + 7е2, РДОИ) < 58, Р0(ЮО) < 5е, /»0(101) <2е + 7е2, Р,(110) < 58, Р0(111) < 8е.
Возьмем два экземпляра схемы 5, реализующей функцию / один экземпляр схемы />', реализующей функцию /, и соединим их выходы с входами схемы И (рис. 2.10). Построенную таким образом схему обозначим у2(£,5"). Вычислим вероятности ошибок на выходе этой схемы.