Parity-Check and Generator Matrices

We need to find a systematic way of generating linear codes as well as fast methods of decoding. By examining the properties of a matrix \(H\) and by carefully choosing \(H\), it is possible to develop very efficient methods of encoding and decoding messages. To this end, we will introduce standard generator and canonical parity-check matrices.

Suppose that \(H\) is an \(m \times n\) matrix with entries in \({\mathbb Z}_2\) and \(n \gt m\). If the last \(m\) columns of the matrix form the \(m \times m\) identity matrix, \(I_m\), then the matrix is a canonical parity-check matrix. More specifically, \(H= (A \mid I_m)\), where \(A\) is the \(m \times (n-m)\) matrix \[\begin{aligned}\end{aligned}\] and \(I_m\) is the \(m \times m\) identity matrix \[\begin{aligned}\end{aligned}\]. With each canonical parity-check matrix we can associate an \(n \times (n-m)\) standard generator matrix \[\begin{aligned}\end{aligned}\]. Our goal will be to show that an \(\mathbf x\) satisfying \(G {\mathbf x} = {\mathbf y}\) exists if and only if \(H{\mathbf y} = {\mathbf 0}\). Given a message block \({\mathbf x}\) to be encoded, the matrix \(G\) will allow us to quickly encode it into a linear codeword \({\mathbf y}\).

We leave the proof of this theorem as an exercise. In light of the theorem, the first \(n - m\) bits in \({\mathbf x}\) are called information bits and the last \(m\) bits are called check bits. In , the first three bits are the information bits and the last three are the check bits.

Before we can prove the relationship between canonical parity-check matrices and standard generating matrices, we need to prove a lemma.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.