I'm trying to figure out what is the correct way to compute a check matrix for a binary Goppa code. So far (searching through the publications) I've found more than one possibility to do that, and I'm not sure how all those are related.
Suppose I have a Goppa code with irreducible Goppa polynomial $g(x)$ of degree $t$ over $GF(2^m) \simeq F[x]/F[p(x)]$ where $p(x)$ is defining polynomial of the field with degree $m$, and a support $\{l_1, l_2, l_3, \dots\} \subseteq GF(2^m) = \{u^0, u^1, u^2, \dots, u^{2^m-1}\}$.
In various sources, following three ways are described to create a check matrix.
- Marta Giorgetti, Interesting examples on maximal irreducible goppa codes, page 2:
$ H_1 = \left( \begin{array}{cccc}
\frac{1}{g(l_1)} & \frac{1}{g(l_2)} & \dots & \frac{1}{g(l_n)} \\
\frac{l_1}{g(l_1)} & \frac{l_2}{g(l_2)} & \dots & \frac{l_n}{g(l_n)} \\
\vdots & & & \\
\frac{l_1^{t-1}}{g(l_1)} & \frac{l_2^{t-1}}{g(l_2)} & \dots & \frac{l_n^{t-1}}{g(l_n)} \\
\end{array} \right) $
- In the same paper, page 3:
$ H_2 = \left( \frac{1}{x – l_1}, \frac{1}{x – l_2}, \dots, \frac{1}{x – l_3} \right) $
(resulting polynomials are expanded as vertical vectors)
- In Engelbert, Overbeck, Schmidt, A summary of McEliece-type cryptosystems
and their security, page 10:
$H_3 = XYZ$
where
$ X = \left( \begin{array}{cccc}
g_t & 0 & \dots & 0 \\
g_{t-1} & g_t & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
g_1 & g_2 & \dots & g_t \\
\end{array}\right) $
$ Y = \left( \begin{array}{cccc}
1 & 1 & \dots & 1 \\
l_1 & l_2 & \dots & l_n \\
l_1^2 & l_2^2 & \dots & l_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
l_1^{t-1} & l_2^{t-1} & \dots & l_n^{t-1} \\
\end{array}\right) $
$ Z = \left( \begin{array}{cccc}
\frac{1}{g(l_1)} & & & \\
& \frac{1}{g(l_2)} & & \\
& & \ddots & \\
& & & \frac{1}{g(l_n)} \\
\end{array}\right) $
My question is why there are more different definitions – whether they are
equivalent, or serve a different purpose, and which of those (and why) would
work with the algebraic decoding algorithm described in the Overview paper.
Thanks
-exa
EDIT – additional question:
All three matrices probably have something in common (e.g. $YZ = H_1$). Question is: What impact does the additional information in H (e.g. the $X$ matrix) have on code properties, and how would that affect/enhance the decoding?
Best Answer
A linear $[n,k]$ code is a $k$-dimensional subspace of an $n$-dimensional vector space over a finite field. It is often defined as the null space of a $(n-k)\times n$ matrix $H$ called a parity check matrix, that is, $\mathbf C$ is a codeword if and only if $H\mathbf C^T = \mathbf 0$. If $A$ is any nonsingular $(n-k)\times (n-k)$ matrix, then $\hat{H}=AH$ is also a parity check matrix for the same code. It is common practice in coding theory to use different parity check matrices for the same code depending on the particular application. For example, an encoder which needs to compute the parity check symbols $p_j$ given the data symbols $d_i$, that is, to find the codeword $$\mathbf C = [d_1,d_2,\ldots, d_k, p_1,p_2, \ldots p_{n-k}]$$ given the data symbols $\mathbf d = [d_1, d_2, \ldots, d_k]$, can use a parity check matrix of the block form $\left [B_{(n-k) \times k} \mid I_{(n-k)\times (n-k)}\right]$ which gives each $p_j = -B_{(n-k) \times k}\mathbf d^T$ as a linear combination of the $d_i$. On the other hand, a decoder (for a BCH code) might use a Vandermonde matrix $\hat{H}$ that has the same null space. That is, $\hat{H}\mathbf C^T = H\mathbf C^T = \mathbf 0$ for all codewords, but the decoder wants to compute the syndrome $\hat{\mathbf S}$ of the received word $\mathbf R$ in the form $\hat{\mathbf S}^T = \hat{H}\mathbf R^T$ rather than first find $\mathbf S^T = H\mathbf R^T$ and then use $\hat{\mathbf S}^T = A\mathbf S^T$ to get the syndrome in the form it needs.
So, to answer the OP's question, different parity check matrices defining the same code are commonly used in coding theory depending on the application. The three different forms shown are very similar and might even define the same code; certainly the first and third forms are equivalent.