TY - JOUR

T1 - Balancing Sets of Vectors

AU - Alon, N.

AU - Bergmann, E. E.

AU - Coppersmith, D.

AU - Odlyzko, A. M.

N1 - Funding Information:
Manuscript received September 27,1986; revised March 10, 1987. This work was supported in part by an Alon Fellowship and in part by The Fund for Basic Research administered by the Israel Academy of Sciences. This paper was presented at the Information Theory Workshop, Oherwolfach, May 1986. N. Alon is with the Department of Mathematics, Tel Aviv University, Ramat Aviv, Tel Aviv, Israel, and Bell Communications Research, Morristown, NJ 07960. E. E. Bergmann is with AT&T Bell Laboratories. Allentown, PA 18103. D. Coppersmith is with IBM Research, Yorktown Heights, NY 10598. A. M. Odlyzko is with AT&T Bell Laboratories, Murray Hill, NJ 07974. IEEE Log Number 8718729.

PY - 1988/1

Y1 - 1988/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023824556&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023824556&partnerID=8YFLogxK

U2 - 10.1109/18.2610

DO - 10.1109/18.2610

M3 - Article

AN - SCOPUS:0023824556

SN - 0018-9448

VL - 34

SP - 128

EP - 130

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

ER -