List decoding of wavelet codes

D. V. Litichevskii

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 53 (2019), pp. 115-126.

Résumé

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 $ for fields of the odd characteristic and $0 $ 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$.

Détail

Mots-clés : wavelet codes
Keywords: polyphase coding, list decoding.

Bibliographie

[1] MacWilliams F. J., Sloane N. J. A., The theory of error-correcting codes, North Holland, 1977 | MR | Zbl

[2] Fekri F., McLaughlin S. W., Mersereau R. M., Schafer R. W., “Double circulant self-dual codes using finite-field wavelet transforms”, Proceedings of 13th International Symposium «Applied Algebra, Algebraic Algorithms and Error-Correcting Codes» (AAECC-13) (Honolulu, Hawaii, USA, 1999), 355–363 | DOI | MR

[3] Fekri F., McLaughlin S. W., Mersereau R. M., Schafer R. W., “Decoding of half-rate wavelet codes; Golay code and more”, Proceedings of 2001 IEEE International Conference on Acoustics, Speech and Signal Processing (Salt Lake City, UT, USA, 2001), v. 4, 2609–2612 | DOI

[4] Daubechies I., Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, 1992 | DOI | MR | Zbl

[5] Mallat S., A wavelet tour of signal processing, 2nd edition, Academic Press, 1999 | MR | Zbl

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

[7] Fekri F., Delgosha F., Finite-field wavelet transforms with applications in cryptography and coding, Prentice Hall, Upper Saddle River, 2012

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

[9] Caire G., Grossman R. L., Poor H. V., “Wavelet transforms associated with finite cyclic groups”, IEEE Transactions on Information 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”, Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP99 (Cat. 99CH36258) (Phoenix, AZ, USA, 1999), v. 3, 1999, 1213–1216 | DOI

[11] Soloviev A. A., Chernikov D. V., “Biorthogonal wavelet codes with prescribed code distance”, Discrete Mathematics and Applications, 28:3 (2018), 179–188 | DOI | DOI | MR | Zbl

[12] Doubechies I., Sweldens W., “Factoring wavelet transforms into lifting steps”, Journal of Fourier Analysis and Applications, 4:3 (1998), 247–269 | DOI | MR

[13] Soloviev A. A., Chernikov D. V., “Biorthogonal wavelet code in fields of characteristic two”, Chelyab. Fiz.-Mat. Zh., 2:1 (2017), 66–79 (in Russian) | MR

[14] Berlekamp E. R., Welch L. R., Error correction of algebraic block codes, US Patent Number US4633470A, 30.12.1986 https://patentview.ip-tools.io/api/pdf/US4633470A

[15] Romashchenko A. E., Rumyantsev A. Yu., Shen' A., Notes on the theory of coding, Moscow Center for Continuous Mathematical Education, M., 2011

[16] Tal I., Vardy A., “List decoding of polar codes”, IEEE Transactions on Information Theory, 61:5 (2015), 2213–2226 | DOI | MR | Zbl

[17] Wu Y., “New list decoding algorithms for Reed–Solomon and BCH codes”, Proceedings of 2007 IEEE International Symposium on Information Theory, 2806–2810 | DOI | MR

[18] 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 | DOI | MR

[19] Litichevskiy D. V., “List decoding of wavelet codes”, Modern problems in mathematics and its applications, Abstracts of International (50-th National) Youth School-Conference, Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ural Federal University named after the First President of Russia B. N. Yeltsin, Yekaterinburg, 2019, 18–19 (in Russian)

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

[21] Soloviev A. A., “Complementary representation of polynomials over finite fields”, Chelyab. Fiz.-Mat. Zh., 2:2 (2017), 199–209 (in Russian) | MR