Codi binari de Golay

Codi binari de Golay

Matriu generadora del Codi Binari Golay estès. La matriu comprèn la matriu identitat i el complement de la matriu d'adjacència de l'icosaedre.

En matemàtiques i enginyeria electrònica, un codi de Golay binari és un tipus de codi lineal de correcció d'errors utilitzat en comunicacions digitals. El codi de Golay binari, juntament amb el codi de Golay ternari, té una connexió particularment profunda i interessant amb la teoria dels grups esporàdics finits en matemàtiques. Aquests codis s'anomenen en honor de Marcel JE Golay, el document de 1949 que els presentava ha estat anomenat, per ER Berlekamp, la "millor pàgina publicada" en teoria de codificació.

Hi ha dos codis binaris de Golay estretament relacionats. El codi de Golay binari estès, G₂₄ (de vegades anomenat "codi de Golay" en la teoria de grups finits) codifica 12 bits de dades en una paraula de 24 bits de manera que es pugui corregir qualsevol error de 3 bits o qualsevol error de 7 bits. es poden detectar errors de bits. L'altre, el codi de Golay binari perfecte, G₂₃, té paraules de codi de longitud 23 i s'obté del codi de Golay binari estès suprimint una posició de coordenades (per contra, el codi de Golay binari estès s'obté del codi de Golay binari perfecte afegint un bit de paritat). En la notació de codificació estàndard, els codis tenen els paràmetres [24, 12, 8] i [23, 12, 7], corresponents a la longitud de les paraules de codi, la dimensió del codi i la distància mínima de Hamming entre dues paraules de codi, respectivament.

Definició matemàtica

En termes matemàtics, el codi de Golay binari estès G ₂₄ consta d'un subespai lineal de 12 dimensions W de l'espai V = F24
2 de paraules de 24 bits de manera que dos elements diferents de W es diferencien en almenys 8 coordenades. W s'anomena codi lineal perquè és un espai vectorial. En total, W comprèn 4096 = 2¹² elements.

• Els elements de W s'anomenen paraules de codi. També es poden descriure com a subconjunts d'un conjunt de 24 elements, on l'addició es defineix com prendre la diferència simètrica dels subconjunts.
• Al codi binari de Golay estès, totes les paraules de codi tenen pesos Hamming de 0, 8, 12, 16 o 24. Les paraules de codi de pes 8 s'anomenen octades i les paraules de codi de pes 12 s'anomenen dodecades.
• Les octades del codi G ₂₄ són elements del sistema Steiner S(5,8,24). Hi ha 759 = 3 × 11 × 23 octades i 759 complements. Es dedueix que hi ha 2576 = 2⁴ × 7 × 23 dodecades.
• Dues octades es tallen (tenen 1 en comú) en coordenades 0, 2 o 4 en la representació vectorial binària (aquestes són les mides d'intersecció possibles a la representació del subconjunt). Una octada i una dodecada es tallen a 2, 4 o 6 coordenades.
• Fins a reetiquetar les coordenades, W és únic.

Aplicacions pràctiques dels codis Golay

Missions a l'espai profund de la NASA

La correcció d'errors va ser vital per a la transmissió de dades a les naus espacials Voyager 1 i 2, sobretot perquè les limitacions de memòria dictaven la descàrrega de dades pràcticament a l'instant sense deixar segones oportunitats. Centenars d'imatges en color de Júpiter i Saturn en els seus sobrevols de 1979, 1980 i 1981 es transmetrien dins d'un ample de banda restringit de telecomunicacions. La transmissió d'imatges en color va requerir tres vegades més dades que les imatges en blanc i negre, de manera que el codi Reed-Muller de correcció de 7 errors que s'havia utilitzat per transmetre les imatges de Mariner en blanc i negre es va substituir per la velocitat de dades molt més alta Golay (24,12). ,8) codi.

Comunicacions per ràdio

Els estàndards militars nord-americans MIL-STD-188 per a l'establiment automàtic d'enllaços en sistemes de ràdio d'alta freqüència especifiquen l'ús d'un codi Golay estès (24, 12) per a la correcció d'errors directes.