Understanding dimension of Goppa code

177 Views Asked by At

My concern is regarding the understanding of the dimension of Goppa Codes and the corresponding dimension of its parity check matrix. The classical definition often referred to as classical view of Goppa Code is given by the set:

$$\Gamma : = \{ c \in \mathbb{F}_{2}^{n} \hspace3pt | \hspace3pt S(c) = \frac{c_{1}}{x - a_{1}} + \frac{c_{2}}{x - a_{2}} + \cdots + \frac{c_{n}}{x - a_{n}} \mod g = 0 \}$$

where, each element in the sequence of code locators $(a_1, a_2, \dots, a_n)$ is an element of $\mathbb{F}_{{2}^{m}}$, $g$ is a square free polynomial of degree $t$ in $\mathbb{F}_{{2}^m}[x]$ such that $g(a_i) \neq 0 \hspace 6 pt\forall i \in \{1, 2, \dots, n\}$, for example an irreducible polynomial in $\mathbb{F}_{{2}^m}[x]$.

My understanding:
$S$ is a linear combination of polynomials $\frac{1}{x - a_i}$ each of degree at most $t-1$. This is because:
$g(a_i) \neq 0 \implies gcd((x - a_i), g) = 1 \implies \exists (x - a_i)^{-1} \in \mathbb{F}_{{2}^m}[x] / g $.
$$\implies (x - a_i)^{-1} \equiv p_{i}(x) = \sum_{j=0}^{t-1} p_{i,j} \cdot x^j \mod g$$.

With the help of the above form, we can represent the polynomial $S$ in $\Gamma$ as: $$S(c) = \sum_{i=1}^{n}c_i \large(\sum_{j=0}^{t-1} p_{i,j} \cdot x^j \large)$$ $$ \iff S(c) = \sum_{j=0}^{t-1} \large(\sum_{i=1}^{n} c_i \cdot p_{i,j} \large)x^j $$. $$\implies \sum_{i=1}^{n} c_i \cdot p_{i,j} = 0 $$.

From the literature, I read that the parity-check matrix which is basically a matrix whose right-kernel space forms the set of the linear code, that is, $H \cdot c^{T} = 0 \hspace3pt \forall c \in \Gamma.$

My Question I can not understand why the kernel matrix $H$ has the dimension $mt \times n$. Can someone please help me to understand how does the factor $m$ come about?

1

There are 1 best solutions below

3
On BEST ANSWER

You got your symbols crossed, or there is a typo.

Dimension is usually referred to by $k.$ The parity check matrix is actually size $tm\times n$. The dimension is $$k\geq n-tm$$ since some of those rows might be linearly dependent.

See the talk by Tanja Lange here where she carefully explains this.