×

New approaches to reduced-complexity decoding. (English) Zbl 0736.94014

Summary: We examine new approaches to the problem of decoding general linear codes under the strategies of full or bounded hard decoding and bounded soft decoding. The objective is to derive enhanced new algorithms that take advantage of the major features of existing algorithms to reduce decoding complexity. We derive a wide range of results on the complexity of many existing algorithms. We suggest a new algorithm for cyclic codes, and show how it exploits all the main features of the existing algorithms. Finally, we propose a new approach to the problem of bounded soft decoding, and show that its asymptotic complexity is significantly lower than that of any other currently known general algorithm. In addition, we give a characterization of the weight distribution of the average linear code and thus show that the Gilbert-Varshamov bound is tight for virtually all linear codes over any symbol field.

MSC:

94B35 Decoding
94B05 Linear codes (general theory)
94B15 Cyclic codes

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bassalygo, L. A.; Zyablov, V. V.; Pinsker, M. S., Problems of complexity in the theory of correcting codes, Problemy Peredachi Informatsii, 13, 5-17 (1977) · Zbl 0396.94017
[2] Baumert, L. D.; McEliece, R. J.; Solomon, G., Decoding with multipliers, (JPL Deep Space Network Progress Report, 42 (1976), Jet Propulsion Laboratory), 42-46, (34)
[3] Benyamin-Seeyar, A.; Shiva, S. G.S.; Bhargava, V. K., Capability of error-trapping technique in decoding cyclic codes, IEEE Trans. Inform. Theory, 32, 166-180 (1986) · Zbl 0593.94014
[4] Berlekamp, E. R., The technology of error-correcting codes, Proc. IEEE, 68, 564-593 (1980)
[5] Berlekamp, E. R.; McEliece, R. J.; van Tilborg, H. C.A., On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24, 384-386 (1978) · Zbl 0377.94018
[6] Blinovskii, V. M., Lower asymptotic bound on the number of linear code words in a sphere of given radius in \(F^n_q\), Problemy Peredachi Informatsii, 23, 50-53 (1987)
[7] Chan, A. H.; Games, R. A., (n,k,t)-covering systems and error-trapping decoding, IEEE Trans. Inform. Theory, 27, 643-646 (1981)
[8] Chase, D., A class of algorithms for decoding block codes with channel measurement information, IEEE Trans. Inform. Theory, 18, 170-182 (1972) · Zbl 0227.94005
[9] Clark, G. C.; Cain, J. B., Error-Correcting Coding for Digital Communications (1981), Plenum Press: Plenum Press New York
[10] Coffey, J. T., On complexity and efficiency in encoding and decoding error-correcting codes, (Ph.D. Dissertation (1989), Department of Electrical Engineering, California Institute of Technology: Department of Electrical Engineering, California Institute of Technology Pasadena, CA)
[11] Coffey, J. T.; Goodman, R. M.F., The complexity of information set decoding, IEEE Trans. Inform. Theory, 36, 1031-1037 (1990) · Zbl 0738.94021
[12] Dmitriev, O. F., An algorithm for the correction of independent errors by cyclic codes, Problemy Peredachi Informatsii, 3, 102-104 (1967)
[13] Evseev, G. S., Complexity of decoding for linear codes, Problemy Peredachi Informatsii, 19, 3-8 (1983) · Zbl 0522.94015
[14] Farrell, P. G.; Rice, M.; Taleb, F., Minimum weight decoding for cyclic codes, Cirencester, UK. Cirencester, UK, Proceedings IMA Conference on Cryptography and Coding (1986)
[15] Farrell, P. G.; Rice, M.; Taleb, F., Division algorithms for hard and soft decision decoders, Florence, Italy. Florence, Italy, Proceedings International Conference on Digital Signal Processing (1987)
[16] Goblick, T. J., Coding for a discrete information source with a distortion measure, (Ph.D. Dissertation (1962), Department of Electrical Engineering, Massachusetts Institute of Technology: Department of Electrical Engineering, Massachusetts Institute of Technology Cambridge, MA) · Zbl 0172.43401
[17] Goodman, R. M.F.; Green, A. D., Microprocessor-controlled permutation decoding of error-correcting codes, Kent, UK. Kent, UK, Proceedings IERE Conference on Microprocessors in Automation and Communications, 41, 365-376 (1978)
[18] Hartmann, C. R.P.; Levitin, L. B., An improvement of the zero-neighbors minimum distance decoding algorithm: the zero-guard algorithm, Kobe, Japan. Kobe, Japan, 1988 IEEE International Symposium on Information Theory (1988)
[19] Hwang, T.-Y., Decoding linear block codes for minimizing word error rate, IEEE Trans. Inform. Theory, 25, 733-737 (1979) · Zbl 0423.94032
[20] Kasami, T., A decoding procedure for multiple-error-correcting cyclic codes, IEEE Trans. Inform. Theory, 10, 134-138 (1964) · Zbl 0116.35302
[21] Koshelev, V. N., On some properties of random group codes of great length, Problemy Peredachi Informatsii, 1, 35-38 (1965)
[22] Kozlov, M. V., The correcting capacities of linear codes, Soviet Phys. Dokl., 14, 413-415 (1969) · Zbl 0193.48203
[23] Levitin, L. B.; Hartmann, C. R.P., A new approach to the general minimum distance decoding problem—the zero neighbors algorithm, IEEE Trans. Inform. Theory, 31, 378-384 (1985) · Zbl 0586.94022
[24] MacWilliams, F. J., Permutation decoding of systematic codes, Bell Syst. Tech. J., 43, 485-505 (1964) · Zbl 0116.35304
[25] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[26] Mandelbaum, D., On vote-taking and complete decoding of certain error-correcting codes, Inform. and Control, 43, 195-197 (1979) · Zbl 0423.94033
[27] Mandelbaum, D., On complete decoding of linear error-correcting codes, Inform. and Control, 47, 195-200 (1980) · Zbl 0458.94045
[28] McEliece, R. J., A public-key cryptosystem based on algebraic coding theory, (JPL Deep Space Network Progress Report, 42 (1978), Jet Propulsion Laboratory), (44) · Zbl 0166.00805
[29] Montgomery, B. L.; Diamond, H.; Kumar, B. V.K. Vijaya, A general minimum distance decoding procedure for binary linear block codes, Ann Arbor, MI. Ann Arbor, MI, Proceedings IEEE International Symposium on Information Theory (1986)
[30] Pierce, J. N., Limit distribution of the minimum distance of random linear codes, IEEE Trans. Inform. Theory, 13, 595-599 (1967) · Zbl 0178.22404
[31] Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inform. Theory, 8, S5-S9 (1962)
[32] Shiva, S. G.S.; Fung, K. C., Permutation decoding of certain triple-error-correcting binary codes, IEEE Trans. Inform. Theory, 18, 444-446 (1972) · Zbl 0234.94011
[33] Wei, V. K., An error-trapping decoder for nonbinary cyclic codes, IEEE Trans. Inform. Theory, 30, 538-541 (1984) · Zbl 0541.94029
[34] Wolf, J. K., Efficient maximum likelihood of linear block using a trellis, IEEE Trans. Inform. Theory, 24, 76-80 (1978) · Zbl 0371.94027
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.