0
$\begingroup$

I am studying Quantum error correction that is based on some aspects on classical error correction.

I am reading some very basics around linear error correcting codes.

I consider a linear code [n,k]: thus it encodes k bits of information into n bits.

My question: I don't understand why the parity check matrix has $n-k$ lines.


What I understand from the topic.

If I call $x$ the column vector of the information bits I want to encode in the n-bits, I define $G$ the generator matrix such that:

$$ y = G x $$

Where $y$ is my encoded information.

The $H$ matrix is built such that its kernel is the code space. Thus, its kernel must be composed of the column vectors of $G$ as the code space is spanned by the column vectors of $G$.

All this means that the line vectors of $H$ must be orthogonal to the column vectors of $G$.

But why do we have to take $n-k$ lines in $H$, why not $n$ lines, or $2$ lines ? I guess it is a way to ensure us that the Kernel of $H$ is exactly the code space but I don't understand why this number of lines ensure this.

$\endgroup$

2 Answers 2

2
$\begingroup$

You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows. You can apply the rank-nullity theorem. If you like, think of the rank of $H$ as the number of pivots you get, when you row reduce. It is the same number you get when you column reduce. Now for $H$ is a $s\times n$-matrix with kernel of dimension $k$. That means by the rank-nullity theorem that $\mathrm{rank}~H+k=n$. So $\mathrm{rank}~H=n-k$ but rank is just the number of pivots (either from row or column reducing). Said another way, $s\geq n-k$ and if $s>n-k$ then after row reducing you get just $n-k$ nonzero rows. So the most compact $H$ is $(n-k)\times k$.

Usually one thinks of generator and parity check matrices as having been row/column reduced with 0 rows serving no purpose so omitted. That forces your dimensions. But yes in principal you could repeat yourself, it just wouldn't help or be what anyone expects. But no, you can't choose just 2 that will make for a larger kernel in general.

$\endgroup$
1
  • $\begingroup$ Thanks. Actually I'm not very used to linear algebra with not square matrices so I don't have much intuition but I see what you mean $\endgroup$
    – StarBuck
    Jul 24, 2019 at 15:03
0
$\begingroup$

If you have k input bits and n output bits, you need to compute only n-k extra bits, so the matrix should be k * (n-k). You multiply the input vector by the matrix and get the extra bits vector.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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