What is a parity check matrix? (Information theory)

Question

Hi all,

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 1

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.