3.1 Generator and Parity Check Matrices

Linear codes use generator and parity check matrices to encode messages and detect errors. The generator matrix creates codewords by multiplying with message vectors, while the parity check matrix verifies if a received vector is valid.

These matrices have special forms that make encoding and decoding easier. The generator matrix in systematic form shows message bits unchanged, while the parity check matrix in standard form helps quickly spot errors in received vectors.

Generator and Parity Check Matrices

Generator Matrix and Systematic Form

• Generator matrix $G$ generates all codewords of a linear code by multiplying it with all possible message vectors
  • Rows of $G$ form a basis for the code
  • For an $(n,k)$ linear code, $G$ is a $k \times n$ matrix
• Systematic form of a generator matrix has the form $G = [I_k | A]$, where $I_k$ is the $k \times k$ identity matrix and $A$ is a $k \times (n-k)$ matrix
  • Systematic form allows for easy encoding and decoding
  • Message bits appear unchanged in the first $k$ positions of the codeword (information bits)
  • Last $n-k$ positions are parity bits, which are linear combinations of the message bits

Parity Check Matrix and Standard Form

• Parity check matrix $H$ is used to check if a received vector is a valid codeword
  • For an $(n,k)$ linear code, $H$ is an $(n-k) \times n$ matrix
  • A vector $\mathbf{c}$ is a codeword if and only if $H\mathbf{c}^T = \mathbf{0}$
• Standard form of a parity check matrix has the form $H = [A^T | I_{n-k}]$, where $A^T$ is the transpose of the matrix $A$ from the systematic form of the generator matrix
  • Rows of $H$ are orthogonal to the rows of $G$, i.e., $GH^T = \mathbf{0}$
  • Columns of $H$ correspond to the parity bits in the codeword

Encoding and Decoding

Encoding Process

• Encoding is the process of converting a message vector $\mathbf{m}$ into a codeword $\mathbf{c}$
  • For a linear code with generator matrix $G$, the encoding process is $\mathbf{c} = \mathbf{m}G$
  • If $G$ is in systematic form, the message bits appear unchanged in the first $k$ positions of the codeword
• Linear independence of the rows of $G$ ensures that each message vector maps to a unique codeword
  • Rows of $G$ form a basis for the code, spanning the entire codespace

Decoding Process

• Decoding is the process of recovering the original message vector $\mathbf{m}$ from a received vector $\mathbf{r}$
  • Compute the syndrome $\mathbf{s} = H\mathbf{r}^T$
    • If $\mathbf{s} = \mathbf{0}$, then $\mathbf{r}$ is a valid codeword
    • If $\mathbf{s} \neq \mathbf{0}$, use the syndrome to determine the error pattern and correct the errors
  • For systematic codes, the message bits can be directly read from the first $k$ positions of the decoded codeword

Matrix Properties

Rank of Generator and Parity Check Matrices

• Rank of the generator matrix $G$ is equal to the dimension $k$ of the code
  • Rows of $G$ are linearly independent
  • Rank of $G$ determines the number of information bits in each codeword
• Rank of the parity check matrix $H$ is equal to $n-k$, where $n$ is the length of the codeword
  • Rows of $H$ are linearly independent
  • Rank of $H$ determines the number of parity bits in each codeword

Nullspace of Parity Check Matrix

• Nullspace (kernel) of the parity check matrix $H$ is the set of all vectors $\mathbf{x}$ such that $H\mathbf{x}^T = \mathbf{0}$
  • Codewords of the linear code are the elements of the nullspace of $H$
  • Dimension of the nullspace is equal to the dimension $k$ of the code
• Nullspace of $H$ is the rowspace of the generator matrix $G$
  • Rows of $G$ form a basis for the nullspace of $H$