On list decoding of wavelet codes over finite fields of characteristic two | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/7

In this paper, we consider wavelet code defined over the field GF(2^m ) with the code length n = 2^m - 1 and information words length (n - 1)/2 and prove that a wavelet code allows list decoding in polynomial time if there are d + 1 consecutive zeros among the coefficients of the spectral representation of its generating polynomial and 0 < d < < (n - 3)/2. The steps of the algorithm that performs list decoding with correction up to e < n - д/n(n - d - 2) errors are implemented as a program. Examples of its use for list decoding of noisy code words are given. It is also noted that the Varshamov - Hilbert inequality for sufficiently large n does not allow to judge about the existence of wavelet codes with a maximum code distance (n - 1)/2.