1
$\begingroup$

I've been reading about error-correcting codes, and I came across the following definition for a parity-check matrix:

''There is an $(n-k) \times n$ matrix $H$, called a parity check matrix for an $[n,k]$ linear code $\mathcal{C}$, defined by $\mathcal{C} = \{x \in \mathbb{F}^{n}_{q} | Hx^{T} = 0 \}.'' $

Then, the book states that the rows of $H$ will also be linearly independent, but I am having trouble seeing why this is true.

As of now, I've noticed that the map $x \mapsto Hx^{T}$ is a linear transformation from $\mathbb{F}^{n}_{q}$ to $\mathbb{F}^{n-k}_{q}$ with $\mathcal{C}$ being the kernel of this linear transformation, but I can't make the connection to linear independence.

Can anyone help?

  • 0
    what is the name of your book and the name of author ? I think it can help me about my coding theory lesson.2012-10-04

2 Answers 2

4

I think Dilip has it (in a comment above). Remember the Rank-Nullity theorem for this one. ($\mathcal{C}$ is the kernel of the linear transformation described by $H$)

1

For $(n,k,d_{min})$ channel codes there is a parity check matrix $H$ such that a given code is valid if and only if $Hx^T=\overline{0}$ where $\overline{0}$ is a vector of zeros.

The mapping from information bits to the code bits is bijective which you can have when $H$ is of rank ($n-k$). If $H$ is not of rank $n-k$ then I also think that one can not get $d_{min}=3$, for example for (7,4,3) Hamming codes.

In other words when we think $Hx^T=y$ as a linear system of equations in $GF^2$. For all $x^T$ The solution exists and one to one from $x$ to $y$ if $H$ is of full rank (rank=$n-k$).