О длине, высоте и надёжности схем, реализующих функции выбора v 2i

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

любую булеву функцию можно реализовать неветвящейся программой при константных неисправностях типа 1 (0) на выходах вычислительных операторов с ненадёжностью не больше 802 при всех е Е (0,1/960].
В качестве сравнения, для схем из ФЭ известно [2], что в произвольном полном конечном базисе любую булеву функцию f можно реализовать схемой из ФЭ при тех же типах неисправностей с ненадёжностью не больше 3е + 100е2 при всех е Е Е (0,1/960]. Однако в некоторых базисах данную верхнюю оценку можно улучшить. Например, в базисе {х1Ух2, Х^ она составляет 2е+42е2 при всех е Е (0,1/140]- в базисе |ж1& amp-ж2, х1 ~ х2} имеем е + 6е2 при всех е Е (0,1/320]. Заметим, что для неветвящихся программ без стоп-операторов (см. замечание 1) 8 = п = 0, следовательно, ^ = е. Тогда верхняя оценка ненадёжности таких программ составляет е + 78е2 при всех е Е (0,1/960], а в некоторых базисах 80е2, что в общем случае лучше, чем для схем из ФЭ.
ЛИТЕРАТУРА
1. Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискретный анализ и исследование операций. 1997. Т. 4. № 1. С. 60−78.
2. Алехина М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов. Пенза: ИИЦ ПГУ, 2006.
3. Алехина М. А., Грабовская С. М. Асимптотически оптимальные по надежности неветвя-щиеся программы с оператором условной остановки. Пенза: ИИЦ ПГУ, 2013.
4. Редькин Н. П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. 1989. Вып. 2. С. 198−222.
УДК 519. 718 Б01 10. 17 223/2226308X78/41
О ДЛИНЕ, ВЫСОТЕ И НАДЁЖНОСТИ СХЕМ, РЕАЛИЗУЮЩИХ ФУНКЦИИ ВЫБОРА ^
А. В. Рыбаков
Рассматриваются клеточные (плоские) схемы, реализующие функции выбора г& gt-2г. Предполагается, что коммутационные элементы абсолютно надёжны, а функциональные подвержены инверсным неисправностям на выходах, причём переходят в неисправные состояния независимо друг от друга. Найдены соотношения для длины и высоты, а также получена оценка ненадёжности таких схем.
Ключевые слова: булевы функции, клеточные (плоские) схемы, инверсные неисправности функциональных элементов, ненадёжность схемы, функция выбора.
Впервые задачу синтеза надёжных схем из ненадёжных функциональных элементов рассматривал Дж. фон Нейман. Он предполагал, что все элементы схемы независимо друг от друга с вероятностью е Е (0- ½) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию ф, а в неисправном — функцию ф. С помощью итерационного метода Дж. фон Нейман установил [1], что в произвольном полном базисе при е Е (0- 1/6] любую булеву функцию можно реализовать схемой, вероятность ошибки, на выходе которой при любом
1 Работа поддержана грантом РФФИ, проект № 14−01−31 360.
Математические основы надёжности вычислительных и управляющих систем
109
входном наборе значений переменных не превосходит ее (е — некоторая положительная константа, зависящая от базиса). Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах [2, 3] и некоторых других, причём главное внимание уделялось сложности надёжных схем.
Асимптотически оптимальные по надёжности схемы из функциональных элементов, реализующие булевы функции, в базисе {ж1& amp-ж2,ж1 V Ж2, Ж1} при инверсных неисправностях на выходах элементов построены в работе [4], а в [5] доказано, что сложность таких схем превышает сложность схем, построенных из абсолютно надёжных элементов, асимптотически не более чем в 3 раза.
В работе [6] впервые предложен класс клеточных схем (КС- ещё их называют плоскими схемами). В [7] получены оценки сложности КС в предположении, что все элементы схемы абсолютно надёжны, а в [8] рассмотрена задача построения клеточных схем из надёжных коммутационных и ненадёжных функциональных элементов, реализующих произвольные булевы функции, и получены оценки ненадёжности и сложности таких схем.
В данной работе рассматриваются клеточные схемы, реализующие функции специального класса, называемые функциями выбора:
г& gt-2г (хьх2,.., Х2г, У0, У1,.. ,^-1) = V К (ж)у|7|,
7

где, а = (а1,…, а2г) — К7(ж) = ж1 … ж^- М = аг22г- (т.е. |а| -число, двоичной
?=1
записью которого является набор а). Поскольку К ((а) обращается в нуль при, а = а и в единицу при, а = а, то при подстановке а1,…, а2^ вместо переменных ж1,…, ж2^ в функцию выбора (ж, а) эта функция обращается в у|а|.
Схемы этих функций используются при построении схем, обладающих достаточно высокой надёжностью.
Как ив [6], предполагается, что базис содержит два типа элементов: функциональные и коммутационные. Каждый из этих элементов может быть повёрнут на плоскости на угол (& amp- = 0,1, 2, 3). Предполагается, что коммутационные элементы абсолют-
но надёжны, а на любом из двух выходов каждого из функциональных элементов с вероятностью е Е (0- ½) независимым образом появляются инверсные неисправности. Считаем, что КС, содержащая ненадёжные элементы, реализует булеву функцию f (жп) (жп = (ж1,…, жп)), если она реализует f (жп) при отсутствии неисправностей. Пусть К С 5 реализует функцию f (жп). Обозначим через Рда^у (Б, ап) вероятность появления ошибки на входном наборе ап схемы Б. Ненадёжность Р (Б) клеточной схемы Б определяется как максимальная вероятность ошибки на выходе схемы при всевозможных входных наборах схемы (т. е. так же, как и для схемы из функциональных элементов). Надёжность схемы Б равна 1 — Р (Б).
Обозначим / (Б) длину клеточной схемы Б, к (Б) -её высоту. Тогда сложность Ь (Б) клеточной схемы равна её площади (Ь (Б) = /(Б)к (Б)) и числу элементов в ней.
Возьмём три экземпляра схемы Б и соединим их выходы со входами схемы, реализующей функцию голосования ж1ж2 Vж1ж3 Vж2ж3. Построенную схему обозначим ^(Б). Схема ^(Б) используется для повышения надёжности исходных схем.
Теорема 1. Функция выбора ^2(ж1,ж2,у0,у1,у2,у3) может быть реализована схемой V длины / = 6 и высоты к =10.
Теорема 2. Функцию выбора v2i можно реализовать схемой, длина которой 1(V2i) = 7 ¦ 22(i-1) + 2i — 3, а высота = ВД («-1)) + 4 + 2i + 22(i-1), где ВД («-1)) —
высота схемы V2(i-1), реализующей функцию выбора v2(i-1).
Для длины, ширины и ненадёжности схемы ^(V2i), реализующей функцию выбора v2i, справедливы следующие соотношения.
Теорема 3. /(^(V*)) = 21 ¦ 22(i-1) + 6i — 2, h (^(V& gt-i)) = 22i/3 + 2i2 + 13i — 13/3, P (^(V2i)) ^ 8e, e G (0- 1/200].
Заметим, что нетрудно найти сложность схемы ^(V2i) из теоремы 3 (для этого достаточно умножить длину на ширину).
ЛИТЕРАТУРА
1. Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata Studies. C. Shannon, J. Mc. Carthy (eds). Princeton University Press, 1956. (Рус. пер.: Автоматы. М.: ИЛ, 1956. С. 68−139.)
2. Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и её приложениям (Москва, 27−29 января 1987 г.). М.: Изд-во МГУ, 1989. С. 166−168.
3. Uhlig D. Reliable networks from unreliable gates with almost minimal complexity // LNCS. 1987. V. 278. P. 462−469.
4. Васин А. В. Об асимптотически оптимальных схемах в базисе {& amp-, V,~} при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2008. № 4. С. 3−17.
5. Алехина М. А., Аксенов С. И. О сложности надежных схем при инверсных неисправностях // Материалы IX Междунар. семинара «Дискретная математика и её приложения», посвящённого 75-летию со дня рождения О. Б. Лупанова (Москва, 18−23 июня 2007 г.). М.: Изд-во мех. -мат. фак-та МГУ, 2007. С. 56−59.
6. Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. 1967. Вып. 19. С. 285−292.
7. Улесова А. Ю. Сложность реализации булевых функций в некоторых моделях клеточных схем: дипломная работа. М.: МГУ им. Ломоносова, фак-т ВМиК, каф. математической кибернетики, 2010.
8. Рыбаков А. В. Сложность асимптотически оптимальных по надежности клеточных схем // Сб. статей XVIII Междунар. науч. -методич. конф. «Университетское образование (МКУО-2014)», Пенза, 10−11 апреля 2014 г. Пенза: Изд-во Пенз. ун-та, 2014. С. 310−311.

ПоказатьСвернуть
Заполнить форму текущей работой