2
$\begingroup$

I'm trying to understand the overall parity bit in a Hamming Code specifically at the end of this wikipedia article. (You can compare my interpretation with the anchor linked example if this seems wrong in case I misunderstood the matrix) $$\mathbf{G} = \left( \begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 & \color{red}1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & \color{red}1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & \color{red}1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & \color{red}0 \end{array} \right)_{4,8}$$

$$\mathbf{H} = \left( \begin{array}{cccc|cccc} 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \color{red}1 & \color{red}1 & \color{red}1 & \color{red}0 & 0 & 0 & 0 & 1 \end{array} \right)_{4,8}$$

As a refresher and if conventions in the article differ from the conventions one might be familiar with, you multiply G by a vector (in the article $\vec{a}=[1,0,1,1]$) to get the original data plus individual parity bits $\vec{a}$G and then multiply the result by H on the receiving end to verify each parity bit equals zero if no error occurred. The last example in wikipedia uses a backwards out of order example where the columns of G 5,6, and 7 are parity bits 4,2, and 1 respectively. The final column 8 (coloring mine) is the overall parity to detect double errors and indicate the parity of every bit. Why is the last bit 0 and not 1 to detect if the overall parity changed (odd errors) or not (even). Is this a typo/error? Research(1 2 3)


Bit coverage for reference: Parity bits which indicate which data bit was wrong as the binary representation of the wrong bit: enter image description here The overall parity bit indicates if an even or odd number of errors occurred.

$\endgroup$

1 Answer 1

3
$\begingroup$

It's perfectly correct. The final column in $G$ is defined so as to make the sum of each row of $G$ to be zero modulo $2$, that is that all rows of $G$ have even parity.

$\endgroup$
5
  • $\begingroup$ I'm thinking... How would that determine the overall parity? $\endgroup$ May 19, 2018 at 9:37
  • 1
    $\begingroup$ @user5389726598465 What happens if you add all four parity bits? $\endgroup$ May 19, 2018 at 9:45
  • $\begingroup$ Then the final column doesn't actually multiply a. That would make sense because then the parity bits are then included in the total parity check not just the data bits. (Sorry for the delay. I have 4 newborn kittens and one went caca.) $\endgroup$ May 19, 2018 at 11:34
  • $\begingroup$ @user5389726598465 The total parity check is also in parity bits, just a bit hidden. $\endgroup$ May 23, 2018 at 9:21
  • $\begingroup$ @Jean-ClaudeArbaut It's still odd that the column is included in the multiplication matrix if it's not part of the multiplication. I guess they had to show it somehow. I will have to come back to a worked textbook example when I have time to see for sure if it's excluded from the matrix multiplication. . $\endgroup$ May 23, 2018 at 9:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .