Some upper bounds on the covering radii of linear codes over \({\mathbb{F}}_q\) and their applications (Q1591637)

The covering radius \(R\) of a code \(C\subset F_q^n\) is the smallest integer such that the spheres of radius \(R\) around the codewords of \(C\) cover the whole space \(F_q^n\). The covering radius is shown to obey the upper bound \(R\leq N-n_q(k,[d/q])\), where \([x]\) denotes the integer part of \(X\) and \(n_q(k,d)\) is the smallest length of a linear code of dimension \(k\) and minimum distance \(d\). In the case \(R\leq d\) the bound is strengthened and conditions are found in order for equality to hold. As applications of this and related bounds it is shown that all binary linear codes of lengths up to 15 or codimension up to 9 are normal. These results have applications in finding \(t(n,k)\), the smallest covering radius of any binary linear code of length \(n\) and dimension \(k\). The amalgamated direct sum (ADS) is important to construct good covering codes. This construction requires the component codes to be normal. Several new results on the amalgamated direct sum construction are given. The authors find new conditions assuring the normality conditions of the ADS that in some cases give a covering radius 1 less than previously guaranteed for ADS codes with even norms. Also good covering codes are constructed as ADS without the condition of normality. This is done by introducing new concepts which are called \(p\)-stable and \(s\)-stable. This approach allows the authors to construct good structured covering codes as ADS of two cyclic codes.