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

Предложен рекурсивный алгоритм декодирования двоичного кода, который определяется как подмножество слоев кода Рида – Маллера первого порядка, задаваемое линейными булевыми функциями от $n$ переменных фиксированного веса $r$ (число существенных переменных $r$). Показано, что сложность декодирования названных подмножеств кодовых слов оценивается величиной $(r+1)\cdot 2^n$ операций типа сложения двух чисел, что улучшает известную ранее оценку $(2r+1)\cdot 2^n$ [1]. Предложенный алгоритм для случая декодирования указанных подмножеств четных (нечетных) весов $r$ имеет сложность $n2^{n-1}$.