列序的复杂度与相关函数

M 序列因其庞大的数量和良好的伪随机性,在现代通讯等领域中有着广泛的应用.线性复杂度作为 M 序列复杂性的一种主要度量方法,不论在实际应用中还是在理论上,均有较为重要的意义.本文主要讨论了 M 序列的复杂度与相关函数的一些关系.     

M序列一个周期的复杂度

在流密码中,M序列及M序列一个周期复杂度是一个重要课题。Chan等人在文献[2]中对M序列的界和分布进行了讨论。本文将对M序列一个周期复杂度进行一些研究,并且主要讨论M序列一个周期复杂度的上下界,遍历性和分布情况。 注 本文在GF(2)上和n≥3情况下讨论。     

Chaitin复杂度、事件的Shannon信息量和无穷随机序列(Ⅱ)

本文是文献[1]的继续,主要考虑以下三个方面的问题,第一,从程序复杂度的观点出发,研究Martin-lf(M.L.)无穷随机序列的性质。我们证明了M.L.无穷随机序列是正规的且服从叠对数定律。第二,M.L.无穷随机序列的有效生成。我们证明了利用标准的方法(如投硬币)可以产生可计算概率分布的M.L.无穷随机序列。第三,对非可计算的概率分布,如何定义它的无穷随机序列。文中给出了两种推广定义,并对其中之一进行了较详细的讨论。     

F2中基于并圈法的M序列生成算法

M序列由于具有良好的统计特性经常被应用在信息安全领域.这使得寻找F₂中M序列反馈函数成为一项有意义的工作.给出了由已知M序列反馈多项式得出新的与已知函数同次数的M序列反馈多项式的新方法.主要工作如下:1)用图形简单的给出了并圈法的逆过程所实现的操作过程.2)将并圈法的逆运算与并圈法先后应用在已有M序列状态图交叉排列的两对前共轭顶点对上,得到了由已知M序列反馈多项式生成新M序列反馈多项式的算法.3)证明了上述给出算法在二阶有限域F₂中的正确性.4)用C语言实现了算法.实验结果表明当移位寄存器的阶不是很大时算法是有效的.     

全部 n 级 M 序列构造方法的计算机实现

<正> 最长 n 级非线性移位寄存器序列简称为 n 级 M 序列,记为(a_0,a_1,…,a_2~n-1),a_i=0或1,它是以2~n 为周期的序列.在序列中连续 n 个元(a_ia_(i+1)…a_(i+n-1))称为状态,n级 M 序列中,全部2~n 个状态两两不同.M 序列具有较好的伪随机性与相关特性,而且数目多,容易保密,因此在通信等工程领域得到了重要应用.例如,M 序列可以在多址通信     

具有2n线性复杂度的2n周期二元序列的3错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n的2n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式, k=3,4.对于一般的线性复杂度为2n-m的2n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式.     

C_0复杂度的改进及其在证券市场中的应用

系统地分析了Lemple-Ziv复杂性度量方法的应用过程中,将实际信号(时间序列)转变成符号序列的诸多方法中存在的一些问题,提出了更合理兼容法.该方法可以有效地刻划各种时间序列的复杂度.文章最后动态地分析了中国证券市场的复杂性.     

基于代数曲线上具有高广义联合线性复杂度的多重序列

多重序列的联合线性复杂度是衡量基于字的流密码体系安全的一个重要指标. 由元素取自F_q上的m 重序列和元素取自F_q^m 上的单个序列之间的一一对应, Meidl 和Özbudak 定义多重序列的广义联合线性复杂度为对应的单个序列的线性复杂度. 在本文中, 我们利用代数曲线的常数域扩张, 研究两类多重序列的广义联合线性复杂度. 更进一步, 我们指出这两类多重序列同时具有高联合线性复杂度和高广义联合线性复杂度.     

伽罗瓦环上的一类No序列的构造

近年来,伽罗瓦环上的序列理论成为人们研究的热点问题.有限域上的No序列是一类伪随机序列,它在序列密码中占具十分重要的角色.本文利用伽罗瓦环上的置换,构造了伽罗瓦环Z_(p~e)上的一类新的No序列,并且研究了其线性复杂度.研究的结果表明此类No序列具有相当大的线性复杂度.     

一类LFSR序列簇的2-adic复杂度

线性复杂度和2-adic复杂度是衡量序列伪随机性的两个重要指标.文章研究这两个指标之间的关系,证明了由不可约多项式生成的LFSR序列簇的极小连接数达到最大可能值,即2~T-1,其中T为不可约多项式的周期,进而该序列簇的2-adic复杂度与对称2-adic复杂度均达到最大可能取值.特别地,当限定不可约多项式是本原多项式时,即可得到m-序列的相应结论.     

p元扩展序列的线性复杂度

给出了由周期为p~m-1的p元序列导出的周期为p~(em)-1的p元扩展序列的线性复杂度.作为一个实例,计算了扩展Legendre序列的线性复杂度.     

一类用迭代方法生成的分片线性谱序列

本文引入了空间L2[0,1]的一种具有指数形式的正交基,其中对应的指数序列称为谱序列.文章得出了一系列理论上的刻画,但主要贡献在于给出迭代解法以生成多节点分片线性谱序列,并且对分片常数谱序列进行了研究.另外,本文还给出在离散情形计算分解系数的快速算法,并估计了算法复杂度.     

概率度量空间中压缩映象的不动点定理

本文通过引入压缩映象集序列的概念,推广并综合了张石生以及V.M.Sehger和A.T.Bharucha-Reid中某些主要定理的结果。     

M 序列反馈函数的构造方法Ⅱ

构造 F_2上的 M 序列(即最大长度非线性移位寄存器序列)及其反馈函数在理论上已有比较完整的方法,但在目前有限的计算能力下,人们仍难以获得足够多的 M 序列,我们在[1]中,提出了一种比较简单的方法,用这种方法,可从任一非奇 n 元布尔函数出发直接写出一批 M 序列反馈函数(简称 M 馈):本文沿用[1]的记号和概念,继续讨论 M 馈的构造方法.     

产生 M 序列的一个递推算法

§1.引言M 序列又称 de Bruijn 序列,是一类具有最长周期的非线性移位寄存器序列。本文研究产生 M 序列的算法。早在70年代万哲先等对构造 M 序列的方法已有系统的研究。此后有一系列的文章研究 M 序列的构造问题。最近 Fredricksen 对这方面的工作给出了一个很好的综述。产生 M 序列的一个常用方法是先由一个较简单的移位寄存器产生许多短圈,再用并圈法将这些短圈合并起来构成 M 序列。如在[1,6]中就已给出过一些将 n 级纯轮换移位寄存器(简记为 PCK_n)和 n 级补轮换移位寄存器(简记为 CCR_n)产生的圈合并为 M 序列的方法。与[1—7]不同,Fredricksen 给出一个将 PCR_n 产生的圈合并为 M 序列的递推算法。最近 Etzion 和 Lempe 在 Fredricksen 算法的基础     

周期pq的广义分圆二元序列线性复杂度（英文）

本文构造了一类周期为pq(p和q是不同的奇素数)的几乎平衡的二元序列,基于4阶Whiteman-广义分圆和2阶经典分圆我们确定了这类序列的线性复杂度.研究结果表明该类序列从线性复杂度的角度来看是非常好的.     

关于 M 序列的相关函数

关于正交码,双正交码和等距码作为信号集应用于各种通信系统的性能已经有了广泛的研究.近年来由于扩展频谱多址通信网络的发展,应用 M 序列作信号集受到注意.由于一般信号集应用于通信系统的性能依赖于信号的相关系数矩阵,对于循环序列则依赖于序列的周期相关函数,本文对 M 序列的相关函数的性质与计算进行研究,得到一些初步结果,也许能对某些应用或对这方面的进一步研究提供一些帮助.     

随机适应误差下线性模型参数M估计的渐近性质

在一些较弱的充分条件下,本文研究了误差为随机适应序列下,线性模型回归参数M估计的强相合性.与文献中已有结果比较,扩大了应用范围,且对矩条件也有较大改进.同时我们给出了随机适应误差下线性模型参数M估计的渐近正态性.     

q元m序列非周期自相关函数的估计与M序列的分段线性化

序列的非周期自相关函数的估计,具有良好非周期自相关性的序列的构造,以及非线性M序列的相关性等方面已有的成果较少.著名的Barker序列当长度大于13时是否存在的问题尚未完全解决,L序列的非周期自相关函数的估计仅在长度较短时有一些数值计算结果,文献曾估计了一类二元序列非周期自相关函数的上界.最近,章照止巧妙地应用组合数学方法估计了状态两两不同的二元序列中一元的个数(在这基础     

复杂度为n+2的序列(英文)

本文研究了复杂度为n+2的序列.利用代换的理论以及词上组合的方法,刻画了这类序列,揭示了它们与Sturmian序列的密切联系.