Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Plotkin bound
Résumé
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 . 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 over the finite field . Let be the minimum
distance of , i.e.
where is the Hamming distance between and . The expression represents the maximum number of possible codewords in a binary code of length and minimum distance . The Plotkin bound places a limit on this expression.
Theorem (Plotkin bound):
i) If is even and , then
ii) If is odd and , then
iii) If is even, then
iv) If is odd, then
where denotes the floor function.
Let be the Hamming distance of and , and be the number of elements in (thus, is equal to ). The bound is proved by bounding the quantity in two different ways.
On the one hand, there are choices for and for each such choice, there are choices for . Since by definition for all and (), it follows that
On the other hand, let be an matrix whose rows are the elements of . Let be the number of zeros contained in the 'th column of . This means that the 'th column contains ones. Each choice of a zero and a one in the same column contributes exactly (because ) to the sum and therefore
The quantity on the right is maximized if and only if holds for all (at this point of the proof we ignore the fact, that the are integers), then
Combining the upper and lower bounds for that we have just derived,
which given that is equivalent to
Since is even, it follows that
This completes the proof of the bound.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.