On the complexity of computing the capacity of codes that avoid forbidden difference patterns

Details On the complexity of computing the capacity of codes that avoid forbidden difference patterns On the complexity of computing the capacity of codes that avoid forbidden difference patterns

2006-01-10

arxiv.org/abs/cs/0601036v1

Computer Science

Information Theory

7 pages. Submitted to IEEE Trans. on Information Theory

Scientific paper

We consider questions related to the computation of the capacity of codes that avoid forbidden difference patterns. The maximal number of $n$-bit sequences whose pairwise differences do not contain some given forbidden difference patterns increases exponentially with $n$. The exponent is the capacity of the forbidden patterns, which is given by the logarithm of the joint spectral radius of a set of matrices constructed from the forbidden difference patterns. We provide a new family of bounds that allows for the approximation, in exponential time, of the capacity with arbitrary high degree of accuracy. We also provide a polynomial time algorithm for the problem of determining if the capacity of a set is positive, but we prove that the same problem becomes NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, we prove the existence of extremal norms for the sets of matrices arising in the capacity computation. This result makes it possible to apply a specific (even though non polynomial) approximation algorithm. We illustrate this fact by computing exactly the capacity of codes that were only known approximately.

Affiliated with

Also associated with

No associations

Rating

On the complexity of computing the capacity of codes that avoid forbidden difference patterns 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 On the complexity of computing the capacity of codes that avoid forbidden difference patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of computing the capacity of codes that avoid forbidden difference patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-214228