Hadamard Codes and Sphere Packing

Yesterday Levent Alpoge announced that he and his colleagues had discovered a new Hadamard matrix using Claude AI. That motivated a post I wrote this morning on how to construct Hadamard matrices. I mentioned in that post that these matrices arise in applications.

This evening I gave an example, describing how NASA used a Hadamard matrix of order 32 to transmit photos from the Mariner 9 spacecraft in 1971.This post will give another application: sphere packing.

Conway and Sloane [1] give a correspondence between binary codes and sphere packings that they call Construction A. Given an (n,M, d) binary code C, center a sphere on a point x if and only ifx is a congruent (mod 2) to codeword in C.

Here (n,M, d) means an error correcting code that encodes M bits of data as strings ofn bits, with a minimum Hamming distance between code words ofd, i.e. all codewords differ in at leastd bits.

The previous post described how to create a (32, 6, 16) code by stacking a Hadamard matrixH of order 32 on top of -H and turning -1's into 0's. The analogous construction for a (8, 4, 4) Hadamard code givesE₈, the densest packing in ⁸.

We start with the Hadamard matrix

and obtain the matrix

whose centers form the sphere packing.

This doesn't look like the E8 sphere packing as it is usually presented, but it's isomorphic.

[1] J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer. 1999.

The post Hadamard Codes and Sphere Packing first appeared on John D. Cook.