Linear Codes

Notation:

In this lecture we will be working with , vectors over the Integers mod 2 . We will be using the defining property of Linear Transformations , which over is just:

Linear Transformations will be described in Matrix form.

An ( row by column) matrix will be written as or . We will refer to a matrix as an dimensional row vector and an matrix as an dimensional column vector.


We will sometimes simplify row vector notation and just write and column vectors notation by writing leaving out the trailing or leading 1.

Matrix Operations:

1. Given an matrix , its transpose is the matrix

2. Given an matrix , and an Given an matrix , its product is the matrix where

3. 

_____________________________________________________________________________________________

The Annoying Question:

Should the convention be that our vectors by row vectors and the corresponding Linear Transformation be matrix multiplication on the right or should they be column vectors and matrix multiplication be on the left?

Answer: it does not matter as long as we are consistant.

Warning: As you search the literature, including the Web, make sure you note which convention is being used.

Our Convention:

Unless noted, vectors will be row vectors with multiplication on the right.

______________________________________________________________________________________________

Linear Codes over

Definition:

Suppose we are given alphabet of symbols and an encoding then is called a Linear Code if is a subspace of .

• 7 bit ASCII is a Linear Code since every vector in is a code word.
  
  

• If is a Linear Code and is a 1 to 1 Linear Transformation then is a Linear Code.

_________________________________________________________________________________________________

Error Detection and Correction for Linear Codes:

Given a Linear Code

• We are given a 1 to 1 Linear Transformation in the form of a Matrix

• We are also given a Linear Transformation ,not 1 to 1, in the form of a Matrix

Methodology:

• Given a symbol encode it as Next encode for transmission as

• Transmit Denote the vector that is received by . Maybe maybe not.
  
  
  

• Compute below if success, if not a transmission error.

_________________________________________________________________________________________

Parity Checking using Matricies (ASCII) :

To make the notation a bit simpler will work with "mini-ASCII", some 4 bit encoding where every vector is a code word.

We use the matricies:

and

for Even Parity checking., we use to encode 4 bit words as 5 bit words for transmission and to check for errors at the receiving end.

Given

Note that is an Even Parity bit.

We transmit At the receiving end compute

Assuming there is at most one bit error:

• If the the transmission was without error

• If there was a transmission error.

Question: Even Parity Check is a Linear Code, is Odd Parity Check?

______________________________________________________________________________________________

The [7,4,3] Hamming Code :

The matricies:

and

Again, given we encode it by multiplying on the right by

An Aside: Having the Identity submatrix as the last four column vectors of seems to be somewhat of a standard so I am following that convention.

__________________________________________________________________________________________________

Properties of the [7,4,3] Hamming Code:

1. Since if is correctly received
   
   
   

   

2. Writing as suppose there is a single bit transmission error:

   The vector received is of the form where , in the position in every other position.

   (Flipping a bit is, in effect, just adding an appropriate unit vector)

   Since , which is just the row of , the bit is an error.