Abstract
Greedy algorithms are one of the oldest known methods for code construction. They are simple to define and easy to implement, but require exponential running time. Codes obtained with greedy construction have very good encoding parameters; hence, the idea of finding faster algorithms for code generation seems natural. We start with an overview of the greedy algorithms and propose some improvements. Then, we study the code parameters of long greedy codes in attempt to produce stronger estimates. It is well known that greedy-code parameters give raise to the Gilbert-Varshamov bound; improving this bound is fundamental problem in coding theory.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Trachtenberg, A.: Designing Lexicographic Codes with a Given Trellis Complexity. IEEE Trans. Information Theory 48(1), 89–100 (2001)
Jenkins, B.: Tables of Binary Lexicodes, http://www.burtleburtle.net/bob/math/lexicode.html
Barg, A.: Complexity Issues in Coding Theory. Handbook of Coding Theory. Elsevier Science, Amsterdam (1998)
Spasov, D.: Implementing the Lexicographic Construction, http://nislab.bu.edu/nislab/projects/lexicode/index.html
O’Brien, K., Fitzpatrick, P.: Covering radius construction codes with minimum distance at most 8 are normal, http://www.bcri.ucc.ie/BCRI_01.pdf
Vardy, A.: Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. In: STOC (1997)
Grassl, M.: Bounds on the minimum distance of linear codes and quantum codes, http://www.codetables.de (accessed on 2009-09-02)
Jiang, T., Vardy, A.: Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes. IEEE Trans. Inform. Theory 50, 1655–1664 (2004)
Vu, V., Wu, L.: Improving the Gilbert-Varshamov bound for q-ary codes. IEEE Trans. Inform. Theory 51, 3200–3208 (2005)
Elia, M.: Some results on the existence of binary linear codes. IEEE Trans. Inform. Theory 29, 933–934 (1983)
Gaborit, P., Zemor, G.: Asymptotic improvement of the Gilbert-Varshamov bound for binary linear codes. IEEE Trans. Inform. Theory 54, 3865–3872 (2008)
Barg, A., Guritman, S., Simonis, J.: Strengthening the Gilbert-Varshamov Bound. Lin. Alg. Appl. 307, 119–129 (2000)
O’Brien, K., Fitzpatrick, P.: Improving the Varshamov bound by counting components in the Varshamov graph. Designs, Codes, and Cryptography 39(3) (2006)
Spasov, D., Gusev, M.: Some notes on the binary Gilbert-Varshamov bound. In: Sixth International Workshop on Optimal Codes and Related Topics, Varna, Bulgaria (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Spasov, D., Gusev, M. (2010). On the Complexity of the Greedy Construction of Linear Error-Correcting Codes. In: Davcev, D., Gómez, J.M. (eds) ICT Innovations 2009. ICT Innovations 2009. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10781-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-10781-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10780-1
Online ISBN: 978-3-642-10781-8
eBook Packages: EngineeringEngineering (R0)