Constructing constrained prefix-free codes

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

Full description

Saved in:
Bibliographic Details
Main Author: Ng, Kai Xiang
Other Authors: Kiah Han Mao
Format: Final Year Project
Language:English
Published: Nanyang Technological University 2020
Subjects:
Online Access:https://hdl.handle.net/10356/139510
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-139510
record_format dspace
spelling sg-ntu-dr.10356-1395102023-02-28T23:13:04Z Constructing constrained prefix-free codes Ng, Kai Xiang Kiah Han Mao School of Physical and Mathematical Sciences hmkiah@ntu.edu.sg Science::Mathematics Engineering::Computer science and engineering::Data::Coding and information theory 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. Bachelor of Science in Mathematical Sciences 2020-05-20T02:53:07Z 2020-05-20T02:53:07Z 2020 Final Year Project (FYP) https://hdl.handle.net/10356/139510 en application/pdf Nanyang Technological University
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Science::Mathematics
Engineering::Computer science and engineering::Data::Coding and information theory
spellingShingle Science::Mathematics
Engineering::Computer science and engineering::Data::Coding and information theory
Ng, Kai Xiang
Constructing constrained prefix-free codes
description 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.
author2 Kiah Han Mao
author_facet Kiah Han Mao
Ng, Kai Xiang
format Final Year Project
author Ng, Kai Xiang
author_sort Ng, Kai Xiang
title Constructing constrained prefix-free codes
title_short Constructing constrained prefix-free codes
title_full Constructing constrained prefix-free codes
title_fullStr Constructing constrained prefix-free codes
title_full_unstemmed Constructing constrained prefix-free codes
title_sort constructing constrained prefix-free codes
publisher Nanyang Technological University
publishDate 2020
url https://hdl.handle.net/10356/139510
_version_ 1759854272483164160