Self-orthogonal vectors and coding
One of the surprising things about linear algebra over a finite field is that a non-zero vector can be orthogonal to itself.
When you take the inner product of a real vector with itself, you get a sum of squares of real numbers. If any element in the sum is positive, the whole sum is positive.
In a finite field, things don't work that way. A list of non-zero squares can add up to zero.
In the previous post, we looked at the ternary Golay code, an error correcting code that multiplies a vector of data by a rectangular matrix mod 3. That post included the example that
[1, 0, 1, 2, 2]
was encoded as
[1 0 1 2 2 0 1 0 2 0 0].
The output is orthogonal to itself:
1^2 + 0^2 + 1^2 + 2^2 + 2^2 + 0^2 + 1^2 + 0^2 + 2^2 + 0^2 + 0^2 0 (mod 3).
In fact, every output of the ternary Golay code will be self-orthogonal. To see this, let v be a 1 by 5 row vector. Then its encoding is vG where G is the 5 by 11 matrix in the previous post. The inner product of vG with itself is
vG (vG)T = vGGTvT.
We can easily show that GGT is a zero matrix using Python:
>>> (G@G.T)%3 [[0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]]
And so
vGGTvT = vOvT = 0.
If a vector is not self-orthogonal, there has been an error. For example, if one of the 0s in our output turned into a 1 or a 2, the inner product of the corrupted vector with itself would be equal to 1 (mod 3) rather than 0.
Self-orthogonality is necessary but not sufficient for an encoded vector to be error-free. Correctly encoded vectors form a 5 dimensional subspace of GF(3)11, namely the row space of G. The set of self-orthogonal vectors in GF(3)11 is a larger space.
A sufficient condition for a row vector w to be the encoding of a data vector v is for
GwT
to be the zero vector (carrying out all calculations mod 3).
The ternary Golay code is capable of detecting and correcting corruption in up to two spots in a vector. For example, suppose we take our vector
[1 0 1 2 2 0 1 0 2 0 0]
above and corrupt it by turning the first couple 2's to 1's.
[1 0 1 1 1 0 1 0 2 0 0]
We'd still get a self-orthogonal vector, but the product GwT would not be zero.
>>> v = np.array( [1, 0, 1, 2, 2] ) >>> w = (v@G)%3 >>> w[3] = w[4] = 1 >>> print((G@w)%3)
This prints
[0 0 0 2 2]
which lets us know that the modified version of w is not a valid encoding, not a part of a row space of G.
If we know (or are willing to assume) that
[1 0 1 1 1 0 1 0 2 0 0]
is the result of no more than two changes applied a valid code word vG, then we can recover vG by looking for the closest vector in the row space of G. Here closeness is measured in Hamming distance: the number of positions in which vectors differ. Every vector in GF(3)11 is within a distance of 2 from a unique code word, and so the code can correct any two errors.
Related postsThe post Self-orthogonal vectors and coding first appeared on John D. Cook.