Here’s a generator matrix,
A parity check matrix for this, is one where (hence the product of 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):
Taking , there are distinct messages (codewords), where , but he generator can create different outputs. So we have non-zero code words and possible outputs, the number of detectable errors is:
The most likely error is the one with the lowest Hamming weight:
- 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)
7 responses to “More on parity matrices”
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.
OK, you are the professional, but I don’t follow your argument.
The maths is modulo 2, so surely each row of is zero?
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?
Yes – you have a point! I’ll have to edit that/update it.
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.)
Cheers! I bought a book – was just about to blog about it.
[…] Comments Adrian McMenamin on More on parity matricesprubin73 on More on parity matricesAdrian McMenamin on More on parity matricesBINSIC […]