Posted by: **atri** | September 18, 2007

## Project 6: Linear Programming bounds on codes

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.

### Like this:

Like Loading...

*Related*

## Leave a Reply