cartesian product … stuff about computing mostly

More on parity matrices

$G = \left( {\begin{array} {rrrr} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \end{array} } \right)$

A parity check matrix for this, $H$ is one where $GH^T = 0$ (hence the product of $H^T$ with a codeword is also 0, though an error word generates a non-zero output).

Two candidates for this present themselves (are there others? I can’t see them):

$H^{\prime}= \left( {\begin{array} {rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array} } \right)$

$H^{\prime\prime}= \left( {\begin{array} {rrrr} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} } \right)$

Taking $H^{\prime}$ , there are $2^k$ distinct messages (codewords), where $k = 2$ , but he generator can create $2^n = 2^4$ different outputs. So we have $2^k - 1$ non-zero code words and $2^n - 1$ possible outputs, the number of detectable errors is:

$2^n - 1 - (2^k - 1) = 2^n - 2^k = 12$

The most likely error is the one with the lowest Hamming weight:

$\left( {\begin{array} {lrrrr} codewords & 0000 & 0101 & 1100 & 1001 \\e_1 & 0001 & 0100 & 1101 & 1000\\e_2 & 0010 & 0111 & 1110 & 1011 \\e_3 & 0011 & 0110 & 1111 & 1010 \end{array} } \right)$

Parity checks as matrix multiplication (cartesianproduct.wordpress.com)
No balloons at the celebration for the Beach Chair Scientist … (beachchairscientist.wordpress.com)
SVD – a simple proof (alfanotes.wordpress.com)

Rate this:

Adrian McMenamin

July 19, 2012

Uncategorized

error correction, error detection, Parity-check matrix

7 responses to “More on parity matrices”

prubin73

August 2, 2012 at 2:24 pm

H’ works as a parity check matrix, but I think H” does not: H” times (1,1,1,1) yields (0,0), but (1,1,1,1) is not generated by G.
1. Adrian McMenamin
  
  August 2, 2012 at 10:14 pm
  
  OK, you are the professional, but I don’t follow your argument.
  
  The maths is modulo 2, so surely each row of $GH^{\prime \prime T}$ is zero?
  1. Paul A. Rubin (@parubin)
    
    August 2, 2012 at 10:22 pm
    
    True, but that’s only half the battle. Don’t you want H” x non-zero (meaning at least one component is nonzero, not that all components are nonzero) for x a non-word? In other words, shouldn’t a non-word generate at least one nonzero bit when checked?
Adrian McMenamin

August 3, 2012 at 12:13 am

Yes – you have a point! I’ll have to edit that/update it.
prubin73

August 3, 2012 at 3:44 pm

As a lark, I wrote a program to compute all minimum-dimension parity check matrices for a given generator matrix. Charitably assuming that I understood what I’m doing, there are two for your generator. H’ is one. The other has rows [1,1,1,1] and [0,0,1,0]. (Note that permuting the rows of a parity check matrix gives another parity check matrix, and adding an additional row x to a parity check matrix is fine as long as x^TG = 0.)
1. Adrian McMenamin
  
  August 3, 2012 at 6:46 pm
  
  Cheers! I bought a book – was just about to blog about it.
Parity check matrices « cartesian product

August 3, 2012 at 7:01 pm

[…] Comments Adrian McMenamin on More on parity matricesprubin73 on More on parity matricesAdrian McMenamin on More on parity matricesBINSIC […]