dijous, 20 de setembre del 2007

Intersection Array Program

I have told about Intersection Array before, now I will post a program to compute it.
This program has been developed by CCG group, directed by Jaume Pujol and programed by me.
There are various options to use the program:
The program is under GPLv3 license and you can download it from CCGroup
The zip is composed by the source code, the documentation (with some exemples) and a binary.
All you can expect to know is explained on the documentation, in fact, I will sum up the uses of the program.
You can use it to compute the intersection array of a given vector in a code. It will show only the column corresponding to the distance of the vector.
You can also try all the posible distance if you know the covering radius of the code. Then the program will search a vector for each distance lesser than covering radius, and it will compute the intersection array.
You can use it to know if a code is completly regular. When this option is set, you must specify a hamming weight, then it will try all the posible vectors of the same weight and check if they have the same intersection array, until the specified weight or until the word length (there can't exist a vector with hamming weiht > word length). This is an important option, because the problem of knowing if a code is completly regular is a non-polynomial problem. This is, a completly regular code is a code which all the vectors at the same distance to the code, have the same intersection array.

divendres, 7 de setembre del 2007

Intersection Array

The intersection array of a vector "V" in a code "C", is a distance d counter of how many vectors "W" where Wi = V + Ei (Ei are all the correctable error vectors in the code). For example if we have a Hamming code (covering radius 1) and we have a vector in the code (d=0), we must compute the distance to the code for each vector W where W are V plus the cosset leaders (except 0 vector).
The first row of the array called A, is the number of W which have the same distance as V that is d(W)=d(V).
The second row of the array called B, is the number of W which have d(W) = d(V)+1.
The third row of the intersection array called C, is the number of W which have d(W) = d(V)-1.
There are more rows, it depends on the covering radius of the code. Is is posible to have 2 * coveringRadius + 1 diferent rows, but the most important are A,B and C.
The columns are the diferent distances of V d(V). So the first column will be for those vectors in the code d(V)=0, the second for those that d(V)=1 etc.

In our example, imagine a Hamming code of length 15. A Hamming Code has covering radius 1 so we will have 3 rows.
We have a vector V which d(V) = 0 we also have 15 diferent Ei vectors so 15 Wi and all will be at d(Wi) = 1 so we will have something like that:
A0 = 0
B0 = 15
C0 = 0
We have a vector V which d(V) = 1 we try all Wi (15 posibilities) and we get that:
A1 = 14
B1 = 0
C1 = 1
We are using a Hamming Code (Covering Radius 1) so we have finished, because interesection array is used with d(V) <= Covering Radius.
We can show all complet intersection array for a Hamming 15 code
( 0 14 )
( 15 0 )
( 0 1 )

And why is that important?

Because we can use intersection array to compute if a code is completly regular.