Декодирование кодов Рида–Маллера при большом числе ошибок

Построены новые алгоритмы мягкого декодирования кодов $RM_r$ длины $N=2^n$ $r$-го порядка со сложностью $O(n^{r-1}N^2)$, $r\geq 2$. Эти алгоритмы хотя и имеют несколько большую трудоемкость, чем известные, но почти всегда правильно исправляют искаженное кодовое слово при $r=\mathrm{const}$, $n\to\infty$ и числе ошибок в нем $(1-\varepsilon)N/2$, значительно большем, чем половина его кодового расстояния. Получены оценки для числа почти всегда исправляемых ошибок с помощью предлагаемого алгоритма и корреляционного алгоритма декодирования, работающего по минимуму расстояния. В частности, показано, что при $r=2$ и $n\to\infty$ почти все ошибки кратности $t\leq(N-Cn^{1/4}N^{3/4})/2$, $C>\ln 4$, могут быть исправлены предложенным алгоритмом декодирования. Приведены результаты экспериментов по декодированию кодов $RM_r$ для $r=2,3$ и $N\leq 2^{10}$, из которых вытекает, что предложенные алгоритмы работоспособны при значительно большем числе ошибок, чем известные мажоритарные алгоритмы декодирования этих кодов.