Bounds on Codes Based on Graph Theory

Details Bounds on Codes Based on Graph Theory Bounds on Codes Based on Graph Theory

2008-06-30

arxiv.org/abs/0806.4979v1

Computer Science

Information Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Bounds on Codes Based on Graph Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on Codes Based on Graph Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on Codes Based on Graph Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-155545