zbMATH — the first resource for mathematics

Fast decoding of non-binary first order Reed-Muller codes. (English) Zbl 0858.94027
Summary: A minimum distance decoding algorithm for non-binary first order Reed-Muller codes is described. Suggested decoding is based on a generalization of the fast Hadamard transform to the non-binary case. We also propose a fast decoding algorithm for non-binary first order Reed-Muller codes with complexity proportional to the length of the code. This algorithm provides decoding within the limits guaranteed by the minimum distance of the code.

94B35 Decoding
94B15 Cyclic codes
Full Text: DOI
[1] Ashikhmin, A., Litsyn, S.: Analysis of quasi-optimal decoding algorithms of biorthogonal codes. Radioelectronica,31(11), pp. 30–34 (1988) (in Russian), English translation: Radio Electronics Commun Syst,31(11), 26–30 (1988)
[2] Ashikhmin, A., Litsyn, S.: List algorithm for search of the maximal element of Walsh transform. Radioelectronica,32(11), 15–22 (1990) (in Russian), English translation: Radio Electronics Commun Syst,32(11), 37–41 (1990)
[3] Ashikhmin, A., Litsyn, S.: Fast decoding of first order Reed-Muller and related codes, submitted · Zbl 0858.94027
[4] Be’ery, Y., Snyders, J.: Optimal soft decision block decoders based on fast Hadamard transform, IEEE. Trans. Inf. Theory,IT-32, 355–364 (1986) · Zbl 0594.94020 · doi:10.1109/TIT.1986.1057189
[5] Berlekamp, E. R.: The technology of error-correcting codes, Proc. IEEE68, 564–593 (1980) · doi:10.1109/PROC.1980.11696
[6] Conway, J. H., Sloane, N. J. A.: Sphere Packings, Lattices and Groups, Berlin, Heidelberg, New York: Springer 1988 · Zbl 0634.52002
[7] Delsarte, P., Goethals, J.-M., Mac Williams, F.J.: On generalized Reed-Muller codes and their relatives, Info. Control,16, 403–442 (1974) · Zbl 0267.94014 · doi:10.1016/S0019-9958(70)90214-7
[8] Glassman, J. A.: A generalization of the fast Fourier transform, IEEE Trans., v.C-19(2), (1970) · Zbl 0185.42501
[9] Golomb, S. W. (ed.), Digital communications with space applications. Prentice-Hall, Englewood Cliffs, NJ 1964 · Zbl 0143.41602
[10] Good, I. J.: The Intercation algorithm and practical Fourier analysis, J. R. Stat. Soc. (London)B-20, 361–372 (1958) · Zbl 0086.12403
[11] Green, R. R.: A serial orthogonal decoder, JPL Space Programs Summary.37-39-IV, 247–253 (1966)
[12] Grushko, I.: Majority logic decoding of generalized Reed-Muller codes, Problemy peredachi informatsii26(3), 12–21 (1990) (in Russian) · Zbl 0719.94023
[13] Kasami, T., Lin, S., Peterson, W.: New generalizations of the Reed-Muller codes, Part 1: Primitive codes, IEEE Trans. Inf. TheoryIT-14, 189–199 (1968) · Zbl 0162.51301 · doi:10.1109/TIT.1968.1054127
[14] Litsyn, S.: Fast algorithms for decoding orthogonal and related codes. Lecture Notes in Computer Science, vol. 539, Mattson H. F., Mora T., Rao T. R. N. (eds.) Applied Algebra, Algebraic Algorithms and Error Correcting Codes, pp. 39–47 (1991) · Zbl 0767.94019
[15] Litsyn, S., Mikhailovskaya, G., Neimirovsky, E., Shekhovtsov, O.: Fast decoding of first order Reed-Muller codes in the Gaussian channel, Problems Control Information Theory14(3), 189–201 (1985) · Zbl 0575.94015
[16] Litsyn, S., Shekhovtsov, O.: Fast decoding algorithm for first order Reed-Muller codes. Problemy Peredachi Informatsii,19(2), 3–7 (1983) · Zbl 0539.94029
[17] MacWilliams, F. J., Sloane, N. J. A.: The theory of error-correcting codes, Amsterdam, The Netherlands: North-Holland 1977 · Zbl 0369.94008
[18] Manley, H. J., Mattson, H. F., Schatz, J. R.: Some applications of Good’s theorem, IEEE Trans. Inform. TheoryIT-26, 475–476 (1980) · Zbl 0436.94024 · doi:10.1109/TIT.1980.1056211
[19] Trakhtman, A., Trakhtman, V.: Basics of a theory of digital signals on finite intervals. Moscow, Sovetskoe Radio, 1975 (In Russian) · Zbl 0569.52017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.