Ê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
Singleton bound
Résumé
In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary block code with block length , size and minimum distance . It is also known as the Joshibound. proved by and even earlier by .
The minimum distance of a set of codewords of length is defined as
where is the Hamming distance between and . The expression represents the maximum number of possible codewords in a -ary block code of length and minimum distance .
Then the Singleton bound states that
First observe that the number of -ary words of length is , since each letter in such a word may take one of different values, independently of the remaining letters.
Now let be an arbitrary -ary block code of minimum distance . Clearly, all codewords are distinct. If we puncture the code by deleting the first letters of each codeword, then all resulting codewords must still be pairwise different, since all of the original codewords in have Hamming distance at least from each other. Thus the size of the altered code is the same as the original code.
The newly obtained codewords each have length
and thus, there can be at most of them. Since was arbitrary, this bound must hold for the largest possible code with these parameters, thus:
If is a linear code with block length , dimension and minimum distance over the finite field with elements, then the maximum number of codewords is and the Singleton bound implies:
so that
which is usually written as
In the linear code case a different proof of the Singleton bound can be obtained by observing that rank of the parity check matrix is . Another simple proof follows from observing that the rows of any generator matrix in standard form have weight at most .
The usual citation given for this result is , but was proven earlier by . Joshi notes that the result was obtained earlier by using a more complex proof. also notes the same regarding .
Linear block codes that achieve equality in the Singleton bound are called MDS (maximum distance separable) codes.
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.