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 -