Konstruktive Methoden in der algebraischen Codierungstheorie für lineare Codes über endlichen Kettenringen
Zusammenfassung der Projektergebnisse
Fehlerkorrigierende Codes werden heute in nahezu jeder Form der Informationsübertragung und Datenspeicherung eingesetzt. Prominente Beispiele sind Kommunikation mit Weltraumsonden, WLAN, Mobiltelefon, digitales Fernsehen, sowie nahezu alle digitale Speichermedien, wie Festplatten und SSDs. Zieht man in Betracht, dass digitale Kommunikation und digitale Speichermedien mittlerweile allgegenwärtig und gewaltige Wirtschaftsfaktoren sind, wird verständlich, dass jede softwaretechnische Verbesserung bedeutende Auswirkung haben kann. Dazu zählen auch verbesserte Fehlerkorrektur-Verfahren, die z.B. direkt Einfluß auf die Akkuleistung von Mobilgeräten haben können. Aus diesem Grund ist die Suche nach immer besseren Codes zur Fehlerkorrektur höchst wichtig. Ausgehend von der bahnbrechenden Entdeckung aus dem Jahr 1994, dass sich einige sehr gute Codes linear über dem Ring Z4 darstellen lassen, wurden in den letzten Jahren verstärkt lineare Codes über Ringen (R-lineare Codes) untersucht. Zur systematischen Suche nach neuen Beispielen sehr guter ringlinearer Codes wurden die in Bayreuth entwickelten und bereits in verschiedenen Gebieten der diskreten Mathematik sehr erfolgreich eingesetzten computergestützten Konstruktionsverfahren auf die vorliegende Fragestellung angepasst. Es gelang damit, zahlreiche neue Beispiele ringlinearer Codes zu finden, deren Fehlerkorrektur-Eigenschaften besser sind als die aller bekannten vergleichbaren linearen Codes über Körpern. In einigen Fällen waren die Codes sogar besser als alle möglichen vergleichbaren linearen Codes über Körpern. Die Ergebnisse wurden in der ersten umfassenden Datenbank zu ringlinearen Codes zusammenmgefasst. Der größte Erfolg des Projektes war, für einige der sehr guten ringlinearen Codes eine rein geometrische Beschreibung zu finden. Überraschenderweise konnten davon ausgehend sogar mehrere unendliche Serien ringlinearer Codes angegeben werden, deren Glieder alle sehr gute Fehlerkorrektur- Eigenschaften besitzen. Möglicherweise sind sogar alle Elemente dieser Serien besser als die vergleichbaren linearen Codes über Körpern. Einen Beweis hierfür zu finden, ist bislang allerdings nicht gelungen. Bemerkenswert ist, dass abgesehen von ringlinearen Verallgemeinerungen klassischer Codeserien (wie z.B. den Z4-linearen QR-Codes) seit der erwähnten bahnbrechenden Arbeit aus dem Jahr 1994 keine vergleichbaren unendlichen Serien ringlinearer Codes mehr gefunden worden waren. Die den ringlinearen Codes zugrunde liegende Geometrie ist die Hjelmslev-Geometrie. Mit den oben erwähnten Computersuchverfahren konnten in diesen Geometrien zudem zahlreiche neue Arcs (Bögen) gefunden werden. Dadurch wurde das Wissen über maximale Punktanzahlen bei Arcs in Hjelmslev-Geometrien deutlich erweitert. Die ästhetische Komponente dieser geometrischen Betrachtungen fand auf dem Kalenderblatt für den Monat Oktober 2010 des Mathematik-Kalenders der DFG Eingang. Darin wurde der Zusammenhang zwischen einem Z4-linearen Code und einem sogenannten Hyperoval in der projektiven Hjelmslev-Ebene über Z4 veranschaulicht. Im Rahmen des Projektes entstand ein verbesserter Algorithmus zur Bestimmung der Minimaldistanz und zur Bestimmung des Gewichtszählers, eines ringlinearen Codes. Dessen Implementierung ermöglicht es, auch für Codes die Minimaldistanz, bzw. den Gewichtszähler zu bestimmen, die für vergleichbare Algorithmen in den verbreiteten Computer-Algebra-Systems nicht handbar sind. Während des Projekts haben sich einige Fragestellungen ergeben, die sich für eine weitere Untersuchung anbieten. Zuallererst wäre es schön, einen Beweis zu finden, dass sämtliche Codes der gefundenen neuen Serien (aber auch der schon bekannten Serie der Kerdock-Codes) besser sind als lineare Codes mit den gleichen Parametern. Dies ist vermutlich eine schwierige Frage. Desweiteren wäre es interessant, sich mittels einer vollständigen Klassifikation (ähnlich wie bei der klassischen projektiven Ebene) einen vollständigen Überblick über die u-Arcs maximaler Ordnung zu verschaffen. Im abgeschlossenen Projekt wurden nur die Ordnungen bestimmt. Als letzte Fragestellung bleibt noch der Übergang zu Kettenringen mit Kettenlängen > 2. Hier wäre insbesondere der Ring Z8 zu nennen, der ebenfalls binäre Codes liefert.
Projektbezogene Publikationen (Auswahl)
-
“Double and bordered α-circulant self-dual codes over finite commutative chain rings,” in Proceedings of the Eleventh International Workshop on Algebraic and Combinatorial Coding Theory 2008 (ACCT-2008), pp. 144–150, 2008
M. Kiermaier and A. Wassermann
-
“New arcs of maximal size in projective Hjelmslev planes of order 9,” Compt. Rend. Acad. bulg. Sci., vol. 63, no. 2, pp. 171–180, 2010
T. Honold, M. Kiermaier, and I. Landjev
-
“New bounds for codes over finite frobenius rings,” Des. Codes Cryptogr., vol. 57, no. 2, pp. 169–179, 2010
E. Byrne, M. Greferath, A. Kohnert, and V. Skachek
-
“2-arcs of maximal size in the affine and the projective Hjelmslev plane over Z25 ,” Adv. Math. Commun., vol. 5, no. 2, pp. 287–301, 2011
M. Kiermaier, M. Koch, and S. Kurz
-
“A Z4 -linear code of high minimum Lee distance derived from a hyperoval,” Adv. Math. Commun., vol. 5, no. 2, pp. 275–286, 2011
M. Kiermaier and J. Zwanzger
-
“The maximal size of 6- and 7-arcs in projective Hjelmslev planes over chain rings of order 9,” Sci. China Math., vol. 55, no. 1, pp. 73–92, 2012
T. Honold and M. Kiermaier
