Balancing Sets of Vectors

N. Alon, E. E. Bergmann, D. Coppersmith, A. M. Odlyzko

Research output: Contribution to journalArticle

51 Scopus citations

Abstract

For n > 0, d≥ 0, n = d (mod2), let K(n,d) denote the minimal cardinality of a family V of ± 1 vectors of dimension n, such that for any + 1 vector w of dimension n there is a viv such that v·w ≤ d, where v · w is the usual scalar product of v and w. A generalization of a simple construction due to Knuth shows that K(n, d)≤[n/(d + 1)]. A linear algebra proof is given here that this construction is optimal, so that K(n,d) = [n/(d +1)] for all n = d (mod2). This construction and its extensions have applications to communication theory, especially to the construction of signal sets for optical data links.

Original languageEnglish (US)
Pages (from-to)128-130
Number of pages3
JournalIEEE Transactions on Information Theory
Volume34
Issue number1
DOIs
StatePublished - Jan 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Balancing Sets of Vectors'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Bergmann, E. E., Coppersmith, D., & Odlyzko, A. M. (1988). Balancing Sets of Vectors. IEEE Transactions on Information Theory, 34(1), 128-130. https://doi.org/10.1109/18.2610