An upper bound for reliability of non-branching programs with an unreliable stop-operator.pdf Программы с оператором условной остановки [1] характеризуются наличием управляющей команды - команды условной остановки, дающей возможность досрочного прекращения работы программы при выполнении определённого условия, а именно при поступлении единицы на вход оператора условной остановки (который ещё называют стоп-оператором). Будем считать, что все вычислительные операторы независимо друг от друга с вероятностью е E (0,1/2) подвержены константным неисправностям либо типа 0, либо типа 1 на выходах [2]. Константные неисправности типа 0 (типа 1) характеризуются тем, что в исправном состоянии вычислительный оператор реализует приписанную ему булеву функцию а в неисправном - функцию 0 (функцию 1). Предполагается, что операторы условной остановки ненадёжны и независимо друг от друга подвержены неисправностям двух типов: первого и второго рода [3]. Неисправность первого рода характеризуется тем, что при поступлении единицы на вход стоп-оператора он с вероятностью 8 E (0,1/2) не срабатывает и, следовательно, работа программы продолжается. Неисправность второго рода такова, что при поступлении нуля на вход стоп-оператора он с вероятностью n E (0,1/2) срабатывает и, следовательно, работа программы прекращается. Обозначим ^ = max{e, 8, n}. Замечание 1. Заметим, что схему из функциональных элементов (ФЭ) [2] можно считать частным случаем неветвящихся программ, а именно неветвящейся программой, в которой нет стоп-операторов. Определение 1. Ненадёжностью N^(Pr) программы Pr назовём максимальную вероятность ошибки на выходе программы Pr при всевозможных входных наборах. Надёжность программы Pr равна 1 - NM(Pr). Определение 2. Особенной функцией называется функция вида x1x2 ф x2x3 ф Ф x1x3 ф £1x1 ф ^2x2 ф ^3x3 ф в0 (в E {0,1}, i = 0,1, 2, 3). Известно [4], что из всякой нелинейной функции от трёх или более переменных отождествлением и/или переименованием переменных можно получить либо некоторую нелинейную функцию двух переменных 0(x1, x2) = x1x2 ф a1x1 ф a2x2 ф а0, либо некоторую особенную функцию ^(x1,x2,x3) = x1x2фx1 x3фx2x3фв^фв^2фв^3фв0, где ao,a1,a2, eo, в1 ,в2,в3 G {0,1}. Поскольку в любом полном конечном базисе содержится нелинейная функция, далее без ограничения общности будем считать, что рассматриваемый полный базис B содержит либо нелинейную функцию двух переменных, либо особенную функцию. Для нелинейной функции двух переменных (x^1 &xc^2)аз (а1, а2, а3 G {0,1}) возможны два случая: 1) а3 = 0, тогда функция принимает вид x^1 Vx^2, и будем называть её обобщённой дизъюнкцией; 2) а3 = 1, в этом случае функция принимает вид x^1 &xa2, будем называть её обобщённой конъюнкцией. Таким образом, рассмотрим три вида базисов, содержащих 1) особенную функцию; 2) обобщённую дизъюнкцию; 3) обобщённую конъюнкцию. Получены следующие результаты. 1. Пусть полный конечный базис B содержит особенную функцию. Теорема 1. В полном конечном базисе, содержащем особенную функцию, любую булеву функцию f можно реализовать такой неветвящейся программой Prf при однотипных константных неисправностях на выходах вычислительных операторов, что при всех e G (0,1/960] справедливо неравенство N^(Pr-f) ^ max{e, п} + 68^2. 2. Пусть полный конечный базис содержит обобщённую дизъюнкцию. Здесь возможны два варианта: вычислительные операторы подвержены константным неисправностям на выходах либо типа 0, либо типа 1. Теорема 2. В полном конечном базисе, содержащем обобщённую дизъюнкцию, любую булеву функцию f можно реализовать такой неветвящейся программой Prf при константных неисправностях типа 0 на выходах вычислительных операторов, что при всех e G (0,1/960] справедливо неравенство N^(Pr-f) ^ e + 78^2. Теорема 3. В полном конечном базисе, содержащем обобщённую дизъюнкцию, любую булеву функцию f можно реализовать такой неветвящейся программой Prf при константных неисправностях типа 1 на выходах вычислительных операторов, что при всех e G (0,1/960] справедливо неравенство N^(Pr-f) ^ 80^2. 3. Пусть полный конечный базис содержит обобщённую конъюнкцию. Так же, как и в предыдущем случае, рассмотрим два варианта: вычислительные операторы подвержены константным неисправностям типа 0 либо типа 1 на выходах. Теорема 4. В полном конечном базисе, содержащем обобщённую конъюнкцию, любую булеву функцию f можно реализовать такой неветвящейся программой Prf при константных неисправностях типа 0 на выходах вычислительных операторов, что при всех e G (0,1/960] справедливо неравенство N^(Pr-f) ^ 80^2. Теорема 5. В полном конечном базисе, содержащем обобщённую конъюнкцию, любую булеву функцию f можно реализовать такой неветвящейся программой Prf при константных неисправностях типа 1 на выходах вычислительных операторов, что при всех e G (0,1/960] справедливо неравенство N^(Pr-f) ^ e + 78^2. Таким образом, в произвольном полном конечном базисе верхняя оценка ненадёжности неветвящихся программ при однотипных константных неисправностях на выходах вычислительных операторов составляет max{e,n} + 78^2 для всех e G (0,1/960] и ^ = max{e,8, п}. Однако в некоторых случаях эта оценка может быть существенно улучшена. Например, в базисе, содержащем обобщённую дизъюнкцию (конъюнкцию), любую булеву функцию можно реализовать неветвящейся программой при константных неисправностях типа 1 (0) на выходах вычислительных операторов с ненадёжностью не больше 80^2 при всех е E (0,1/960]. В качестве сравнения, для схем из ФЭ известно [2], что в произвольном полном конечном базисе любую булеву функцию f можно реализовать схемой из ФЭ при тех же типах неисправностей с ненадёжностью не больше 3е + 100е2 при всех е E E (0,1/960]. Однако в некоторых базисах данную верхнюю оценку можно улучшить. Например, в базисе {x1 Vx2, x1} она составляет 2е+42е2 при всех е E (0,1/140]; в базисе {x1&x2, x1 ~ x2} имеем е + 6е2 при всех е E (0,1/320]. Заметим, что для неветвящихся программ без стоп-операторов (см. замечание 1) 8 = n = 0, следовательно, ^ = е. Тогда верхняя оценка ненадёжности таких программ составляет е + 78е2 при всех е E (0,1/960], а в некоторых базисах 80е2, что в общем случае лучше, чем для схем из ФЭ.

Скачать электронную версию публикации