Передача сообщений в неисправных гиперкубах с использованием исправных подкубов

Известно [1], что двоичный $n$-мерный гиперкуб является топологической моделью представления булевых функций $n$ переменных, и, с другой стороны, – моделью структуры связей ряда многопроцессорных вычислительных систем. Здесь предполагается, что вершины гиперкуба соответствуют процессорным элементам вычислительной системы, а ребра – связям между процессорными элементами. Неисправными могут быть как процессорные элементы (вершины гиперкуба), так и связи между ними (ребра гиперкуба). Если неисправные вершины гиперкуба сопоставить нулевым значениям полностью определенной булевой функции, то простые импликанты [1] последней будут соответствовать исправным простым подкубам гиперкуба, т.е. подкубам, которые не содержат неисправных вершин и (или) ребер и сами не содержатся целиком в других исправных простых подкубах.
В статье представлен алгоритм получения простых импликантов, использующий список запрещенных наборов значений входных переменных функции, т.е. входных наборов, на которых функция принимает нулевые значения (список двоичных номеров неисправных вершин гиперкуба). Этим алгоритм отличается от широко известного в булевой алгебре алгоритма [2], работающего с рабочими входными наборами, т.е. наборами, на которых функция принимает единичные значения. Приведено расширение алгоритма [2], позволяющее работать с неисправными ребрами гиперкуба.
Основным в статье является алгоритм организации проходящих через исправные простые подкубы путей передачи сообщений между парами исправных вершин гиперкуба, одна из которых является отправителем, а другая – получателем сообщения. Пути выбираются по графу, вершины которого представлены простыми импликантами (исправными простыми подкубами), а ребра соединяют пары вершин, пересечения импликантов которых не пустые.