Linear Algebra over the Integers Mod 2

Notation and Observations:

1. A row vector is just a sequence of n $\QTR{Large}{1}$ s and $\QTR{Large}{0}$ s.
2. The unit vector is the row vector with a $\QTR{Large}{1}$ in the $\QTR{Large}{i\ }$ th position.
3. For any vector $\QTR{Large}{x}$ , $\ \ \QTR{Large}{x}$ is the just vector $\QTR{Large}{x}$ with the $\QTR{Large}{i\ }$ th bit flipped.
4. More generally given , $\ \ \QTR{Large}{x}$ is the just vector $\QTR{Large}{x}$ with the bits flipped in every position there is a $\QTR{Large}{1}$ in $\QTR{Large}{y}$ , or the vector $\QTR{Large}{y}$ with the bits flipped in every position there is a $\QTR{Large}{1}$ in $\QTR{Large}{x.\ }$ The same thing!
5. Again a Linear Transformations , over is just: has to satisfy the property

____________________________________________________________________________________________________________

Linear Codes over

Definition:

Suppose we are given alphabet of symbols $\dsum \$ 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 $\QTR{Large}{H}$

Methodology:

Given a symbol $\QTR{Large}{s}\$ encode it as Next encode $\QTR{Large}{C(s)}$ for transmission as
Transmit $\QTR{Large}{w}$ . Denote the vector that is received by . Maybe maybe not.
Compute below if success, if not a transmission error.

______________________________________________________________________________________________

The [7,4,3] $_{\QTR{Large}{2}}$ Hamming Code :

The matricies:

MATH and MATH

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

Note that for a unit vector , is just the $\QTR{Large}{i\ }$ th row of $\QTR{Large}{G}$ which for every row has at least three $\QTR{Large}{1}$ s.

The claim is that if you flip at least one bit of to say then

and differ by at least three bits(See Bullet $\QTR{Large}{4}$ . above).

_____________________________________________________________________

Notes For Assignment 1:

We need to show that if If differ by at least one bit , will differ by at least three.

If $\QTR{Large}{x}$ and differ by three or four bits than so will and since the final four bits of these vectors are the bits of $\QTR{Large}{x}$ and . Therefore we only need to look at the cases

where $\QTR{Large}{x}$ and differ by one and two bites.

Let

Suppose $\QTR{Large}{x}$ and differ by one bit, then for some $\QTR{Large}{i\ }$ and

Since just the $\QTR{Large}{i}$ th row, has at least three $\QTR{Large}{1}$ s, that is flips three bits we are done

Suppose $\QTR{Large}{x}$ and differ by two bit, then for some

Since we just need to look the sums of the various pairs of rows of $\QTR{Large}{G}$ to check that there is always at least three $\QTR{Large}{1\ }$ s in each sum.

An interesting case is

which just makes it.

All of this provides a methology for developing error correcting codes for other word sizes, say