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

Date Issued
2009-09-28
Author(s)
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.
Subjects

Linear codes, Greedy ...

File(s)
Loading...
Thumbnail Image
Name

On_the_Complexity_of_the_Greedy_Construc.pdf

Size

122.19 KB

Format

Adobe PDF

Checksum

(MD5):a987ea110d40a653bea3c6f58fb86644