Sequences and their applications

• Main Author: Chrisnata, Johan
• Other Authors: Kiah Han Mao
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Science::Mathematics::Sequences
• Online Access: https://hdl.handle.net/10356/155586
• Institution: Nanyang Technological University

Binary and q-ary sequences have always been used in communication channel as the carrier or the vessel of information. In order to establish an efficient and error-free communication channel, investigations on the properties of sequences are crucial. This dissertation is devoted to the study of sequences to investigate its properties which can be useful to establish a more reliable communication channel. The properties that we will investigate in this dissertation are the linear complexities of sequences and the reconstruction of a sequence from its sub-sequences. The linear complexity of a binary sequence is defined as the length of the shortest linear feedback shift-register that generates the binary sequence. In the first part of this dissertation, we devised a novel and efficient algorithm to find the linear complexity of any binary sequence. This algorithm is a generalization of the well-known Games-Chan algorithm. Furthermore, this algorithm can be applied in linear time and is faster than previous well-known algorithms for certain parameters of length of periodic sequences. The second property that we will investigate in this dissertation is the reconstruction capability of binary sequences in particular from its subsequences. This is called the sequence reconstruction problem. The problem considers a communication scenario where the sender transmits a sequence from some codebook and the receiver obtains multiple noisy reads of the original sequence. Noisy reads here refer to possibly erroneous copies of the original sequence. The receiver/decoder then aims to reconstruct the original sequence from these noisy reads. The error that we consider in this dissertation is only deletion error where some elements of the original sequence might be deleted. Thus, the noisy reads here are in the form of subsequences of the original sequence. There are two variants of the problem that we are going to consider for this problem. Firstly, we assume that the decoder receives all possible subsequences of a certain fixed length from the original sequence, including its multiplicity. In other words, the decoder obtains the profile of sub-sequences of the original sequence, namely the k-deck of the binary sequence . The k-deck of a sequence is defined as the multiset of all its subsequences of length k. We determine the exact value of the number of distinct k-decks for all binary sequences of the same length for small values of k and provide asymptotic estimates of this value when k is fixed. Specifically, we introduce a trellis-based method to compute this value for fixed k in polynomial time. The second variant is under the assumption that the decoder does not receive every possible subsequence of the original sequence, but only receives some fixed number of noisy reads. In other words, the decoder receives a fixed number of subsequences. In this case, we also assume that all received noisy reads are distinct. We construct codes that are capable of correcting t deletions with multiple noisy reads. Special attention is given to the case when t=1 and t=2.