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

Blondel, Vincent [UCL] Jungers, Raphaël M. [UCL] Protasov, Vladimir

Some questions related to the computation of the capacity of codes that avoid forbidden difference patterns are analysed. The maximal number of it-bit sequences whose pairwise differences do not contain some given forbidden difference patterns is known to increase exponentially with n; the coefficient of the exponent is the capacity of the forbidden patterns. In this paper, new inequalities for the capacity are given that allow for the approximation of the capacity with arbitrary high accuracy. The computational cost of the algorithm derived from these inequalities is fixed once the desired accuracy is given. Subsequently, a polynomial time algorithm is given for determining if the capacity of a set is positive while the same problem is shown to be NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, the existence of extremal norms is proved for any set of matrices arising in the capacity computation. Based on this result, a second capacity approximating algorithm is proposed. The usefulness of this algorithm is illustrated by computing exactly the capacity of particular codes that were only known approximately.