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

Bodewig, Michael; Triesch, Eberhard; Rautenbach, Dieter

doi:34432

An introduction of greedy extension sets for the application on fix free codes = Eine Anwendung von Greedy Extension Sets auf fixfreie Codes

Bodewig, Michael

2015

Verantwortlichkeitsangabevorgelegt von Michael Bodewig

ImpressumAachen : Publikationsserver der RWTH Aachen University 2015

UmfangVI, 106 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2015

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor) ; Rautenbach, Dieter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2015-05-21

Online
URN: urn:nbn:de:hbz:82-rwth-2015-028875
URL: https://publications.rwth-aachen.de/record/479104/files/479104.pdf
URL: https://publications.rwth-aachen.de/record/479104/files/479104.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Mathematik (frei) ; Fix-Free Code (frei) ; Greedy Extension Set (frei) ; 3/4-Conjecture (frei) ; Kraftsum (frei) ; Redundancy (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

Apart from the acceleration of the decoding process, the instantaneous decodability of fix-free codes in both directions makes data retrievable by opposite direction decoding in case of transmission errors. Fix-free codes were first introduced in 1956 by Schützenberger and the variable codeword length justifies their application in compression standards like JPEG-2000, H.263+, and MPEG-4. In regard of a more theoretical treatment, automata and algebraic structures associated with codes take a particularly convenient form in the case of fix-free codes. Therefore, a connection with automata theory and abstract algebra is established. Due to the inclusion of both prefixes and suffixes, fix-free codes inherit their relevance for search theory from prefix-free codes. In addition, the significance of suffix-prefix overlaps for genome assembly discloses a relation with molecular biology.In view of fix-free codes, maximality, the 3/4-Conjecture and optimality are closely connected. The subsets of maximal fix-free codes provide confirmation for the 3/4-Conjecture, which claims the existence of fix-free codes for sequences with a Kraftsum up to 3/4 and would improve the upper bound for the minimum redundancy of fix-free codes. The greedy extension sets introduced in this thesis contribute to the construction of maximal fix-free codes and hence also to the 3/4-Conjecture and provide desirable properties regarding optimality due to small codeword lengths. The main theorem allows the calculation of greedy extension sets with respect to the code which is extended and the set providing the selectable codewords. This calculation is simplified for codes with a fixed length that are extended and initiates the construction of maximal fix-free codes. In contrast to most of the known existence statements in literature, this provides the determination of additional fix-free codes by thinning out the maximal ones. Beside the mentioned constructions, the 3/4-Conjecture is supported by sufficient criteria using extendability and shiftability. On the one hand, the sufficient conditions hold for several special cases, on the other hand, the strong dependence of the number of selectable words on the respective level raises difficulties. As a further method to determine the existence of a fix-free code for a given sequence, an alternative sequence is calculated, for which the existence problem can be solved instead.

OpenAccess:
PDF PDF (PDFA)
(additional files)