.de tB
.nf
.sp -1v
.ta 5.9i
	\(bx
.br
.fi
..
.de HX
.if \\$1=3 .ds }0
..
.ds xX .aU
.de aU
Allentown, PA 18103
..
.ds yY .bU
.de bU
Yorktown Heights, NY 10598
..
.ds zZ .cU
.de cU
Murray Hill, NJ 07974
..
.ds wW .dU
.de dU
Tel Aviv University
Ramat Aviv, Tel Aviv
and
Bell Communications Research
Morristown, NJ 07960
..
.EQ
delim $$
define cB % C back 65 size 9 | fwd 25 "" %
define vv % bold v %
define ww % bold w %
define uu % bold u %
define zz % bold z %
define yy % bold y %
define eqsl % "\o'\(eq\(sl'" %
gsize 12
.EN
.am DE
.sp
..
.nr Pt 1
.nr Ht 1
.ds HP 12 12 12
.ds HF 3 2 2
.S 12
.ND ""
.TL ""
Balancing Sets of Vectors
.AF "Department of Mathematics" 1
.AU "Noga Alon* " NA wW
.AF "AT&T Bell Laboratories"
.AU "E. E. Bergmann" EEB xX
.AF "IBM Research" 1
.AU "D. Coppersmith" DC yY
.AF "AT&T Bell Laboratories"
.AU "A. M. Odlyzko" AMO zZ
.AS 1
.ls 2
.P
For $n~>~0$, $d~>=~0$, $n ~==~ d ( roman mod 2)$, let
$K(n,^d)$ denote the minimal cardinality of a family
$V$ of $+- 1$ vectors of length $n$, such that for any
$+- 1$ vector $uu$ of length $n$ there is a $vv ~member~ V$ such
that $|^ vv ^cdot^ uu ^| ~<=~d$, where $vv ^cdot^ uu$ is the usual
scalar product of $vv$ and $uu$.
A generalization of a very simple construction due to Knuth shows
that $K(n,^d) ~<=~ lc n/(d+1) rc$.
A proof is given here that this construction is optimal,
so that $K(n,^d) ~=~ lc n/(d+1) rc$ for all $n~==~d$ (mod 2).
This construction and its extensions have
applications to communication theory, especially to
construction of signal sets for optical data links.
.AE
.FS *
Research supported in part by Alon Fellowship and by The Fund for
Basic Research Administered by the Israel Academy of Sciences.
.FE
.ls 1
.OK ""
.MT 4 1
.ls 2
.H 1 "Introduction"
Let $K (n,^d)$ denote the minimal $k$ for which there exist
$+- 1$ vectors $vv sub 1 ^,...,^ vv sub k$ of length $n$
such that for any $+- 1$ vector $ww$ of length $n$,
there is an $i$, $1 ~<=~ i ~<=~ k$, such that
$| vv sub i ~cdot~ ww | ~<=~ d$, where $vv ~cdot~ ww$ denotes
the usual inner product of two vectors.
Since $vv ~cdot~ ww ~==~ ~n$ (mod 2) for any two
$+- 1$ vectors $vv$ and $ww$ of length $n$,
$K (n,^ 0)$ is defined only for even $n$, while
$K(n,^d)$ for $d ~>=~ 1$ is well-defined for all $n$.
A very simple and surprising construction of Knuth [9]
shows that $K (n, ^0) ~<=~ n$ for even $n$.
The main result of this note
is that for $n$ even, $K(n,^ 0) ~=~ n$.
More generally, Knuth's construction shows
that $K(n,^d) ~<=~ lc n/(d+1) rc$
for $n~==~d$ (mod 2), and we show that this construction
is best possible.
.P
The reason Knuth's result is surprising is that it might
appear that if one tries to select $+- 1$ vectors
$vv sub 1 ^,...,^ vv sub n$ so as to minimize
.DS 3
.EQ (1.1)
max from w ~ min from {1 <= i <= n} ~
| vv sub i ~cdot~ ww |
.EN
.DE
(where the maximum is over all $+- 1$ vectors $ww$
of length $n$), then the best choice to make is to take
the $vv sub i$ to be pairwise orthogonal; i.e., as the rows of a
Hadamard matrix of order $n$.
Hadamard matrices are conjectured to exist for $n ~=~ 1,^2$, and
all those $n$ divisible by 4, but this is not known to be true
in general [8].
When the $vv sub i$ are chosen as the rows of a
Hadamard matrix, it is easy to show that the maximum
in (1.1) is $<= n sup 1/2$.
.P
In many cases this bound is not best possible
(for one thing, $n sup 1/2$ is usually not an integer,
and one can even show that some Hadamard matrices give
bounds for (1.1) that are smaller than the
largest integer $<= n sup 1/2$ that is $==~ n$ (mod 2)).
However, for Sylvester matrices of order $n ~=~ 4 sup m$ [8]
it can be shown that the $n sup 1/2$ bound is tight,
since they have a $+- 1$ eigenvector.
.P
Our upper bound for $K(n,^d)$ is obtained from a
simple modification of Knuth's construction [9]
which shows $K( n , ^0) ~<=~ n$ for $n$ even.
It is so simple that we present it
in the introduction.
.H 3 "Theorem 1."
.I
If $n ~>~ 0$, $d ~>=~ 0$, $n ~==~ d$
(mod 2), then
.DS 3
.EQ (1.2)
K(n,^d) ~<=~ left ceiling n over d+1 right ceiling ~,
.EN
.DE
where $left ceiling x right ceiling$ is the least integer
$>= x$.
.R
.H 3 "Proof."
We first consider $d ~=~ 0$, $n ~==~ 0$
(mod 2).
Consider the following $n+1$ by $n$ matrix
.DS 3
.EQ (1.3)
matrix {
rcol {1 above -1 above -1 above "" above -1 above -1}
rcol {1 above 1 above -1 above 3dot above -1 above -1}
rcol { 1 above 1 above 1 above "" above -1 above -1}
ccol {... above ... above ... above "" above ... above ...}
rcol {1 above 1 above 1 above "" above -1 above -1}
rcol {1 above 1 above 1 above "" above 1 above -1}
}
.EN
.DE
and let $vv sub i$, $1 ~<=~ i ~<=~ n +1$, denote the
vector that forms the $i$-th row of (1.3).
We claim that for any $+- 1$ vector $ww$ of length $n$,
$ww ~cdot~ vv sub i ~=~ 0$ for some $i ~<=~ n$.
To see this, note that $ww ~cdot~ vv sub 1 ~=~ - ww ~cdot~ vv sub n+1$,
while $ww ~cdot~ vv sub i ~=~ ww ~cdot~ vv sub i+1 ~+- 2$
for each $i ~<=~ n$, so, since $ww ~cdot~ vv sub i ~==~ 0$
(mod 2)
for all $i$, there is at least one $i ~<=~ n$ such that
$ww ~cdot~ vv sub i ~=~ 0$
(this is something like a discrete mean value theorem).
If $ww ~cdot~ vv sub n+1 ~=~ 0$, then also $ww ~cdot~ vv sub 1 ~=~ 0$,
which establishes our claim that $ww ~cdot~ vv sub i ~=~ 0$
for some $ i ~<=~ n$.
This completes the proof that $K(n,^0) ~<=~ n$ for
$n ~==~ 0$ (mod 2).
.P
The bounds for the other $K(n,^d)$ are obtained by
selecting the vectors $vv sub 1$, $vv sub d+2$,
$vv sub 2d+3 ^,...,^ vv sub r(d+1)+1$, where
$r~=~ left ceiling n/(d+1) right ceiling ~-~ 1$.
Since for any $+- 1$ vector $ww$ and any $j, ~~ 0 ~<=~ i ~<~ r$,
.DS 3
.EQ
| ww ~cdot~ vv sub j(d+1)+1 ~-~ ww ~cdot~ vv sub (j+1)(d+1)+1 |
~<=~ 2d ~+~ 2 ~,
.EN
.DE
an argument similar to the one above shows that
$| ww ~cdot~ vv sub j(d+1)+1 | ~<=~ d$ for at least
one $j,~ 0 ~<=~ j ~<=~ r$.
.tB
.P
Our main result is a proof, given in Section\ 2, that the
construction of Theorem\ 1 is optimal.
.H 3 "Theorem 2."
.I
If $n~>~0$, $d~>=~ 0$, $n~==~d$ (mod 2), then
.DS 3
.EQ (1.4)
K(n,^d) ~>=~ lc n over {d^+^1} rc ^,
.EN
.DE
so that $K(n,^d) ~=~ lc n/(d^+^1) rc$.
.R
.P
The proof we give uses only elementary linear algebra,
and is similar to the proof used in Appendix of [1].
Another, but still related, proof can be given using
commutation algebra and Hilberts' Nullstellinsatz [7].
.P
The proof of Theorem 2 can be used to prove the following
mass general result.
.H 3 "Theorem 3."
.I
Suppose $n~>~0$, and let $D$ be an arbitrary set of integers,
where each $d~member~ D$ satisfies $n~==~d$ (mod 2).
Let $V$ be a set of $+- 1$ vectors of length $n$, such that for
every $+- 1$ vector $uu$ of length $n$, there is a $vv ~member~V$ with
$uu ^cdot vv ~member~ D$.
Then
.DS 3
.EQ (1.5)
| V | ~>=~ n/ | D | ^.
.EN
.DE
.R
.P
Theorem 2 is the special case of this theorem, where
$D~=~ "{" 0,~ +- 2 ,~ +- 4 ^,...,^ +- d "}"$, as
$D ~=~ "{" +- 1 ,~ +- 3 ^,...,^ +- d "}"$.
In general, (1.5) can be very far from best possible.
It would be interesting to find the best possible
bound for various sets $D$.
.P
It is possible to generalize the problem considered here
and consider balancing families of vectors whose components
are $+- 1$, $+- i$, or more generally, with roots of
unity for some fixed $r$.
Some preliminary results in this direction have been
obtained by the last two authors and P.\ Shor.
.P
Our balancing vector problem can be rephrased in
terms of an extremal problem for subsets of a set,
with a $+-^1$ vector $( u sub 1 ^,...,^ u sub n )$ of
length $n$ corresponding to a subset $A$ of $"{" 1 ^,...,^ n "}"$,
with $j ~epsilon~ A$ if and only if $u sub j ~=~ 1$.
F. Galvin recently posed a problem in this setting
that is similar to ours.
He asked for the determination of
the minimal integer $m ~=~ m(n)$ such that there exist subsets
$A sub 1 ^,...,^ A sub m$ of $"{" 1 ^,...,^ 4n "}"$, each
of size $2n$, such that for any subset
$B ~!subset~ "{" 1 ^,...,^ 4n "}"$
with $2n$ elements there is at least one $i$,
$1 ~<=~ i ~<=~ m$, with $A sub i ~cap~ B$ having $n$ elements.
Frankl and Ro\*:dl [5] have noticed that if one defines
$A sub i ~=~ "{" i,~ i+1 ^,...,^ i ~+~ 2n-1 "}"$
for $1 ~<=~ i ~<=~ 2n$, then it is easy to see
that these $A sub i$ have the right property,
and so $m ~<=~ 2n$.
Frankl and Ro\*:dl
proved that $m ~>~ epsilon ~n$ for some fixed
$epsilon ~>~ 0$.
They conjectured initially that $m~=~2n$, but this
was shown to be false by Markert and West (unpublished), who
found using Madamard matrices that $m(2) ~<=~3$ and
$m(4) ~<=~ 7$.
On the other hand, the recent proof [4] of Itos' conjecture
(that every linear subspace of dimension $2n^+^1$ of the space
$GF(2) sup 4n$ has a vector of Manning weight exactly $2n$) leads to
a proof that $m(n) ~=~ 2n$ for $n$ odd.
Although the Galvin problem is somewhat similar to that of
determining $K(2n,^ 0)$, there does not seem to be any simple
dependence between them.
.P
A still different conjecture that is related to the
determination of $K(2n,^0)$ is due to
S.\ Poljak (unpublished).
It states that if $G$ is the graph with vertices
equal to the $2 sup n$ binary vectors of length $n$,
and edges between vertices that are at Hamming distance 1,
then the minimal number of hyperplanes that cut each
edge is exactly $n$.
It is easy to see that $n$ hyperplanes can be found that cut each
edge, but that $>=~ n$ hyperplanes as changes needed has only been
shown for a few values of $n$ by
Z.\ Fu\*:redi and S.\ Poljak.
.P
Our research on balancing sets of vectors was motivated by
a problem in optical data communication
which also arises in other communication areas.
This problem is described in Section\ 3.
.H 1 "Proof of Theorem 2"
Put $N~=~ "{" 1,~ 2^,...,^ n "}"$, and let $U$ be the set
of all $+- 1$ vectors of length $n$.
A vector $uu ~member~ U$ is \f2even\f1 if it has an even
number of \-1's, otherwise it is \f2odd\f1.
.H 3 "Lemma 2.1."
.I
Let $P ( yy ) ~=~ P ( y sub 1 ,~ y sub 2 ^,...,^ y sub n )$ be
a multilinear polynomial of degree less than $n/2$ over the reals,
i.e.,
$P ~=~ SIGMA left { alpha sub X ^cdot^ prod from {i member X} ~y sub i :~~
X~subset~N,~ | X | ~<~ n/2 right }$ where
$alpha sub X ~member~ R$.
If $P ( yy ) ~=~ 0$ for every even vector
$yy ~member~ U$ than $P~==~0$
(i.e., $alpha sub X ~=~ 0$ for all $X$).
Similarly, if $P ( yy ) ~=`0$ for every odd vector $yy ~member~ U$,
then $P~==~0$.
.R
.H 3 "Proof."
We can prove the even case.
(The odd case is analogous.)
By the hypotheses, for every even subset $Y~subset~N$ we have
.DS 3
.EQ
SIGMA left { alpha sub X (-1) sup {| Y cap X |} :~~ X~subset~ N,~~
| X | ~<~ n/2 right } ~=~ 0 ^.
.EN
.DE
It thus suffices to check that the columns of the matrix
.DS 3
.EQ
A ~=` ( alpha sub {Y,X} ) ~=~
((-1) sup {| Y cap X |} ) ~ Y ~subset~N ,~~
| Y | roman even ;~~ X~subset~N,~ | X | ~<~ n/2
.EN
.DE
are linearly independent (over the reals).
One can easily check that
.DS 3
.EQ
( A sup T A) sub {X sub 1 ,^ X sub 2} ~mark =~
SIGMA left { (-1) sup {| Y cap X sub 1 | ^+^ | Y cap Y sub 2 |} :~~
Y~subset~ N,~ | Y | ~roman even right }
.EN
.sp
.EQ
~lineup =~ SIGMA left { (-1) sup {| Y cap ( X sub 1 ciplus X sub 2 ) |} :~~
Y~subset~ N,~ | Y | ~ roman even right } ^.
.EN
.DE
The last sum is $2 sup n-1$ for $X sub 1 ~=~ X sub 2$.
For $X sub 1 ~!=~ X sub 2$, since
$X sub 1 ~ciplus~ X sub 2 ~!=~ N$, $empty$ this sum is
.DS 3
.EQ
SIGMA left { (-1) sup {| A |} ~2 sup {n- | X sub 1 ciplus X sub 2 | -1} :~~
A~subset~ X sub 1 ~ciplus~ X sub 2 right } ~=` 0 ^.
.EN
.DE
We conclude that $A sup T A$ is nonsingular and hence that $A$ has full
column rank.
This completes the proof of the lemma.
.P
We can now prove Theorem 2.
For simplicity we consider the case $n~==~0$ (mod 4) and
$d~==~0$ (mod 4).
(The proofs for the other cases are analogous.)
Let $V~subset~U$ be a set of vectors such that for every
$u~member~U$ there is a $v~member~V$ with
$| vv ^cdot^ uu | ~<=~ d$.
We must show that $| V | ~>=~ n/(d^+^1)$.
Let $V sub 0$ be the set of all even vectors of $V$ and let
$V sub 1$ be the set of all odd vectors of $V$.
.P
Consider the following polynomial in
$yy ~=~ ( y sub 1 ,~ y sub 2 ^,...,^ y sub n )$;
.DS 3
.EQ
P( yy ) ~=~ prod from {v member V sub 0} ~ ( vv ^cdot^ yy ) ~
prod from {v member V sub 1} ~
( 2 sup 2 ^-^ ( vv ^cdot^ yy ) sup 2 ) ~
prod from {v member V sub 0} ~
(4 sup 2 ^-^ ( vv ^cdot^ yy ) sup 2 ) ^cdot^ ... ^cdot^
prod from {v member V sub 0} ~
(d sup 2 ^-^ ( vv ^cdot^ yy ) sup 2 ) ^.
.EN
.DE
Since $n~==~0$ (mod 4), $( vv sub 1 ^cdot^ vv sub 2 ) ~==~ 0$ (mod 2)
for all $vv sub 1$, $vv sub 2 ~member~ U$.
Also, as is easily checked, for every
$vv sub 1 ,~ vv sub 2~member~ U$,
$( vv sub 1 ^cdot^ vv sub 2 ) ~==~ 0$ (mod 4) if and only if
both $vv sub 1$ and $vv sub 2$ are even or both are odd.
Otherwise, $( vv sub 1 ^cdot^ vv sub 2 ) ~==~ 2$ (mod 4).
By assumption, for every even vector
$yy ~=~ ( y sub 1 ^,...,^ y sub n )~member~U$ there
is a $vv ~member~ V$ with
$| vv ^cdot^ yy | ~<=~ d$, i.e.,
$vv ^cdot^ yy ~member~ "{" 0,~ +- 2 ,~ +- 4 ^,...,^ +- d "}"$.
Since $vv ^cdot^ yy$ can be in
$"{" 0,~ +- 4 ^,...,^ +- d "}"$ only if $vv$ is even,
and can be in $"{" +- 2 ,~ +- 6 ^,...,^ +- (d-2) "}"$ only if
$vv$ is odd, we conclude that for every even
$yy ~member~ U$, $P ( yy ) ~=~ 0$.
.P
Let $P bar ( yy )$ be the multilinear polynomial obtained from
$P ( yy )$ by replacing repeatedly each occurrence of
$y sub i sup 2$ in the standard representation of $P$ as a sum
of monomials by 1.
Clearly $P bar ( yy ) ~=~ P ( yy )$ for all
$yy ~member~U$, and $roman deg ~P bar ~<=~ roman deg ~P$.
Since $P bar ( yy ) ~=~ 0$ for every even
$yy ~member~ U$ and $P bar ~eqsl ~0$,
(since $P bar ( yy ) ~!=~ 0$ for every odd
$yy ~member~ U$), we conclude, by Lemma 2.1, that
$roman deg ~P ~>=~ roman deg ~P bar ~>=~ n/2$.
Therefore
.DS 3
.EQ (2.1)
roman deg ~P ~=~ | V sub 0 | ~+~ d over 2 ~
( | V sub 0 | ~+~ | V sub 1 | ) ~>=~ n/2 ^.
.EN
.DE
.P
We now repeat the above process for odd vectors
$yy ~member~ U$.
Define
.DS 3
.EQ
G( yy ) ~=~ prod from {v member V sub 1 } ~ ( v ^cdot^ yy ) ~
prod from {v member V sub 0 } ~
( 2 sup 2 ^-^ ( v ^cdot^ yy ) sup 2 ) ^cdot^ ... ^cdot^
prod from {v member V sub 1} ~
(d sup 2 ^-^ ( v ^cdot^ yy ) sup 2 ) ^.
.EN
.DE
Observe, as before, that $G( yy ) ~=~ 0$ for every odd
$yy ~member~ U$ and
$G( yy ) ~!=~ 0$ for every even
$yy ~member~ U$.
This implies, as before, that
.DS 3
.EQ (2.2)
| V sub 1 | ~+~ d over 2 ~
( | V sub 0 | ~+~ | V sub 1 | ) ~>=~ n/2 ^.
.EN
.DE
The summation of (2.1) and (2.2) implies that
$(d^+^1) ^| V | ~>=~n$ and completes the proof of Theorem 1.1.
.tB
.H 3 "Remarks:"
Another proof of Theorem 2 can be given using the fact that
the polynomial $P( yy )$ vanishes on the zero set of the ideal
generated by
$y sub 1 sup 2 ^-^1 ^,...,^ y sub n sup 2 ^-^1,~
y sub 1 y sub 2 ^,...,^ y sub n ^-^ 1$.
Hilbert's Nullstellinsatz can then be used
to show that $P$ vanishes identically.
.H 1 "Applications"
The problem which motivated the research reported in this
note arose in optical data communications,
and is similar to the problem that motivated Knuth's investigation [9].
We will regard the basic signal bits used in an
optical channel as $+-$1's.
In many applications, such as data links, where the data
rates are very high but the electronics have to be simple to
be economical, it is desirable to encode information so that the
transmitted stream will have a low d.c. component; i.e.,
in any long block, there will be about as many $+1$'s as $-1$'s.
For other problems and solutions in the design of simple
balanced signal sets, see [2,\|3,\|6,\|10,\|11].
.P
It is possible to encode each $-1$ as $(+1 ^-1)$ and each
$+1$ as $(-1 ^ +1)$, but
this code (called Manchester code) has information rate of $1/2$ and so is very inefficient.
A more efficient method is to take blocks of $m$ bits and encode them in
blocks of $n ~=~ m ~+~ k$ bits, which have exactly as many
$+1$'s as $-1$'s.
For example, since $2 sup 17 ~=~ 131,072$ and
$left ( pile {20 above 10} right ) ~=~ 184,756$, we could take
$m ~=~ 17$ and $n ~=~ 20$.
Similarly, since $2 sup 33 ~=~ 8,589,934,592$ while
$left ( pile {36 above 18} right ) ~=~ 9,075,135,300$, we could
take $m ~=~ 33$ and $n ~=~ 36$.
However, no way is known to efficiently encode or decode
information using these codes [12].
The best algorithm for assigning a unique integer between 1 and
$left ( pile { 2 r above r} right )$ to each subset of size
$r$ of a set of size $2 r$ takes either on the order of $r$ operations
on integers of about $r$ bits when about $r sup 2$ stored
$r$-bit values are available, or about $r sup 2$ operations
when about $r$ stored values are available.
Thus this scheme would probably be practical only
for very small values of $m$ and $n$, where direct
memory lookup is feasible, for example for $m ~=~ 6$
and $n ~=~ 8$.
.P
Proposals have been made to use scramblers to transform
the data stream into a more random-looking sequence
which will therefore have a small average d.c. component.
Scramblers using a linear feedback shift register can be
implemented very efficiently.
However, there are data patterns for which scramblers will
fail, and in data communications, where long repetitions of
a particular data sequence are fairly common, it seems
reasonable to try to protect against even such
pathological cases.
.P
Knuth's and our proposed solution to the d.c. component problem is
to use balancing sets of vectors.
In the very simplest case, corresponding to the
construction for $R(m,^ left floor m/2 right floor )$, we could
take blocks of $m$ data bits
$x sub 1 ^...^x sub m$ and encode them into
$n ~=~ m +1$ bits $y sub 1 ^...^ y sub n$ as follows:
If $| sum x sub i | ~<=~ m/2$, then
$y sub i ~=~ x sub i$ for $1 ~<=~ i ~<=~ m$ and $y sub n ~=~ 1$,
while if $| sum  x sub i | ~>~ m/2$, then
$y sub i ~=~ -x sub i$ for $1 ~<=~ i ~<=~ left floor m/2 right floor$,
$y sub i ~=~ x sub i$ for $left floor m/2 right floor ~<~ i ~<=~ m$,
and $y sub n ~=~ -1$.
It then follows that $| sum ~ y sub i | ~<=~ (n+1)/2$,
so the d.c. component is substantially decreased.
At the other extreme, we can use (for $m$ even) the
construction that achieves $R(m,^ 0)$.
In this case the data block
$(x sub 1 ^,...,^ x sub m )$ would
be encoded as
$(x sub 1 ^ v sub i1 ^,...,^ x sub m ^ v sub im ,^ z sub 1 ^,...,^ z sub k )$,
where $(v sub i1 ^,...,^ v sub im )$ is the vector from
(1.3) that's orthogonal to $(x sub 1 ^,...,^ x sub m )$,
and $z sub 1 ^,...,^ z sub k$ are $+- 1$'s indicating the value of
$i$.
Since we need to distinguish only between $m$ different values
of $i$, we can use $k$ on the order of $log sub 2 ~n$, even
if we select the $z sub i$ so that $z sub 1 ~+~ ... ~+~ z sub k ~=~ 0$
in order for each transmitted block to have zero
d.c. component.
(For $m ~<=~ 924$, for example, we could take
$k ~=~ 12$, as $left ( pile { 12 above 6} right ) ~=~ 924$,
so that encoding and decoding could be implemented
by easy table lookup, with addresses at most 12 bits wide.)
Some other modifications of the basic scheme are discussed
in [9].
If the d.c. component does not have to be zero, we could
use some of the other schemes derived in Theorem\ 1 to obtain
bounds for $K(m,^d)$.
The balancing vector scheme has the advantage that it can be
implemented with very simple electronics even for large
block lengths, which leads to a high information rate.
Furthermore, by making small adjustments in the basic scheme,
it is possible to achieve additional desirable properties, such
as a guaranteed number of internal transitions (i.e.,
differences between neighboring bits) inside each
transmitted block to aid in clock synchronization.
.SG mjb
.ls 2
.bp
.ce
\f3REFERENCES\f1
.sp 2
.VL 7
.LI "[1]"
N. Alon, Sh. Friedland, and G. Kalai,
Regular subgraphs of almost regular graphs,
\f2J. Combinatorial Theory Ser. B 37\f1 (1984), 79-91.
.LI "[2]"
E. E. Bergmann, A. M. Odlyzko, and S. Sangani,
Weight $1/2$ block codes for optical communications, to
be published.
.LI "[3]"
B. S. Basik, The spectral density of a coded binary signal,
\f2Bell System Tech. J. 51\f1 (1972), 921-932.
.LI "[4]"
H. Enomoto, P. Frankl, N. Ito, and K. Nomura,
manuscript in preparation.
.LI "[5]"
P. Frankl and V. Ro\*:dl,
Forbidden intersections, to be published.
.LI "[6]"
J. N. Franklin and J. R. Pierce,
Spectra and efficiency of binary codes without dc,
\f2IEEE Trans. Comm., COM-21\f1 (1972), 1438-1440.
.LI "[7]"
W. Fulton, \f2Algebraic Curves\f1,
Benjamin/Cummings, 1969.
.LI "[8]"
A. V. Geramita and J. Seberry,
\f2Orthogonal Designs,\f1 Lecture Notes in Pure and Applied
Mathematics, Vol.\ 45, Marcel Dekker, 1979.
.LI "[9]"
D. E. Knuth, Efficient balanced codes, \f2IEEE Trans. Information Theory
IT-32\f1 (1986), 51-53.
.LI "[10]"
G. L. Pierobon, Codes for zero spectral density at zero frequency,
\f2IEEE Trans. Information Theory IT-30\f1 (1984), 435-439.
.LI "[11]"
K. A. Schouhamen Immink and G. F. M. Beenker,
Binary transmission codes with higher order spectral zeros at
zero frequency, to be published.
.LI "[12]"
H. S. Wilf, A unified setting for sequencing, ranking, and
selection algorithms for combinatorial objects,
\f2Advances in Math. 24\f1 (1977), 281-291.
.LE
.ls 1
.CS \0 \0 \0 \0 \0 \0