As we have seen in class, for the worst case noise model, the trade-off that we are interested in that between the rate and the (relative) distance of the code. The optimal trade-off is known when the alphabet size is large enough (for example, when the alphabet size is at least the block length of the code). However, the optimal trade-off for smaller alphabets (and binary codes in particular) is still not known. For a given relative distance the best known lower bound (called the Gilbert-Varshamov bound, which we will see in class) on rate is achieved by random codes while the best known upper bound on rate uses linear programming. The latter is focus of this project.
A recent paper on this topic is On Delsarte’s Linear Programming Bounds for Binary Codes (FOCS05) by Navon and Samorodnitsky. Some background material related to this topic can be found in these lecture notes from Madhu Sudan’s coding theory course.
Posted in projects
