Geodesic
On list decoding of wavelet codes over finite fields of~characteristic two
Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 94-106.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. The steps of the algorithm that performs list decoding with correction up to $e$ 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}$.
Mots-clés : wavelet codes
Keywords: polyphase coding, list decoding. 
@article{PDM_2019_2_a6,
     author = {D. V. Litichevskiy},
     title = {On list decoding of wavelet codes over finite fields of~characteristic two},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {94--106},
     publisher = {mathdoc},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_2_a6/}
}
TY  - JOUR
AU  - D. V. Litichevskiy
TI  - On list decoding of wavelet codes over finite fields of~characteristic two
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 94
EP  - 106
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_2_a6/
LA  - ru
ID  - PDM_2019_2_a6
ER  - 
%0 Journal Article
%A D. V. Litichevskiy
%T On list decoding of wavelet codes over finite fields of~characteristic two
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 94-106
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_2_a6/
%G ru
%F PDM_2019_2_a6
D. V. Litichevskiy. On list decoding of wavelet codes over finite fields of~characteristic two. Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 94-106. http://geodesic.mathdoc.fr/item/PDM_2019_2_a6/

[1] MacWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier, 1977, 744 pp. | MR

[2] Fekri F., McLaughlin S. W., Mersereau R. M., Schafer R. W., “Double circulant self-dual codes using finite-field wavelet transforms”, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, Berlin, 1999, 355–363 | DOI | MR

[3] Fekri F., McLaughlin S. W., Mersereau R. M., Schafer R. W., Error Control Coding using Finite-Field Wavelet Transforms, Center for Signal Image Processing, Atlanta, 1999, 13 pp.

[4] Daubechies I., Ten Lectures on Wavelets, SRC “Regular and Chaotic Dynamics”, Izhevsk, 2001, 464 pp. (in Russian)

[5] Mallat S., Wavelet Tour of Signal Processing, 2nd ed., Academic Press, Boston, 1999, 799 pp. | MR | Zbl

[6] Phoong S. M., Vaidyanathan P. P., “Paraunitary filter banks over finite fields”, IEEE Trans. Signal Processing, 45:6 (1997), 1443–1457 | DOI | Zbl

[7] Fekri F., Mersereau R. M., Schafer R. W., “Theory of paraunitary filter banks over fields of characteristic two”, IEEE Trans. Inform. Theory, 48:11 (2002), 2964–2979 | DOI | MR | Zbl

[8] Fekri F., Delgosha F., Finite-Field Wavelet Transforms with Applications in Cryptography and Coding, Prentice Hall, Upper Saddle River, 2010, 304 pp.

[9] Caire G., Grossman R. L., Poor H. V., “Wavelet transforms associated with finite cyclic groups”, IEEE Trans. Inform. Theory, 39:4 (1993), 1157–1166 | DOI | MR | Zbl

[10] Fekri F., Mersereau R. M., Schafer R. W., “Theory of wavelet transform over finite fields”, Proc. IEEE Intern. Conf. Acoustics, Speech, and Signal Processing, 3 (1999), 1213–1216

[11] Chernikov D. V., “Error-correcting codes using biorthogonal filter banks”, Siberian Electronic Mathematical Rep., 12 (2015), 704–713 (in Russian) | Zbl

[12] Doubechies I., Sweldens W., “Factoring wavelet transforms into lifting steps”, J. Fourier Anal. Appl., 4:3 (1998), 247–269 | DOI | MR

[13] Soloviev A. A., Chernikov D. V., “Biorthogonal wavelet codes in the fields of characteristic two”, Chelyabinsk Physics and Mathematics J., 2:1 (2017), 66–79 (in Russian) | MR

[14] Berlekamp E. R., Algebraic Coding Theory, McGraw-Hill Book Company, N.Y., 1968, 470 pp. | MR | Zbl

[15] Sidelnikov V. M., Theory of Coding, Fizmatlit Publ., M., 2008, 324 pp. (in Russian)

[16] Berlekamp E. R., Welch L. R., Error Correction of Algebraic Block Codes, US Patent 4633470A, 30.12.1986

[17] Romashchenko A. E., Rumyantsev A. J., Shen A., Notes on the theory of coding, MCCME Publ., M., 2011, 80 pp. (in Russian)

[18] Sudan M., “Decoding of Reed Solomon codes beyond the error-correction bounds”, J. Complexity, 13:1 (1997), 180–193 | DOI | MR | Zbl

[19] Guruswami V., Sudan M., “Improved decoding of Reed–Solomon and algebraic-geometric codes”, IEEE Trans. Inform. Theory, 45:6 (1999), 1757–1767 | DOI | MR | Zbl

[20] Litichevskiy D. V., “List decoding of the biorthogonal wavelet code with predetermined code distance on a field with odd characteristic”, Prikladnaya Diskretnaya Matematika, 2018, no. 39, 72–77 (in Russian) | MR

[21] Soloviev A. A., “Complementary representation of polynomials over finite fields”, Chelyabinsk Physics and Mathematics J., 2:2 (2017), 199–209 (in Russian) | MR