Automorphism groups of self-dual codes

• Automorphismengruppen selbstdualer Codes

Günther, Annika; Nebe, Gabriele (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2009)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2009

Kurzfassung

Diese Arbeit behandelt klassische lineare Blockcodes, wie sie zur Fehlererkennung und Fehlerkorrektur bei der Übertragung und Speicherung von Daten verwendet werden. Der duale Code zu einem solchen linearen Code ist der Orthogonalraum bezüglich eines Euklidischen oder Hermiteschen Skalarprodukts. Ist ein Code mit seinem dualen Code identisch, so heißt er selbstdual. Selbstduale Codes sind von besonderem mathematischen Interesse, zum Beispiel da die Invariantentheorie einen Überblick über mögliche Gewichtszähler liefert und somit den Nachweis erbringen kann, das gewisse Codes optimale fehlerkorrigierende Eigenschaften haben. Die Automorphismengruppe eines Codes besteht aus den Koordinatenpermutationen, die den Code (als Menge) invariant lassen. Besitzt ein Code gewisse Automorphismen, so verleiht ihm dies zusätzliche Struktur. Im Fall der zyklischen Codes etwa, die invariant sind unter zyklischer Koordinatenpermutation, ermöglicht diese zusäzliche Struktur besonders effiziente Decodieralgorithmen. In der vorliegenden Arbeit werden Codes aus darstellungstheoretischer Sicht betrachtet, das heißt, ein Code wird als Modul über der Gruppenalgebra A aufgefasst, die durch seine Automorphismengruppe über dem Grundkörper gebildet wird. Für eine gegebene Permutationsgruppe G werden in bestimmten Fällen notwendige und hinreichende Kriterien für die Existenz eines G-invarianten selbstdualen Codes bestimmt. Insbesondere wird die Situation charakterisiert, in der ein selbstdualer G-invarianter Typ II-Code existiert. Dies sind Codes über Körpern der Charakteristik 2, die eine Verallgemeinerung der doppelt geraden binären Codes darstellen, Ein binärer Code heißt doppelt gerade, falls die Hamming-Gewichte aller Codewörter durch 4 teilbar sind. Weiter wird in Anlehnung an die Knesersche Nachbarschaftsmethode ein Verfahren entwickelt, mit dem sich die Menge C aller selbstdualen G-invarianten Codes algorithmisch bestimmen lässt. Es werden Formeln entwickelt, mit denen sich die Anzahl der selbstdualen G-invarianten Codes a priori, im Wesentlichen aus den Kompositionsfaktoren eines solchen Codes, aufgefasst als A-Modul, bestimmen lässt, falls A halbeinfach ist. Unter Zuhilfenahme eines Ergebnisses von Dickson wird bewiesen, dass genau dann ein selbstdualer G-invarianter Typ II-Code einer durch 8 teilbaren Länge N existiert, wenn G in der alternierenden Gruppe auf N Punkten liegt und ein selbstdualer G-invarianter Code der Länge N existiert (hierfür wird ein einfaches darstellungstheoretisches Kriterium gegeben). Dazu werden selbstduale Typ II-Codes als selbstduale isotrope Teilräume eines quadratischen Raums V beschrieben und G auf natürliche Weise in die orthogonale Gruppe O dieses quadratischen Raums eingebettet. Als Untergruppe von O operiert G auf dem der Menge aller selbstdualen isotropen Teilräume von V, und ein selbstdualer Typ II-Code ist G-invariant genau dann, wenn der entsprechende Teilraum von V unter G stabilisiert wird. Der Stabilisator eines selbstdualen isotropen Teilraums von V liegt nun im Kern der sogenannten Dickson-Invariante, eines Homomorphismus von O, der auf der symmetrischen Gruppe zum Signum einschränkt. Zur algorithmischen Bestimmung aller G-invarianten selbstdualen Codes der Länge N wird der Nachbarschaftsgraph aller solcher Codes eingeführt. Zwei Codes C,D sind adjazent in diesem Graphen genau dann, wenn ihr Schnitt ein maximaler Teilmodul von C ist. Es wird bewiesen, dass dieser Graph stets zusammenhängend ist und daher die Menge aller selbstdualen G-invarianten Codes durch sukzessive Berechnung von Nachbarn bestimmt werden kann, sobald ein einziger solcher Code bekannt ist. Zur Illustration werden für gewisse einfache Gruppen G alle selbstdualen binären Codes bestimmt, deren Automorphismengruppe eine transitive Untergruppe enthält, welche isomorph zu G ist. Die Berechnungen werden durch gewisse kanonische Automorphismen des Nachbarschaftsgraphen erleichtert, indem der Nachbarschaftsalgorithmus auch auf die Suche nach Bahnenvertretern beschränkt werden kann. Ein Kriterium für die Vollständigkeit einer solchen Klassifikation liefern die Formeln zur Bestimmung der Anzahl aller selbstdualen G-invarianten Codes, falls A halbeinfach ist. Diese Formeln werden mit Hilfe einer Morita-Äquivalenz bewiesen, die das Problem der Anzahlbestimmung im Wesentlichen auf das wohlbkannte Problem der Anzahlbestimmung linearer selbstdualer Codes reduziert.