A New Table of Binary/Ternary Mixed Covering Codes

被引：8
作者：
Östergård P.R.J. [1 ]
Hämäläinen H.O. [1 ,2 ,3 ]
机构：
[1] Department of Computer Science, Helsinki University of Technology
[2] 41120 Puuppola
[3] c/o Patric R. J. Ostergard, Department of Computer Science, Helsinki University of Technology
来源：
Designs, Codes and Cryptography | 1997年 / 11卷 / 2期
关键词：
Covering codes; Football pool problem; Mixed codes; Simulated annealing;
D O I：
10.1023/A:1008228721072
中图分类号：
学科分类号：
摘要：
A table of upper bounds for K3,2(n1, n2; R), the minimum number of codewords in a covering code with n1 ternary coordinates, n2 binary coordinates, and covering radius R, in the range n = n1 + n2 ≤ 13, R ≤ 3, is presented. Explicit constructions of codes are given to prove the new bounds and verify old bounds. These binary/ternary covering codes can be used as systems for the football pool game. The results include a new binary code with covering radius 1 proving K2(13, 1) ≤ 736, and the following upper bound for the football pool problem for 9 matches: K3 (9, 1) ≤ 1356.
引用
收藏
页码：151 / 178
页数：27
相关论文
共 41 条
  • [1] Blokhuis A., Lam C.W.H., More coverings by rook domains, J. Combin. Theory Ser. A, 36, pp. 240-244, (1984)
  • [2] Brouwer A.E., Shearer J.B., Sloane N.J.A., Smith W.D., A new table of constant weight codes, IEEE Trans. Inform. Theory, 36, pp. 1334-1380, (1990)
  • [3] Carnielli W.A., On covering and coloring problems for rook domains, Discrete Math., 57, pp. 9-16, (1985)
  • [4] Chen W., Honkala I.S., Lower bounds for q-ary covering codes, IEEE Trans. Inform. Theory, 36, pp. 664-671, (1990)
  • [5] Cohen G.D., Karpovsky M.G., Mattson Jr. H.F., Schatz J.R., Covering radius - Survey and recent results, IEEE Trans. Inform. Theory, 31, pp. 328-343, (1985)
  • [6] Cohen G.D., Lobstein A.C., Sloane N.J.A., Further results on the covering radius of codes, IEEE Trans. Inform. Theory, 32, pp. 680-694, (1986)
  • [7] Davies R., Royle G.F., Graph domination, tabu search and the football pool problem, Discrete Appl. Math
  • [8] Etzion T., Greenberg G., Constructions for perfect mixed codes and other covering codes, IEEE Trans. Inform. Theory, 39, pp. 209-214, (1993)
  • [9] Exoo G.
  • [10] Golomb S.W., Posner E.C., Rook domains, Latin squares, affine planes, and error-distributing codes, IEEE Trans. Inform. Theory, 10, pp. 196-208, (1964)
12345