Plotkin bound

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. 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 } {displaystyle {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 {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. Theorem (Plotkin bound): i) If d {displaystyle d} is even and 2 d > n {displaystyle 2d>n} , then ii) If d {displaystyle d} is odd and 2 d + 1 > n {displaystyle 2d+1>n} , then iii) If d {displaystyle d} is even, then iv) If d {displaystyle d} is odd, then where ⌊   ⌋ {displaystyle leftlfloor ~ ight floor } denotes the floor function.