On length, height and reliability of circuits realizing selection function.pdf Впервые задачу синтеза надёжных схем из ненадёжных функциональных элементов рассматривал Дж. фон Нейман. Он предполагал, что все элементы схемы независимо друг от друга с вероятностью е E (0; 1/2) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию ф, а в неисправном - функцию ф. С помощью итерационного метода Дж. фон Нейман установил [1], что в произвольном полном базисе при е E (0; 1/6] любую булеву функцию можно реализовать схемой, вероятность ошибки, на выходе которой при любом входном наборе значений переменных не превосходит ce (c - некоторая положительная константа, зависящая от базиса). Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах [2, 3] и некоторых других, причём главное внимание уделялось сложности надёжных схем. Асимптотически оптимальные по надёжности схемы из функциональных элементов, реализующие булевы функции, в базисе {x1&x2,x1 V x2,X1} при инверсных неисправностях на выходах элементов построены в работе [4], а в [5] доказано, что сложность таких схем превышает сложность схем, построенных из абсолютно надёжных элементов, асимптотически не более чем в 3 раза. В работе [6] впервые предложен класс клеточных схем (КС; ещё их называют плоскими схемами). В [7] получены оценки сложности КС в предположении, что все элементы схемы абсолютно надёжны, а в [8] рассмотрена задача построения клеточных схем из надёжных коммутационных и ненадёжных функциональных элементов, реализующих произвольные булевы функции, и получены оценки ненадёжности и сложности таких схем. В данной работе рассматриваются клеточные схемы, реализующие функции специального класса, называемые функциями выбора: Vn(Xi,X2, . . . ,X2i,yo,yi, . . .,V22i-i) = \/ K (£)У|а|, а 2i где а = (о1,... ,o2i); Ka (ж) = x^1 ...x^f; |а| = Y оi22i-j (т.е. |а| -число, двоичной j=i записью которого является набор а). Поскольку Ka (а) обращается в нуль при а = а и в единицу при а = а, то при подстановке а1,... , a2i вместо переменных x1,... , x2i в функцию выбора v2i (x, y) эта функция обращается в y^. Схемы этих функций используются при построении схем, обладающих достаточно высокой надёжностью. Как ив [6], предполагается, что базис содержит два типа элементов: функциональные и коммутационные. Каждый из этих элементов может быть повёрнут на плоскости на угол kn/2 (k = 0,1, 2, 3). Предполагается, что коммутационные элементы абсолютно надёжны, а на любом из двух выходов каждого из функциональных элементов с вероятностью e G (0; 1/2) независимым образом появляются инверсные неисправности. Считаем, что КС, содержащая ненадёжные элементы, реализует булеву функцию f (Xn) (Xn = (x1,... , xn)), если она реализует f (Xn) при отсутствии неисправностей. Пусть КС S реализует функцию f (Xn). Обозначим через Pf (a„) (S,an) вероятность появления ошибки на входном наборе an схемы S. Ненадёжность P(S) клеточной схемы S определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах схемы (т. е. так же, как и для схемы из функциональных элементов). Надёжность схемы S равна 1 - P(S). Обозначим l(S) длину клеточной схемы S, h(S) -её высоту. Тогда сложность L(S) клеточной схемы равна её площади (L(S) = l(S)h(S)) и числу элементов в ней. Возьмём три экземпляра схемы S и соединим их выходы со входами схемы, реализующей функцию голосования x1x2 Vx1x3 Vx2x3. Построенную схему обозначим ^(S). Схема ^(S) используется для повышения надёжности исходных схем. Теорема 1. Функция выбора v2(x1,x2,yo,y1,y2,y3) может быть реализована схемой V2 длины l = 6 и высоты h =10. Теорема 2. Функцию выбора v2i можно реализовать схемой, длина которой 1(V2i) = 7 ■ 22(i-1) + 2i - 3, а высота h(V>i) = h(V2(i-1)) + 4 + 2i + 22(i-1), где h(V2(i-1)) - высота схемы V2(i-1), реализующей функцию выбора v2(i-1). Для длины, ширины и ненадёжности схемы ^(V2i), реализующей функцию выбора v2i, справедливы следующие соотношения. Теорема 3. /(^(Vk)) = 21 ■ 22(i-1) + 6i - 2, h(^(V2i)) = 22i/3 + 2i2 + 13i - 13/3, PC0(V2i)) ^ 8е, е E (0; 1/200]. Заметим, что нетрудно найти сложность схемы ^(V2i) из теоремы 3 (для этого достаточно умножить длину на ширину).

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