Constructing constrained prefix-free codes

Abstract

The Optimal Coding problem is a well-known problem in information theory. The aim is for two parties to transmit information to each other through channels as efficiently as possible. In this Final Year Project, we construct prefi x-free code under runlength-limited (RLL) constraints. We apply this constraint on the well-known Huffman codes, as well as construct other versions of these constraint codes, based on Horibe, and compare the efficiency of both codes. We construct 2-RLL codes in two ways: Tribonacci trees with equal probabilities, and weight balancing technique with probabilities of a geometric distribution. Finally we compare the constructed codes against Huffman codes with constraint and concluded that Huffman codes with 2-RLL constraint are more efficient.