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...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
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 |