close

Вход

Забыли?

вход по аккаунту

?

ДОСТАТОЧНЫЕ УСЛОВИЯ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫМИ СХЕМАМИ С НЕНАДЕЖНОСТЬЮ 2t.

код для вставкиСкачать
Известия вузов. Математика
2010, № 5, c. 79–82
http://www.ksu.ru/journals/izv_vuz/
Гос. номер статьи по НТЦ "Информрегистр" 0421000123 \0049
М.А. АЛЕХИНА, А.В. ВАСИН
ДОСТАТОЧНЫЕ УСЛОВИЯ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫМИ СХЕМАМИ
С НЕНАДЕЖНОСТЬЮ 2ε
Аннотация. Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B. Предполагается, что все элементы схемы
независимо друг от друга с вероятностью ε (ε ∈ (0; 1/2)) подвержены инверсным неисправностям на выходах.
Найдены булевы функции ϕ(x1 , x2 , x3 ), наличие хотя бы одной из которых в рассматриваемом базисе B достаточно для реализации всех булевых функций схемами, функционирующими с ненадежностью не больше 2ε + 144ε2 при ε ≤ 1/960. Кроме того, если B ⊂ B3 \ G (B3
— множество всех булевых функций, зависящих от трех переменных x1 , x2 , x3 , G — множество булевых функций, каждая из которых конгруэнтна либо xσ1 1 xσ2 2 ∨ xσ1 1 xσ3 3 ∨ xσ2 2 xσ3 3 , либо
xσ1 1 xσ2 2 ⊕ xσ3 3 , либо xσ1 1 x2σ2 ∨ xσ2 2 xσ3 3 (σ1 , σ2 , σ3 ∈ {0, 1})), то наличие хотя бы одной из функций ϕ(x1 , x2 , x3 ) достаточно для реализации почти всех булевых функций асимптотически
оптимальными по надежности схемами, функционирующими с ненадежностью 2ε при ε → 0.
Ключевые слова: ненадежные функциональные элементы, асимптотически оптимальные по
надежности схемы, инверсные неисправности на выходах элементов, синтез схем из ненадежных элементов.
УДК: 519.718
Abstract. We consider realizations of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis B. We assume that all elements independently of
each other with the probability ε (ε ∈ (0; 1/2)) are subjected to inverse failures at the output.
We construct Boolean functions ϕ(x1 , x2 , x3 ) such that the presence of at least one of them in the
considered basis B guarantees the realizability of all three Boolean functions by circuits whose
reliability does not exceed 2ε + 144ε2 with ε ≤ 1/960. In addition, if B ⊂ B3 \ G (B3 is the set of
all Boolean functions of three variables x1 , x2 , and x3 , and G is the set of Boolean functions such
that each one of them is congruent either to xσ1 1 xσ2 2 ∨ xσ1 1 xσ3 3 ∨ xσ2 2 xσ3 3 , or to xσ1 1 xσ2 2 ⊕ xσ3 3 , or to
xσ1 1 x2σ2 ∨ xσ2 2 xσ3 3 (σ1 , σ2 , σ3 ∈ {0, 1})), then the presence of at least one of functions ϕ(x1 , x2 , x3 )
guarantees the realizability of almost all Boolean functions by asymptotically optimal (with respect
to the reliability) circuits, whose unreliability equals 2ε with ε → 0.
Keywords: unreliable functional elements, circuits asymptotically optimal with respect to reliability, inverse failures on outputs of elements, synthesis of circuits composed of unreliable elements.
Рассматривается реализация булевых функций схемами из ненадежных функциональных
элементов в произвольном полном конечном базисе B. Предполагается, что все элементы
Поступила 10.11.2009
79
80
М.А. АЛЕХИНА, А.В. ВАСИН
схемы независимо друг от друга с вероятностью ε (ε ∈ (0; 1/2)) подвержены инверсным
неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном
состоянии функциональный элемент реализует приписанную ему булеву функцию e, а в
неисправном — функцию e.
Считаем, что схема S из ненадежных элементов реализует булеву функцию f (x1 , . . . , xn ),
если при поступлении на входы схемы набора a = (a1 , . . . , an ) при отсутствии неисправa) вероностей в схеме на ее выходе появляется значение f (
a). Обозначим через Pf (a) (S, ятность ошибки на входном наборе a схемы S, реализующей функцию f . Число P (S) =
a) назовем ненадежностью схемы S. Надежность схемы S равна 1 − P (S).
max Pf (a) (S, a
Пусть Pε (f ) = inf P (S), где ε — вероятность инверсной неисправности на выходе одного
S
элемента, а инфимум берется по всем схемам S из ненадежных элементов, реализующим
функцию f (x1 , x2 , . . . , xn ). Схема A из ненадежных элементов, реализующая функцию f ,
называется асимптотически оптимальной по надежности, если P (A) ∼ Pε (f ) при ε → 0, т. е.
(f )
= 1.
lim PPε(A)
ε→0
В работах [1] и [2] выделено множество функций G = G1 ∪ G2 ∪ G3 , зависящих от переменных x1 , x2 , x3 , где G1 — множество функций конгруэнтных функциям xσ1 1 xσ2 2 ∨ xσ1 1 xσ3 3 ∨
xσ2 2 xσ3 3 , G2 — множество функций, конгруэнтных функциям xσ1 1 xσ2 2 ⊕ xσ3 3 , G3 — множество
функций конгруэнтных функциям xσ1 1 xσ2 2 ∨ xσ2 2 xσ3 3 , где σ1 , σ2 , σ3 ∈ {0, 1}. Множество G
содержит пятьдесят шесть функций. В [3] найдено множество G4 функций, зависящих от
переменных x1 , x2 , x3 , x4 и конгруэнтных функциям xσ1 1 xσ2 2 ∨xσ3 3 xσ4 4 или (xσ1 1 ∨xσ2 2 )(xσ3 1 ∨xσ4 4 ).
Наличие в базисе любой из этих функций достаточно для того, чтобы произвольную булеву
функцию можно было реализовать схемой с ненадежностью, асимптотически равной ε, где
ε — вероятность инверсной неисправности на выходе одного элемента в схеме.
Теорема 1 ([4]). Допустим, что любую функцию можно реализовать схемой с ненадежностью не больше p (p ≤ 1/2). Пусть схема Sg реализует функцию g ∈ G1 ∪ G4
с ненадежностью P (Sg ), причем v 1 и v 0 — вероятности ошибок схемы Sg на наборах
(σ 1 , σ 2 , σ 3 ) и (σ1 , σ2 , σ3 ) соответственно, если g зависит от трех переменных, и на наборах (σ 1 , σ 2 , σ 3 , σ 4 ) и (σ1 , σ2 , σ3 , σ4 ) соответственно, если g зависит от четырех переменных. Тогда произвольную функцию f (x1 , . . . , xn ) можно реализовать такой схемой S, что
P (S) ≤ max{v 0 , v 1 } + 3pP (Sg ) + 3p2 , если g ∈ G1 , и P (S) ≤ max{v 0 , v 1 } + 4pP (Sg ) + 6p2 ,
если g ∈ G4 .
Пусть M1 — множество функций, конгруэнтных функциям xσ1 1 xσ2 2 ∨ xσ1 1 xσ2 2 xσ3 3 , M2 —
множество функций, конгруэнтных функциям xσ1 1 xσ2 2 xσ3 3 ∨ xσ1 1 xσ2 2 xσ3 3 ∨ xσ1 1 xσ2 2 xσ3 3 , M3 —
множество функций, конгруэнтных функциям x1 (xσ2 2 ∨ xσ3 3 ), M4 — множество функций,
конгруэнтных функциям xσ1 1 xσ2 2 xσ3 3 ∨ xσ1 1 xσ2 2 xσ3 3 , где σ1 , σ2 , σ3 ∈ {0, 1}, а также множества
M1∗ , M2∗ , M3∗ , M4∗ — множества функций, двойственных соответственно функциям множеств
M1 , M2 , M3 , M4 .
4
(Mi ∪ Mi∗ ) содержит ровно девяносто восемь функций.
Множество M =
i=1
Лемма 1. Пусть ϕ(x1 , x2 , x3 ) ∈ B ∩ M . Если ϕ или ϕ∗ равна x1 x2 x3 ⊕ x1 x2 ⊕ x2 x3 ⊕ x1 x3 ,
то функцию g(x1 , x2 , x3 ) ∈ G1 можно реализовать схемой Sg c ненадежностью P (Sg ) ≤
2ε + 28ε2 . В остальных случаях функцию g ∈ G ∪ G4 можно реализовать схемой Sg c
ненадежностью P (Sg ) ≤ 2ε.
О РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫМИ СХЕМАМИ 81
Для доказательства в каждом возможном варианте для функции ϕ(x1 , x2 , x3 ) построим
схему, удовлетворяющую условиям леммы.
Лемма 2. Пусть схема Sφ реализует функцию φ ∈ G2 ∪ G3 с ненадежностью P (Sφ ) = pφ .
Тогда можно построить такую схему Sg , реализующую функцию g = xσ1 1 xσ2 2 ∨ xσ1 1 xσ3 3 ∨
xσ2 2 xσ3 3 ∈ G1 , что
1) P (Sg ) ≤ pφ +2p⊕ (p⊕ — максимальная из ненадежностей схем, реализующих функции
x1 ⊕ x2 и x1 ⊕ x2 ⊕ 1), а v 1 , v 0 ≤ pφ + 2pφ p⊕ + p2⊕ , если φ ∈ G2 ;
2) P (Sg ) ≤ 2pφ , а v 1 = v 0 ≤ pφ , если φ ∈ G3 .
Теорема 2. Пусть ε ≤ 1/960, B — базис такой, что M ∩ B = ∅. Тогда любую булеву
функцию f (x1 , x2 , . . . , xn ) в базисе B можно реализовать такой схемой S, что P (S) ≤
2ε + 144ε2 .
Доказательство теоремы 2 проводится с использованием теоремы 1 и лемм 1–2.
Обозначим через B3 множество всех функций, зависящих от переменных x1 , x2 , x3 , через
B3 \ G — множество всех булевых функций, зависящих от переменных x1 , x2 , x3 , исключая
функции множества G.
Пусть K(n) — множество булевых функций f (x1 , x2 , . . . , xn ), не представимых в виде
x))b или (xai &xbj ∨xai &xbj &h(
x))c , где h(
x) — произвольная функция, i, j ∈ {1, 2, . . . , n},
(xai &h(
n−1
n−2
+ (n2 − n) · 22 ). Поэтому
a, b, c ∈ {0, 1}. Нетрудно видеть, что |P2 (n) \ K(n)| ≤ 4 · (n22
n
n−1
n−2
+ (n2 − n) · 22 ).
|K(n)| ≥ 22 − 4 · (n · 22
Теорема 3 ([2]). Пусть ε ≤ 1/4, функция f (
x) ∈ K(n), и S — любая схема в базисе B3 \G,
реализующая функцию f . Тогда P (S) ≥ 2ε − 2ε2 .
x) ∈ K(n) и S — любая
Следствие. Пусть B ⊂ B3 \ G — базис, B ∩ M = ∅, ε ≤ 1/4, f (
схема в базисе B, реализующая функцию f . Тогда P (S) ≥ 2ε − 2ε2 .
Доказательство вытекает из теоремы 3, поскольку B ⊂ B3 \ G.
Таким образом
(1) из теоремы 2 следует, что если в произвольном полном конечном базисе B содержится функция из множества M , то в этом базисе любую булеву функцию можно
реализовать схемой S, ненадежность которой не больше 2ε + 144ε2 при ε ≤ 1/960;
(2) из теоремы 2 и следствия следует, что если B — базис такой, что B ⊂ B3 \ G и
→1
B ∩ M = ∅, то в базисе B для почти всех булевых функций (поскольку |K(n)|
n
22
с ростом n) асимптотически оптимальные по надежности схемы функционируют с
ненадежностью, асимптотически равной 2ε при ε → 0.
Литература
[1] Васин А.В. О функциях специального вида // Тр. VIII международн. конф. “Дискретные модели в
теории управляющих систем”. – М.: МАКС Пресс, 2009. – C. 43–46.
[2] Алехина М.А., Васин А.В. О надежности схем в базисах, содержащих функции не более чем трех
переменных // Учен. зап. Казанск. ун-та. Сер. физ.-матем. науки. – 2009. – T. 151. – Кн. 2. – C. 25–36.
[3] Аксенов С.И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Изв. вузов. Поволжский регион. Естествен. науки. – 2005. – № 6.
– C. 42–55.
[4] Алехина М.А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов.
– Пенза: ИИЦ ПГУ, 2006. – 157 c.
[5] Алехина М.А., Пичугина П.Г. О надежности двойственных схем в полном конечном базисе // Материалы XIII Международн. школы-семинара “Синтез и сложность управляющих систем”. – М.: Изд-во
мех.-мат. ф-та МГУ, 2009. – C. 10–13.
82
М.А. АЛЕХИНА, А.В. ВАСИН
М.А. Алехина
доцент, заведующий кафедрой дискретной математики,
Пензенский государственный университет,
ул. Красная, д. 40. г. Пенза, 440026,
e-mail: alehina@pnzgu.ru
А.В. Васин
аспирант, кафедра дискретной математики,
Пензенский государственный университет,
ул. Красная, д. 40. г. Пенза, 440026,
e-mail: alvarvasin@mail.ru
M.A. Alekhina
Associate Professor, Head of the Chair of Discrete Mathematics,
Penza State University,
40 Krasnaya str., Penza, 440026, Russia,
e-mail: alehina@pnzgu.ru
A.V. Vasin
Postgraduate, Chair of Discrete Mathematics,
Penza State University,
40 Krasnaya str., Penza, 440026, Russia,
e-mail: alvarvasin@mail.ru
Документ
Категория
Без категории
Просмотров
3
Размер файла
139 Кб
Теги
асимптотическое, условия, достаточно, булевых, функции, схемами, ненадежности, реализации, оптимальный
1/--страниц
Пожаловаться на содержимое документа