Ê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
Griesmer bound
Résumé
In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension k and minimum distance d.
There is also a very similar version for non-binary codes.
For a binary linear code, the Griesmer bound is:
Let denote the minimum length of a binary code of dimension k and distance d. Let C be such a code. We want to show that
Let G be a generator matrix of C. We can always suppose that the first row of G is of the form r = (1, ..., 1, 0, ..., 0) with weight d.
The matrix generates a code , which is called the residual code of obviously has dimension and length has a distance but we don't know it. Let be such that . There exists a vector such that the concatenation Then On the other hand, also since and is linear: But
so this becomes . By summing this with we obtain . But so we get As is integral, we get This implies
so that
By induction over k we will eventually get
Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity
for any integer a and positive integer k.
For a linear code over , the Griesmer bound becomes:
The proof is similar to the binary case and so it is omitted.
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.