New upper bounds on codes via association schemes and linear programming

Beniamin Mounits; Tuvi Etzion; Simon Litsyn

doi:10.3934/amc.2007.1.173

Article Contents

2007, Volume 1, Issue 2: 173-195. Doi: 10.3934/amc.2007.1.173

This issue Previous Article Next Article Cryptographic protocols on real hyperelliptic curves

New upper bounds on codes via association schemes and linear programming

1.
Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ, P.O. Box 94079, 1090 GB Amsterdam
2.
Department of Computer Science, Technion, Haifa 32000
3.
School of Electrical Engineering, Tel Aviv University, Tel Aviv 69978

Received: August 2006

Revised: February 2007

Published: July 2007

Abstract / Introduction Related Papers Cited by

Abstract

Let $A(n, d)$ denote the maximum number of codewords in a binary code of length n and minimum Hamming distance $d$. Upper and lower bounds on $A(n, d)$ have been a subject for extensive research. In this paper we examine upper bounds on $A(n, d)$ as a special case of bounds on the size of subsets in metric association scheme. We will first obtain general bounds on the size of such subsets, apply these bounds to the binary Hamming scheme, and use linear programming to further improve the bounds. We show that the sphere packing bound and the Johnson bound as well as other bounds are special cases of one of the bounds obtained from association schemes. Specific bounds on $A(n, d)$ as well as on the sizes of constant weight codes are also discussed.

Keywords:

Mathematics Subject Classification: Primary: 94B65; Secondary: 05E30.

Citation:

Article Metrics

HTML views() PDF downloads(106) Cited by(0)

New upper bounds on codes via association schemes and linear programming

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

New upper bounds on codes via association schemes and linear programming

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content