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$.
The eight-bit words can be classified into three types.
- Words of the $[8,4,4]$ extended Hamming code. There are 16 of these, and they have even weight.
- Words that are distance 1 from a codeword. There are 128 of these, and they have odd weight.
- Words that are distance 2 from a codeword. There are 112 of these, and they have even weight. Each such word is equidistant from four codewords.
From this it is clear that if there are three errors in transmission of a codeword, the received word will have odd weight, and therefore will fall into class 2. It will therefore be decoded as if it were distance 1 from a codeword. That is, it will always be decoded to the wrong codeword.
Added: As for decoding, suppose we use the parity check matrix
$$H=\begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{bmatrix}$$
and regard the first seven bits as coming from the $[7,4,3]$ Hamming code with the eighth bit as parity check bit. Given received word $w,$ we compute $Hw,$ which is a four-bit word. If the received word is a codeword, $Hw$ will equal $0000.$ If the received word has odd weight, bit $1$ of $Hw$ will be set, and the decoder will assume one error. Under this assumption, if $Hw=1000$ then the error was in bit $8;$ otherwise, the last three bits of $Hw$ are the binary encoding of the position of the error. Finally, if the received word has even weight but is not a codeword, then $Hw$ will not equal $0000$ but its first bit will not be set. The decoder will then report a noncorrectable error.
Best Answer
The short answer is that you get the syndrome $H_m$ by multiplying the received vector $r$ with the parity check matrix: $H_m=H r^T$.
There are several equivalent parity check matrices for this Hamming code, and you haven't shown us which is the one your source uses. The bits that you did give hint at the possibility that the check matrix could be $$ H=\pmatrix{1&0&1&0&1&0&1\cr0&1&1&0&0&1&1\cr0&0&0&1&1&1&1\cr}. $$ To be fair, that is one of the more popular choices, and also fits your received word / syndrome pair :-). The reason I'm nitpicking about this is that any one of the $7!=5040$ permutations of the columns would work equally well for encoding/decoding. Being an algebraist at heart, I often prefer an ordering that exhibits the cyclic nature of the code better. Somebody else might insist on an ordering the matches with systematic encoding. Doesn't matter much!
Here your received vector $r=(1,0,0,1,0,0,1)$ has bits on at positions 1, 4 and 7, so the syndrome you get is $$ H_m=H r^T=\pmatrix{1\cr 0\cr0\cr}+\pmatrix{0\cr 0\cr1\cr}+\pmatrix{1\cr 1\cr1\cr}=\pmatrix{0\cr 1\cr0\cr} $$ the modulo two sum of the first, fourth and seventh columns of $H$.
If $r$ were a valid encoded message, then the syndrome $H_m$ would be the zero vector. As that was not the case here, an error (one or more) has occurred. The task of the decoder is to find the most likely error, and the usual assumptions lead us to the goal of toggling as few bits of $r$ as possible.
The nice thing about the Hamming code is that we can always do this by toggling at most one bit. We identify $H_m$ as the second column of $H$, so to make the syndrome zero by correcting a single bit we need to toggle the second bit of $r$.
What makes the Hamming code tick is that all possible non-zero syndrome vectors occur as columns of $H$. Therefore we always meet our goal of making the syndrom zero by toggling (at most) a single bit of any received word.