Progress Report Summer 2004
Genevieve Patterson and Frederick Leitner(Advisor)
This summer’s research work is an extension of the project I completed during the Spring 2004 semester. In my spring project, I wrote a tutorial website that outlined basic concepts of coding theory and related linear algebra. My webpage focused on explaining two linear codes, and how they were useful in checking data for errors. The tutorial described what Hamming and Parity Check codes were, whether they were a “good code”, how the quality of the code was measured, what mathematics were used in developing the codes, and the tutorial finally offered several java applets demonstrating how the codes functioned.
In last semester’s project, I gave an example of the Hamming(4, 7) code. This code took a block of four data elements and encoded that block, which added three parity data elements. This is only one of many Hamming codes that can be used. This summer’s project is to create a java program package that will demonstrate the larger family of Hamming codes. Using this Hamming code package, users could specify which type of Hamming code they want to use, and my package would allow them to encode a data stream using their specifications for encryption.
The
goal of my research this semester is to develop a java package that will be a
convenient place to implement these Hamming codes. To implement these linear
codes we need to be able to perform matrix operations over arbitrary finite
fields. Consequently, the first step of this project was to write java packages
to handle matrix operations over generic fields. The code to deal with these
situations over fields of p elements
is included below. The next step is to implement the Hamming Codes over these
finite fields.
The real-world applications of error checking and linear block codes are in digital data transfer. Typical communication channels include telephone lines, high-frequency radio links, microwave links, satellite links, semi-conductor memories, and magnetic tapes. Data is encoded to be transferred over these channels. Linear block codes are used to encode the data. In many situations the encoded data can be corrupted during transfer. Corruption occurs when there is noise on the line or some physical disturbance interrupts the data. If the data does not arrive in perfect condition, error-checking codes are required to find the errors in the data and possibly fix these errors.
Included below is the java code implementing matrix operations over arbitrary finite fields:
/**
*
abstract super class for data storage elements
*/
public abstract class FieldElem
{
public FieldElem()
{
}
public abstract FieldElem addTo(FieldElem
f);
public abstract FieldElem multiplyBy(FieldElem
f);
public abstract void scalarMultiply(int scalar);
public abstract FieldElem inverse();
public abstract FieldElem negate();
public abstract FieldElem copy();
public abstract FieldElem zero();
public abstract FieldElem one();
public abstract void setValue(FieldElem
f);
public abstract boolean equals(FieldElem
f);
public abstract String toString();
}
/**
* static class for
common operations on FieldElems
*/
public class FieldOps
{
public static
FieldElem multiply(FieldElem
f, FieldElem e){
FieldElem temp=f.copy();
return temp.multiplyBy(e);
}
public static
FieldElem scalarMultiply(FieldElem
f, int
scalar)
{
FieldElem temp= f.copy();
temp.scalarMultiply(scalar);
return temp;
}
public static
FieldElem inverse(FieldElem
f)
{
FieldElem temp= f.copy();
return temp.inverse();
}
public static
FieldElem add(FieldElem
f, FieldElem e)
{
FieldElem temp= f.copy();
return temp.addTo(e);
}
public static
FieldElem negation(FieldElem
f)
{
FieldElem temp= f.copy();
return temp.negate();
}
public static
boolean equals(FieldElem
f, FieldElem e)
{
return f.equals(e);
}
public static
FieldElem zero(FieldElem
f)
{
return f.zero();
}
public static
FieldElem one(FieldElem
f)
{
return f.one();
}
}
/**
* stores
elements in
the field
Fp
*/
import java.util.*;
public class FPElem extends FieldElem
{
private int number;
private int prime;
private static Hashtable inverse=new Hashtable();
public FPElem(int
n, int
p)
{
//check
that p is a prime number
prime= p;
number=n;
}
public int getValue()
{
return number;
}
public int getPrime()
{
return prime;
}
public void changeValue(int newNumber)
{
number= newNumber%prime;
}
public void changePrime(int newPrime)
{
prime= newPrime;
}
public FieldElem addTo(FieldElem
f)
{
// note:
prime and f.getPrime() should be equal
FPElem
temp= (FPElem)
f.copy();
return new
FPElem((number+temp.getValue())%prime, prime);
}
public FieldElem multiplyBy(FieldElem
f)
{
//note:
prime and f.getPrime() should be equal
FPElem
temp= (FPElem)
f.copy();
return new
FPElem((number*temp.getValue())%prime, prime);
}
public void scalarMultiply(int scalar)
{
number=(number*scalar)%prime;
}
public FieldElem inverse()
{
Object
temp= inverse.get(this);
if(temp!=null)
return ((FieldElem)
temp).copy();
else
{
boolean haveInverse=
false;
int answer=0;
while(!haveInverse)
{
if((number*answer)%prime==1)
{
haveInverse=true;
break;
}
else
haveInverse=false;
answer++;
}
FPElem temp2= new FPElem(answer, prime);
inverse.put(this, temp2);
return temp2.copy();
}
}
public FieldElem negate()
{
return new
FPElem(number*-1, prime);
}
public FieldElem copy()
{
return new
FPElem(number, prime);
}
public FieldElem zero()
{
return new
FPElem(0, prime);
}
public FieldElem one()
{
return new
FPElem(1, prime);
}
public void setValue(FieldElem
f)
{
FPElem
temp= (FPElem)
f.copy();
number= temp.getValue()%prime;
}
public boolean equals(FieldElem f)
{
FPElem
temp= (FPElem)
f.copy();
if(number==temp.getValue()%prime)
return true;
else
return false;
}
public String toString()
{
String
returner= number+", "+prime+
" ";
return returner;
}
}
/**
* a matrix
is a two dimensional
array of FieldElems
*/
public class Matrix
{
private FieldElem[][] fematrix;
public Matrix(int
rows, int
cols)
{
fematrix= new FieldElem[rows][cols];
}
public int getRows()
{
return fematrix.length;
}
public int getColumns()
{
return fematrix[0].length;
}
public FieldElem getElemAt(int row, int col)
{
return fematrix[row][col];
}
public void changeElem(int row, int col, FieldElem newElem)
{
fematrix[row][col]=
newElem;
}
public String toString()
{
String returner=
new String();
for(int j=0; j< getRows(); j++)
{
for(int k=0; k< getColumns();
k++)
{
returner+= fematrix[j][k].toString();
}
returner+= "/n";
}
return returner;
}
}
/**
* static class containing
matrix operations
corresponding to
the matrix
class
*/
public class MatrixOps
{
private static FieldElem swaps;
private static Matrix out;
public static Matrix add(Matrix m1, Matrix m2)
{
if(m1.getRows()==m2.getRows())
{
if(m1.getColumns()==m2.getColumns())
out = new Matrix(m1.getRows(), m1.getColumns());
else
return null; //this will throw an error
}
else
return null; //also throw error
for(int j= 0; j< m1.getRows(); j++)
{
for(int k = 0; k< m2.getColumns();
k++)
{
out.changeElem(j, k, m1.getElemAt(j, k).addTo(m2.getElemAt(j,
k)));
}
}
return out;
}
public static Matrix scalarMultiply(Matrix
m1, FieldElem
scalar)
{
Matrix
out= new
Matrix(m1.getRows(), m1.getColumns());
for(int j =0; j< out.getRows(); j++)
{
for(int k=0; k<out.getColumns(); k++)
(out.getElemAt(j, k)).setValue(FieldOps.multiply((out.getElemAt(j, k)), scalar));
}
return out;
}
public static Matrix matrixMultiply(Matrix
m1, Matrix m2)
{
FieldElem
sum= FieldOps.zero(m1.getElemAt(0,
0));
if(m1.getColumns()==m2.getRows())
out= new Matrix(m2.getRows(), m2.getColumns());
else