This article only references primary sources. Please help improve this article by adding secondary or tertiary sources.Find sources: "Plotkin bound" – news · newspapers · books · scholar · JSTOR (October 2024) (Learn how and when to remove this message)
This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: "Plotkin bound" – news · newspapers · books · scholar · JSTOR (October 2024)
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.
Statement of the bound[edit]A code is considered "binary" if the codewords use symbols from the binary alphabet { 0 , 1 } {\displaystyle \{0,1\}} . In particular, if all codewords he 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 {\displaystyle \mathbb {F} _{2}^{n}} over the finite field F 2 {\displaystyle \mathbb {F} _{2}} . Let d {\displaystyle d} be the minimum distance of C {\displaystyle C} , i.e.
d = min x , y ∈ C , x ≠ y d ( x , y ) {\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}
. In particular, if all codewords he 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
{\displaystyle \mathbb {F} _{2}^{n}}
over the finite field
F
2
{\displaystyle \mathbb {F} _{2}}
. Let
d
{\displaystyle d}
be the minimum distance of
C
{\displaystyle C}
, i.e.
where d ( x , y ) {\displaystyle d(x,y)} is the Hamming distance between x {\displaystyle x} and y {\displaystyle y} . The expression A 2 ( n , d ) {\displaystyle A_{2}(n,d)} represents the maximum number of possible codewords in a binary code of length n {\displaystyle n} and minimum distance d {\displaystyle d} . The Plotkin bound places a limit on this expression.
is the Hamming distance between
x
{\displaystyle x}
and
y
{\displaystyle y}
. The expression
A
2
(
n
,
d
)
{\displaystyle A_{2}(n,d)}
represents the maximum number of possible codewords in a binary code of length
n
{\displaystyle n}
and minimum distance
d
{\displaystyle d}
Theorem (Plotkin bound):
i) If d {\displaystyle d} is even and 2 d > n {\displaystyle 2d>n} , then
A 2 ( n , d ) ≤ 2 ⌊ d 2 d − n ⌋ . {\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}
, then
ii) If d {\displaystyle d} is odd and 2 d + 1 > n {\displaystyle 2d+1>n} , then
A 2 ( n , d ) ≤ 2 ⌊ d + 1 2 d + 1 − n ⌋ . {\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .}
, then
iii) If d {\displaystyle d} is even, then
A 2 ( 2 d , d ) ≤ 4 d . {\displaystyle A_{2}(2d,d)\leq 4d.}
iv) If d {\displaystyle d} is odd, then
A 2 ( 2 d + 1 , d ) ≤ 4 d + 4 {\displaystyle A_{2}(2d+1,d)\leq 4d+4}
where ⌊ ⌋ {\displaystyle \left\lfloor ~\right\rfloor } denotes the floor function.
Proof of case i[edit]
denotes the floor function.
Let d ( x , y ) {\displaystyle d(x,y)} be the Hamming distance of x {\displaystyle x} and y {\displaystyle y} , and M {\displaystyle M} be the number of elements in C {\displaystyle C} (thus, M {\displaystyle M} is equal to A 2 ( n , d ) {\displaystyle A_{2}(n,d)} ). The bound is proved by bounding the quantity ∑ ( x , y ) ∈ C 2 , x ≠ y d ( x , y ) {\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)} in two different ways.
be the number of elements in
C
{\displaystyle C}
in two different ways.
On the one hand, there are M {\displaystyle M} choices for x {\displaystyle x} and for each such choice, there are M − 1 {\displaystyle M-1} choices for y {\displaystyle y} . Since by definition d ( x , y ) ≥ d {\displaystyle d(x,y)\geq d} for all x {\displaystyle x} and y {\displaystyle y} ( x ≠ y {\displaystyle x\neq y} ), it follows that
∑ ( x , y ) ∈ C 2 , x ≠ y d ( x , y ) ≥ M ( M − 1 ) d . {\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}
choices for
y
{\displaystyle y}
for all
x
{\displaystyle x}
), it follows that
On the other hand, let A {\displaystyle A} be an M × n {\displaystyle M\times n} matrix whose rows are the elements of C {\displaystyle C} . Let s i {\displaystyle s_{i}} be the number of zeros contained in the i {\displaystyle i} 'th column of A {\displaystyle A} . This means that the i {\displaystyle i} 'th column contains M − s i {\displaystyle M-s_{i}} ones. Each choice of a zero and a one in the same column contributes exactly 2 {\displaystyle 2} (because d ( x , y ) = d ( y , x ) {\displaystyle d(x,y)=d(y,x)} ) to the sum ∑ ( x , y ) ∈ C , x ≠ y d ( x , y ) {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)} and therefore
∑ ( x , y ) ∈ C , x ≠ y d ( x , y ) = ∑ i = 1 n 2 s i ( M − s i ) . {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)=\sum _{i=1}^{n}2s_{i}(M-s_{i}).}
be an
M
×
n
{\displaystyle M\times n}
matrix whose rows are the elements of
C
{\displaystyle C}
be the number of zeros contained in the
i
{\displaystyle i}
'th column of
A
{\displaystyle A}
ones. Each choice of a zero and a one in the same column contributes exactly
2
{\displaystyle 2}
(because
d
(
x
,
y
)
=
d
(
y
,
x
)
{\displaystyle d(x,y)=d(y,x)}
) to the sum
∑
(
x
,
y
)
∈
C
,
x
≠
y
d
(
x
,
y
)
{\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)}
and therefore
The quantity on the right is maximized if and only if s i = M / 2 {\displaystyle s_{i}=M/2} holds for all i {\displaystyle i} (at this point of the proof we ignore the fact, that the s i {\displaystyle s_{i}} are integers), then
∑ ( x , y ) ∈ C , x ≠ y d ( x , y ) ≤ 1 2 n M 2 . {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.}
holds for all
i
{\displaystyle i}
Combining the upper and lower bounds for ∑ ( x , y ) ∈ C , x ≠ y d ( x , y ) {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)} that we he just derived,
M ( M − 1 ) d ≤ 1 2 n M 2 {\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}
which given that 2 d > n {\displaystyle 2d>n} is equivalent to
M ≤ 2 d 2 d − n . {\displaystyle M\leq {\frac {2d}{2d-n}}.}
Since M {\displaystyle M} is even, it follows that
M ≤ 2 ⌊ d 2 d − n ⌋ . {\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}
This completes the proof of the bound.
See also[edit] Diamond code Elias Bassalygo bound Gilbert–Varshamov bound Griesmer bound Hamming bound Johnson bound Singleton bound References[edit] Plotkin, Morris (1960). "Binary codes with specified minimum distance". IRE Transactions on Information Theory. 6 (4): 445–450. doi:10.1109/TIT.1960.1057584.