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 language | English (US) |
|---|---|
| Pages (from-to) | 128-130 |
| Number of pages | 3 |
| Journal | IEEE Transactions on Information Theory |
| Volume | 34 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1988 |
Bibliographical note
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.