Applications of combinatorics in coding theory
Duc Tu Dao · 2023
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 di↵erent 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 di↵erence 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 v To pursue a doctorate is a constructive and enlightening adventure paid o↵ by countless distressing experiments and maddening arguments.It would not be possible for me to complete this dissertation without the support of many individuals.