Applications of combinatorics in coding theory

• Main Author: Dao, Duc Tu
• Other Authors: Kiah Han Mao
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/165395
• Institution: Nanyang Technological University

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.