Abstract:
In this paper, we consider wavelet code defined over the field $\mathrm{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-\sqrt{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}$.
Keywords:wavelet codes, polyphase coding, list decoding.
Fulltext:
PDF file (601 kB)