基于UIO测试序列的错误诊断算法

唯一输入输出(Unique Input Output)测试序列是协议测试中常用的一种测试序列,在一个已有的错误诊断算法基础上,结合UIO测试序列的一些特点,该文提出了一种应用于UIO测试序列的错误诊断算法。该算法充分利用了UIO测试序列给出的判定消息,及测试结果中可能的错误转换后的输入/输出消息,从而能高效完全地诊断单个错误。最后用实验数据给出了该文算法和原始算法之间的比较结果。     

基于确定有穷自动机描述的仿人智能控制记忆

模仿熟练操作者通过记忆多步连续调控系统的方式,将记忆用上下文无关文法表示.根据控制经验和滚动预测优化建立特征状态转换表和构造不确定有穷自动机,给出了转换确定有穷自动机的算法.在任意特征状态下,通过一系列的DFA状态转换函数的复合运算,得到使系统稳定下来的控制模态序列.     

基于改进FSM的协议一致性测试方法

介绍了一种基于FSM(finite state machine)的生成一致性测试序列的改进算法,该方法混合了UIO(unique input/output)方法和T方法,UIO方法的测试能力优于T方法,但是生成的测试序列的长度较后者要长一些。实验结果表明,本改进方法的能力与UIO方法相同,并且测试序列的长度接近于T方法。     

基于DNA有穷自动机的素性测试法

有穷自动机,一种计算能力极其有限的计算模型,具有解决素性测试的能力通过构造法得到了证明。既而提出了一种基于有穷自动机的测试一个整数是否为素数的DNA算法,并且详细描述了该有穷自动机的构造方法,将有穷自动机的状态用DNA单链分子来编码,而输入则用DNA双链分子编码,用带环的双链DNA分子来编码状态转移规则,通过限制性内切酶的切割实现状态的转移。该算法的创新之处在于它是基于有穷自动机这种计算能力极其有限的计算模型的,并且该算法不仅能判断一个整数是否是素数,还能用于素因子分解。该算法的优点是实验实现容易,所需的时间是输入的多项式函数而不是指数函数。     

基于软件网络加权k-核分析的关键类识别方法

识别关键类可以帮助人们尽快理解不熟悉的软件系统.尽管目前已有一些关键类识别方面的工作,但是大部分方法构建的依赖图是无权的,未考虑类之间交互的种类及次数.有鉴于此,提出了一种基于软件网络加权k-核分析的关键类识别方法.首先,用加权类耦合网络抽象类（接口）、类（接口）间的交互及其次数;然后,引入加权k-核分解方法计算类的加权核数;最后,以加权核数作为类重要性的量度指标,降序排列所有类,并通过过滤得到候选关键类.真实软件上的数据实验验证了本文方法的有效性.     

基于启发式SCCs的广义Büchi 自动机判空检测算法

 基于自动机理论模型检测的一个关键算法是判断有穷状态系统是否满足属性的判空检测.对标准Büchi自动机作判空检测,容易引起状态爆炸.本文以TGBA为研究对象,提出基于启发式SCCs的广义Büchi自动机判空检测算法.该算法在on-the-fly算法的基础上结合启发式深度优先搜索和SCCs检测算法,能较快地判断TGBA的非空性.通过正确性证明、复杂性分析和实验验证了该算法的正确可行性.在TGBA非空的情况下,该算法的时空性能比已有算法更优.     

新颖的正则NFA引擎构造方法

提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp。NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小。     

一种价格时间Petri网的状态空间计算

价格时间Petri网是对web服务过程和工作流模型等进行时间和成本分析的一种新工具.而价格时间自动机则是一种相对成熟的工具.提出一种状态空间计算方法,可以将价格时间Petri网的状态空间构造为一个价格时间自动机.该方法的核心思想是在扩展状态类中增加价格参数.进一步证明了构造出的价格时间自动机和初始的价格时间Petri网是双相似的.     

有限状态自动机在复杂界面操作中的应用

为提高程序开发效率和软件稳定性,减轻应用程序在复杂界面操作上的代码量,设计实现了基于有限状态自动机的界面控制器.界面控制器在自动机的基础上引入动作集,通过将界面上的复杂操作抽象为简单的状态和状态转换函数,可实现对界面的复杂操作与逻辑控制,具有建模方便、小巧轻便和简单易用的优点.     

基于LCS的特征树最大相似性匹配网页去噪算法

提出了一种基于LCS的特征树最大相似性匹配网页去噪算法.通过将目标网页和相似网页转化为特征树,并将特征树映射为一个特征节点序列,利用LCS算法能获得最长子序列全局最优解的特点,找出两棵特征树之间的不同节点作为候选集,并对候选集进行聚集评分找出网页重要内容块.给出了算法的原型系统,并对每一个模块的实现做了详尽的描述.     

UIO序列优化搜索算法的研究

UIO序列是对有限状态机进行功能测试的有效手段,在VLSI、通信协议等时序系统中有很强的实际应用背景.本文基于可区分状态组这一概念设计了一个搜索算法,进一步利用搜索信息建立了一个基于"小于"关系的启发策略,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝,新设计出的多路OPEN/CLOSED表存储机制也加快了相关的判别、处理过程.根据实验结果,分析了优化措施对于改进了搜索过程、减少搜索信息的产生、提高搜索速度有显著的贡献.该算法与以往的算法相比,在时间复杂度和空间复杂度两方面都得到了很大改进.     

一种多人多出DS/CDMA系统中的半盲多用户检测算法

多用户检测技术是DS/CDMA中的一项关键技术,而天线阵的广泛应用也促使对多入多出系统的研究。该文将两种技术结合在一起,考虑到基站在一般情况下总是知道本小区的多个用户的扩频码,在此半盲意义下研究了将子空间方法应用于多用户检测的技术。这种技术可适用于低速移动台在慢衰落信道下的盲检测。仿真结果表明这种算法相对于只利用一个用户的扩频码的盲检测算法性能有相当大的提高。     

JPEG2000算法中基于有界输入有界输出(BIBO)增益控制的小波变换定点实现技术

该文提出一种在JPEG2000算法中兼容5/3小波变换和9/7小波变换高效硬件定点实现技术。所提出的技术使用9/7提升小波变换的有界输入有界输出(Bounded Input Bounded Output, BIBO)增益来确定小波变换中间值的存储位深,使用5/3提升小波变换的BIBO增益来确定9/7提升小波变换中量化参数的选择方式和量化的实现方式,最终使用同一存储空间来存放定点5/3提升小波变换和定点9/7提升小波变换系数。该文提出的技术不仅大大节省了JPEG2000算法中小波实现模块中的硬件存储资源和算法计算量,而且也节省了后续基于上下文的位平面算术编码模块和率失真优化截取模块的存储资源和算法计算量。     

多入单出正交空时分组码系统的调制识别

在现代无线通信系统中,采用正交空时分组码(STBC)的多天线发射技术是提高通信速率和可靠性,并且能够实现简单译码的关键技术。该文针对瑞利信道系统模型,提出一种适用于多入单出正交空时分组码(OSTBC)的调制识别算法。该算法通过对接收到的数据进行重排,将多入单出的系统模型转化为类似多入多出的系统模型,并且根据信源的特殊性用最大似然的思想实现调制类型的识别。仿真结果验证了所提算法的有效性。     

一种多输入多输出变换域通信系统的设计及其抗干扰性能研究

传统多输入多输出技术可以提高信道容量,但不能解决信号抗干扰问题;而变换域通信系统已经被证明是一种良好的抗干扰通信系统。通过引入变换域处理技术,提出了一种多输入多输出变换域通信系统(MIMO-TDCS),旨在突破传统MIMO系统的应用瓶颈。对其收发信机模型和抗干扰机制作了简要介绍,并通过仿真窄带干扰下的误码率性能,表明MIMO-TDCS是一种可靠的抗干扰通信手段。     

A Novel Circulant Approximation Method for Frequency Domain LMMSE Equalization

The coefficients of a Linear Minimum Mean Square Error (LMMSE) equalizer for a stationary random signal are defined by a Toeplitz system. The Toeplitz structure can be exploited to reduce computational complexity. In this paper we investigate the Levinson and Schur algorithm, as well as circulant embedding and circulant approximation methods applied to the Preconditioned Conjugate Gradient (PCG) method and Frequency Domain Equalization (FDE). We develop a novel circulant approximation method which improves the performance/complexity tradeoff. We show that the optimal choice of algorithms largely depends on the antenna configuration. Investigated configurations are Single Input Single Output (SISO), Single Input Multiple Output (SIMO) and Multiple Input Multiple Output (MIMO). All considered algorithms are benchmarked in terms of implementation complexity and capacity achieved by a High Speed Downlink Packet Access (HSDPA) receiver in a multipath fading scenario.     

Tomlinson-Harashima Precoded MIMO in wireless networks: to THP or not to THP?

We investigate a wireless network architecture that utilizes Tomlinson Harashima Precoded Multiple Input Multiple Output (THP MIMO) technique for improved system capacity. We consider THP MIMO in a multi user scenario, together with a proposed smart scheduling technique and we explore the capacity performance through extensive capacity analysis considering varying SNR levels, varying number of users and number of transmit/receive antennas, under fading and shadowing, also considering errors in channel state information (CSI). We also evaluate the complexity of THP MIMO and present a low-complexity scheduling algorithm that employs Gram-Schmidt algorithm for incremental implementation of THP’s QR factorization. In the end, we identify the network and channel conditions under which THP MIMO can be preferred over classical conventional MIMO, and we conclude that for practical transceivers with up to four antennas, THP MIMO can provide significant capacity enhancement over conventional MIMO at lower complexity, performing slightly below the sum rate capacity bound. Another important advantage that is observed in this study is better immunity of THP MIMO to CSI errors, as compared to conventional MIMO.     

RF beamforming for MIMO cognitive user

Using Multiple Input Multiple Output (MIMO) architecture in cognitive radio (CR) secondary users improves the system performance in terms of interference cancellation and data rate enhancement but at the expense of adding complexity and cost. A solution to reduce this complexity is employing radio frequency (RF) beamforming networks at the transmitter/receiver front-ends. In this paper, we consider a MIMO secondary user equipped with such RF beamforming network. Moreover, we find the transmit/receive optimum RF beamforming network for a MIMO spatial multiplexing system. We evaluate the performance of the optimally designed RF beamforming technique over a Rician channel via computer simulations. The simulation results are assessed for different RF beamforming structures and the number of primary transmitters which cause interference on the secondary receiver.     

Principles and methods of testing finite state machines-a survey

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing