Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/165395
Title: Applications of combinatorics in coding theory
Authors: Dao, Duc Tu
Keywords: Science::Mathematics
Issue Date: 2023
Publisher: Nanyang Technological University
Source: Dao, D. T. (2023). Applications of combinatorics in coding theory. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/165395
Abstract: Combinatorics is the branch of mathematics studying the enumeration of sets of elements. It includes a diversity of topics that have unexpected interrelations and tremendous applications. This dissertation is devoted to applying combinatorial tools to solve recent problems in coding theory. In the first part of this dissertation, we study positioning sequences, whose all subsequences of length n not only are different but also satisfy additional properties. Without extra properties, the sequences are known as de Bruijn sequences. We consider robustness as the first additional property. A binary sequence is a robust positioning sequence of streng n, distance d if every substring of length n is distance d apart from each other. For n <= 50, we determine exactly the maximum length of robust positioning sequences for certain parameters. In the process, we provide generalizations of the Plotkin bound for such sequences and introduce a class of combinatorial objects, known as partial difference packing. The run-length limited constraint is another property to embed in positioning sequences. Considering gaps in the current model in free-space quantum key distribution, we want each subsequence of the positioning sequences to contain at most s consecutive 0’s. Exploiting the de Bruijn graph, we determine the optimal upper bound for the length of run-length limited positioning sequences. Based on Lyndon words, a classical object in combinatorics, we obtain sequences that attain the upper bound. The remaining part of this dissertation considers constant weight codes. We are interested in the methods to encode arbitrary messages into codewords of a certain weight with minimal average redundancy. Inspired by the best-known schemes introduced by Immink (2014), we construct an encoding scheme with average redundancy differing from the optimal redundancy by a constant. Combinatorial results on the enumeration of lattice paths support us to estimate the average redundancy of new schemes asymptotically.
URI: https://hdl.handle.net/10356/165395
DOI: 10.32657/10356/165395
Schools: School of Physical and Mathematical Sciences 
Rights: This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0).
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Dao Duc Tu_thesis.pdf1.59 MBAdobe PDFThumbnail
View/Open

Page view(s)

214
Updated on Feb 20, 2024

Download(s) 50

100
Updated on Feb 20, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.