List decoding of wavelet codes

D. V. Litichevskii

Chelyabinsk State University, ul. Brat’ev Kashirinykh, 129, Chelyabinsk, 454001, Russia

Abstract: This paper discusses the possibility of list decoding of wavelet codes and states that wavelet codes over the field $GF(q)$ of an odd characteristic with the length of the code and information words $n=q-1$ and $\frac{n}{2} $, respectively, as well as over the field of an even characteristic with the length of the code and information words $n=q-1$ and $\frac{n-1}{2}$, respectively, allow list decoding if among the coefficients of the spectral representation of the polynomials generating them there are $d + 1$ consecutive zeros, $0 <d <\frac{n}{2}$ for fields of the odd characteristic and $0 <d < \frac{n-3}{2}$ for fields of the even characteristic. Also, a description is given of an algorithm that allows one to perform list decoding of wavelet codes subject to the listed conditions. As a demonstration of the operation of this algorithm, step-by-step solutions for model problems of list decoding of noisy wavelet code words over fields of even and odd characteristics are given. In addition, a wavelet version of Golay's quasi-perfect ternary code is constructed. The lengths of its code and information words are $8$ and $4$, respectively, the code distance is $4$, the minimum radius of balls with centers in code words covering the space of words of length $8$ is $3$.

Keywords: wavelet codes, polyphase coding, list decoding.

UDC: 519.725

MSC: 12Y05, 94B05, 94B60, 94B35

Received: 07.04.2019

DOI: 10.20537/2226-3594-2019-53-10

Bibliographic databases:

• 
•