I understand how Hamming Codes and their error detection works, but I'm confused how the parity check matrix is found. How exactly is this computed?
[Math] Finding the parity check matrix for $(15, 11)$ Hamming Codes
coding-theorycombinatoricsdiscrete mathematicslinear algebra
Related Solutions
The question is very confusing. You say you have 8 codewords. Then you say you want to find a linear code. What, if any, is the connection between the 8 codewords you have and the linear code you want to find?
Then you say you want to use a $(7,4)$ Hamming code. But a $(7,4)$ Hamming code has 16 codewords, so how does this relate to the 8 codewords you say you have?
Then you say you need to find a generator matrix and a parity check matrix. Do you need these for the $(7,4)$ Hamming code? or is this for the 8 codewords you have?
The only part of the question I feel comfortable answering is, yes, you can find a generator matrix from a parity check matrix. Any good text or notes on coding theory should show you how to do that.
Then in the comments you ask whether there is an easier way than just using $(111000000)$, $(000111000)$, and $(000000111)$. I don't know if there is an easier way, since I can't figure out what you are trying to accomplish (see my first three paragraphs). But you can certainly use those vectors to form the generator matrix for an 8-word, 1-error-correcting linear code and, while there may be better ways, I can't imagine a simpler one.
It seems to me that questions about forming generator matrices and turning parity check matrices into generator matrices were answered in your earlier question, Coding Theory and Generating a matrix.
Hints:
(1) The check matrix $H$ of a Hamming code has a property that any two columns of $H$ are linearly independent. For a binary Hamming code with block length $2^r-1$ (where $r \ge 2$), a nice way to generate such a matrix is to write the binary representations of $1,2,3,\ldots,2^r-1$ as the columns.
For example, consider the binary Hamming code with block length $7$ (i.e., $2^3-1$). The binary representations of $1,2,3,4,5,6,7$ are $001,010,011,100,101,110,111$, so a check matrix for one binary Hamming code with block length 7 is:
$$ H = \left(\begin{array}{ccccccc} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1\\ \end{array}\right). $$
To put this in standard form, swap columns around until $H$ is in the form $(A\quad I)$, where $I$ is an identity matrix. In this case, one such permutation of columns is the check matrix
$$ H' = \left(\begin{array}{ccccccc} 0&1&1&1 &1&0&0\\ 1&0&1&1 &0&1&0\\ 1&1&0&1 &0&0&1\\ \end{array}\right) $$
Warning: There are multiple check matrices that satisfy standard form. You'll have to ask your instructor which one you should be looking for.
For your case, let $r=4$ so that you have block length $2^4-1=15$ (so your check matrix will have dimensions $4 \times 15$).
(2) There are several ways to decode a binary Hamming code, but the easiest to explain is syndrome decoding. Let's continue with the block length $7$ Hamming code I defined above with $H'$. Suppose $r = 1001010$ is the received word, a $1 \times 7$ matrix. Define the syndrome as
$$ s = H'r^\top = \left(\begin{array}{ccccccc} 0&1&1&1 &1&0&0\\ 1&0&1&1 &0&1&0\\ 1&1&0&1 &0&0&1\\ \end{array}\right)\left(1001010\right)^\top = \left(\begin{array}{c} 1\\1\\0 \end{array}\right). $$
Note that sums and differences are performed mod 2, i.e., with the $\operatorname{xor}$ operation.
The received word $r$ is the sum of an error word $e$ and the transmitted codeword $c$, i.e., $r = e + c$. Since the Hamming code is a linear code, we have
$$H'r^\top = H'(e+c)^\top = H'e^\top + H'c^\top = H'e^\top + 0.$$
So, we need to find a word $e$ of Hamming weight $1$ such that $H'e^\top = \left(\begin{array}{c} 1\\1\\0 \end{array}\right)$. You can either try all 8 possibilities ($0000000$, $1000000$, $0100000$, ...) or try writing out the product and see if you can figure it out algebraically. See if you can find the pattern! The value of $e$ in this case will be $0010000$, so the decoded word $c = r-e = 1001010-0010000=1011010$.
Best Answer
The duals of the Hamming codes are the Simplex codes, so the parity check matrix of a Hamming code is the generator matrix of a Simplex code.
For a generator matrix of a Simplex code of dimension $k$ over the binary alphabet, you just put all non-zero vectors in $\mathbb{F}_2^k$ as columns into a matrix.
For example a generator matrix of a binary Simplex code of dimension $4$ is given by $$\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$$
By duality, this is a check matrix of a binary $(15,11)$ Hamming code.
For general alphabets $\mathbb{F}_q$, you have to select a system of projective representatives of the non-zero vectors in $\mathbb{F}_q^k$ for the columns.