Быстрое корреляционное декодирование некоторых подмножеств слов кода Рида–Маллера первого порядка

Описывается быстрый корреляционный алгоритм декодирования двоичного кода, который определяется как подмножество слов кода Рида–Маллера первого порядка, задаваемое линейными булевыми функциями от $m$ переменных с фиксированным числом $k$ ненулевых коэффициентов. Показано, что при $k=\mathrm{const}$ и $m\to\infty$ число операций, требуемое для реализации алгоритма декодирования, асимптотически оценивается сверху величиной $(2k+1)2^m$.