多个序列最短线性移位寄存器综合的迭代算法

近十几年来,多个序列最短线性移位寄存器综合问题,在信息论和控制论中为许多学者所关心和重视,但至今没有很好的算法。本文给出了解决这个问题的迭代算法,并证明了所求得的线性移位寄存器确实是产生多个序列的最短线性移位寄存器。此外,本文还给出最短线性移位寄存器唯一性的充要条件,以及在不唯一的情况下产生多个序列的所有最短线性移位寄存器集合.当t为1时,本文的算法就是著名的Berlekamp-Massey迭代算法。     

产生 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 算法的基础     

前馈序列与反馈序列的关系

本文引入移位寄存器序列的向量值表示讨论了线性移位寄存器的前馈序列与反馈序列同时为ｍ序列时的关系,得到了它们在向量值表示下的一个关系式。     

m序列的移位相减性

ｍ序列是一类最重要的线性移位寄存器序列．文献［１］证明了移位相加是２元ｍ序列的特有性质，本文证明了任意的ｑ元ｍ的序列都具有移位相减性，并说明了移位相加是移位相减的特例。     

关于“停走”生成器概率模型中的符合率问题

本文首先建立了“停走”生成器辅出序列的概率模型,给出了“停走”生成器输出序列与其线性移位寄存器序列之间的符合率的计算公式。     

M序列自相关系数的递推算法

一、前言 伪随机序列是一类有着广泛应用的伪随机码.在数字通讯、测距及跟踪系统中常用其来调制信号,以达到提高可靠性与有效性以及保密等目的.最常用的一类伪随机码则是由移位寄存器产生的序列.对于线性的情形,已有比较完整的结果,而对于非线性情形,则要复杂得多.目前,讨论得最多而用途最广的是所谓最长的序列,即M序列. 在我们的工作中,已经证明了,凡满足下述两条件:     

相关免疫函数的结构与构造

一、引言 在流密码学中,人们通常采用一个线性移位寄存器或多个线性移位寄存器再加一个滤波函数来作为流密钥序列生成器。非线性滤波函数的作用是为了提高流密钥序列的线性复杂度。Siegenthaler指出:如果滤波函数选择不当,破译者在仅知密文的情况下可以使用相关攻击的方法来攻击该体制。为了抵抗相关攻击的方法,Siegenthaler提出了相关免疫函数的概念,并给出开关函数是相关免疫函数的必要条件。肖国镇和J.L.     

常见随机数发生器的缺陷及组合随机数发生器的理论与实践

随机数是蒙特卡罗 Monte- Carlo方法的基础 .本文首先指出线性同余法和移位寄存器 (亦称 Tausworthe)序列等常见随机数发生器的一些缺陷 ;在此基础上介绍可产生具有优良品质随机数的组合发生器。本文既介绍理论结果 ,用以证明组合发生器确实可以优于单个发生器 ;也具体构造了几个可供实际使用的组合随机数发生器。严格而全面的统计检验表明 ,它们可以产生具有优良品质的随机数     

Q矩阵的结构与有限域上多项式的可约性

<正> 近年来,由移位寄存器所产生的序列在一些实际问题中得到了应用,例如数字通信中的纠错编码、测距等,因此种序列的伪随机性还可用于一些需要随机数的领域,如蒙特卡罗方法等.     

生成Q元M序列的理论和算法

本文定义了Q=Z/(q)上任意非奇异反馈移位寄存器的因子关联图。给出了一个构造Q上M序列的基本原理。进而给出了几个生成Q上M序列的无记忆算法。     

一种生成k元de Bruijn序列的算法

目前,已有很多生成全长的移位寄存器序列(又称de Bruijn序列)的方法,他们的共同思想是先通过某种简单的移位寄存器生成所有不同的圈,然后再把它们联接为一个全长圈。在这篇文章中,我们先定义一个项链的周期约化,进而提出一种新的生成任意k元de Bruijn序列的方法。这种方法把这类算法从域推广到整数模上,而且在n≥3和k≥4时,这种算法能生成一大批de Bruijn序列。     

求解一类隐线性互补问题的投影MAOR算法

用MAOR迭代算法求解一类L-矩阵的隐线性互补问题.证明了由此算法产生的迭代序列的聚点是隐线性互补问题的解.并且当问题中的矩阵是M-矩阵时,算法产生的迭代序列单调收敛于隐互补问题的解.     

非线性移位寄存器的一个分析算法

本文对于反馈函数含小项少的非线性移位寄存器,提出了一个分析算法。由这算法可得到状态图中圈的数目、圈的长度及枝的最大长度,算法计算量比穷举法小;同时还导出了非线性移位寄存器的算法稳定判据,并得到了用公式表示的若干分析结果。     

基于矩阵模型表示的(线性)有限自动机的同步序列判定

在有限自动机矩阵模型表示方法的基础上,采用矩阵理论和布尔代数为工具,分别给出了判定输入序列是否是(线性)有限自动机的同步序列的新充要条件和求解线性有限自动机的最短同步序列的新算法.     

连续型动态规划的新算法研究

提出了求解一维连续型动态规划问题的自创算法----离散近似迭代法,并结合双收敛方法求解多维连续型动态规划问题. 该算法的基本思路为：在给定其它状态向
量序列的基础上,每次对一个状态变量序列进行离散近似迭代,并找出该状态变量的最优序列,直到所有状态向量序列都检查完.当模型为非凸非凹动态规划时,
证明了该算法的收敛性.当模型为凸动态规划时,证明了该算法的线性收敛性. 最后,以一个具体算例验证了该模型和算法的有效性.     

求解反应扩散对流问题的并行块单调迭代算法

考虑求解一类非线性反应扩散对流方程的块单调迭代算法,其中包括传统的块Picard,块Jacobi,以及在区域分解算法中常用的并行Schwarz算法.所讨论的算法可从问题的一个上解和下解出发,产生一个上解迭代序列和下解迭代序列并单调收敛于离散问题的解.这类算法的优点在于算法的并行结构好且可直接通过所产生的上解和下解迭代序列,得到迭代解的最大模误差界.在理论上,得到了算法的单调收敛性、线性与超线性收敛性.     

整数扩展欧几里得矩阵序列的选择项算法的修正

Wang和Pan提出了一个计算整数扩展欧几里得矩阵序列的选择项的算法,并把此算法应用于模有理数重构问题和数值有理数重构问题.这个算法仅消耗接近线性的时间复杂度,与目前已知的整数gcd算法的最佳时间复杂度相一致,而整数gcd算法只是此算法的一个特殊情形.分析了这个算法,指出了算法中由于考虑的不够全面而存在的错误,补充了矩阵序列性质的理论部分,并修正这个算法.     

一种基于Dijkstra算法的机器人避障问题路径规划

移动机器人的避障问题是移动机器人控制领域的研究热点.针对给定的移动机器人避障问题,探讨了最短路径及最短时间路径的路径规划问题.对于最短路径问题,建立了简化的路径网格模型,将其抽象为由节点及边构成的两维图,再使用经典的Dijkstra算法获得可行的最短路径.对于最短时间路径问题,通过分析移动机器人弯道运行的速度曲线,基于几何方法得出了移动时间与过渡圆弧圆心之间严格的数学关系,此后借助MATLAB优化函数获得最佳的移动路径.算法可为类似机器人避障问题的解决提供借鉴.     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

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

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