1
$\begingroup$

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.

$\endgroup$

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.