Parity checks as matrix multiplication

A partity check can be represented as a form of matrix multiplication.

Imagine we have an input bit stream, a, of length k:

$(a_0 ... a_{k -1})$

Then a matrix of the form below will perform an even parity check if k is odd (or an odd parity check if k is even):

$\left( {\begin{array} {rrrrr} 1 & 0 & ... & 0 & 1 \\ 0 & 1 & ... & 0 & 1 \\ 0 & 0 & ... & 0 & 1 \\ ... & ... & ... & ... & 1 \\ 0 & 0 & ... & 1 & 1 \end{array} } \right)$

Here’s a very simple worked example:

Let a = 10110

Parity check matrix = $\left( {\begin{array} {rrrrrr} 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{array} } \right)$

Output = 101101 (modulo 2 arithmetic is used to compute each ‘column’ in the output)

Of course parity checks are a crude form of 1 bit error detection and do not allow for error correction.

Advertisement

2 responses to “Parity checks as matrix multiplication”

1. […] Parity checks as matrix multiplication […]

2. […] Comments More on parity matri… on Parity checks as matrix m…More on error correc… on The difference between Hamming…The difference betwe… […]