Синтез надежных схем, реализующих функции двухзначной и трехзначной логик

• Автор: Барсукова, Оксана Юрьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Пенза
• Количество страниц: 87 с. : ил.

Оглавление
Введение

Глава 1. Ненадежность схем, реализующих функции трехзначной логики

1.1 Необходимые понятия и вспомогательные утверждения

1.2 Базис Россера - Туркетта

1.2.1 Верхние оценки ненадежности схем

1.2.2 Нижние оценки ненадежности схем

1.2.3 Выводы

1.3 Базис, состоящий из функции Вебба

1.3.1 Верхние оценки ненадежности схем

1.3.2 Нижние оценки ненадежности схем
1.3.3 Выводы
1.4 Произвольный базис
1.4.1 Произвольные неисправности
1.4.2 Инверсные неисправности
1.4.3 Выводы
Глава 2. Ненадежность схем, реализующих булевы функции
2.1 Верхние оценки ненадежности схем
2.2 Нижние оценки ненадежности схем
2.3 Выводы
Заключение
Литература

Введение
Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории надежности управляющих систем.
Задача синтеза управляющих систем является одной из основных задач дискретной математики и математической кибернетики. В современной технике и математике в подавляющем большинстве случаев используется двузначная логика. Это исторически сложившееся положение предопределено ее сравнительной простотой и сделало ее применение предпочтительным (в сравнении с другими логическими системами) с технической и экономической точек зрения. Однако сложность решаемых задач, а, следовательно, и технических устройств, постоянно возрастает. Уже подходят к своему пределу многие технологические возможности, такие как увеличение плотности элементов в схемах, повышение рабочей частоты. Применение многозначной логики является одним из путей решения названных проблем.
К многозначным логикам, к их математическому аппарату как к источнику математических моделей, обладающих большими потенциальными возможностями, обращались в [1,2]. Обзор работ по многозначной логике можно прочесть в [3]. В работе [4] па компромиссной основе согласованы математические и технические (МДП-техншш - от словосочетания металл-диэлектрик-полупроводник) требования и интересы, построен функционально полный в Д базис и рассмотрены некоторые аспекты синтеза электронных схем в этом базисе.
Кроме того, многозначная логика с успехом применяется во множестве технических разработок, среди которых различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т.д. Поэтому актуальна задача построения надежных схем, реализующих как булевы функции, так и функции многозначной логики.
Впервые задачу синтеза надежных схем из ненадежных функциональных элементов рассматривал Дж. фон Нейман [5]. Он предполагал,

что элементы схемы подвержены инверсным неисправностям па выходах, когда функциональный элемент с приписанной ему булевой функцией ср в неисправном состоянии, в которое переходит независимо от других элементов схемы с вероятностью е (е € (0,1/2)), реализует функцию ср. Для повышения надежности исходных схем Дж. фон Нейман использовал схему, реализующую функцию голосования д(хi, х2, х'з) = л 1Ж2 Vхiт3Vтд.г'з (еще эту функцию называют медианой). С помощью итерационного метода Дж. фон Нейман установил, что произвольную булеву функцию f(x,..., хп) (та G N) можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит се при любом е € (0,1/6] (с - некоторая положительная константа).
Таким образом, ненадежность схемы 1) сравнима с ненадежностью одного отдельно взятого элемента (такие схемы в теории надежности принято называть надежными); 2) не зависит от числа та переменных функции. Основной недостаток метода Дж. Фон Неймана в том, что повышение надежности схем сопровождается существенным (по крайней мере логарифмическим) увеличением сложности схем. Затем надежные схемы с инверсными неисправностями на выходах элементов исследовались в работах С. И. Ортюкова [6] , Д. Улига [7] и некоторых других авторов, причем главное внимание уделялось именно сложности схем.
Задачу построения схем, надежность которых близка к максимально высокой надежности (такие схемы называют асимптотически оптимальными по надежности) решали: М.А. Алехина [8] в случае однотипных константных неисправностей только на входах или только на выходах базисных элементов в полных неприводимых базисах из двухвходовых элементов; В.В. Чугунова [9] в случае инверсных неисправностей на входах элементов в полных неприводимых базисах из двухвходовых элементов;
A.B. Васин [lOj в случае инверсных неисправностей на выходах элементов во всех полных базисах, содержащих функции не более, чем трех переменных.
В отличие от названных работ в этой диссертации впервые рассматривается задача построения надежных схем из ненадежных элементов, реализующих функции трехзначной логики (1-ая глава) и функции двухзначной

(1 - 2s)[(l - 2ef + 2s • s] + 2s • s = 1 - 6s + 16s2 - 12s3.
Тогда вероятность появления ошибки на выходе подсхемы D равна Ро — 6s—16s2+12s3. По следствию 1.1 из теоремы 1.1 получаем неравенство P(S) > 6s — 16е2 + 12е3, т. е. утверждение теоремы верно.
Теорема 1.6 доказана.
Следовательно, любая схема, реализующая функцию / £ К функционирует с ненадежностью, которая асимптотически (при е —> 0) не меньше 6с. Это означает, что для функции / £ К схема, удовлетворяющая условиям теоремы 1.5, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 6s при е —ь 0.
1.2.3. Выводы
1. Из теоремы 1.5 следует, что любую функцию из Рз можно реализовать схемой, функционирующей с ненадежностью, асимптотически (при е —> 0) не больше 6е.
2. Из теоремы 1.6 следует, что любую функцию из класса К (содержащего почти все функции из Рз) нельзя реализовать схемой с ненадежностью, асимптотически (при £ —» 0) меньше 6с. Это означает, что для функции / £ К схема, удовлетворяющая условиям теоремы 1.5, является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 6s при е —> 0.
Таким образом, в базисе Россера - Туркетта: 1) любую функцию из Рз можно реализовать схемой, ненадежность которой асимптотически (при £ —¥ 0) не больше 6е; 2) для почти любой функции такая схема является асимптотически оптимальной по надежности и функционирует с ненадежностью, асимптотически равной 6е при е —> 0.
1.3. Базис, состоящий из функции Вебба
Рассмотрим реализацию функций из множества Рз схемами из ненадежных функциональных элементов в базисе, состоящем из функции Вебба Уз(хi,.T2) = max(xi,х2) -f 1 (mod 3) (далее в этом разделе будем считать,