List decoding of the biorthogonal wavelet code with predetermined code distance on a~field of odd characteristic

D. V. Litichevskiy

Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 72-77

Résumé

In the article, a list decoding algorithm for the biorthogonal wavelet codes $W[n,n/2,d]$ with a predetermined code distance on a field of odd characteristic is presented. The “list decoding” problem the algorithm solves is the following: given an input message of the length $n$, compute all the codewords the Hamming distance to which does not exceed the given value. The list decoding algorithm for the code $W[n,n/2,d]$ is based on the transformation of the list decoding problem for $W[n,n/2,d]$ to the list decoding problem for the Reed–Solomon code $\mathrm{RS}[n,n-d+1]$ by proper converting the incoming messages and on the subsequent solution of the second problem by the improved Guruswami–Sudan algorithm. Decoding results for the code $W[n,n/2,d]$ are found by solving a system of linear equations with respect to the coefficients of the information polynomial. The system is obtained from the Fourier transform of the code word of the wavelet code for each found information word of the code $\mathrm{RS}[n,n-d+1]$. In the system, the symbols of this word are constant terms. Examples of the list decoding for the code $W[26,13,12]$ are given. The algorithm has been implemented in the form of a computer program for which an author's certificate has been received.

Détail

Mots-clés : wavelet codes
Keywords: code with predetermined code distance, list decoding.