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.