Том 8, серия 1, номер 2, 2001 г., Стр. 3-14

УДК 519.718
М. А. Алехина
О надежности схем в базисах $\{x\mid y\}$, $\{x\downarrow y\}$ при однотипных константных неисправностях на входах элементов

Аннотация:
Показано, что любую булеву функцию в базисе $\{x\mid y\}$ при неисправностях типа 0 и в базисе $\{x\downarrow y\}$ при неисправностях типа $1$ можно реализовать схемой с ненадежностью не более $2\gamma+8\gamma^2+106\gamma^3$, где $\gamma$ – вероятность неисправности каждого входа элемента, $\gamma\leqslant 1/100$; для любой булевой функции $f$, $f\not\equiv 1$, и любой схемы $S$, реализующей $f$, при $\gamma<1/2$ ненадежность схемы не меньше $2\gamma-\gamma^2$; любую булеву функцию в базисе $\{x\mid y\}$ при неисправностях типа $1$ и в базисе $\{x\downarrow y\}$ при неисправностях типа $0$ можно реализовать схемой с ненадежностью не более $2\gamma^2+36\gamma^3+162\gamma^4$ при $\gamma\leqslant1/50$; для любой булевой функции $f$, $f\not\equiv0$, и любой схемы $S$, реализующей $f$, при $\gamma<1/2$ ненадежность схемы не меньше $\gamma^2$.
Табл. 2, ил. 4, библиогр. 7.

Алехина М. А. ¹
1. Пензенский государственный университет,
ул. Красная, 40, 440017 Пенза, Россия
е-mail: alehina@diamond.stup.ac.ru

Статья поступила 25 декабря 2000 г.
Исправленный вариант — 6 марта 2001 г.