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'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?

share|improve this question
2  
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? –  Dilip Sarwate Aug 29 '12 at 18:56
    
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? –  Dilip Sarwate Aug 29 '12 at 22:17
    
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? –  josh Aug 30 '12 at 15:48
    
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}$ –  Dilip Sarwate Aug 30 '12 at 16:56
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$. –  Dilip Sarwate Aug 30 '12 at 17:03

2 Answers 2

up vote 3 down vote accepted

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$)

share|improve this answer

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$).

share|improve this answer

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.