# Proper way to create Goppa code check matrix?

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

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?

-
You do see that $YZ$ is the same as $H$ of your first example, right? A code is a subspace that is the null space of a parity check matrix, and different parity check matrices can be used to define the code. If $H$ is a $(n-k)\times n$ parity check matrix, so is $AH$ for any nonsingular $(n-k)\times(n-k)$ matrix, and in your example, $X$, being a lower triangular matrix, is nonsingular. Decoding algorithms use specific forms of matrices because they need specific forms of the syndrome of the received word. – Dilip Sarwate May 14 '12 at 13:54
Yeah, noticed that $YZ=H_1$ - I mostly was puzzled about why would those papers use different check matrices when all of them use the same decoding algorithm (Algebraic decoding, as seen in Overview paper). Even more confusion for me was caused by the fact that my implementation of the decoding from Overview (thus logically using $H_3$) only works with the $H_2$. – exa May 14 '12 at 15:22

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.