Bounds on Codes Based on Graph Theory
Preprint
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 Erd\H{o}s-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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Primal-Dual Distance Bounds of Linear Codes With Application to CryptographyIEEE Transactions on Information Theory, 2006
- Algebraic Graph Theory2001
- Upper bounds for constant-weight codesIEEE Transactions on Information Theory, 2000
- The Diametric Theorem in Hamming Spaces—Optimal AnticodesAdvances in Applied Mathematics, 1998
- The Complete Intersection Theorem for Systems of Finite SetsEuropean Journal of Combinatorics, 1997
- The exact bound in the Erdös-Ko-Rado theoremCombinatorica, 1984
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- A new upper bound for error-correcting codesIEEE Transactions on Information Theory, 1962
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETSThe Quarterly Journal of Mathematics, 1961
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956