Canal-U

4.5. Error-Correcting Pairs

We present in this session a general decoding method for linear codes. And we will see it in an example. Let C be a generalized Reed-Solomon code of dimension k associated to the pair (c, d). Then, its dual is again a generalized Reed-Solomon code with the same locator and another column multiplier we will denote by d^ (d dual). Now, consider the codes A and B.  These codes have not been chosen at random. First, notice that the star product of these two codes is the dual of C. Suppose that these codes are known. We will present here an efficient decoding algorithm for C. So, let y be the received word, that is, it is a sum of  a valid codeword and an error vector, and suppose that there have been at most t errors. We define the following kernel that is the set of elements of the code A which are the solutions of this equation. We will see that the kernel associated to the received vector is equivalent to the kernel associated to the error vector. And the reason is very simple. First, notice that the star product of the codes A and B, as we have already said, is the dual of C. Moreover, by definition, the inner product of the code with its dual is 0.  So, the codeword would not affect this system. So, what do we have?  We have that the kernel associated to the received vector is equivalent to the kernel of the received vector. This is because the star product of A and B is the dual code. So, now, we look for a nontrivial element on this kernel, that is, a nontrivial solution of this system, where e is the error vector. Let us define, first, the error locator polynomial associated to the vector c, that is, the root of this polynomial indicate the error position. The evaluation of this element belongs to the code A if, and only if, the dimension of A is greater than t.