Authors 
: 

Document type 
: 
Article de périodique (Journal article) – Article de recherche

Abstract 
: 
Some questions related to the computation of the capacity of codes that avoid forbidden difference patterns are analysed. The maximal number of itbit 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 NPhard 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. 
Access type 
: 
Accès restreint 
Publication date 
: 
2006 
Language 
: 
Anglais 
Journal information 
: 
"IEEE Transactions on Information Theory"  Vol. 52, no. 11, p. 51225127 (2006) 
Peer reviewed 
: 
yes 
Publisher 
: 
Ieeeinst Electrical Electronics Engineers Inc (Piscataway)

issn 
: 
00189448 
eissn 
: 
15579654 
Publication status 
: 
Publié 
Affiliation 
: 
UCL
 FSA/INMA  Département d'ingénierie mathématique

Keywords 
: 
approximation algorithm ; capacity of codes ; coding theory ; complexity of capacity ; joint spectral radius ; NPhardness

Links 
: 
