Vidéo pédagogique

4.5. Error-Correcting Pairs

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

We present in this session ageneral decoding method for linear codes. And we will see it in an example. Let C be a generalizedReed-Solomon code of dimension k associated to the pair (c, d). Then, its dual is again ageneralized Reed-Solomon code with the same locatorand another column multiplier we will denote by d^ (d dual). Now, consider the codes A and B.  These codes have notbeen chosen at random. First, notice that the star productof these two codes is the dual of C. Suppose that these codes areknown. We will present here an efficientdecoding algorithm for C. So, let y be the receivedword, that is, it is a sum of  a valid codeword and anerror vector, and suppose that there have been at most t errors. We define the followingkernel that is the set of elements of the code A which arethe solutions of this equation. We will see that the kernelassociated to the received vector is equivalent to thekernel associated to the error vector. And the reason is very simple. First, notice that the starproduct of the codes A and B, as we have alreadysaid, is the dual of C. Moreover, by definition, theinner product of the code with its dual is 0.  So, the codeword wouldnot affect this system. So, what do we have?  We have that the kernelassociated to the received vector is equivalent to thekernel of the received vector. This is because the starproduct of A and B is the dual code. So, now, we look for anontrivial element on this kernel, that is, a nontrivialsolution of this system, where e is the error vector. Let us define, first, theerror locator polynomial associated to the vectorc, that is, the root of this polynomial indicatethe error position. The evaluation of thiselement belongs to the code A if, and only if, thedimension of A is greater than t.

Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 4.5. Error-Correcting Pairs. [Vidéo]. Canal-U. (Consultée le 20 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème