Geodesic
List decoding of the biorthogonal wavelet code with predetermined code distance on a field of odd characteristic
Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 72-77
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Mots-clés : wavelet codes
Keywords: code with predetermined code distance, list decoding. 
@article{PDM_2018_1_a5,
     author = {D. V. Litichevskiy},
     title = {List decoding of the biorthogonal wavelet code with predetermined code distance on a~field of odd characteristic},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {72--77},
     year = {2018},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_1_a5/}
}
TY  - JOUR
AU  - D. V. Litichevskiy
TI  - List decoding of the biorthogonal wavelet code with predetermined code distance on a field of odd characteristic
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 72
EP  - 77
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_1_a5/
LA  - ru
ID  - PDM_2018_1_a5
ER  - 
%0 Journal Article
%A D. V. Litichevskiy
%T List decoding of the biorthogonal wavelet code with predetermined code distance on a field of odd characteristic
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 72-77
%N 1
%U http://geodesic.mathdoc.fr/item/PDM_2018_1_a5/
%G ru
%F PDM_2018_1_a5
D. V. Litichevskiy. List decoding of the biorthogonal wavelet code with predetermined code distance on a field of odd characteristic. Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 72-77. http://geodesic.mathdoc.fr/item/PDM_2018_1_a5/

[1] Guruswami V., Sudan M., Improved Decoding of Reed–Solomon and Algebraic-Geometric Codes, Electronic Colloquium on Computational Complexity. Report No. 43, 1998

[2] Soloviev A. A., Chernikov D. V., “Biorthogonal wavelet codes with predetermined code distance”, Diskr. Mat., 29:2 (2017), 96–108 (in Russian) | DOI

[3] Ruth R., Ruckenstein G., “Efficient decoding of Reed–Solomon codes beyond half the minimum distance”, IEEE Trans. Inform. Theory, 46:1 (2000), 246–257 | DOI | MR

[4] McEliece R. J., The Guruswami–Sudan Decoding Algorithm for Reed–Solomon Codes, IPN Progress Report 42-153, May 15, 2003

[5] Chernikov D. V., “Polyphase scheme of noise-immune encoding over fields of odd characteristic”, Chelyab. Fiz.-Mat. Zh., 1:3 (2016), 77–85 (in Russian) | MR