1
$\begingroup$

How to design a $(8,4)$ linear block code with highest possible error correction and error detection capability?

I have studied linear block codes topic but if I do the conventional way, in case of $(n,k)$ block code, I need a generator matrix which is given as $\mathbf G=[\mathbf P|\mathbf I_k]$, where $\mathbf P$ is the parity matrix and $\mathbf I_k$ the identity matrix. But to find parity matrix I need to find the code words. But how to do that? Since third codeword should be the addition of first two code words. Any kind of help will be appreciated.

$\endgroup$
  • $\begingroup$ @DilipSarwate Thanks for the answer. But my professor expects me to write the best code words possible. $\endgroup$ – user12083 Mar 23 '15 at 19:46
  • 1
    $\begingroup$ Look in your textbook (or on the Internet) for extended Hamming codes. $\endgroup$ – Dilip Sarwate Mar 24 '15 at 13:25
3
$\begingroup$

In this answer, I will focus on error correction. I will use as little coding theory as possible, and I'll try to approach the problem from the point of view of a novice taking their first steps in code design.

Our objective is to find the best (8,4) linear block code possible, that is, one that corrects as many bit errors as possible. Is it possible to know in advance how good an (8,4) code can be? To answer this question, we have an invaluable tool: the Hamming bound. It says that a $(n,k)$ code that can correct $t$ errors must satisfy

$$ \sum_{i=0}^t \binom{n}{i} \leq 2^{n-k}. $$

It is easy to write a program that takes $n$ and $k$ as arguments, and outputs the largest $t$ that satisfies the bound. For $n=8$ and $k=4$, we find that the largest possible $t$ is 1. Note that, since the minimum distance is given by

$$ d_{min} = \lfloor (t-1)/2 \rfloor, $$

we still don't know whether the best code has $d_{min}=3$ or $d_{min}=4$. Both will have the same error correcting capabilites, but the code with minimum distance 4 has additional error detecting capabilities.

(Note that, even if there exist numbers $(n,k,t)$ that satisfy the Hamming bound, it is not guaranteed that a $(n,k,t)$ code actually exists. However, if the bound is not satisfied, we know for sure that no such code exists.)

Now that we have a goalpost ($d_{min}=4$), we can focus on finding a code that achieves it. We know that the generator matrix $G$ has $k$ rows and $n$ columns. In its systematic form, $G=[I_k|P]$, where $P$ has $k$ rows and $n-k$ columns. For our (8,4) code, we have to find a matrix $P$ with 4 rows and 4 columns.

Since we don't have any other tools at this point, we can try a brute-force approach, since there are "only" $2^{16}$ possible matrices $P$ (actually a bit less, since we don't want to repeat any columns). Let's try this matrix:

$$ P=\begin{bmatrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1\end{bmatrix}. $$

It is not hard to write a program that generates all 16 possible code words using $P$. The final step is to verify if our code has $d_{min}=4$. This is easy, since the code is linear; all we have to do is find the non-zero code word with smallest weigth (with smallest number of ones). For the matrix $P$ given above, it turns out that $d_{min}=2$, so the code is not the best possible.

It is easy to find generator matrices with $d_{min}=3$; extending the distance to 4 takes a bit more work.

In conclusion:

  • The Hamming bound can be used to determine what values of $t$ and (approximate) $d_{min}$ we can expect from a code with small $n$ and $k$. For large $n$ and $k$, the achievable value of $t$ may be much less than that given by the bound. Surprisingly, determinining $t$ for given $n$ and $k$ is (for the general case) an unsolved problem.

  • Design by brute force (by trying many $P$ matrices) is feasible only for small codes. Even for an (8,4) code you may have to try more than 60,000 possibilities. The number grows exponentially with the code size. The amount of work required to generate the entire code, and to determine $d_{min}$ by inspection, soon grows so large that it becomes entirely unfeasible.

  • It is for this reason that so much research has been done into techniques that allow for less complex design of large codes. When you study other codes, such as cyclic and convolutional codes, keep in mind this motivation. You probably shouldn't try to solve your problem using the brute-force technique outlined here except to get a feel for the sheer magnitude of the computational complexity involved in the design of good codes, and also in their encoding and decoding procedures.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I did try to manually write the linear block code for (8,4) but that was like hit and trial. But another question that comes now is that is this code unique? Because the answer might vary with every individual. Also the generator matrix will be unique? The minimum hamming distance i get is 3. But other code words also have distance as 4,5. $\endgroup$ – user12083 Mar 23 '15 at 19:42
  • $\begingroup$ @user12083 Please see the edited answer. Also: the generator matrix is not unique. And, I'd suggest following Dilip's advice to look at the extended Hamming codes, since the best (8,4) code belongs to this family. Looking into it will make solving your problem much easier. $\endgroup$ – MBaz Mar 24 '15 at 0:45
  • $\begingroup$ +1 for a very good answer! Thank you for taking the time to improving it and making it really useful. I am deleting my comments on the main question since they are no longer applicable to the revised version, and substituting a new comment re the extended Hamming codes only. $\endgroup$ – Dilip Sarwate Mar 24 '15 at 13:22
  • $\begingroup$ @DilipSarwate Thanks for pointing out the flaws in the original answer and for prodding me to improve it. $\endgroup$ – MBaz Mar 24 '15 at 14:10
2
$\begingroup$

MBaz's revised answer gives all the information necessary to solve the problem, but here is a slightly different take on it.

A binary code of length $n$ cannot have a minimum distance that exceeds $\frac n2$. Essentially, the idea is that one cannot go more than half-way into a forest; after one has passed the midpoint, one is coming out of the forest!

Be that as it may, for a linear code, the minimum distance is the same as the minimum weight (least weight of all the nonzero codewords) of the code. So, for a $[8,4]$ binary code with generator matrix $G = [I \mid P]$ where $I$ is the $4\times 4$ identity matrix and $P$ a $4\times 4$ matrix that we can choose, let's choose the rows of $P$ as the $\binom{4}{3}= 4$ binary vectors of Hamming weight $3$, thus making each row of $G$ a vector of weight $4$. Note that the columns of $P$ are also vectors of weight $3$; indeed, one option is to complement all the bits of $I$ and take the result to be $P$ !! This choice also has the advantage that the right half of each row of $G$ is just the complement of the left half.

How about the sum of two rows of $G$? Well, the left $4$ positions contribute a weight of $2$ as do the right $4$ positions, and so these codewords also have weight $4$. There are $\binom{4}{2} = 6$ such codewords.

How about the sum of $3$ rows of $G$? Well, the left four positions contribute a weight of $3$ while in the right four positions, in three positions, we are summing $2$ ones and a zero, and in the fourth we are summing three ones for a total contribution of $1$ to the weight. So these $\binom{4}{3}= 4$ codewords also have weight $4$.

Finally, the sum of all $4$ rows of $G$ is just the all-ones vector, and we are done. We have shown that all $4+6+4+1 = 15$ nozero codewords of this linear code have weight $4$ or $8$, and so the minimum weight (and hence the minimum distance) of the code is $4$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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