Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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: 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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.