On the complexity of computing the capacity of codes that avoid forbidden difference patternsстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 18 июля 2013 г.
Аннотация:Some questions related to the computation of the
capacity of codes that avoid forbidden difference patterns are
analysed. The maximal number of n-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