Bounds on codes based on graph theory Academic Article uri icon

abstract

  • Let A q (n,d) be the maximum order (maximum number of codewords) of a q-ary code of length n and Hamming distance at least d. And let A(n, d, w) that of a binary code of constant weight w. Building on results from algebraic graph theory and Erdos-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on A q (n, d) and A(n, d, w) can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications. 2007 IEEE.

published proceedings

  • 2007 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-7

author list (cited authors)

  • El Rouayheb, S. Y., Georghiades, C. N., Soljanin, E., & Sprintson, A.

citation count

  • 10

complete list of authors

  • El Rouayheb, Salim Y||Georghiades, Costas N||Soljanin, Emina||Sprintson, Alex

publication date

  • June 2007