2-adic有限状态自动机的新实现方法

周期为2p的二元序列的2—adic复杂度文章提出了一個快速算法确定周期为2p的二元序列的2-adic复杂度，给出了具体确定其序列2-adic复杂度的一个有效上界。

标签：2-adic复杂度；周期序列；FCSR序列引言流密码是私钥密码中一类非常重要的密码体制，流密码的安全性取决于密钥流的安全性，要求密钥流序列尽可能具有随机序列的某些特性。

根据不同的攻击方法，人们提出了很多衡量序列安全性的指标，2-adic复杂度及线性复杂度是其中两个重要指标。

它们分别是针对带进位反馈移位寄存器（FCSR）和线性反馈移位寄存器（LFSR）两种序列发生器而提出来的。

较高的2-adic复杂度和线性复杂度使得密钥流序列可以有效抵抗有理逼近算法[1]和B-M算法[4]的攻击。

1994年，Klapper和Goredky提出了带进位反馈移位寄存器模型[3]。

设q为奇数，则连接数为q的FCSR结构图如图1：其中q+1=q1·2+…+qr·2r，qr=1，qi，an-i∈{0，1}，1？燮i？燮r，mn-1∈Z。

具体实施过程如下：（ⅰ）计算；（ⅱ）右移一位，输出寄存器最右端的an-r；（ⅲ）令an=？滓n（mod2）放入寄存器的最左端；注：称m是记忆。

FCSR的一个状态是指记忆m和寄存器的比特，即（mn-1，an-1，...，an-r）是FCSR的一个状态。

若这个状态以后还出现，则称该状态是周期的。

1 基础知识定义1 设=（s0，s1，s2，…）表示一条二元周期序列，称能够生成的最短的带进位反馈移位寄存器的长度为的2-adic复杂度，并记为？准2（），而称其连接数q为的最小生成数。

引理1 令=（s0，s1，s2，…）为一条二元周期序列，且其可被以q为连接数的带进位反馈移位寄存器生成，则有？琢（）=？撞si2i=s0+s12+s222+…=-r/q，其中满足-q？燮r？燮0，gcd（r，q）=1。

则此带进位移位寄存器是生成的最短的带进位的反馈移位寄存器。

有限状态自动机的C#实现
孙琳;王珺吉;苏华
【期刊名称】《电脑编程技巧与维护》
【年(卷),期】2011(000)018
【摘要】基于Visual C#语言实现了有限状态自动机.该自动机具有小巧轻便、简单易用的优点,可应用于程序复杂界面的操作与控制.
【总页数】2页(P28,41)
【作者】孙琳;王珺吉;苏华
【作者单位】78179部队,四川都江堰611830;78179部队,四川都江堰611830;95666部队,成都610041
【正文语种】中文
【相关文献】
1.基于有限状态自动机的复合事件检测的程序实现 [J], 周涛
2.2-adic有限状态自动机的新实现方法 [J], 林志强
3.基于有限状态自动机的人眼开度PERCLOS实现算法 [J], 巩晓倩;蒲亦非;杨智勇;周激流
SD对话有限状态自动机的设计与实现 [J], 江海昇;范辉
5.基于C#的批量表格合并系统设计与实现 [J], 刘仕华
因版权原因，仅展示原文概要，查看原文内容请购买。

一种获得有限自动机状态间关系的高效算法乔登科;柳厅文;孙永;郭莉【期刊名称】《计算机研究与发展》【年(卷),期】2012()S2【摘要】正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.【总页数】7页(P138-144)【关键词】正则表达式;状态膨胀;状态关系;活跃状态集【作者】乔登科;柳厅文;孙永;郭莉【作者单位】中国科学院信息工程研究所;中国科学院大学;信息内容安全技术国家工程实验室;中国科学院计算技术研究所【正文语种】中文【中图分类】TP3【相关文献】1.一种对无环确定有限自动机化简的高效算法 [J], 曾显华;张超;雷向东;2.关系数据库中关联规则挖掘的一种高效算法 [J], 王芳;王万森3.一种新的确定型有限自动机状态表示及压缩 [J], 张蕾; 于凯; 王思秀; 陆光4.村民群体与村规民约间良性关系的构建研究——基于一种人与制度间关系的民间法哲学视角 [J], 徐伟红5.由Hibiscus cannabinus×H·Radiatus获得的杂种F1代与染色体组的亲缘关系（在马尔万西克研究种间的和属间的杂交XV） [J], HikaruKuwada;何友锡;夏早清因版权原因，仅展示原文概要，查看原文内容请购买。

周期为2mpn的二元序列的2-adic复杂度
陈兰芳;戚文峰
【期刊名称】《通信学报》
【年(卷),期】2005(26)6
【摘要】有理逼近算法的提出,使得序列的2-adic复杂度成为衡量序列安全性的重要指标.对周期为2mpn的二元序列,给出了类似的扩展Games-Chan算法,并且利用这一算法,进一步确定了序列2-adic复杂度的一个有效上界.
【总页数】6页(P6-10,17)
【作者】陈兰芳;戚文峰
【作者单位】郑州信息工程大学,信息工程学院应用数学系,河南,郑州,450002;郑州信息工程大学,信息工程学院应用数学系,河南,郑州,450002
【正文语种】中文
【中图分类】O157.4;TN918.1
【相关文献】
1.周期为2p的二元序列的2-adic复杂度 [J], 姜丽颖
2.确定GF(qm)上周期为2n的二元序列的2-adic复杂度的快速算法 [J], 董丽华;胡予濮
3.2mpn周期二元序列的线性复杂度和k错线性复杂度 [J], 谭林;戚文峰
4.多重周期二元序列的联合k错2-adic复杂度 [J], 董丽华;胡予濮;曾勇
5.pn-周期二元多维序列2-adic联合复杂度快速算法 [J], 李富林;朱士信
因版权原因，仅展示原文概要，查看原文内容请购买。

有限自动机存储器实现方法
刘大本
【期刊名称】《青岛大学学报（工程技术版）》
【年(卷),期】2000(015)004
【摘要】叙述了自动机可用EPROM存储器来实现的新方法.把有限自动机每一状态及在此状态下的输入信息作为地址,对应这个地址的存储单元存放下一个状态及输出信息,通过对EPROM的读操作,使数据线上产生相应的输出,实现自动机的动作.这样可使逻辑线路大为简化,因而大大提高了可靠性.
【总页数】3页(P66-68)
【作者】刘大本
【作者单位】青岛远洋船员学院,青岛,266071
【正文语种】中文
【中图分类】TP23
【相关文献】
1.有限自动机的类类型实现方法 [J], 刘大本
2.有限自动机的电气实现方法 [J], 无
3.典型存储器动态老炼试验方法研究与实现 [J], 罗俊杰
4.有限自动机〈X,S,Z,F,G〉的一种MSI实现方法 [J], 吴浩敏;陈偕雄
5.美国研发新方法有助于实现快速、低功耗的计算机存储器 [J], 张慧
因版权原因，仅展示原文概要，查看原文内容请购买。

有限状态机FSM（FiniteStateMachine）及实现⽅式介绍⼀、为什么引⼊有限状态机？　最近做⼀个项⽬，项⽬中很多实体(Entity)，每个实体都有很多状态(State)，各状态会经过不同事件(Event)触发后转换到另⼀个状态。

这些事件包括但不限于：⽤户页⾯点击触发，⽣效时间或失效时间到达，其他依赖实体状态变更等。

在状态变更后还会有⼀系列动作(Action)处理。

⼀旦相互依赖实体或实体本⾝状态增多，状态转换变多，处理这些状态的业务代码也会分散在各处，代码处理很容易漏掉，维护成本很⾼。

所以考虑引⼊有限状态机。

⼆、什么是有限状态机？ 有限状态机,也称为FSM(Finite State Machine)，其在任意时刻都处于有限状态集合中的某⼀状态。

当其获得⼀个输⼊字符时，将从当前状态转换到另⼀个状态，或者仍然保持在当前状态。

任何⼀个FSM都可以⽤状态转换图来描述，图中的节点表⽰FSM中的⼀个状态，有向（⽅向表⽰从⼀个初态转换到次态）加权（权表⽰事件）边表⽰输⼊字符时状态的变化。

如果图中不存在与当前状态与输⼊字符对应的有向边，则FSM将进⼊“消亡状态(Doom State)”，此后FSM将⼀直保持“消亡状态”。

状态转换图中还有两个特殊状态：状态1称为“起始状态”，表⽰FSM的初始状态。

状态6称为“结束状态”。

在启动⼀个FSM时，⾸先必须将FSM置于“起始状态”，然后触发⼀系列时间，最终，FSM会到达“结束状态”或者“消亡状态”。

图1：状态转换图说明：在通常的FSM模型中，⼀般还存在⼀个“接受状态”，并且FSM可以从“接受状态”转换到另⼀个状态，只有在识别最后⼀个字符后，才会根据最终状态来决定是否接受所输⼊的字符串。

此外，也可以将“其实状态”也作为接受状态，因此空的输⼊序列也是可以接受的。

1. 状态机要素状态机可归纳为4个要素，即现态、条件、动作、次态。

“现态”和“条件”是因，“动作”和“次态”是果。