RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Казанского университета. Серия Физико-математические науки // Архив

Учён. зап. Казан. гос. ун-та. Сер. Физ.-матем. науки, 2009, том 151, книга 2, страницы 154–163 (Mi uzku758)

Пятнадцатая международная конференция "Проблемы теоретической кибернетики"

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

В. В. Чугунова

Кафедра дискретной математики Пензенского государственного университета

Аннотация: Рассмотрена реализация булевых функций схемами из ненадежных функциональных элементов, подверженных инверсным неисправностям на входах с вероятностью ошибки $\varepsilon$, $0<\varepsilon<1/2,$ на каждом входе функционального элемента. Показано, что если к каждому из неприводимых полных базисов, содержащих функции, зависящие не более чем от двух переменных, добавить функцию голосования, то во всех полученных базисах оценка ненадежности асимптотически оптимальных по надежности схем равна $3\varepsilon^2$ (при $\varepsilon\to0$) для всех булевых функций $f(x_1,x_2,\dots,x_n)$, за исключением констант 0, 1 и функций $x_i$, $\overline x_i$, где $i=1,\dots,n$.

Ключевые слова: булевы функции, асимптотически оптимальные по надежности схемы.

УДК: 519.718

Поступила в редакцию: 21.02.2009



© МИАН, 2024