Determining properties of linear code from generator matrix

Question

I have a problem in error-correcting codes.

Say we have a generator matrix of a linear binary code

$$g=\begin{pmatrix} 10011 \\ 01101 \end{pmatrix} $$

Q1: How many different codeword do we have? How many code bits can the code correct?

Say the generator matrix of a $(6,2)$ binary code is $$g=\begin{pmatrix} 101001\\ 011111 \end{pmatrix}$$

Q2: How many errors can it guarantee to detect?

My try:

For Q1:

The way I find the number of codeword is count the number of rows in $g$ and raise it as a power to 2. So the answer is $2^2=4$.

For detecting and correcting I’m not sure, should I find the hamming distance and subtract 1?

I hope someone can explain to me how I can find the number bits I can detect and correct.

Answer 1

If the minimal distance is $d$, then

• Up to $d-1$ errors can be detected. This means that if a sent codeword is modified by flipping at least one and up to $d-1$ bits, then the receiver can tell that some bits were flipped.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping at least one and up to $d-1$ bits. Since $1 \leq d_H(w,w') < d$ (where $d_H$ is Hamming distance), we see that $w'$ is not a codeword (since the distance between any two different codewords is always at least $d$), and so we can detect that errors have occurred.

• Up to $\lfloor \frac{d-1}{2} \rfloor$ can be corrected. This means that if a sent codeword is modified by flipping at most $\lfloor \frac{d-1}{2} \rfloor$ bits, then the original codeword can be recovered.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping up to $\lfloor \frac{d-1}{2} \rfloor$ bits. I claim that $w$ is the unique codeword at distance at most $\lfloor \frac{d-1}{2} \rfloor$ from $w'$. Indeed, if $z$ were another such codeword then $$ d_H(w,z) \leq d_H(w,w') + d_H(w',z) \leq 2 \lfloor \tfrac{d-1}{2} \rfloor < d, $$ contrary to the definition of minimal distance.