Error correcting code from octonions

Yesterday I wrote about how to multiply octets of real numbers, the octonions. Today I'll show how to create an error correcting code from the octonions. In fact, we'll create a perfect code in the sense explained below.

We're going to make a code out of octonions over a binary field. That is, we're going to work with octets of bits rather than octets of real numbers. Our code is going to produce 8-bit numbers which we can think of as octonions with components in each dimension equal to either 0 or 1, and we'll carry out addition mod 2.

Basis of the code

The earlier post bootstrapped the multiplication facts for octonions from the equation

e₁ e₂ = e₄

and two symmetry rules:

1. You can shift the subscripts by a constant amount mod 7.
2. You can permute each rule if you multiply by the sign of the permutation.

The first rule says we have the following equations:

e₁ e₂ = e₄
e₂ e₃ = e₅
e₃ e₄ = e₆
e₄ e₅ = e₇
e₅ e₆ = e₁
e₆ e₇ = e₂
e₇ e₁ = e₃

Our code is going to be based on the complements of the triples in the multiplication rules above. For example, the first rule contains subcripts 1, 2, and 4, and so its complement contains subscripts 3, 5, 6, and 7. So we want the seven octonions

e₃ + e₅ + e₆ + e₇
e₁ + e₄ + e₆ + e₇
e₁ + e₂ + e₅ + e₇
e₁ + e₂ + e₃ + e₆
e₂ + e₃ + e₄ + e₇
e₁ + e₃ + e₄ + e₅
e₂ + e₄ + e₅ + e₆

and one more octonion, the sum of all the bases:

1 + e₁ + e₂ + e₃ + e₄ + e₅ + e₆ + e₇

Our code will be spanned by these eight octonions. Written as 8-bit numbers, or code will be spanned by

00010111
01001011
01100101
01110010
00111001
01011100
00101110
11111111

Every pair of binary numbers above differs in four positions. We can verify this with the following Python code.

 from itertools import combinations, product def popcount(n): return bin(n).count('1') def hd(m, n): # Hamming distance return popcount(m ^ n) gen = [ 0b00010111, 0b01001011, 0b01100101, 0b01110010, 0b00111001, 0b01011100, 0b00101110, 0b11111111, ] for pair in combinations(gen, 2): assert(hd(pair[0], pair[1]) == 4)

We didn't need to import product for the code above, but we'll need it below.

Note that the popcount of the XOR of two numbers counts how many places where their bit representations differ, i.e. it computes the Hamming distance between the two bit vectors.

Hamming code

The fact that the octets above spread out well, each being a Hamming distance of 4 from all the rest, suggests they could be useful in coding, and in fact the vectors above span the Hamming code (8, 4, 4).

These octets from the previous section will be the basis of our code, basis" in the colloquial sense of a starting point. They span our set of code words, but they're not a basis in the linear algebra sense because they are not linearly independent. The following code shows that the octets span a 4 dimensional space, i.e. you can make 2⁴ different bit patterns by XORing together combinations of these octets.

 codewords = set() n = 4 for b in combinations(gen, n): for coeff in product(range(2), repeat=n): s = 0 for i in range(n): s ^= coeff[i]*b[i] codewords.add(s) assert(len(codewords) == 16)

The code tells that our octets have a span of size 16, i.e. 4 dimensions over a 2-bit field.

(Normally this would be presented by doing linear algebra, but I'm doing it by brute force just for variety. I assume readers who are more comfortable with code than math will appreciate this.)

Perfect codes

The Hamming (8, 4, 4) code is perfect" in the sense that its packing radius equals its covering radius.

The packing diameter is the minimum distance between code words, and the packing radius is half the packing diameter.

The following code shows this is 2.

 packing_radius = min( hd(p[0], p[1]) for p in combinations(codewords, 2))/2 print(packing_radius)

Since the packing diameter is 4, we can detect if up to 3 bits are corrupted: no bit pattern that differs from a code word in three positions is a code word.

The covering radius is the maximum distance from any vector to a code word. The following Python snippet shows that no 8-bit vector is a Hamming distance of more than 2 from a code word.

 def dist_to_codeword(n): return min(hd(n, c) for c in codewords) covering_radius = max(dist_to_codeword(n) for n in range(256)) print(covering_radius)

More coding theory posts

• Introduction to Hamming codes
• Maximum distance separable codes
• Golay codes

The post Error correcting code from octonions first appeared on John D. Cook.