Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called the rank-metric. This allows us to consider error-correcting codes in this space.

One example of codes in this metric are Gabidulin codes, which are analogues of Reed-Solomon codes. Essentially, we consider the rows of an $n \times m$ matrix as elements of the extension field $\mathbb{F}_{q^m}$. So now we consider the space of linearized polynomials over $\mathbb{F}_{q^m}$ of q-degree k-1 as the set of messages, and to get a codeword, we evaluate such a polynomial at $n$ evaluation points $g_1, g_2, \dots, g_n \in \mathbb{F}_{q^m}$ which are linearly independent as vectors over the base field $\mathbb{F}_q$, giving a vector in $\mathbb{F}_{q^m}^n$ which we can then interpret again as a matrix in $\mathbb{F}_q^{n \times m}$. This code, just like Reed-Solomon codes, has distance $n-k+1$.

Now consider the decoding of such codes. We shall consider the analogue of the Berlekamp-Welch decoder for Reed-Solomon codes. We are given a word $(y_1,y_2,\dots,y_n)^T$ within a distance (according to the rank-metric) of $t$ from a codeword corresponding to the linearized polynomial $f$ say, and our aim is to algorithmically find $f$ when $t$ is less than half of the distance. This is worked out in the following paper: http://perso.univ-rennes1.fr/pierre.loidreau/articles/wcc_2005/Welch_Berlekamp.pdf If you are familiar with the Berlekamp-Welch decoder, this paper should be easy enough to read through quickly. In the paper, consider proof of proposition 2 in section 4. There, it claims that

"Now let us consider a non-zero solution $(V_0,P_0)$ of 1), then any solution $(V,N)$ of 2) satisfies the following system of equations:

$$V_0[N(g_i)-V(P_0(g_i))]=0 $$ $\forall i=1,\dots,n$"

How is this equation obtained? The paper states it as if its obvious, but I am unable to prove this. Any help would be appreciated. Thanks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.