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...

وصف كامل

محفوظ في:
التفاصيل البيبلوغرافية
المؤلف الرئيسي: Ho, Shaun
مؤلفون آخرون: Kiah Han Mao
التنسيق: Thesis-Master by Research
اللغة:English
منشور في: Nanyang Technological University 2020
الموضوعات:
الوصول للمادة أونلاين:https://hdl.handle.net/10356/143338
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
الوصف
الملخص: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.