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

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

Оглавление
Введение

Глава 1. Необходимые понятия и вспомогательные утверждения

Глава 2. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью £

2.1 Верхние оценки ненадежности схем

2.2 Нижние оценки ненадежности схем

2.3 Выводы
Глава 3. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью 2е

3.1 Верхние оценки ненадежности схем

3.2 Нижние оценки ненадежности схем

3.3 Выводы
Глава 4. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью Зе
4.1 Верхние оценки ненадежности схем
4.2 Нижние оценки ненадежности схем
4.3 Выводы
Глава 5. Базисы, в которых для почти всех функций асимптотически оптимальные схемы функционируют с ненадежностью 4е или 5е
5.1 Верхние оценки ненадежности схем
5.2 Нижние оценки ненадежности схем
5.3 Выводы
Глава 6. Сложность схем
Литература

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

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

Доказательство. Пусть в базисе В содержится функция <р{х,Х2, Жз) = ж^&ж!]2Х/ж^&Жз3 Є О, где о; Є {0,1}, г = 1,2,3. Без ограничения общности
МОЖНО СЧИТаТЬ, ЧТО <Х2 = 1, Т.Є. Ір(хі, Х2, Хз) = х‘[1&£Х2 V Ж2&Ж33.
Покажем, что ^(^і, ®2, £з), жз) = ж^&жг V ЖД&Ж33 V Ж2&Ж33.
Действительно,
ір(х 1, <р(жь ж2, ж3), ж3) = щ(жі, (ж^жг V Ж2Ж33), ж3) =
= жфДж^жг V Ж2Ж33) V (жі1Ж2 V ж2Жз3)жз3 =
= ж^1((жі1Ж2)(ж2Жз3)) V ж^жгжз3 V ж2Жз
= жД(ж^ V Ж2)(жг V Ж33) V (х^Х2 V Ж2)Жз3 =
= (жДж?1 V ж^Ж2)(жг V Ж33) V (жД V жг)жз3 =
= х1Х2Х2 V жД Ж2Ж33 V ж/1 Ж33 V Ж2Ж33 =
= Ж^(ж2Жз3 V Ж33) V Ж2Ж33 =
= Ж^(ж2 V Ж33) V Ж2Ж33 = жДж2 V жДЖд3 V Ж2Ж33.
Моделируя формулу (р(Ж’1, <£>(Жі, Ж2, Жз), Жз), построим схему вд из двух элементов, реализующую функцию ж^1Ж2 V ж^'жз3 V Ж2Ж33.
Вычислим вероятности ошибок г»1 и г>° этой схемы на наборах а — (аі,0,<7з) и Р = (аі,1, аз) соответственно. Получаем Vі = є = и0. Далее действуем также, как при доказательстве теоремы 1.2.
Возьмем три экземпляра схемы £, реализующей функцию / и удовлетворяющей лемме 1.3, а также схему и построим схему Ф(5). Используя следствие 1.1, оценим ненадежность схемы Ф(5) и получим Р(Ф(5')) ^ є + 3456є2 ^ 4,6є при є Е (0,1/960]. По схеме Ф(<Б1) построим схему Ф2(5). По следствию 1.1 получим Р(Ф2(51)) ^ є + 127є2 ^ 1,14г, т.к. є Є. (0,1/960]. По схеме ФД#) построим схему Ф3(5). По следствию 1.1 имеем Р(Ф3(5)) < є + 7,7є2 < є + 8є2.
Теорема 2.3 доказана.
Из теорем 2.1, 2.2, 2.3 получаем следующий результат.
Следствие 2.1. Если в полном конечном базисе В содероісится функция из множества Є, то в этом базисе любую булеву функцию можно реализовать схемой, ненадежность которой не больше є + 200є2 при всех г Є (0,1/960].