Размерность адамаровой алгебры делится на 4 // Успехи матем. наук. <...> Ортогональные разложения ассоциативных алгебр и сбалансированные системы идемпотентов // Maтем. сб. <...> Поступила в редакцию 10.09.2010 УДК 519.714 О МИНИМАЛЬНЫХ ПАРАЛЛЕЛЬНЫХ ПРЕФИКСНЫХ СХЕМАХ И. С. <...> Сергеев1 Найдено точное значение сложности минимальной префиксной схемы m переменных глубины log2m в случае, когда m является степенью двойки. <...> Получены новые верхние оценки сложности префиксных схем при различных ограничениях на глубину и отдельно для случая схем с операцией сложения по модулю 2. <...> New upper bounds for the complexity of prefix circuits are obtained under various depth restrictions and separately for the circuits of XOR-gates. <...> Пусть ◦ — бинарная ассоциативная операция на некотором множестве. <...> Множество функx1 ◦ . ◦ xk,k =1,.,m, (1) называется системой префиксов (или префиксных сумм) упорядоченного набора переменных x1,. ,xm. <...> Схемы из функциональных элементов над базисом {◦}, реализующие систему (1), называют префиксными схемами. <...> Число m (входов схемы) будем называть порядком схемы. <...> В ряде вычислительных и схемотехнических задач (некоторые из них приведены в [1]) возникает необходимость в построении параллельных префиксных схем, т.е. имеющих глубину по порядку log2m. <...> В настоящей работе рассматривается вопрос минимизации сложности префиксных схем при заданном ограничении на глубину. <...> Обозначим через L(m) сложность минимальной префиксной схемы порядка m и глубины log2m (это наименьшее возможное значение глубины). <...> В работе [4] доказана нетривиальная нижняя оценка и уточнена верхняя: Нижняя оценка относится к универсальной префиксной схеме, т.е. не зависящей от вида операции ◦. <...> В работах [3, 4] также строилось семейство префиксных схем не минимальной глубины, но таких, в которых максимальный префикс (сумма всех входов) реализуется на наименьшей возможной глубине. <...> Обозначим через Πm,k множество префиксных схем глубины log2m + k, реализующих максимальный префикс с глубиной log2m, и через L(m,k) — сложность минимальной схемы <...>