Эта публикация цитируется в
3 статьях
Математика
Оценки ненадежности схем в базисе Россера - Туркетта
М. А. Алехина,
О. Ю. Барсукова Пензенский государственный университет, Пенза
Аннотация:
Актуальность и цель. В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное место. Стоит отметить, что до сих пор рассматривались задачи построения надежных схем, реализующих только булевые функции. В данной работе предложена математическая модель построения асимптотически оптимальных по надежности схем, реализующих функции трехзначной логики. Исследуется задача реализации функций трехзначной логики схемами из ненадежных функциональных элементов в базисе Россера - Туркетта. Предполагается, что все базисные элементы независимо друг от друга переходят в неисправные состояния и любой базисный элемент на любом входном наборе (с вероятностью
$1 - 2\epsilon$) выдает правильное значение и с вероятностью, равной
$\epsilon$, может выдать любое из двух неправильных. Целью данной работы является получение нижних и верхних оценок ненадежности схем и построение асимптотически оптимальных по надежности схем.
Результаты. В результате исследования полученные ранее верхние оценки ненадежности удалось доказать, существенно ослабив ограничения на (ранее эта вероятность зависела от n - числа переменных функции, а в этой работе ее удалось заменить константой). Доказана асимптотическая точность верхних оценок, т.е. в базисе Россера - Туркетта найден класс K функций трехзначной логики такой, что при реализации любой функции из этого класса любой схемой нижняя оценка ненадежности этой схемы будет асимптотически равна верхней оценке ненадежности. Класс описан в явном виде, а также найдена оценка для количества функций, входящих в данный класс.
Выводы. Установлено, что любую функцию трехзначной логики можно реализовать схемой, функционирующей с ненадежностью, асимптотически (при
$\epsilon \rightarrow 0$) не больше
$6\epsilon$. Доказано, что функции класса K (содержащего почти все функции трехзначной логики) нельзя реализовать схемами с ненадежностью, асимптотически (при
$\epsilon \rightarrow 0$) меньше
$6\epsilon$. Таким образом, почти все функции трехзначной логики можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически
$6\epsilon$ равной при
$\epsilon\to 0$.
Ключевые слова:
функции трехзначной логики, схема из функциональных элементов, ненадежность схемы.
УДК:
519.718