Parity checks as matrix multiplication

Standard

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.

2 thoughts on “Parity checks as matrix multiplication

  1. Pingback: More on parity matrices « cartesian product

  2. Pingback: CRCs as matrix maths « cartesian product

Comments are closed.