On prefix codes satisfying RLL-constraint for Zipf distribution

Abstract

The study of Information Theory has been ubiquitously applied to many fields in the digital world, with significant focus in transmitting data through channels as efficiently as possible. Therein lies the Optimal Coding Problem; where symbols of varying probabilities of occurring in the source text are encoded to as few bits as possible. In this thesis, we will focus on special type of codes which are bound by the Runlength-limited constraint. We apply this constraint to familiar optimal compression algorithms, like Huffman coding, as well as construct our own version of these constraint codes, with help from a dynamic programming algorithm made by Golin. The results obtained from testing the efficiency of these codes showed that Golin’s construction is more efficient than Huffman coding with the Runlength-limited constraint, in terms of optimality. Finally, we further analyse the structures of coding trees that follow the Runlength-limited constraint and show that such trees produce very particularly unique patterns.