What is a parity check matrix? (Information theory)
I'm studying information theory but one thing I can't seem to work out.
I know that given a linear code C and a generator matrix M I can work out all the possible codewords of C.
However I do not understand:
- What a parity check matrix is http://en.wikipedia.org/wiki/Parity-check_matrix
- How to make a parity check matrix from a generator matrix
I'd really appreciate any pointers!
Thanks!
Answer
I think your link explains it fairly well, but I'll try to simplify further.
Let x be your message, a k-element row vector. Let G be your generator matrix, an k-by-n binary matrix where n > k. Let y be your n-element transmitted codeword where y = xG. Let z be your n-element received codeword.
Hopefully, z = y. But when transmitting y across a noisy channel, it is possible for y to become corrupted, e.g., z != y.
An (n-k)-by-n parity matrix H is applied to the received codeword z to check if z is valid. The vector w = zH' can detect up to a certain number of bit errors in z.