Codi de Golay ternari

En teoria de codificació, els codis de Golay ternaris són dos codis de correcció d'errors estretament relacionats. El codi generalment conegut simplement com a codi ternari de Golay és un $[11,6,5]_{3}$ -codi, és a dir, és un codi lineal sobre un alfabet ternari; la distància relativa del codi és tan gran com pot ser possible per a un codi ternari i, per tant, el codi de Golay ternari és un codi perfecte. El codi de Golay ternari estès és un codi lineal [12, 6, 6] obtingut afegint un dígit de verificació de suma zero al codi [11, 6, 5]. En la teoria de grups finits, el codi de Golay ternari estès de vegades es coneix com el codi de Golay ternari.

Propietats

Codi de Golay ternari

El codi ternari de Golay consta de 3⁶ = 729 paraules de codi. La seva matriu de control de paritat és

$\left[{\begin{array}{cccccc|ccccc}2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1&1&2&2&0&0&0&0&1\end{array}}\right].$

Dues paraules de codi diferents difereixen almenys en 5 posicions. Cada paraula ternària de longitud 11 té una distància de Hamming de com a màxim 2 a partir d'una paraula de codi exactament. El codi també es pot construir com el codi de residu quadràtic de longitud 11 sobre el camp finit F₃ (és a dir, el camp de Galois GF(3)).

Utilitzat en una piscina de futbol amb 11 partits, el codi de Golay ternari correspon a 729 apostes i garanteix exactament una aposta amb com a màxim 2 resultats equivocats.

El conjunt de paraules de codi amb Hamming pes 5 és un disseny 3-(11,5,4).

La matriu generadora donada per Golay (1949, Taula 1.) és

$\left[{\begin{array}{cccccc|ccccc}1&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&1&0&2\\0&0&0&1&0&0&2&1&0&1&2\\0&0&0&0&1&0&2&0&1&2&1\\0&0&0&0&0&1&0&2&2&1&1\\\end{array}}\right].$

El grup d'automorfisme del codi ternari de Golay (original) és el grup Mathieu M11, que és el més petit dels grups simples esporàdics.

Codi Golay ternari estès

L'enumerador de pes complet del codi de Golay ternari estès és

$x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).$

El grup d'automorfismes del codi de Golay ternari estès és 2. M₁₂, on M₁₂ és el grup Mathieu M12.

El codi de Golay ternari estès es pot construir com l'envergadura de les files d'una matriu de Hadamard d'ordre 12 sobre el camp F₃.

Considereu totes les paraules de codi del codi estès que només tenen sis dígits diferents de zero. Els conjunts de posicions en què apareixen aquests dígits diferents de zero formen el sistema de Steiner S(5, 6, 12).

Una matriu generadora per al codi de Golay ternari estès és

$\left[{\begin{array}{ccccccccccccc}1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&2&2&1\\0&0&1&0&0&0&|&1&1&0&1&2&2\\0&0&0&1&0&0&|&1&2&1&0&1&2\\0&0&0&0&1&0&|&1&2&2&1&0&1\\0&0&0&0&0&1&|&1&1&2&2&1&0\\\end{array}}\right]=[I_{6}|B].$

La matriu de control de paritat corresponent per a aquesta matriu generadora és $[-B|I_{6}]^{T}$, on $T$ denota la transposició de la matriu.

Una matriu generadora alternativa per a aquest codi és

$\left[{\begin{array}{rrrrrrcrrrrrr}1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&-1&-1&1\\0&0&1&0&0&0&|&1&1&0&1&-1&-1\\0&0&0&1&0&0&|&1&-1&1&0&1&-1\\0&0&0&0&1&0&|&1&-1&-1&1&0&1\\0&0&0&0&0&1&|&1&1&-1&-1&1&0\\\end{array}}\right]=[I_{6}|B_{alt}].$

I la seva matriu de control de paritat és $[-B_{alt}|I_{6}]^{T}$.

Els tres elements del camp finit subjacent es representen aquí per $\{0,1,-1\}$, més que per $\{0,1,2\}$. També s'entén que $2=1+1=-1$ (és a dir, la inversa additiva d'1) i $-2=(-1)+(-1)=1$. Els productes d'aquests elements de camp finit són idèntics als dels nombres enters. Les sumes de files i columnes s'avaluen mòdul 3.

Història i aplicacions

El codi ternari de Golay va ser publicat per Golay el 1949. Va ser descobert de manera independent dos anys abans per l'entusiasta de la piscina de futbol finlandesa Juhani Virtakallio, que el va publicar el 1947 als números 27, 28 i 33 de la revista de futbol Veikkaaja. (Barg 1993)

S'ha demostrat que el codi ternari de Golay és útil per a una aproximació a la computació quàntica tolerant a errors coneguda com a destil·lació d'estat màgic.