Computergestützte Suche nach optimalen linearen Codes über endlichen Kettenringen unter Verwendung heuristischer Methoden

Titelangaben

Zwanzger, Johannes:
Computergestützte Suche nach optimalen linearen Codes über endlichen Kettenringen unter Verwendung heuristischer Methoden.
Bayreuth , 2011
( Dissertation, 2011 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

In den Jahren 1968 und 1972 entdeckten Preparata bzw. Kerdock zwei unendliche Serien sehr guter nichtlinearer binärer Codes. Beide umfassen den Nordstrom-Robinson-Code, einen (16, 2^8, 6)-Code, dessen Minimaldistanz die obere Schranke von 5 für lineare binäre Codes gleicher Länge und Kardinalität übertrifft. Lange Zeit war unklar, warum die Codes beider Serien formal dual zueinander sind, d. h. warum ihre Gewichtszähler die MacWilliams-Identität erfüllen. Erst in den neunziger Jahren fand man heraus, dass sie als Bilder linearer Codes über dem Ring Z4 unter der sogenannten Grayabbildung dargestellt werden konnten. Diese Entdeckung löste einerseits das Rätsel und rückte gleichzeitig die Untersuchung linearer Codes über Z4 in den Fokus der Forschung. In den Folgejahren wurden Codes über endlichen Kettenringen als natürliche Verallgemeinerung der klassischen Codes über endlichen Körpern erkannt. Für jeden endlichen Kettenring R ist der Faktorring R/Rad(R) isomorph zu einem endlichen Körper GF(q), und mit Hilfe einer verallgemeinerten Version der Grayabbildung kann jeder R-lineare Code in einen - für gewöhnlich nichtlinearen - Code über GF(q) überführt werden. R-lineare Codes, deren Graybild eine bessere Minimaldistanz aufweist als optimale lineare Codes über GF(q) mit denselben Parametern, nennen wir BTL-Codes (better-than-linear). Ist noch unklar, ob lineare Codes derselben Minimaldistanz über GF(q) existieren, sprechen wir von BTKL-Codes (better-than-known-linear). Im Unterschied zu den umfassenden Tabellen für lineare Codes über Körpern gab es - abgesehen von Z4 - bisher nur wenig vergleichbares Datenmaterial zu linearen Codes über endlichen Kettenringen. Diese Lücke zu schließen und gleichzeitig nach weiteren Beispielen für BTL- und BTKL-Codes zu suchen, waren die Hauptziele der vorliegenden Arbeit. Um dies zu erreichen, wurde ein heuristischer Algorithmus aus meiner Diplomarbeit für die Suche nach guten linearen Codes über endlichen Körpern auf die Situation über endlichen Kettenringen verallgemeinert. Es handelt sich hierbei um einen Greedy-Algorithmus, der versucht, die gewünschten Codes durch schrittweises Erweitern von Generatormatrizen zu konstruieren. Die Entscheidungen in jedem Schritt basieren dabei auf einer von probabilistischen Überlegungen geleiteten Bewertungsfunktion. Eine weitere Verallgemeinerung ermöglichte es außerdem, die Methode auf eine größere Klasse von Problemen anzuwenden. In dieser Arbeit betraf dies im Speziellen die Konstruktion linearer Codes nach der Kramer-Mesner-Methode, also solchen, deren Automorphismengruppe eine bestimmte, vorgeschriebene Untergruppe enthält. Mit Hilfe dieser Verfahren wurde eine Datenbank von mehr als 93.000 linearen Codes mit hoher Minimaldistanz über 24 verschiedenen endlichen Kettenringen aufgebaut. Mehr als 1.200 dieser Codes sind als optimal nachgewiesen. Außerdem wurden mehrere neue BTL- und BTKL-Codes gefunden. Einer von ihnen entpuppte sich als der erste Vertreter einer unendlichen Serie über Z4, für deren beiden Anfangsglieder die BTL-Eigenschaft gezeigt werden konnte. Für einen anderen Code fand sich eine interessante geometrische Interpretation. Die Methoden wurden auch zur Konstruktion klassischer Codes über endlichen Körpern mit vorgeschriebener Automorphismengruppe eingesetzt. Dies führte zur Verbesserung der internationalen Tabellen für die beste bekannte Minimaldistanz an insgesamt 497 Stellen, wobei mindestens 38 der gefundenen Codes optimal sind. Auf Grundlage dieser Ergebnisse ist festzustellen, dass die verallgemeinerte Version des Algorithmus sich als mächtiges Werkzeug für Konstruktionsprobleme der hier vorliegenden Art erwiesen hat. Die erzeugten Tabellen legen außerdem die Vermutung nahe, dass BTL- und BTKL-Codes eher seltene Objekte sind, insbesondere für andere Kettenringe als Z4.

Abstract in weiterer Sprache

In 1968 (by Preparata) and 1972 (by Kerdock), two infinite series of very good nonlinear binary codes were discovered. Both families include the Nordstrom-Robinson code, a (16, 2^8, 6)-code which exceeds the upper bound of 5 on the minimum distance of linear binary codes of the same size and length. For a long time it was not clear why the codes of the Kerdock and Preparata series are formal duals of each other, i. e. why their weight enumerators satisfy the MacWilliams identities. Only in the 1990s it was discovered that they could be represented as the image of Z4-linear codes under the so-called Gray map, which solved the riddle and brought the investigation of linear codes over the ring Z4 into the major focus of research. In the following years, codes over finite chain rings were recognized as a natural generalization of the classical codes over finite fields. For every finite chain ring R, the factor ring R/Rad(R) is isomorphic to a finite field GF(q), and by application of a generalized version of the Gray map, any R-linear code can be translated into a - usually nonlinear - code over GF(q). R-linear codes whose Gray image has a better minimum distance than optimal linear codes over GF(q) with the same parameters are called BTL-codes (better-than-linear). The term BTKL-codes (better-than-known-linear) is used if it is not known yet whether linear codes of equal minimum distance over GF(q) exist. In contrast to the large tables for linear codes over finite fields, there were - except for Z4 - only few results on linear codes over finite chain rings. Closing this gap and simultaneously looking for new examples of BTL- and BTKL-codes was the main objective of this thesis. To achieve the goal, a heuristic algorithm for the construction of good linear codes over finite fields from my diploma thesis was generalized to the situation over finite chain rings. It works by stepwise extension of generator matrices in a greedy manner which is based on a probabilistic evaluation function. A further generalization made it applicable to a wider range of problems, in particular to the construction of linear codes by the method of Kramer and Mesner, i. e. by prescribing a subgroup which must be contained in the automorphism group of the codes. Using these methods, a database of more than 93.000 high quality linear codes for 24 different finite chain rings was created. More than 1.200 of these are proven optimal and several new examples of BTL- and BTKL-codes were found. One of them lead to the discovery of an infinite series of Z4-linear codes whose first two members could be proven to be BTL. For another one an interesting geometric interpretation was found. The algorithm was also applied to classical linear codes over finite fields. Here the entries of the international tables for the lower bound on the minimum distance could be improved at 497 positions, in at least 38 cases the corresponding codes are optimal. These results show that the generalized version of the algorithm is a powerful tool for construction problems like those discussed in this thesis. Further, the generated tables suggest that BTL- and BTKL-codes do not exist in abundance, especially not for chain rings other than Z4.