In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.
A code is considered "binary" if the codewords use symbols from the binary alphabet
{
0
,
1
}
. In particular, if all codewords have a fixed length n, then the binary code has length n. Equivalently, in this case the codewords can be considered elements of vector space
F
2
n
over the finite field
F
2
. Let
d
be the minimum distance of
C
, i.e.
d
=
min
x
,
y
∈
C
,
x
≠
y
d
(
x
,
y
)
where
d
(
x
,
y
)
is the Hamming distance between
x
and
y
. The expression
A
2
(
n
,
d
)
represents the maximum number of possible codewords in a binary code of length
n
and minimum distance
d
. The Plotkin bound places a limit on this expression.
Theorem (Plotkin bound):
i) If
d
is even and
2
d
>
n
, then
A
2
(
n
,
d
)
≤
2
⌊
d
2
d
−
n
⌋
.
ii) If
d
is odd and
2
d
+
1
>
n
, then
A
2
(
n
,
d
)
≤
2
⌊
d
+
1
2
d
+
1
−
n
⌋
.
iii) If
d
is even, then
A
2
(
2
d
,
d
)
≤
4
d
.
iv) If
d
is odd, then
A
2
(
2
d
+
1
,
d
)
≤
4
d
+
4
where
⌊
⌋
denotes the floor function.
Let
d
(
x
,
y
)
be the Hamming distance of
x
and
y
, and
M
be the number of elements in
C
(thus,
M
is equal to
A
2
(
n
,
d
)
). The bound is proved by bounding the quantity
∑
(
x
,
y
)
∈
C
2
,
x
≠
y
d
(
x
,
y
)
in two different ways.
On the one hand, there are
M
choices for
x
and for each such choice, there are
M
−
1
choices for
y
. Since by definition
d
(
x
,
y
)
≥
d
for all
x
and
y
(
x
≠
y
), it follows that
∑
(
x
,
y
)
∈
C
2
,
x
≠
y
d
(
x
,
y
)
≥
M
(
M
−
1
)
d
.
On the other hand, let
A
be an
M
×
n
matrix whose rows are the elements of
C
. Let
s
i
be the number of zeros contained in the
i
'th column of
A
. This means that the
i
'th column contains
M
−
s
i
ones. Each choice of a zero and a one in the same column contributes exactly
2
(because
d
(
x
,
y
)
=
d
(
y
,
x
)
) to the sum
∑
x
,
y
∈
C
d
(
x
,
y
)
and therefore
∑
x
,
y
∈
C
d
(
x
,
y
)
=
∑
i
=
1
n
2
s
i
(
M
−
s
i
)
.
The quantity on the right is maximized if and only if
s
i
=
M
/
2
holds for all
i
(at this point of the proof we ignore the fact, that the
s
i
are integers), then
∑
x
,
y
∈
C
d
(
x
,
y
)
≤
1
2
n
M
2
.
Combining the upper and lower bounds for
∑
x
,
y
∈
C
d
(
x
,
y
)
that we have just derived,
M
(
M
−
1
)
d
≤
1
2
n
M
2
which given that
2
d
>
n
is equivalent to
M
≤
2
d
2
d
−
n
.
Since
M
is even, it follows that
M
≤
2
⌊
d
2
d
−
n
⌋
.
This completes the proof of the bound.
