hexacode


The hexacode is a 3-dimensional linear codeMathworldPlanetmath of length (http://planetmath.org/LinearCode) 6, defined over the field 𝔽4, all of whose codewords have weight 0, 4, or 6. It is uniquely determined by these properties, up to monomial linear transformations (http://planetmath.org/MonomialMatrix) and in 𝔽4. The hexacode is crucial to the construction of the extended binary Golay code via Curtis’ Miracle Octad Generator. The exposition below follows ([1], Chapter 11). Another for the hexacode is ([2], Chapter 4).

1 Construction of the hexacode

There are several constructions of the hexacode, all leading to the same result. In the following, we write the elements of 𝔽4 as {0,1,Ο‰,ω¯} where Ο‰ is a cube root of unity. We write elements of the hexacode as elements of 𝔽46, separated into three of two.

1. The span of the elements

ω⁒ω¯⁒ω⁒ω¯⁒ω⁒ω¯ω⁒ω¯⁒ω¯⁒ω⁒ω¯⁒ωω¯⁒ω⁒ω⁒ω¯⁒ω¯⁒ωω¯⁒ω⁒ω¯⁒ω⁒ω⁒ω¯

2. The elements of 𝔽46 of the form

(a,b,c,ϕ⁒(1),ϕ⁒(Ο‰),ϕ⁒(ω¯))

where a,b,cβˆˆπ”½4 and ϕ⁒(x)=a⁒x2+b⁒x+c.

3. The elements a⁒b⁒c⁒d⁒e⁒f of 𝔽46 which satisfy the three rules

a+b=c+d=e+f=sa+c+e=a+d+f=b+c+f=b+d+e=ω⁒sb+d+f=b+c+e=a+d+e=a+c+f=ω¯⁒s

Here s is called the of the codeword.

An element of the hexacode is called a hexacodeword.

2 Justification of a hexacodeword

It is not difficult to show that all of the above constructions give the same 3-dimensional linear code of 6. However, it is somewhat tedious to use one of above constructions to determine whether a given element of 𝔽46 is in the hexacode. Instead, it is possible to show that an element of 𝔽46 is a hexacodeword if and only if it satisfies the shape and sign rules below. Using these rules, one can (with some practice) quickly distinguish hexacodewords from non-hexacodewords.

The shape rule says that, up to permutations of the three blocks and flips of the elements within a block, every hexacodeword has one of the shapes

00  00  0000⁒a⁒a⁒a⁒a0⁒a⁒  0⁒a⁒b⁒cb⁒c⁒b⁒c⁒b⁒ca⁒a⁒b⁒b⁒c⁒c

where a,b,c are 1,Ο‰,ω¯ in some .

The sign rule says that in every hexacodeword, either:

  • β€’

    all 3 blocks have sign 0, or

  • β€’

    the productPlanetmathPlanetmath of the signs of the three blocks is positive.

The sign of a block is determined as follows:

  • β€’

    + for 0⁒a or a⁒b where b=a⁒ω

  • β€’

    - for a⁒0 or a⁒b where b=a⁒ω¯

  • β€’

    0 for 00 or a⁒a

where a≠0.

For example,

  • β€’

    00  11⁒ω⁒ω and 01  0⁒ω⁒  1⁒ω¯ are not hexacodewords because they fail the shape rule.

  • β€’

    01  01⁒ω⁒ω¯ satisfies the shape rule, and the signs are + + +, so it is a hexacodeword.

  • β€’

    1⁒ω⁒ω⁒1  1⁒ω satisfies the shape rule, and the signs are + - +, so it is not a hexacodeword.

  • β€’

    00  11  11 satisfies the shape rule, and the signs are 0 0 0, so it is a hexacodeword.

  • β€’

    ω⁒0⁒ω⁒0⁒ω¯⁒1 satisfies the shape rule, and the signs are - - +, so it is a hexacodeword.

3 Completion of a partial hexacodeword

The hexacode has the property that the following two problems always have a unique solution.

1. (3-problem) Given values in any 3 of the 6 positions, completePlanetmathPlanetmathPlanetmathPlanetmath it to a full hexacodeword.

2. (5-problem) Given values in any 5 of the 6 positions, complete it to a full hexacodeword after possibly changing one of the given values.

Conway says that the best method for solving these is to simply ”guess the correct answer, then justify it” (using the shape and sign rules), though he also does give systematic algorithms for solving them.

Examples of 3-problems:

01  1⁒?⁒?⁒?β†’01  10⁒ω¯⁒ω?⁒?⁒  1⁒ω¯⁒?⁒0β†’0⁒ω⁒  1⁒ω¯⁒ω⁒01⁒?⁒ω⁒ω⁒?⁒?β†’11⁒ω⁒ω⁒ω¯⁒ω¯

Examples of 5-problems:

00  11⁒ω⁒?β†’00  11  11⁒ (position 5 changed)0⁒?⁒  1⁒ω¯⁒ω⁒ω¯→0⁒ω⁒  1⁒ω¯⁒ω⁒0⁒ (position 6 changed)Β 1⁒ω⁒?⁒1  1⁒ω→1⁒ω⁒ω¯⁒1  1⁒ω⁒ (no position changed)Β 

References

  • 1 J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices, and Groups. Springer-Verlag, 1999.
  • 2 Robert L. Griess, Jr. Twelve Sporadic Groups. Springer-Verlag, 1998.
Title hexacode
Canonical name Hexacode
Date of creation 2013-03-22 18:43:08
Last modified on 2013-03-22 18:43:08
Owner monster (22721)
Last modified by monster (22721)
Numerical id 15
Author monster (22721)
Entry type Definition
Classification msc 94B05
Related topic MiracleOctadGenerator
Related topic BinaryGolayCode