WWW.NEW.PDFM.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Собрание документов
 


«М. А. Алехина, С. И. Аксенов, А. В. Васин О ФУНКЦИЯХ И СХЕМАХ, ПРИМЕНЯЕМЫХ ДЛЯ ПОВЫШЕНИЯ НАДЕЖНОСТИ СХЕМ Найден широкий класс булевых функций, способных повышать надежность схем. ...»

Известия высших учебных заведений. Поволжский регион

УДК 519.718

М. А. Алехина, С. И. Аксенов, А. В. Васин

О ФУНКЦИЯХ И СХЕМАХ, ПРИМЕНЯЕМЫХ

ДЛЯ ПОВЫШЕНИЯ НАДЕЖНОСТИ СХЕМ

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

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

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

Дж. фон Нейман предложил итерационный метод, позволяющий при 0 1/ 6 произвольную булеву функцию реализовать схемой, ненадежность которой асимптотически не больше при условии, что в рассматриваемом базисе содержится функция голосования g ( x1, x2, x3 ) x1x2 x1x3 x2 x3 .

Метод дает экспоненциальное увеличение сложности схемы (примерно в 3k раз, где k – используемое число итераций). В этом его главный недостаток .

Схема из ненадежных элементов имеет две важные характеристики:

вероятность ошибки на выходе схемы (ненадежность) и сложность схемы .

Оптимизации сложности схем уделялось главное внимание в работах С. И. Ортюкова [2], Д. Улига [3] и некоторых других авторов. Задача построения асимптотически оптимальных по надежности схем из ненадежных элементов решалась М. А. Алехиной [4]. Сформулируем результаты этих и других авторов .

Рассматривается реализация булевых функций схемами из ненадежных элементов над конечным полным базисом B {e1,..., em } [5]. Множество всех функциональных элементов Ei, функции которых ei принадлежат базису B, будем также называть базисом B [6]. Схема из ненадежных функциональных элементов реализует булеву функцию f ( x1,..., xn ), если при поступлении на вход схемы двоичного набора a (a1,..., an ) при отсутствии неисправностей на выходе схемы появляется значение f (a). Каждому элементу базиса приписано положительное число v( Ei ) – вес данного элемента. Сложность L(S) схемы S определяется как сумма весов всех входящих в нее элементов. Предполагается, что все элементы схемы независимо друг от друга с вероятностью ( 0 1/ 2 ) подвержены инверсным неисправностям на выходах .

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

№ 3, 2008 Физико-математические науки. Математика Пусть P f inf P S, где S схема из ненадежных элементов, реализующая булеву функцию f. Схему A из ненадежных элементов, реализующую булеву функцию f, назовем асимптотически оптимальной по наP A дежности, если P A ~ P f при 0, т.е. lim 1 .

f 0 P Вводится функция Шеннона L p, (n) max min L( S ), где минимум беS f рется по всем схемам S из ненадежных элементов, реализующим функцию f ( x1,..., xn ) с ненадежностью P ( S ) p, а максимум – по всем булевым функциям f от n переменных .

Пусть min v( Ei ) /( n( Ei ) 1), где минимум берется по всем элементам Ei базиса, для которых n( Ei ) 1, а n( Ei ) – число существенных переменных функции ei, реализуемой элементом Ei, i 1,..., m. Для схем, реализующих булевы функции и состоящих только из надежных элементов (т.е .





0, 0 ), О. Б. Лупанов [7] показал, что L0,0 ( n) ~ 2n / n .

С. И. Ортюков [2] получил следующий результат: если 0 0, p q () Lg, где Lg – минимальное число надежных элементов, необходимое для реализации функции голосования g ( x1, x2, x3 ) x1x2 x2 x3 x1x3 в рассматриваемом базисе, q() 3 2 o( 2 ) при 0, то существует такая функция () при 0, что L p, ( n) () 2n /n .

Д. Улиг [3] для инверсных неисправностей с вероятностью ошибки не более показал, что для любых c, b (c, b 0) существует ( (0,1/ 2)) такое, что при любом, 0, и любом p, p (1 b) Lg, справедливо соотношение L p, ( n) (1 c) 2n / n .

С. И. Ортюков и Д. Улиг для инверсных неисправностей нашли методы синтеза оптимальных по сложности схем, функционирующих с некоторым уровнем надежности .

С. В. Яблонский [8] рассматривал задачу синтеза надежных схем в базисе B = {x1&x2, x1x2, x1, g ( x1, x2, x3 ) }. В отличие от С. И. Ортюкова и Д. Улига, он предполагал, что элемент, реализующий функцию голосования g ( x1, x2, x3 ) x1x2 x2 x3 x1x3, абсолютно надежный, а конъюнктор, дизъюнктор и инвертор – ненадежные, подвержены произвольным неисправностям, ненадежность каждого из них не больше. Доказано [8], что для любого p 0 существует алгоритм, который для каждой булевой функции f ( x1,..., xn ) строит такую схему S, что P ( S ) p, L(S) 2n1 / n .

Отметим, что все названные авторы для повышения надежности схем использовали функцию голосования g ( x1, x2, x3 ) x1x2 x2 x3 x1x3 .

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

Предполагалось, что неисправности элементов статистически независимы .

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

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

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

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

Задача реализации булевых функций асимптотически оптимальными по надежности схемами при инверсных неисправностях на входах элементов решена В. В. Чугуновой для всех полных неприводимых базисов, содержащих функции не более чем двух переменных [9]. Сложность этих схем (так же, как в случае однотипных константных неисправностей) по порядку равна сложности схем, построенных только из надежных элементов .

Для повышения надежности М. А. Алехина [4] применяла схемы, реализующие как функцию голосования g ( x1, x2, x3 ) x1x2 x1x3 x2 x3, так и функции x1x2 x3 x4 и x1 x2 x3 x4. С. И. Аксенов [10] расширил множество функций, схемы которых обладают свойством повышать надежность .

Он рассматривал функции вида

–  –  –

Пусть f ( x1,..., xn ) произвольная булева функция. Возьмем t экземпляров схемы S, реализующей функцию f c ненадежностью P ( S ) p, и dt экземпляров схемы S', реализующей функцию f с ненадежностью P ( S ) p .

Соединим первые t из d входов схемы Sm с выходами t экземпляров схемы S соответственно, а последние dt входов схемы Sm с выходами dt экземпляров схемы S' соответственно .

Поскольку любую булеву функцию можно реализовать схемой с ненадежностью не больше p 1/ 2, возьмем ld экземпляров схемы S0, реализующей константу 0 с ненадежностью P ( S0 ) p. Соединим (d+1)-й, …, l-й входы схемы Sm с выходами ld экземпляров схемы S0 соответственно .

Возьмем kl экземпляров схемы S1, реализующей константу 1 с ненадежностью P ( S1 ) p, и последние kl входов схемы Sm соединим с выходами kl экземпляров схемы S1 соответственно .

Построенная таким образом схема D реализует функцию f (рис. 1) .

~ x … … … …

–  –  –

ристических наборах такие, что max{v0, v1} ~ при 0. Это обстоятельство позволяет утверждать, что существуют функции, отличные от функций из класса M k, наличие которых в базисе дает такой же результат .

Пример 1. Предположим, что в конечном полном базисе B содержится функция вида x11 x22 x33 или ( x11 x22 ) x33, где i {0, 1}, i 1, 2, 3. Поскольку



Похожие работы:

«Глава первая Льюис Барнавельт ёрзал и обтирал потные руки о сиденье рычащего автобуса, следующего до Нью-Зибиди. На дворе стоял тёплый летний вечер 1948 года. Там, за окнами автобуса, порывисто завывал ветер. Сквозь плотно запечатанное стекло Льюис наблюдал, как под лунным светом колышут...»

«А К А Д Е М И Я Н А У К С С С Р ТРУДЫ ОТДЕЛА ДРЕВНЕРУССКОЙ ЛИТЕРАТУРЫ ИНСТИТУТА РУССКОЙ ЛИТЕРАТУРЫ XI А. К. ЮГОВ Образ князя-волшебника и некоторые спорные места в „Слове о полку Игореве „Аще и вща душа въ д р у з...»

«Руководство для национальных координаторов по Конвенции и инструментам КМВ РУКОВОДСТВО ДЛЯ НАЦИОНАЛЬНЫХ КООРДИНАТОРОВ ПО КОНВЕНЦИИ И ИНСТРУМЕНТАМ КМВ Сведения о публикации Сведения о публикации Опубликовано Секретариатом Конвенции по сохранению мигрирующих видов дик...»

«РАЗРАБОТКА И ЭКСПЛУАТАЦИЯ НЕФТЯНЫХ МЕСТОРОЖДЕНИЙ © Коллектив авторов, 2009 УДК 622.276.031:532.11.001.24 Методика построения карт изобар с использованием результатов гидродинамических исследований и промысловых данных на примере Верх-Тарского месторождения А.И. Тюнькин (ОАО "Новоси...»

«Зразки завдань для практичних занять 1. Запишіть слов’янські та неслов’янські прізвища по-українськи. Поясніть можливі відмінності в переданні прізвищ. Лермонтов, Елисеев, Каменев, Муравьёв, Лисицин, Никитин, Беликов, Кондратьев, Алексеев, Беленцов, Онегин, Артёмов, Пирогов, Седых, Филимонов...»

«1 Перевод Белоусова В.И. Процессы зоны корней во фреато-магматической трубке: модель размещения и значение для эволюции маародиатремовых вулканов (V. Lorenz,, S. Kurszlaukis Root zone processes in the phreatomagmatic pipe emplacement model and consequences for the evolu...»

«Интернет-магазин Игровед – лучшие настольные игры www.igroved.ru (495) 668-06-08 Правила настольной игры "Револьвер 1-1: Засада на расстоянии выстрела" (Revolver 1-1: Ambush on Gunshot Trail) Автор: Mark Chaplin Игра для 2 игроков Перевод правил...»

«А. Б. Летучий Возвратность Возвратные глаголы – глаголы, содержащие постфикс -ся (ср. лечиться, улыбаться, вернуться) во всех формах или в части форм (для пассивного употребления -ся). Присоединяясь к глаголу, -ся меняет его синтаксические...»

«И. В. Петров, М. И. Петрова Водные пути древних карел Северо-западная часть побережья Ладожского озера представляет из себя множество длинных и узких заливов и массу больших и малых островов. Это и есть Ладожс...»







 
2018 www.new.pdfm.ru - «Бесплатная электронная библиотека - собрание документов»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.