On prefix codes satisfying RLL-constraint for Zipf distribution
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis-Master by Research |
| Language: | English |
| Published: |
Nanyang Technological University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/143338 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|