Синтез надежных схем, реализующих функции двухзначной и трехзначной логик тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Барсукова, Оксана Юрьевна

• Барсукова, Оксана Юрьевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Барсукова, Оксана Юрьевна

Оглавление

Введение 3 Глава 1. Ненадежность схем, реализующих функции трехзначной логики

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

1.2 Базис Россера - Туркетта

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

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

1.2.3 Выводы

1.3 Базис, состоящий из функции Вебба

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

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

1.3.3 Выводы

1.4 Произвольный базис

1.4.1 Произвольные неисправности

1.4.2 Инверсные неисправности

1.4.3 Выводы

Глава 2. Ненадежность схем, реализующих булевы функции

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

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

2.3 Выводы

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Синтез надежных схем, реализующих функции двухзначной и трехзначной логик»

Введение

Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории надежности управляющих систем.

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

К многозначным логикам, к их математическому аппарату как к источнику математических моделей, обладающих большими потенциальными возможностями, обращались в [1,2]. Обзор работ по многозначной логике можно прочесть в [3]. В работе [4] на компромиссной основе согласованы математические и технические (МДП-техшгки - от словосочетания металл-диэлектрик-полупроводник) требования и интересы, построен функционально полный в Рз базис и рассмотрены некоторые аспекты синтеза электронных схем в этом базисе.

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

Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [5]. Он предполагал,

что элементы схемы подвержены инверсным неисправностям на выходах, когда функциональный элемент с приписанной ему булевой функцией ip в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью е {е € (0,1/2)), реализует функцию (р. Для повышения надежности исходных схем Дж. фон Нейман использовал схему, реализующую функцию голосования д(хi, х2, х*з) = х\х2У х\х^У х2х<^ (еще эту функцию называют медианой). С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию /(жi,..., хп) (п 6 N) можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом £ € (0,1/6] (с - некоторая положительная константа).

Таким образом, ненадежность схемы 1) сравнима с ненадежностью одного отдельно взятого элемента (такие схемы в теории надежности принято называть надежными); 2) не зависит от числа п переменных функции. Основной недостаток метода Дж. Фон Неймана в том, что повышение надежности схем сопровождается существенным (по крайней мере логарифмическим) увеличением сложности схем. Затем надежные схемы с инверсными неисправностями на выходах элементов исследовались в работах С. И. Ортюкова [6] , Д. Улига [7] и некоторых других авторов, причем главное внимание уделялось именно сложности схем.

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

В отличие от названных работ в этой диссертации впервые рассматривается задача построения надежных схем из ненадежных элементов, реализующих функции трехзначной логики (1-ая глава) и функции двухзначной

логики (булевы функции) при неисправностях двух типов (2-ая глава).

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

Во второй главе решается задача синтеза надежных схем, реализующих булевы функции, но предполагается, что базисные элементы подвержены сразу двум типам неисправностей: инверсным неисправностям на выходах с вероятностью s (s Е (О,1/4)) и появлению неопределенности на выходе * (* 0 {0,1}) с вероятностью 6 (5 Е (0,1/4)). Предполагается также, что 1) в каждый такт работы любой элемент схемы подвержен только одной неисправности; 2) при появлении на выходе какого-либо элемента схемы неопределенности схема продолжает работать. Такие неисправности элементов рассматриваются впервые, ранее не исследовались.

Приведем известные и связанные с тематикой диссертации результаты о надежности схем из ненадежных функциональных элементов, реализующих булевы функции.

Пусть В - произвольный полный конечный базис в Рг. Пусть / -произвольная булева функция. Считаем, что схема 5 из ненадежных элементов реализует булеву функцию / в базисе В, если она реализует ее при отсутствии неисправностей. Предполагается, что все элементы схемы переходят в неисправные состояния независимо друг от друга. Обозначим

через Ре(/) = inf P(S), где инфимум берется по всем схемам S из ненадеж-s

ных элементов, реализующим булеву функцию /. Схема А из ненадежных элементов, реализующая булеву функцию / в базисе В, называется асимптотически оптимальной (асимптотически наилучшей) по надежности, если Р(Л) ~ Р£(/) при г 0, т. е. lim = 1.

М.А. Алехиной [11] доказано, что в базисах {.Ti|.X2} и {х\ 4- -^2} при инверсных неисправностях на выходах элементов с вероятностью е почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотиче-

ски равной Зг при £ —0. Решенная в этой статье задача является частным случаем задачи, решенной во 2-ой главе диссертации, если считать 5 = 0.

Пусть Вз - множество всех булевых функций, зависящих от трех переменных х\, .т2, гсз-

A.B. Васин [10] решил задачу синтеза асимптотически оптимальных по надежности схем во всех полных базисах В С при инверсных неисправностях на выходах элементов. Он доказал, что почти любую булеву функцию можно реализовать асимптотически оптимальной по надежности схемой, функционирующей с ненадежностью, асимптотически равной кв • £ при £ —> 0. Константа кв зависит от базиса В, и кв Е {1, 2, 3, 4, 5}.

Задачи синтеза надежных схем, на выходе которых могут быть три различных значения, рассмотрена в диссертационной работе.

Диссертация состоит из введения, двух глав, заключения и списка литературы, содержащего 29 наименований. Общий объем работы - 87 страниц.

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

В разделе 1.1 вводятся вспомогательные понятия и определения, необходимые для формулировки результатов.

Пусть п Е N, а Pj(n) - множество функций трехзначной логики, каждая из которых зависит от переменных xi,...,xn, т.е. функций /(:xi,...,xn) : {0,1,2}" {0,1,2}. Обозначим через Р3 множество всех функций трехзначной логики.

Пусть В ~ произвольный полный конечный базис (В С Р3). Пусть f(x 1,..., хп) - произвольная функция трехзначной логики, S - любая схема, ее реализующая. Обозначим через xl (I G N) набор длины I с координатами из множества {0,1, 2}. В частности, (жх, ...,хп) = хп.

Будем считать, что схема S из ненадежных элементов реализует функцию f(xn), если при поступлении на входы схемы S набора ап при отсутствии неисправностей в схеме на ее выходе появляется значение f{än). Предполагается, что элементы схемы переходят в неисправные состояния независимо друг от друга, а неисправности элементов могут быть произвольными.

Обозначим через P{(S, än) вероятность появления значения г (г £ {0,1, 2}) на выходе схемы S при входном наборе än, а через Pf(än)^r(S, än) - вероятность появления ошибки на выходе схемы S при входном наборе а", на котором f{än) = т, т.е. P/(än)^r(S, ~ап) = PT+i(S, än) + PT+2(S, ап). (В выражениях т + 1 и т + 2 сложение осуществляется по модулю 3.)

Например, если входной набор ап схемы S такой, что f(än) = 0 (т.е. при отсутствии неисправностей в схеме S на ее выходе появляется значение 0), то вероятность ошибки на этом наборе равна Pf(ä^o{S,än) = P1(S,än) + P2(S,än).

Ненадео/спостъю схемы S будем называть число P(S) = m£ix{Py(än)^T(5', <2П)}, где максимум берется по всем входным наборам ап схемы S. Надежность схемы S равна 1 — P(S).

Далее в первой главе всюду, кроме раздела 1.4.1, предполагается, что базисные элементы с вероятностью £ подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что элемент с функцией ip(xm) на любом входном наборе ат таком, что (p(äm) = т, с вероятностью 1 — 2е (г £ (0,1/4)) выдает значение г, с вероятностью £ выдает значение г +1 (mod 3) и с вероятностью £ выдает значение т + 2 (mod 3).

Очевидно, что ненадежность любого базисного элемента равна 2е.

Пусть Ре(/) = infP(S'), где инфимум берется по всем схемам S из ненадежных элементов, реализующим функцию / над базисов В. Схема А из ненадежных элементов, реализующая функцию трехзначной логики /, называется асимптотически оптимальной по надежности, если Р(А) Pe{f) при £ О, т.е. lim Щ = 1.

В разделе 1.2 решается задача построения асимптотически оптимальных по надежности схем в базисе Россера - Туркетта {0,1,2, Jq(xi), Ji(xi), </2(^1), max{xi, х2}, min{x'i, ж2}}.

В разделе 1.2.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.5), что любую функцию трехзначной логики можно реализовать такой схемой С, что Р(С) < б£ + 126е2 при всех £ G (0,1/1000]. Следовательно, любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше б£.

В разделе 1.2.2. получены нижние оценки ненадежности схем.

Пусть К\{п) - множество функций трехзначной логики, каждая из которых зависит от переменных (n ^ 3), принимает все

три значения 0,1,2 и не представима ни в виде Xk V h{xn), ни в виде xkhh{xn) (к G {1, 2,.... n}, h(xn) - произвольная функция трехзначной логики, xSzy = minja:, у}, х V у = тах{ж, у}). Нетрудно проверить (утверждение 1), что класс К\{п) содержит почти все функции из Рз(п). Пусть

оо

Кг = U КЛп)- В

теореме 1.6 доказано, что для произвольной функции

п=з

/ 6 К\ любая схема S, реализующая /, при е е (0,1/1000] функционирует с ненадежностью P(S) > бе — 16е2 + 12е3. Следовательно, любая схема, реализующая функцию / G К\ функционирует с ненадежностью, которая асимптотически (при £ 0) не меньше бе. Это означает, что для функции / 6 К\ схема, удовлетворяющая условиям теоремы 1.5, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 6£ при е —> 0.

Таким образом, в базисе Россера - Туркетта: 1) любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при £ —У 0) не больше 6г; 2) для почти любой функции такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной б£ при s —> 0.

В разделе 1.3 предложен метод построения надежных схем в полном базисе, состоящем из функции Вебба V^(xь-тг) = max(.Ti,.T2) + 1 (mod 3).

В разделе 1.3.1 получена верхняя оценка ненадежности схем, а именно доказано (теорема 1.9), что любую функцию / € Рз можно реализовать такой схемой D, что P(D) < 8е + 268s2 при всех е Е (0,1/104]. Следовательно, любую функцию из Рз можно реализовать схемой, ненадежность которой асимптотически (при е —> 0) не больше 8е.

В разделе 1.3.2 получена нижняя оценка ненадежности схем.

Пусть К2{п) - множество функций трехзначной логики, каждая из которых зависит от переменных rci,..., (n ^ 3), принимает все три значения 0,1,2 и не представима в виде шах { хь h{xn) } + с {к в {1,..,п}, с <Е {0, 1, 2}, h{xn) -произвольная функция трехзначной логики). Нетрудно проверить (утвер-

ждение 2), что класс /^(п) содержит почти все функции из Рз{п). Пусть 00

К2 = [J К2(п)- В теореме 1.10 доказано, что для произвольной / £ Кч

71=3

любая схема S, реализующая /, при е £ (0,1/104] функционирует с ненадежностью P(S) > 6s — 16е2 + 12е3. Следовательно, любая схема, реализующая функцию f € К2, функционирует с ненадежностью, которая асимптотически (при £ —> 0) не меньше б£.

Таким образом, из теорем 1.9 и 1.10 получаем следующий результат: в базисе {Уз(х1,х2}} почти любую функцию трехзначной логики можно реализовать надежной схемой, функционирующей с ненадежностью, асимптотически не больше и асимптотически не меньше бе при г —> 0.

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

В разделе 1.4.1 предполагается, что базисные элементы подвержены произвольным неисправностям и переходят в неисправные состояния независимо друг от друга.

Пусть ат,/5т - некоторые троичные наборы (т ^ 3). Обозначим через /э(ат, ¡Зт) число координат, в которых наборы ám и /Зт различаются.

Обозначим через Gm класс функций д(хт) £ Р3, каждая из которых обладает следующими свойствами: существуют такие троичные наборы ám, Рт, 7™, что

1) значения ^(а-771), дфт), д(ут) попарно различны;

2) для любого набора á™ (p(ám,á™) ^ 1) верно д(а™) = д(ат)', для любого набора /З]71 (рфт, ^f1) ^ 1) верно дф™) = дфт); для любого набора 7Г M7m, 7Р) ^ 1) верно = д{7т).

Наборы ám, 7т будем называть характеристическими наборами

оо

функции д{хш). Пусть G = (J Gm.

т=3

Схемы, реализующие функции из множества G, будем применять для повышения надежности исходных схем, используя следующую теорему (теорема 1.12): предположим, что любую функцию из Р3 можно реализовать схемой с ненадежностью не больше р, и пусть схема Sg реализу-

ет функцию д{хт) G G с ненадежностью P(Sg), причем v°,v1,v2 - вероятности ошибок схемы Sg па характеристических наборах ат (д(ат) = 0), Рт {д0т) — 1), 7т (д(ут) — 2) соответственно; тогда произвольную функцию / можно реализовать такой схемой А, что Р{А) ^ тах{г?°, v1, v2} + mpP(Sg) + (2т - т - 1 )р2.

В разделе 1.4.2 предполагается, что базисные элементы с вероятностью £ подвержены инверсным неисправностям на выходах.

Пусть Щп) - множество функций трехзначной логики, каждая из которых зависит от переменных xi, ...,хп и отлична от функций х\, ...,хп. Очевидно, что класс К^(п) содержит почти все функции; пусть =

оо

I^J Кз(п). Из теоремы 1.13 следует, что в произвольном полном конечном

п=i

базисе В для функции / G K-¿ любая, реализующая ее схема S функционирует с ненадежностью P{S) > 2е.

В теореме 1.14 доказано, что в полном конечном базисе В любую функцию / G Рз можно реализовать такой схемой А, что при всех е G (0,1/(AilO4)] верно неравенство Р(А) ^ 2Á2e + ki£2, где Ai - число элементов в схеме, реализующей функцию Вебба, \2 - число элементов в схеме, реализующей функцию д{хт) G G, ki = 17т\2\2 + 65(2m — т — l)Aj.

Из теоремы 1.13 следует, что ненадежность схем, построенных при доказательстве теоремы 1.14 (и содержащих хотя бы один функциональный элемент), по порядку равна е. Таким образом, в произвольном полном конечном базисе любую функцию / G можно реализовать надежной схемой (функцию / $ можно реализовать абсолютно надежно, не используя функциональных элементов).

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

Доказано (следствие 1.2), что если конечный полный базис В таков, что при некотором т ^ 3 верно В П Gm ф 0, то любую функцию / можно реализовать такой схемой А, что при всех s G (0, l/(Ail04)] верно неравенство Р{А) ^ 2е + к2е2, где Ai (как и в теореме 1.14) - число элементов в схеме, реализующей функцию Вебба, к2 = 17т\2 + 65 (2т ~т — 1)\\.

Таким образом, из теоремы 1.13 и следствия 1.2 получаем следующий результат: если конечный полный базис В таков, что б П б ^ 0, то 1) любую функцию из Р3 можно реализовать схемой, ненадежность которой асимптотически (при е —0) не больше 2е\ 2) для любой функции, отличной от переменной, такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 2е при е —0.

Во второй главе рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисе, состоящем из функции штрих Шеффера /¿(.ть .т2) = х\ ■ хч (еще эту функцию называют антиконъюнкцией). Предполагается, что 1) все элементы схемы независимо друг от друга переходят в неисправные состояния двух типов: инверсные неисправности на выходах элементов (когда в исправном состоянии элемент с булевой функцией х\ ■ хч в неисправном состоянии реализует булеву функцию х^ ■ хч) и появление неопределенности *, * {0,1}; 2) в каждый такт работы элемент подвержен либо только инверсной неисправности на выходе, либо только появлению неопределенности * на выходе, причем при появлении на выходе какого-либо элемента схемы неопределенности она (схема) продолжает работать.

Пусть £ (£ £ (0,1/4)) - вероятность появления инверсной неисправности на выходе элемента, 5 (6 £ (0.1/4)) - вероятность появления неопределенности на выходе элемента, т\ (т\ £ [0,1/4)) - вероятность появления 0 на выходе элемента при поступлении на его входы наборов (1,*), (*Д), (*,*); а через т2 (т2 £ [0,1/4)) - вероятность появления 1 на выходе элемента при поступлении на его входы наборов (1,*), (*Д), (*>*)•

В разделе 2.1 получена верхняя оценка ненадежности схем.

Доказано (теорема 2.3), что любую булеву функцию / можно реализовать такой схемой Д что Р{И) < Ъе + 38 + 32 • (3£2 + <52) + 2т2(48е2 +175) при всех £, <5, т\ и 7*2, удовлетворяющих условиям £ + 5 > т\ + 72, Т~1 < £ и £ £ (0,1/260], 5 £ (0,1/260], т2 £ (0,1/260].

Из теоремы 2.3 следует, что любую булеву функцию можно реализовать схемой, функционирующей с ненадежностью, асимптотически не больше 3£ + 35 при £ —0, 5 -» 0.

Заметим, что из условий £ + 5 > т\ + 72, т\ < £ при £ —0, 5 —> О следует, что т\ —> 0, т2 —> 0.

В разделе 2.2 получена нижняя оценка ненадежности схем. Пусть К^{п) - множество булевых функций, каждая из которых зависит от переменных х]_,...,хп (п > 3) и не представима в виде (х^1г(хп))ь (г £ {1,2,...,п}, а, {0,1}, 1г(хп) - произвольная булева функция). Нетрудно проверить (утверждение 4), что класс К^{п) содержит почти все

оо

булевы функции. Пусть К4 = К^{п).

тг=3

Доказано (теорема 2.5), что для произвольной функции / € К а любая схема 5*, реализующая функцию /, функционирует с ненадежностью Р(Я) > Зе + 35 + 1р{£,5,тът2), где <р(е,6,тът2) = -13е5 - 552 - Не2 -35т2 — 25гх — 2ег1 при всех £, 5, т\, т2 удовлетворяющих условиям £+5 < 1/8, £ + 5 > Т1 + т2 и т\ < £. Следовательно, любая схема, реализующая функцию / £ функционирует с ненадежностью, которая асимптотически не меньше 3£ + 35 при £ —0, 5 —>■ 0. Это означает, что для функции / £ К\ схема, удовлетворяющая условиям теоремы 2.3, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 3£ + 35 при £ —> 0, 5 —0.

Таким образом, при выполнении условий теорем 2.3 и 2.5 получаем следующие результаты: 1) любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше 3£ + 35 при £ —У 0, 5 —> 0; 2) для почти любой булевой функции такая схема является асимптотически оптимальной по надежности.

В заключении диссертации содержатся выводы и рекомендации.

Основные результаты диссертации опубликованы в работах [12] -[22], среди них 7 работ, написаны в соавторстве с научным руководителем М.А. Алехиной. В совместных работах результаты являются собственными, М.А. Алехиной принадлежат постановка задачи.

Автор благодарит своего научного руководителя профессора М.А. Алехину за постоянное внимание к работе, поддержку и полезные советы, а также сотрудников и аспирантов кафедры дискретной математики МГУ им. М.В. Ломоносова за ценные замечания и советы.

Глава 1. Ненадежность схем, реализующих функции

трехзначной логики

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

Пусть п £ 14, а -Рз(п) - множество функций трехзначной логики, каждая из которых зависит от переменных х\,...,хп, т.е. функций /(х'1,хп) : {0,1,2}" —{0,1,2}. Обозначим через Рз множество всех функций трехзначной логики, а через х1 - набор длины I (I е ]Ч) с координатами из множества {0,1,2}. В частности, (х\,..., хп) = хп.

Пусть В - произвольный полный конечный базис в Р3. Рассмотрим реализацию функций трехзначной логики схемами из функциональных элементов над базисом В.

Определение схемы из функциональных элементов, реализующей систему булевых функций, можно найти в работах [24], [25], [26]. Аналогично определяется схема из функциональных элементов, реализующая систему функций трехзначной логики. Мы приведем определение схемы на языке графов, как в работе [26].

Орграф назовем упорядоченным, если для каждой вершины в которую входит кг дуг, задан порядок е\, е2,.... е^ этих дуг.

Схемой из функциональных элементов в базисе В будем называть ациклический упорядоченный орграф, в котором:

1. Каждому истоку (полюсу) приписана некоторая переменная, причем разным истокам приписаны разные переменные (истоки при этом называются входами схемы, а приписанные им переменные - входными переменными);

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

3. Некоторые вершины выделены как выходы (истоки одновременно могут являться выходами).

Далее будем считать, что все элементы схемы ненадежны, переходят в неисправные состояния независимо друг от друга, а схема из ненадежных элементов реализует систему функций ¡1(хп),..., £ К) трехзначной

логики, если при поступлении на входы схемы набора ап при отсутствии неисправностей в схеме на ее выходах появляются соответственно значения /1 (йп),...,/¿(ап). В частности, при I — 1 имеем схему из ненадежных элементов, которая реализует одну функцию /1(хп).

Пусть схема 5 реализует функцию /(хп). Обозначим через Рг(3,ап) вероятность появления значения г (г е {0.1,2}) на выходе схемы <5" при входном наборе ап, а через ап) - вероятность появления ошибки

на выходе схемы 5 при входном наборе ап, на котором /(ап) = т. Ясно, что Рдап)^т(3- ап) = Рт+г(3, ап) + Рт+2{3, ап). (В выражениях г + 1 и г + 2 сложение осуществляется по модулю 3.)

Например, если входной набор ап схемы 5 такой, что /(ап) = 0 (т.е. при отсутствии неисправностей в схеме 5 на ее выходе появляется значение 0), то вероятность ошибки на этом наборе равна Pf(an)^ío{S,an) — Р1(3,ап) + Р2(3,ап).

Ненадежностью схемы 3 будем называть число Р(3) = ulдiк{Pf^)-íT{S,an)}, где максимум берется по всем входным наборам ап схемы 5. Надеэ1сностпъ схемы 3 равна 1 — Р(б').

Сложностью Ь{3) схемы 5 назовем число функциональных элементов в ней.

Известно [25, с. 45], что через Ji(x) {г е {0,1, 2}) обозначается функция, равная 2 при х — г и равная 0 при х ф г.

Справедлива лемма о разложении функции трехзначной логики по переменной (аналог разложения булевой функции по переменной).

Лемма 1.1. При любом п 6 N любую функцию /(^ь можно

представить следующим образом:

2) при к — 1

/(х1,х2,...,хп) = Мх1)к/(0,х2,...хп)У У^{х1)Ь/(1,х2, ...хп) V Л(.гч)&/(2,а:2, ...,£„);

2) при к 6 {2, ...,п - 1}

f(xi, ...,хк-Ъхк,хк+1, ...,хп) = J0(xk)&f(xi, ...,.-rfc_i,0,.x/c+1,..., xn)V

yJi{xk)Szf(xi,..., xk-i, 1, xk+i, ...,xn) V J2{xk)kf(xi,.... при к = n

f(x 1,..., жп) = J0(a:n)&;/(xi,..., .Tn_b 0)V VJi(a:n)&/(xi,..., z„_i, 1) V •••, Ят»-ь 2).

Доказательство проводится непосредственной подстановкой различных значений переменной хк в правую и левую части этой формулы.

Для получения нижних оценок ненадежности схем используется теорема 1.1.

Теорема 1.1. Пусть f(xn) - произвольная функция, которая принимает три значения 0, 1, 2; S - любая схема, ее реализующая. Пусть подсхема А схемы S содержит выход схемы S и реализует функцию (£>(ут) с ненадежностью Р(А) < 1/2. Пусть ро = minP ,rmw0(A 6™), где такой

входной набор схемы А, что <р(Ь™) — 0; р\ = minP /гт),1(Л, ¿71); где Ъ™

bf 1

такой входной набор схемы А, что (p(b™) — 1; р2 = min P^m^i^, b™),

ъ™

где Ъ21 такой входной набор схемы А, что (pib™) — 2.

Тогда вероятности ошибок на выходе схемы S удовлетворяют неравенствам:

Pf(ä»)MSiän) ^ Pv> если Д5") = °> Pf{ü»)Ms>än) - рь если Д«п) = 1;

Pf(ä»)MS> ^ V2, если f(än) = 2.

Доказательство. Пусть ап такой входной набор схемы S, что f(än) = 0. В зависимости от набора ап и неисправностей в схеме на входы схемы А поступает некоторый набор длины т с компонентами из множества {0,1,2}. Обозначим множество всех таких наборов через М{ап). Разобьем множество M(än) на подмножества Mi(än) = {ст\(р(ст) = г}, г е {0,1. 2}. Обозначим через Vi(än) вероятность появления на входах схемы А набора из множества Mi{än). Очевидно, что Vi(än) > 0 и vo(än) +vi(än) + v2(än) = 1.

Найдем вероятность Po(S, án) появления 0 на выходе схемы S:

P0(S, áf)<v0(án)(l-p0)+v1(án)P(A) + v2(án)P(A) = = (l-v1(án)~ v2(án))(l - ро) + (Vl(an) + v2(an))P{Á) = 1 - ро - Ыап) + ^(ап))(1 - ро -Р(А)).

Тогда вероятность появления ошибки на выходе схемы S удовлетворяет неравенству:

Pf{an)¥o(S, ап) > ро + Ы(ап) + v2(án))(l - р0 - Р(А)) > pQ + МО +

v2(án))(l - 2Р(А)) > ро, поскольку Р(А) < 1/2.

Пусть ап такой входной набор схемы S, что f(an) = 1. Аналогично проверяется, что вероятность появления ошибки на выходе схемы S удовлетворяет неравенству:

Pf(a^)MS^n) > Pi + Ыап) + Ыап))(1 - ЪР(А)) > Рь поскольку Р{А) < 1/2.

Пусть ап такой входной набор схемы S, что /(ап) = 2. Аналогично проверяется, что вероятность появления ошибки на выходе схемы S:

Pf(a-)Ms^n) > Р2 + м«п) + - 2Р(А)) > р2, поскольку

Р(А) < 1/2.

Теорема 1.1 доказана.

Следствие 1.1. P(S) > тах{ро,р\,р2}

Пусть / - функция, которая принимает три значения 0, 1,2. Пусть S -любая схема, реализующая функцию /, и пусть в схеме S можно выделить подсхему D, которая имеет один вход, содержит выход схемы S и реализует либо тождественную функцию у, либо у + 1 (mod 3), либо у + 2 (mod 3), т.е. реализует некоторую функцию y+j (mod 3), j G {0,1, 2}. Обозначим через С подсхему, получаемую из схемы S удалением подсхемы D (см. рис. 1.1).

Список литературы диссертационного исследования кандидат наук Барсукова, Оксана Юрьевна, 2014 год

Литература

1. ВиноградовЮ. А., ИорданскийМ. А. Машинный анализ схем ЭВМ // Проблемы кибернетики, вып. 24. - М.: Наука, 1972. - С. 147-160.

2. Моделирующие системы с многозначными гибридным кодированием // Сб. науч. трудов под ред. М. А. Ракова. - Киев: Наукова думка, 1980, 192 с.

3. Ларионов В. В. Замкнутые классы /с-значной логики, содержащие классы монотонных или самодвойственных функций // Дисс. ... канд. физ.-мат. наук. - Москва, 2010. - 158 с.

4. Виноградов Ю. А. О синтезе трехзначных схем // Математические вопросы кибернетики, вып. 3. - М.: Наука, 1991. - С. 187-198.

5. von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies, edited by Shannon C., Mc. Carthy J. Princeton University Press, 1956. (Русский перевод: Автоматы. M.: ИЛ, 1956. С. 68-139.)

6. Ортюков С.И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и ее приложениям (Москва, 27- 29 января 1987 г.). М.: Изд-во Моск. ун-та, 1989. С. 166-168.

7. 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).

8. Алехина M.A. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов (Монография). - Пенза: Информационно - издательский центр ПГУ, 2006. - 156 с.

9. Чугунова В.В. Синтез асимптотически оптимальных по надежности схем при инверсных неисправностях на входах элементов // Дисс. ... кандидата физ.-мат. наук. - Пенза, 2007.

10. Васин А.В. Асимптотически оптимальные по надежности схемы в

полных базисах из трехвходовых элементов / / Дисс. ... кандидата физмат. наук. Пенза, 2010.

11. Алехина М.А. О надежности и сложности схем в базисе {х\у} при инверсных неисправностях элементов // Дискретный анализ и исследование операций. Апрель-июнь 2005. - Сер. 1. Том 12 - №2 - С. 3-11.

12. Барсукова О.Ю. О возможности применения одного метода повышения надежности к схемам, реализующим функции из Рз // Материалы международной научно-практической конференции "Молодежь и наука: модернизация и инновационное развитие страны"(г. Пенза, 15-16 сентября 2011 г.) - Пенза: Изд-во ПГУ, 2011. - Часть 1. - С. 110-112.

13. Барсукова О.Ю. Об одном методе повышения надежности схем, реализующих функции из Рз // Материалы восьмой международной молодежной школы по дискретной математике и ее приложениям (г. Москва, 24-29 октября 2011 г.). М.: Редакционно-издательская группа ИПМ им. М.В.Келдыша, 2011. - Часть 1. - С. 10-13.

14. Алехина М.А., Барсукова О.Ю. О надежности схем, реализующих функции из Рз // Известия высших учебных заведений. Поволжский регион. Физико-математические пауки. - 2012 г. - № 1. - № 1 (21). - С. 57-65.

15. Барсг/кова О.Ю. О верхней оценке ненадежности схем, реализующих функции из Рз// Сборник статей XVII Международной научно-методической конференции "Университетское образование (МКУО-2013)". - Пенза: Изд-во ПГУ, 2013. - С. 261-262.

16. Алехина М.А., Барсукова О.Ю. Верхние оценки ненадежности схем в базисе "антиконъюнкция"при неисправностях двух типов // Сборник статей Международной научно-технической конференции "Проблемы автоматизации и управления в технических системах" (г. Пенза, 23-25 апреля 2013г.) - Пенза: Изд-во ПГУ, 2013. - С. 71-73.

17. Алехина М.А., Барсукова О.Ю. О ненадежности схем из функциональных элементов, подверженных двум типам неисправностей // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2013 г. - № 3 - С. 33-50.

18. Алехина М.А., Барсукова О.Ю. Верхняя оценка ненадежности схем

в базисе, состоящем из функции Вебба // Материалы девятой молодежной научной школы по дискретной математике и ее приложениям (г. Москва, 16-21 сентября 2013 г.). - М.: Изд-во ИПМ РАН, 2013. -С. 9-12.

19. Алехина М.А., Барсукова О.Ю. О надежности схем в базисе Россера-Туркетта // Современные проблемы компьютерных наук (СПКН-2013): сборник материалов I Международной научно-практической конференции, посвященной 70-летию образования Пензенского государственного университета (г. Пенза, 29-30 октября 2013 г.). - Пенза: ИИЦ ПГУ, 2013 г. - С. 96-98.

20. Алехина М.А., Барсукова О.Ю. О нижних оценках ненадежности схем, реализующих функции из Р3 // Сборник материалов регионального молодежного форума "Открытые инновации - вклад молодежи в развитие региона"(Россия, г. Пенза, 22 ноября 2013 г.). - Пенза: ИИЦ ПГУ, 2013 г. - С. 9-10.

21. Алехина М.А., Барсукова О.Ю. Оценки ненадежности схем в базисе Россера-Туркетта // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. - 2014 г. - № 1(29). - С. 519.

22. Барсукова О.Ю. О синтезе надежных схем, реализующих функции из Рз // Сборник статей XVIII Международной научно-методической конференции "Университетское образование (МКУО-2014)". - Пенза: Изд-во ПГУ, 2014. - С. 215-217.

23. Барсукова О.Ю. О повышении надежности схем в Р3// Сборник статей XVIII Международной научно-методической конференции "Университетское образование (МКУО-2014)". - Пенза: Изд-во ПГУ, 2014. -С. 217-218.

24. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984.

25. Яблонский C.B. Введение в дискретную математику: Учебное пособие для вузов. / Под ред. В.А. Садовиичего. - 3-е изд., стер. - М.: Высш. шк.; 2001. - 384 с.

26. Алексеев В.Б. Лекции по дискретной математике: учебное пособие. -

M.: Издательский отдел Фак-та ВМиК МГУ им. М.В. Ломоносова, 2004. - 76 с.

27. Редъкин Н.П. Надежность и диагностика схем. - М.: Изд-во МГУ, 1992. - 192 с.

28. AlekhinaM. A. Synthesis and complexity of asymptotically optimal circuits with unreliable gates // Fundamenta Informaticae. IOS Press, 2010. — Volume 104, number 3, pp. 219-225.

29. АлехинаМ. А., Аксенов С. И., Васин А. В. О функциях и схемах, применяемых для повышения надежности схем // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — № 3. - Пенза: ИИЦ ПГУ, 2008. - С. 30-38.