A Graham-Sloane Type Construction for s-Surjective Matrices
Iiro Honkala
DOI: 10.1023/A:1022490600755
Abstract
We give a construction of ( n- s)-surjective matrices with n columns over \mathbb Z q \mathbb{Z}_q using Abelian groups and additive s-bases. In particular we show that the minimum number of rows ms q( n,n- s) in such a matrix is at most s s q n-s for all q, n and s.
Pages: 347–351
Keywords: $s$-surjective matrix; additive basis; orthogonal array
Full Text: PDF
References
1. N. Alon, "Explicit construction of exponential sized families of k-independent sets," Discrete Math., 56 (1986), 191-193.
2. I. Anderson, Combinatorics of Finite Sets, Clarendon Press, Oxford, 1987.
3. I. Anderson, Combinatorial Designs: Construction Methods, Ellis Horwood Limited, Chichester, 1990.
4. A. Brace and D. E. Daykin, "Sperner type theorems for finite sets," Proc. Br. Combinatorial Conf., Oxford (1972), 18-37, Institute of Mathematics and its Applications, Southend-on-Sea.
5. A.E. Brouwer, J.B. Shearer, N.J.A. Sloane, and W.D. Smith, "A new table of constant weight codes," IEEE Trans. Inform. Theory, 36 (1990) 1334-1380.
6. P. Busschbach, "Constructive methods to solve problems of s-surjectivity, conflict resolution, coding in defective memories," Rapport Interne ENST 84D005, Paris, Dec. 1984.
7. G.D. Cohen, "Applications of coding theory to communication combinatorial problems," Discrete Math., 83 (1990) 237-248.
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, 31 (1985) 328-343.
9. R. L. Graham and N.J.A. Sloane, "Lower bounds for constant weight codes," IEEE Trans. Inform. Theory, 26 (1980) 37-43.
10. R.L. Graham and N.J.A. Sloane, "On the covering radius of codes," IEEE Trans. Inform. Theory, 31 (1985) 385-401.
11. H. Halberstam and K.F. Roth, Sequences, vol. 1, Oxford Univ. Press, Oxford, 1966.
12. M. Hall Jr., Combinatorial Theory, John Wiley & Sons, New York, 2nd edition, 1986.
13. N. Hammerer and G. Hofmeister, "Zu einer Vermutung von Rohrbach," J. Reine Angew. Math., 286/287 (1976) 239-247.
14. I. Honkala, "Modified bounds for covering codes," IEEE Trans. Inform. Theory, 37 (1991) 351-365.
15. D.J. Kleitman and J. Spencer, "Families of independent sets," Discrete Math., 6 (1973) 255-262.
16. T. Klove, "A new lower bound for A(n,4,w)," IEEE Trans. Inform. Theory, 27 (1981) 257-258.
17. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
18. H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie," Math. Zeitschr., 42 (1936) 1-30.
19. G. Roux, "k-proprietes des tableaux de n colonnes," These Doctorat Univ. Paris 6, March 1987.
2. I. Anderson, Combinatorics of Finite Sets, Clarendon Press, Oxford, 1987.
3. I. Anderson, Combinatorial Designs: Construction Methods, Ellis Horwood Limited, Chichester, 1990.
4. A. Brace and D. E. Daykin, "Sperner type theorems for finite sets," Proc. Br. Combinatorial Conf., Oxford (1972), 18-37, Institute of Mathematics and its Applications, Southend-on-Sea.
5. A.E. Brouwer, J.B. Shearer, N.J.A. Sloane, and W.D. Smith, "A new table of constant weight codes," IEEE Trans. Inform. Theory, 36 (1990) 1334-1380.
6. P. Busschbach, "Constructive methods to solve problems of s-surjectivity, conflict resolution, coding in defective memories," Rapport Interne ENST 84D005, Paris, Dec. 1984.
7. G.D. Cohen, "Applications of coding theory to communication combinatorial problems," Discrete Math., 83 (1990) 237-248.
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, 31 (1985) 328-343.
9. R. L. Graham and N.J.A. Sloane, "Lower bounds for constant weight codes," IEEE Trans. Inform. Theory, 26 (1980) 37-43.
10. R.L. Graham and N.J.A. Sloane, "On the covering radius of codes," IEEE Trans. Inform. Theory, 31 (1985) 385-401.
11. H. Halberstam and K.F. Roth, Sequences, vol. 1, Oxford Univ. Press, Oxford, 1966.
12. M. Hall Jr., Combinatorial Theory, John Wiley & Sons, New York, 2nd edition, 1986.
13. N. Hammerer and G. Hofmeister, "Zu einer Vermutung von Rohrbach," J. Reine Angew. Math., 286/287 (1976) 239-247.
14. I. Honkala, "Modified bounds for covering codes," IEEE Trans. Inform. Theory, 37 (1991) 351-365.
15. D.J. Kleitman and J. Spencer, "Families of independent sets," Discrete Math., 6 (1973) 255-262.
16. T. Klove, "A new lower bound for A(n,4,w)," IEEE Trans. Inform. Theory, 27 (1981) 257-258.
17. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
18. H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie," Math. Zeitschr., 42 (1936) 1-30.
19. G. Roux, "k-proprietes des tableaux de n colonnes," These Doctorat Univ. Paris 6, March 1987.