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?

  • 3
    Since $\mathcal C$ is the set of all vectors in $\mathbb F_q^n$ that are mapped to $0 \in $\mathbb F_q^{n-k}$, $\mathcal C$ is the _kernel_ of the linear transformation from $\mathbb F_q^n$ to $\mathbb F_q^{n-k}$ that is specified by $H$. We are given that $\mathcal C$, regarded as a subspace of $\mathbb F_qT^n$ has dimension $k$. Would this statement about dimensionality be true if the rows of $H$ were linearly dependent?2012-08-29
  • 0
    With typos corrected (I hope!) Since $\mathcal C$ is the set of all vectors in $\mathbb F_q^n$ that are mapped to $0 \in \mathbb F_q^{n-k}$, $\mathcal C$ is the _kernel_ of the linear transformation from $\mathbb F_q^n$ to $\mathbb F_q^{n-k}$ that is specified by $H$. We are given that $\mathcal C$, regarded as a subspace of $\mathbb F_q^n$ has dimension $k$. Would this statement about dimensionality be true if the rows of $H$ were linearly dependent?2012-08-29
  • 0
    Here's what I'm thinking after your comment: By the rank-nullity theorem, we have that $n = dim(\mathbb{F}^{n}_{q}) = dim(\mathcal{C}) + dim(Hx^{T}) = k + (n-k)$. If the rows of $H$ were not linearly independent, then $H$ would have a rank less than $n - k$, which would imply that $dim(Hx^{T}) < n-k$. Am I heading in the right direction?2012-08-30
  • 0
    Pretty much yes. In terminology more commonly used in coding theory, the $k$ rows of the generator matrix $G$ are the basis vectors of $\mathcal C$, a $[n,k]$code, and the $n-k$ rows of the parity check matrix $H$ are the basis vectors of the _dual code_ $\mathcal C^{\perp}$ which is a $[n,n-k]$ code, and $HG^T = 0$, that is, every vector in $\mathcal C$ is orthogonal to every vector in $\mathcal C^{\perp}$2012-08-30
  • 1
    _Any_ matrix $H$ with $n$ columns (and at least $n-k$ rows) which enjoys the property that $Hx^T = 0$ if and only if $x \in \mathcal C$, a $[n,k]$ code, can be called a parity check matrix for the code. For some decoding purposes (e.g. BCH codes), it is convenient to use a $H$ with more rows than $n-k$, but since $\mathcal C$ is the kernel of the linear transformation defined by $H$, $H$ must have row rank $n-k$.2012-08-30
  • 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$).