Метод синтеза надежных клеточных схем с использованием функции выбора

Актуальность и цели. Один из важнейших разделов математической кибернетики - теория синтеза, надежности и сложности управляющих систем. Хорошо известны такие модели вычисления дискретных функций, как схемы из функциональных элементов. Эти схемы как из абсолютно надежных, так и ненадежных элементов изучаются давно, для них получено большое число результатов. Однако в реальных схемах приходится учитывать не только функционирование элементов, но и геометрию схемы. В связи с этим была предложена модель клеточных схем из функциональных элементов, где схема представляется в виде прямоугольника, разделенного на клетки, в которых располагаются элементы схемы, имеющие определенные размеры и занимающие некоторую площадь. Клеточные элементы могут быть как функциональными, т.е. реализующими какую-то функцию от своих входов, так и коммутационными, которые служат для передачи сигнала к следующему элементу с возможным изменением направления. В работе предполагается, что коммутационные элементы абсолютно надежны, а на любом из двух выходов каждого из функциональных элементов с одной и той же вероятностью независимым образом появляются инверсные неисправности. Ранее предлагался метод построения асимптотических оптимальных по надежности клеточных схем, основанный на разложении функции по переменной. Однако схемы, построенные таким образом, обладают слишком высокой сложностью. Цель этой статьи - существенно улучшить оценку сложности для асимптотически оптимальных по надежности клеточных схем. Материалы и методы. Для построения асимптотически оптимальных по надежности клеточных схем используются клеточные схемы, реализующие функции выбора. Показано, как при помощи таких схем реализовать любую булеву функцию от n переменных, а также оценена ненадежность и сложность предлагаемых схем, причем сложность существенно меньше по сравнению с ранее известной. Результаты. Предложен метод синтеза асимптотически оптимальных по надежности клеточных схем с улучшенной сложностью. Получена оценка ненадежности предлагаемых схем. Доказаны теоремы о сложности предлагаемых схем. Вывод. Известная оценка сложности для асимптотически оптимальных по надежности клеточных схем была существенно улучшена.