Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.