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)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2015

Abstract

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.

Institutions

• Chair of Mathematics II (for Engineers) [113210]
• Department of Mathematics [110000]