Covering radius computations for binary cyclic codes
Authors:
Randall Dougherty and Heeralal Janwa
Journal:
Math. Comp. 57 (1991), 415434
MSC:
Primary 94B75
MathSciNet review:
1079013
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We compute the covering radius of each binary cyclic code of length (for both even and odd lengths) and redundancy . We also compute the covering radii of their punctured codes and shortened codes. Thus we give exact covering radii of over six thousand codes. For each of these codes (except for certain composite codes), we also determine the number of cosets of each weight less than or equal to the covering radius. These results are used to compute the minimum distances of the above cyclic codes. We use the covering radii of shortened codes and other criteria for normality to show that all but eight of the cyclic codes for which we determine the covering radius are normal. For all but seven of these normal codes, we determine the norm using some old results and some new results proved here. We observe that many cyclic codes are among the best covering codes discovered so far, and some of them lead to improvements on the previously published bounds on , the smallest covering radius of any binary linear [n, k] code. Among some other applications of our results, we use our table of covering radii and a code augmentation argument to give four improvements on the values of , where is the largest minimum distance of any binary [n, k] code. These results show that the covering radius is intimately connected with the other three parameters of a linear code, n, k, and d. We also give a complete classification (up to isomorphism) of cyclic selfdual codes of lengths 42, 56, and 60. The computations were carried out mainly on concurrent machines (hypercubes and Connection Machines); we give a description of our algorithm.
 [1]
Elwyn
R. Berlekamp, Algebraic coding theory, McGrawHill Book Co.,
New York, 1968. MR 0238597
(38 #6873)
 [2]
A.
E. Brouwer, A.
M. Cohen, and A.
Neumaier, Distanceregular graphs, Ergebnisse der Mathematik
und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)],
vol. 18, SpringerVerlag, Berlin, 1989. MR 1002568
(90e:05001)
 [3]
Richard
A. Brualdi and Vera
S. Pless, On the length of codes with a given covering radius,
Coding theory and design theory, Part I, IMA Vol. Math. Appl.,
vol. 20, Springer, New York, 1990, pp. 9–15. MR 1047868
(91e:94025), http://dx.doi.org/10.1007/9781461389941_2
 [4]
Richard
A. Brualdi, Vera
S. Pless, and Richard
M. Wilson, Short codes with a given covering radius, IEEE
Trans. Inform. Theory 35 (1989), no. 1, 99–109.
MR 995328
(90g:94016), http://dx.doi.org/10.1109/18.42181
 [5]
A.
R. Calderbank and J.M.
Goethals, On a pair of dual subschemes of the Hamming scheme
𝐻_{𝑛}(𝑞), European J. Combin.
6 (1985), no. 2, 133–147. MR 810694
(87d:94045)
 [6]
R.
Calderbank and W.
M. Kantor, The geometry of twoweight codes, Bull. London
Math. Soc. 18 (1986), no. 2, 97–122. MR 818812
(87h:51022), http://dx.doi.org/10.1112/blms/18.2.97
 [7]
A.
R. Calderbank and N.
J. A. Sloane, Inequalities for covering codes, IEEE Trans.
Inform. Theory 34 (1988), no. 5, 1276–1280.
Coding techniques and coding theory. MR 987672
(90f:94039), http://dx.doi.org/10.1109/18.21257
 [8]
Gérard
D. Cohen, Mark
G. Karpovsky, H.
F. Mattson Jr., and James
R. Schatz, Covering radius—survey and recent results,
IEEE Trans. Inform. Theory 31 (1985), no. 3,
328–343. MR
794430 (86g:94041), http://dx.doi.org/10.1109/TIT.1985.1057043
 [9]
Gérard
D. Cohen, AntoineC.
Lobstein, and N.
J. A. Sloane, Further results on the covering radius of codes,
IEEE Trans. Inform. Theory 32 (1986), no. 5,
680–694. MR
859092 (88b:94019), http://dx.doi.org/10.1109/TIT.1986.1057227
 [10]
Philippe
Delsarte, Four fundamental parameters of a code and their
combinatorial significance, Information and Control
23 (1973), 407–438. MR 0335135
(48 #13453)
 [11]
S. M. Dodunekov, Some quasiperfect double error correcting codes, Problemy Peredachi Informatsii 3 (1984), 1723.
 [12]
Diane
E. Downie and N.
J. A. Sloane, The covering radius of cyclic codes of length up to
31, IEEE Trans. Inform. Theory 31 (1985), no. 3,
446–447. MR
794445 (86f:94036), http://dx.doi.org/10.1109/TIT.1985.1057033
 [13]
V. D. Goppa, Algebraicogeometry codes, Math. USSRIzv. 21 (1983), 7591.
 [14]
R.
L. Graham and N.
J. A. Sloane, On the covering radius of codes, IEEE Trans.
Inform. Theory 31 (1985), no. 3, 385–401. MR 794436
(87c:94048), http://dx.doi.org/10.1109/TIT.1985.1057039
 [15]
J.
W. P. Hirschfeld, Linear codes and algebraic curves,
Geometrical combinatorics (Milton Keynes, 1984) Res. Notes in Math.,
vol. 114, Pitman, Boston, MA, 1984, pp. 35–53. MR 777155
(86m:94035)
 [16]
Heeralal
Janwa, Some new upper bounds on the covering radius of binary
linear codes, IEEE Trans. Inform. Theory 35 (1989),
no. 1, 110–122. MR 995329
(90f:94041), http://dx.doi.org/10.1109/18.42182
 [17]
H. Janwa and H. F. Mattson, Jr., The covering radius and normality of tdense codes, presented in part at the IEEE Internat. Sympos. on Inform. Theory, Ann Arbor, Michigan, October 1986 (to appear).
 [18]
, On the normality of binary linear codes, IEEE Trans. Inform. Theory (to appear).
 [19]
Karen
E. Kilby and N.
J. A. Sloane, On the covering radius problem for codes. I. Bounds
on normalized covering radius, SIAM J. Algebraic Discrete Methods
8 (1987), no. 4, 604–618. MR 918062
(89e:94012a), http://dx.doi.org/10.1137/0608049
 [20]
F. J. MacWilliams and N. J. A. Sloane, The theory of errorcorrecting codes, NorthHolland, Amsterdam, 1977.
 [21]
H.
F. Mattson Jr., Another upper bound on covering radius, IEEE
Trans. Inform. Theory 29 (1983), no. 3,
356–359. MR
712398 (85b:94013), http://dx.doi.org/10.1109/TIT.1983.1056680
 [22]
H.
F. Mattson Jr., An improved upper bound on covering radius,
Applied algebra, algorithmics and errorcorrecting codes (Toulouse, 1984),
Lecture Notes in Comput. Sci., vol. 228, Springer, Berlin, 1986,
pp. 90–106. MR 888614
(88f:94041), http://dx.doi.org/10.1007/3540167676_53
 [23]
Aileen
M. McLoughlin, The complexity of computing the covering radius of a
code, IEEE Trans. Inform. Theory 30 (1984),
no. 6, 800–804. MR 782215
(86h:94022), http://dx.doi.org/10.1109/TIT.1984.1056978
 [24]
W.
Wesley Peterson and E.
J. Weldon Jr., Errorcorrecting codes, 2nd ed., The M.I.T.
Press, Cambridge, Mass.London, 1972. MR 0347444
(49 #12164)
 [25]
V. Pless, Introduction to the theory of errorcorrecting codes, Wiley, New York, 1981.
 [26]
N.
J. A. Sloane, A new approach to the covering radius of codes,
J. Combin. Theory Ser. A 42 (1986), no. 1,
61–86. MR
843463 (87j:94015), http://dx.doi.org/10.1016/00973165(86)900075
 [27]
N.
J. A. Sloane and J.
G. Thompson, Cyclic selfdual codes, IEEE Trans. Inform.
Theory 29 (1983), no. 3, 364–366. MR 712400
(85e:94022), http://dx.doi.org/10.1109/TIT.1983.1056682
 [28]
J. H. van Lint, Introduction to coding theory, SpringerVerlag, New York, 1982.
 [29]
Tom
Verhoeff, An updated table of minimumdistance bounds for binary
linear codes, IEEE Trans. Inform. Theory 33 (1987),
no. 5, 665–680. MR 918189
(88j:94039), http://dx.doi.org/10.1109/TIT.1987.1057356
 [30]
V.
A. Zinov′ev and S.
N. Litsyn, Shortening of codes, Problemy Peredachi Informatsii
20 (1984), no. 1, 3–11 (Russian); English
transl., Problems Inform. Transmission 20 (1984),
no. 1, 1–7. MR 776762
(86g:94023)
 [1]
 E. R. Berlekamp, Algebraic coding theory, McGrawHill, New York, 1968. MR 0238597 (38:6873)
 [2]
 A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distanceregular graphs, SpringerVerlag, New York, 1989. MR 1002568 (90e:05001)
 [3]
 R. A. Brualdi and V. S. Pless, On the length of codes with a given covering radius, preprint. MR 1047868 (91e:94025)
 [4]
 R. A. Brualdi, V. S. Pless, and R. M. Wilson, Short codes with a given covering radius, IEEE Trans. Inform. Theory IT35 (1989), 99109. MR 995328 (90g:94016)
 [5]
 A. E. Calderbank and J.M. Goethals, On a pair of dual subschemes of the Hamming scheme , European J. Combin. 6 (1985), 133147. MR 810694 (87d:94045)
 [6]
 A. E. Calderbank and W. M. Kantor, The geometry of twoweight codes, Bull. London Math. Soc. 18 (1986), 97122. MR 818812 (87h:51022)
 [7]
 A. R. Calderbank and N. J. A. Sloane, Inequalities for covering codes, IEEE Trans. Inform. Theory IT34 (1988), 12761280. MR 987672 (90f:94039)
 [8]
 G. D. Cohen, M. G. Karpovsky, H. F. Mattson, Jr., and J. R. Schatz, Covering radius survey and recent results, IEEE Trans. Inform. Theory IT31 (1985), 328343. MR 794430 (86g:94041)
 [9]
 G. D. Cohen, A. C. Lobstein, and N. J. A. Sloane, Further results on the covering radius of codes, IEEE Trans. Inform. Theory IT32 (1986), 680694. MR 859092 (88b:94019)
 [10]
 Ph. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Inform. and Control 23 (1973), 407438. MR 0335135 (48:13453)
 [11]
 S. M. Dodunekov, Some quasiperfect double error correcting codes, Problemy Peredachi Informatsii 3 (1984), 1723.
 [12]
 D. E. Downey and N. J. A. Sloane, The covering radius of cyclic codes of length up to 31, IEEE Trans. Inform. Theory IT31 (1985), 446447. MR 794445 (86f:94036)
 [13]
 V. D. Goppa, Algebraicogeometry codes, Math. USSRIzv. 21 (1983), 7591.
 [14]
 R. L. Graham and N. J. A. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory IT31 (1985), 385401. MR 794436 (87c:94048)
 [15]
 J. W. P. Hirschfeld, Linear codes and algebraic curves, Geometrical Combinatorics (F. C. Holroyd and R. J. Wilson, eds.), Pitman, 1984, pp. 3553. MR 777155 (86m:94035)
 [16]
 H. Janwa, Some new upper bounds on the covering radius of binary linear codes, IEEE Trans. Inform. Theory IT35 (1989), 110122. MR 995329 (90f:94041)
 [17]
 H. Janwa and H. F. Mattson, Jr., The covering radius and normality of tdense codes, presented in part at the IEEE Internat. Sympos. on Inform. Theory, Ann Arbor, Michigan, October 1986 (to appear).
 [18]
 , On the normality of binary linear codes, IEEE Trans. Inform. Theory (to appear).
 [19]
 K. E. Kilby and N. J. A. Sloane, On the covering radius problem for codes: (i) bounds on normalized covering radius, (ii) codes of low dimension; normal and abnormal codes, SIAM J. Algebraic Discrete Methods 8 (1987), 604627. MR 918062 (89e:94012a)
 [20]
 F. J. MacWilliams and N. J. A. Sloane, The theory of errorcorrecting codes, NorthHolland, Amsterdam, 1977.
 [21]
 H. F. Mattson, Jr., Another upper bound on covering radius, IEEE Trans. Inform. Theory IT29 (1983), 356359. MR 712398 (85b:94013)
 [22]
 , An improved upper bound on covering radius, Applied Algebra, Algorithmics, and Errorcorrecting Codes (Toulouse, 1984), Lecture Notes in Comput. Sci., vol. 288, SpringerVerlag, New York, 1986, pp. 90106. MR 888614 (88f:94041)
 [23]
 A. McLoughlin, The complexity of computing the covering radius of a code, IEEE Trans. Inform. Theory IT30 (1984), 800804. MR 782215 (86h:94022)
 [24]
 W. W. Peterson and E. J. Weldon, Jr., Errorcorrecting codes, 2nd ed., MIT Press, Cambridge, MA, 1972. MR 0347444 (49:12164)
 [25]
 V. Pless, Introduction to the theory of errorcorrecting codes, Wiley, New York, 1981.
 [26]
 N. J. A. Sloane, A new approach to the covering radius of codes, J. Combin. Theory Ser. A 42 (1986), 6186. MR 843463 (87j:94015)
 [27]
 N. J. A. Sloane and J. G. Thompson, Cyclic selfdual codes, IEEE Trans. Inform. Theory IT29 (1983), 364366. MR 712400 (85e:94022)
 [28]
 J. H. van Lint, Introduction to coding theory, SpringerVerlag, New York, 1982.
 [29]
 T. Verhoeff, An updated table of minimumdistance bounds for binary linear codes, IEEE Trans. Inform. Theory IT33 (1987), 665680. MR 918189 (88j:94039)
 [30]
 V. A. Zinov'ev and S. N. Litsyn, Table of best known binary codes, preprint, 1984. MR 776762 (86g:94023)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
94B75
Retrieve articles in all journals
with MSC:
94B75
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199110790138
PII:
S 00255718(1991)10790138
Article copyright:
© Copyright 1991 American Mathematical Society
