An introduction of greedy extension sets for the application on fix free codes

• Eine Anwendung von Greedy Extension Sets auf fixfreie Codes

Bodewig, Michael; Triesch, Eberhard (Thesis advisor); Rautenbach, Dieter (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2015)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2015

Kurzfassung

Abgesehen von der Beschleunigung des Dekodierungsprozesses, verhindert die sofortige Dekodierbarkeit fixfreier Codes in beide Richtungen im Fall von Übertragungsfehlern den Verlust von Daten durch entgegengerichtete Dekodierung. Fixfreie Codes wurden zum ersten Mal von Schützenberger im Jahr 1956 betrachtet und die variable Codewortlänge rechtfertigt ihre Anwendung in Kompressionsstandards wie JPEG-2000, H.263+ und MPEG-4. Ein theoretischerer Zugang offenbart besonders positive Eigenschaften von Automaten und algebraische Strukturen, die mit Codes assoziiert werden, im Fall von fixfreien Codes. Da fixfreie Codes sowohl die Struktur von Präfixen als auch Suffixen berücksichtigen, wird ihre Relevanz für Suchprobleme von den präfixfreien Codes vererbt. Zudem etabliert die Wichtigkeit von Suffix-Präfix-Überlappungen für die Entschlüsselung des menschlichen Genoms eine Verbindung zur Molekularbiologie. In Bezug auf fixfreie Codes sind Maximalität, die 3/4-Vermutung und Optimalität eng verknüpft. Teilmengen maximaler fixfreier Codes bekräftigen die 3/4-Vermutung, welche die Existenz fixfreier Codes für Zahlenfolgen mit Kraftsumme bis zu 3/4 behauptet und die obere Schranke der minimalen Redundanz fixfreier Codes verbessern würde.Die in dieser Dissertation vorgestellten greedy extension sets tragen zur Konstruktion fixfreier Codes und daher auch zur 3/4-Vermutung bei und haben wünschenswerte Optimalitätseigenschaften aufgrund kleiner Codewortlängen. Der Hauptsatz ermöglicht die Bestimmung von greedy extension sets in Abhängigkeit vom zu erweiternden Code und der Menge wählbarer Codewörter. Diese Berechnung wird für zu erweiternde Codes fester Länge vereinfacht und ist Ausgangspunkt für die Konstruktion maximaler fixfreier Codes. Im Gegensatz zu den meisten Existenzaussagen in der Literatur, ermöglicht dies die Ermittlung weiterer fixfreier Codes durch Ausdünnung der maximalen. Neben den genannten Konstruktionen wird die 3/4-Vermutung durch hinreichende Bedingungen bekräftigt, die Erweiterungen und Verschiebungen verwenden. Zum einen werden diese hinreichenden Bedingungen in speziellen Fällen nachgewiesen, zum anderen entstehen Schwierigkeiten durch die starke Abhängigkeit der Anzahl wählbarer Wörter von der jeweiligen Länge. Als weitere Methode zur Bestimmung der Existenz fixfreier Codes für eine gegebene Zahlenfolge, wird eine alternative Zahlenfolge berechnet, für welche stattdessen die Existenzfrage geklärt werden kann.

Einrichtungen

• Lehrstuhl II für Mathematik (für Ingenieure) [113210]
• Fachgruppe Mathematik [110000]