Single point of access to the national research repositories

Subject: Linear codes, Greedy Codes, Lexicodes, Gilbert-Varshamov Bound, Greedy Algorithms

Year: 2009

Type: Proceeding article

Title: On the Complexity of the Greedy Construction of Linear Error-Correcting Codes

Author: Spasov, Dejan
Author: Gushev, Marjan

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.

Publisher: Springer, Berlin, Heidelberg

Relation: International Conference on ICT Innovations

Identifier: oai:repository.ukim.mk:20.500.12188/20317
Identifier: http://hdl.handle.net/20.500.12188/20317

Title	Date	Views
On the Complexity of the Greedy Construction of Linear Error-Correcting Codes	2009	22