On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

We consider upper bounds on two fundamental parameters of a code; minimum distance and covering radius. New upper bounds on the covering radius of non-binary linear codes are derived by generalizing a method due to S. Litsyn and A. Tietäväinen lt:newu and combining it with a new upper bound on the asymptotic information rate of non-binary codes. The upper bound on the information rate is an application of a shortening method of a code and is an analogue of the Shannon-Gallager-Berlekamp straight line bound on error probability. These results improve on the best presently known asymptotic upper bounds on minimum distance and covering radius of non-binary codes in certain intervals.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Aaltonen, Bounds on the information rate of a tree code as a function on the code's feedback decoding minimum distance, Ann. Univ. Turku. Ser. A I, Vol. 181 (1981).

  2. M. Aaltonen, A new upper bound on nonbinary block codes, Discrete Math., Vol. 83 (1990), pp. 139-160.

    Google Scholar 

  3. F. R. K. Chung, V. Faber and T. A. Manteuffel, An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. Discr. Math., Vol. 7 (1994) pp. 443-457.

    Google Scholar 

  4. G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, Elsevier, Amsterdam (1997).

  5. G. Cohen, S. Litsyn, A. Lobstein and H. Mattson, Jr., Covering radius 1985-1994, Applicable Algebra in Engineering, Communication and Computing, Vol. 8 (1997) pp. 173-239.

    Google Scholar 

  6. C. Delorme and P. Solé, Diameter, covering index, covering radius and eigenvalues, Europ. J. Combin., Vol 12 (1991) pp. 95-108.

    Google Scholar 

  7. P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control, Vol. 23 (1973) pp. 407-438.

    Google Scholar 

  8. T. Helleseth, T. Kløve, and J. Mykkeltveit, On the covering radius of binary codes, IEEE Trans. Inform. Theory, Vol. 24 (1978) pp. 627-628.

    Google Scholar 

  9. I. Honkala, S. Litsyn, and A. Tietäväinen, On algebraic methods in covering radius problems, In: Cohen, G., Giusti M., Mora, T. (eds.) Applied Algebra, Albegraic Algorithms and Error-Correcting Codes. Lecture Notes in Computer Science, Vol 948. Berlin, Heidelberg, New York: Springer (1995).

    Google Scholar 

  10. J. van Lint, Introduction to Coding Theory, Springer-Verlag, Berlin, Heidelberg, New York (1982).

    Google Scholar 

  11. S. Litsyn and A. Tietäväinen, Upper bounds on the covering radius of a code with a given dual distance, Europ. J. Combin., vol. 17 (1996) pp. 265-270.

    Google Scholar 

  12. A. Lubotszky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica, Vol. 8 (1988) pp. 261-277.

    Google Scholar 

  13. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam (1977).

    Google Scholar 

  14. R. McEliece, E. Rodemich, H. Jr. Rumsey and L. Welch, New upper bounds on the rate of a code via Delsarte-MacWilliams inequalities, IEEE Trans. Inform. Theory, Vol. 23 (1977) pp. 157-167.

    Google Scholar 

  15. T. Rivlin, The Chebyshev polynomials, John Wiley & Sons, New York (1974).

    Google Scholar 

  16. C. E. Shannon, R. G. Gallager and E. R. Berlekamp, Lower bounds to error probability for coding on discrete memoryless channels. II, Information and Control, Vol. 10, (1967), pp. 522-552.

    Google Scholar 

  17. P. Solé, Asymptotic bounds on the covering radius of binary codes, IEEE Trans. Inform. Theory, Vol. 36, (1990), pp. 1470-1472.

    Google Scholar 

  18. P. Solé and K. Mehrotra, Generalization of the Norse bounds to codes of higher strength, IEEE Trans. Inform. Theory, Vol. 37 (1991) pp. 190-192.

    Google Scholar 

  19. P. Solé and P. Stokes, Covering radius, codimension, and dual-distance width, IEEE Trans. Inform. Theory, Vol. 39 (1993) pp. 1195-1203.

    Google Scholar 

  20. G. Szegö, Orthogonal Polynomials, Colloquium Publications, vol. 23, American Math. Soc., Providence, RI (1975).

    Google Scholar 

  21. A. Tietäväinen, An upper bound on the covering radius as a function of its dual distance, IEEE Trans. Inform. Theory, Vol. 36 (1990) pp. 1472-1474.

    Google Scholar 

  22. A. Tietäväinen, Covering radius and dual distance, Designs, Codes and Cryptography, Vol. 1 (1991) pp. 31-46.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Turku, FIN-20500, Turku, Finland.

    Tero Laihonen

  2. Department of EE-systems, Tel-Aviv University, Ramat-Aviv, 69978, Israel.

    Simon Litsyn

Authors
  1. Tero Laihonen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Simon Litsyn
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laihonen, T., Litsyn, S. On Upper Bounds for Minimum Distance and Covering Radius of Non-binary Codes. Designs, Codes and Cryptography 14, 71–80 (1998). https://doi.org/10.1023/A:1008260505585

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008260505585

Search

Navigation