РУАЭСТ (RUAEST)
СИНТЕЗ И СЛОЖНОСТЬ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ КЛЕТОЧНЫХ СХЕМ
Актуальность и цели. Работа относится к одному из важнейших разделов математической кибернетики – теории синтеза, надежности и сложности управляющих систем. Хорошо известны такие модели вычисления дискретных функций, как схемы из функциональных элементов. Эти схемы как из абсолютно надежных, так и ненадежных элементов изучаются давно, для них получено большое число результатов. Однако в реальных схемах приходится учитывать не только функционирование элементов, но и геометрию схемы. В связи с этим была предложена модель клеточных схем из функциональных элементов, где схема представляется в виде прямоугольника, разделенного на клетки, в которых располагаются элементы схемы, имеющие определенные размеры и занимающие некоторую площадь. Клеточные элементы могут быть как функциональными, т.е. реализующими какую-то функцию от своих входов, так и коммутационными, которые служат для передачи сигнала к следующему элементу с возможным изменением направления. В работе предполагается, что коммутационные элементы абсолютно надежны, а на любом из двух выходов каждого из функциональных элементов с одной и той же вероятностью независимым образом появляются инверсные неисправности. Такие схемы являются естественной математической моделью интегральных схем, в связи с чем имеют множество приложений в различных разделах науки и техники и являются актуальными для исследований. Цель работы – построить асимптотически оптимальные по надежности клеточные схемы и оценить их сложность Материалы и методы. Для построения асимптотически оптимальных по надежности клеточных схем использован метод, в основе которого лежит метод синтеза асимптотически оптимальных по надежности схем из функциональных элементов. Для этого метода были построены клеточные схемы, доказаны соответствующие теоремы о верхней и нижней оценках ненадежности и оценена сложность построенных схем. Результаты. Предложен метод синтеза асимптотически оптимальных по надежности клеточных схем. Получены верхняя и нижняя оценки ненадежности этих схем. Впервые доказана оценка сложности асимптотически оптимальных по надежности клеточных схем. Выводы. Для построения асимптотически оптимальных по надежности клеточных схем можно использовать методы синтеза асимптотически оптимальных по надежности схем из функциональных элементов.