[Math] Coding Theory and Generating a matrix

coding-theory

My question is: How can I construct a generator matrix for a one-error correcting linear code with 8 codewords? What would the values of the parameters [n,k] be and what would the size of the parity check matrix be?

Does this mean that I need to find a Code that is one error-correcting?

I think this means that the minimum distance between two of the vectors is 3?

Best Answer

If a $[n,k]$ linear binary code has $8$ codewords, you are being told that $k = \log_2 8 = 3$; an $[n,k]$ binary code has $2^k$ codewords. As discussed in Jyrki Lahtonen's answer to another question that you asked today, the Hamming spheres of radius $1$ centered at the $8$ codewords must not have any vectors in common. Since there are $1 + \binom{n}{1} = 1+n$ vectors in each such sphere, and $2^n$ vectors total, $n$ must be large enough so that $$2^n \geq 8(n+1) \Rightarrow n \geq 6.$$ Note also that you are asked for the generator matrix of the code which is a $k\times n$ matrix whose row-space (set of all $2^k$ linear combinations of the rows) is the set of codewords. So you could take the vectors suggested to you by Gerry Myerson as the rows of the generator matrix.

Be aware that shorter codes ($n$ smaller that $9$) can also be found. If you know about single-error-correcting Hamming codes, you can write down a $[7,4]$ code or a $[7,3]$ consisting of all the even weight codewords of the former, that can correct single errors.

Related Question