LINEAR COMPLEXITY AND RELATED COMPLEXITY MEASURES
LINEAR COMPLEXITY AND RELATED COMPLEXITY MEASURES
复制标题
DOI：
10.1142/9789812837172_0001
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Arne Winterhof
中科院分区：
文献类型：
--
作者：
Arne Winterhof
序列的线性复杂度不仅是不可预测性的度量，因此适用于密码学，而且在信息论中也很有趣，因为它与柯尔莫哥洛夫复杂度密切相关。然而，与柯尔莫哥洛夫复杂度相反，线性复杂度是可计算的，因此具有实际意义。它也与编码理论有关。一方面，序列的线性复杂度可以根据其相关性来估计，并且低相关序列设计与纠错码理论之间有很强的联系。另一方面，线性复杂度可以用Berlekamp-Massey算法来计算，该算法最初是为BCH码的译码而引入的。本章综述了几种主要的数论方法，用于线性复杂度的理论分析和相关的复杂度度量，并描述了几类特别有趣的具有高线性复杂度的序列。
The linear complexity of a sequence is not only a measure for the unpredictability and thus suitability for cryptography but also of interest in information theory because of its close relation to the Kolmogorov complexity. However, in contrast to the Kolmogorov complexity the linear complexity is computable and so of practical significance.It is also linked to coding theory. On the one hand, the linear complexity of a sequence can be estimated in terms of its correlation and there are strong ties between low correlation sequence design and the theory of error-correcting codes. On the other hand, the linear complexity can be calculated with the Berlekamp-Massey algorithm which was initially introduced for decoding BCH-codes.This chapter surveys several mainly number theoretic methods for the theoretical analysis of the linear complexity and related complexity measures and describes several classes of particularly interesting sequences with high linear complexity.