Construction of and applications for optimal spreading sequences based on ultra discrete dynamical systems

本文在超离散动力系统的基础上构造了最优扩展序列。对于它们的应用，我们考虑了具有马尔可夫链扩展序列的异步扩频多址通信系统。三年研究的主要成果总结如下：i)通过对大偏差分析的改进，得到了此类系统中误码概率的精确渐近分析。将误码率的理论表达式与实验结果进行比较，我们证实，与扩展序列长度相比，用户数量过少时，中心极限渐近分析无效，但对于大偏差渐近分析则是相关的。ii)考虑离散分段单调递增马尔可夫变换，给出了基于离散化变换生成所有全长序列的有界单调真值表算法。该算法适用于所有de Bruijn序列的生成。iii)给出了de Bruijn序列归一化自相关函数最小值的一个新的下界。

In this research we constructed optimal spreading sequences based on ultra discrete dynamical systems. For their applications, we considered asynchronous spread spectrum multiple access communication systems with spreading sequences of Markov chains. The main results in the three-year study are summarized as follows. i) By refinement of the large deviations analysis, we obtained exact asymptotic analyses of bit error probabilities in such systems. Comparing theoretical expressions of bit error probabilities with experimental results, we confirmed that for too small numbers of users compared to the lengths of spreading sequences, the central limit asymptotic analyses became invalid, but for large deviations asymptotic analyses turned out to be relevant. ii) We considered discretized piecewise-monotone-increasing Markov transformations and gave an algorithm, called the bounded monotone truth-table algorithm, for generating all full-length sequences which were based on the discretized transformations. The algorithm was applicable to generation of all de Bruijn sequences. iii) We gave a novel lower bound of the minimum values of the normalized auto-correlation functions for de Bruijn sequences.