专利名称：测试数字逻辑器件中实时有限状态机的方法
技术领域：
本发明涉及数字逻辑系统领域，特别涉及一种测试数字逻辑器件中实时有限状态 机的方法。
背景技术：
在数字逻辑系统中，有限状态机对数字系统的设计具有十分重要的作用。有限状 态机的输出取决于过去输入部分和当前输入部分。一般来说，除了输入部分和输出部分外， 有限状态机还含有一组具有“记忆”功能的寄存器，这些寄存器的功能是记忆有限状态机的 内部状态，它们常被称为状态寄存器。在有限状态机中，状态寄存器的下一个状态不仅与输 入信号有关，而且还与该寄存器的当前状态有关，因此有限状态机又可以认为是组合逻辑 和寄存器逻辑的一种组合。有限状态机可归纳为4个要素，即现态、条件、动作、次态。现态是指当前所处的状 态。条件又称为事件，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。动 作指条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状 态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。次态指 条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态” 一旦被激活，就转变 成新的“现态”了。在数字逻辑系统中，有限状态机的实现往往需要考虑实时因素，既可以表现为实 时条件，也可表现为实时动作。对实时有限状态机进行完善的测试是保证数字逻辑系统无设计缺陷的重要方法。针对如图1所示的实时有限状态机，假定其共有N个状态Sp S2........Sn，对于
每个状态，可能的触发输入条件数量分别为I” I2........IN，每个触发输入条件都可能存
在的时间约束值。根据一般数字逻辑器件的特点，假定上电复位后，实时有限状态机进入状
χ Sl O尽管实际设计数字逻辑器件中的实时有限状态机时，通常不会包含所有的状态转 移，但为了实现对实时有限状态机的完备测试，设计测试案例时需要考虑所有的状态转移。如果针对实时有限状态机进行完善测试，其完善的测试案例应包含『个路径，每 个路径都经过N个节点。但这些路径中有1个路径的所有节点都是S1，相当于永远停留在 状态节点S1,其它的路径可根据实际情况进一步合并。例如3状态节点实时有限状态机之中9个路径最终合并后减少为7个，4状态节 点实时有限状态机之中64个路径最终合并后减少为40个。合并处理对于路径的减少与Nm个路径总数比还是较少的。同时需要考虑到如果 当前状态为S1,需要遍历I1种触发输入条件，如果当前状态为S2,需要遍历I2种触发输入条
件，......，如果当前状态为Sn，则需要遍历In种触发输入条件，再考虑到触发输入条件的
时间约束值的连续性特征，如果对所有状态转移路径、触发输入条件及时间约束值全部遍 历，其可能的测试案例数量随着N的增加而爆炸性增加。
因此完善的测试不但不可能由人工完成，即使采用计算机辅助测试，其测试时间 也会持续很长时间。因此必须在合理化简测试案例的基础上，采用计算机自动测试完成对 数字逻辑器件中实时有限状态机的完善测试。

发明内容
(一)要解决的技术问题本发明要解决的技术问题是如何化简测试案例、对数字逻辑器件中实时有限状态 机进行自动测试。(二)技术方案为解决上述技术问题，提供一种测试数字逻辑器件中实时有限状态机的方法，包 括步骤Si，基于白盒测试原则，减少测试案例，在此基础上完成测试案例的编制，并生成 测试序列；S2，上位机向实时控制器发送测试命令，实时控制器提供受控电源和测试激励信 号，按照全自动测试方式进行测试，生成测试结果；S3，实时控制器采集测试结果，并将所述测试结果发送给上位机生成测试报告和 测试日志。其中，所述步骤Sl中，所述减少测试案例的过程包括步骤Sl-I，从上电复位的初始状态S1开始，遍历该状态所有触发输入条件I1个，检查状 态转移是否正确；S1-2，对初始状态按照正常触发方式转移的下一个状态Si,遍历所有触发输入条 件Ii个，检查状态转移是否正确；S1-3，按照步骤S1-2的方式，对所有N个状态进行测试。S1-4，对于所述触发输入条件中的时间约束值，进行离散化处理。优选地，当所述时间约束值最大为Tmax时，在W，2Tmax]之间，取值间隔选为Tmax/10 ；且在[2Tmax，5Tmax]之间，取值间隔选为Tmax。优选地，当所述时间约束值最小为Tmin时，在
之间，取值间隔选为3Tmin/10 ；在[Tmin，2Tmin]之间，取值间隔选为Tmin/10 ；且在[2Tmin，5Tmin]之间，取值间隔选为Tmin。优选地，当所述时间约束值为[T1, T2]时，在
之间，取值间隔选为31/10 ；在[T1, T2]之间，取值间隔选为(T2-T1)AO ；在[T2，5T2]之间，取值间隔选为T2。优选地，当所述时间约束值为单点值T时，在
之间，取值间隔选为Τ/10 ；在[2Τ，5Τ]之间，取值间隔选为Τ。(三)有益效果
本发明针对实时有限状态机的完善测试，基于状态转移化简和状态转移触发输入 条件时间约束值离散化处理，提供减少测试案例数量的方法，同时给出了基于实时有限状 态机自动测试系统，以全自动方式完成数字逻辑器件中实时有限状态机的测试工作。该发 明能够解决测试案例数量爆炸的问题，大大提高测试效率。


图1是本发明实施例的实时有限状态机结构模型图；图2是本发明实施例应用简化生成方法测试的实时有限状态机；图3是本发明实施例的实时有限状态机自动测试系统原理框图；图4是本发明实施例的自动测试系统测试流程具体实施例方式下面结合附图和实施例，对本发明的具体实施方式
作进一步详细描述。以下实施 例用于说明本发明，但不用来限制本发明的范围。1、实时有限状态机测试案例的化简方法传统的基于实时有限状态机全状态节点遍历而生成测试案例方法，不会遗漏测试 路径，但测试案例数量会随着N的增加而爆炸性增加，因此必须考虑化简的方法。以状态节点为中心考虑状态转移的化简，可以大幅度减少测试案例的数量。具体 方法如下1)首先，从上电复位的初始状态S1开始，遍历该状态所有可能的触发输入条件I1 个，检查状态转移正确与否。2)然后，对初始状态S1能正常转移到的下一个状态Si,遍历该状态所有可能的触 发输入条件Ii个，检查状态转移正确与否。测试案例中测试该状态的条件是按照正常触发 方式从初始状态S1转移到该状态Si。3)按照这种方式，将所有N个状态全部测试完成，需要注意的是，测试案例中按照 正常触发方式进入某一状态可能要经过其它几个已经测试过的状态。对于上述的状态转移所需要的触发输入条件时间约束值，考虑时间约束值的不同 情况，测试时必须离散化处理。1)当触发输入条件时间约束值最大为Tmax时，离散化处理a)在W，2Tmax]之间，取值可以密一些，例如间隔可选为Tmax/10 ；b)大于2Tmax的值优选取到5Tmax值即可，它们之间的间隔可选为Tmax。2)当触发输入条件时间约束值最小为Tmin时，离散化处理a)在
之间，取值可以稀疏一些，例如间隔可选为3Tmin/10，即取0、 3Tmin/10、6Tmin/10、9Tmin/10 ；b)在[Tmin，2Tmin]之间，取值可以密一些，例如间隔可选为Tmin/10 ；c)大于2Tmin的值优选取到5Tmin值即可，取值可以稀疏一些，例如间隔可选为Tmin。3)当触发输入条件时间约束值为[T1, T2]时，离散化处理a)在
之间，取值可以稀疏一些，例如间隔可选为31/10，即取0、31/10、 61/10、91/10 ；
b)在[T1, T2]之间，取值可以密一些，例如间隔可选为(T2-T1VlO ；c)大于T2的值优选取到5T2值即可，取值可以稀疏一些，例如间隔可选为T2。4)当触发输入条件时间约束值为单点值T时，离散化处理a)在
之间，取值可以密一些，例如间隔可选为T/10 ；b)在[T，2T]之间，取值可以密一些，例如间隔可选为Τ/10 ；c)大于2Τ的值优选取到5Τ值即可，取值可以稀疏一些，例如间隔可选为Τ。3、实时有限状态机的测试案例简化生成方法举例下面以图2所示的实时有限状态机为例，说明其测试案例的简化生成方法。图2 描述了一个双机热备的模式控制实时有限状态机，其一共有5个状态模式，状态转移规则 如下1)状态转移的触发输入条件为1组72位二进制数据，包括32位序列号、16位条 件码、8位预留码、16位CRC码，因此有效的状态转移触发输入条件为16位二进制数据，共 有65536种可能。2)上电复位后首先进入上电模式。3)进入上电模式4. 7分钟内满足进入主模式的条件则转移为主模式。4)进入上电模式4. 7分钟内满足进入跟随模式的条件则转移为跟随模式。5)进入上电模式4. 7分钟内不满足进入主或跟随模式的条件则转移为复位模式。6)进入跟随模式800ms内满足进入备模式的条件则转移为备模式。7)主、备模式的周期为400ms，一旦在控制周期内出现错误，主或备模式都会转移 为复位模式。8)备模式满足进入主模式的条件则转移为主模式。9)主模式满足进入备模式的条件则转移为备模式。10)复位模式满足进入上电模式的条件则转移为上电模式。图2所示实时有限状态机的时间约束值有3个4. 7分钟、800ms、400ms，都属于 “时间约束值为最大”的情况，离散化处理分别如下对于4. 7分钟，在
之间，间隔取为0. 47分钟；在[9. 4分钟，23. 5分 钟]之间，间隔取为4. 7分钟。对于800ms，在
之间，间隔取为80ms ；在[1.6s，4s]之间，间隔取为 800ms ο对于400ms,在
之间，间隔取为40ms ；在
之间，间隔取为 400ms ο测试案例简化生成方法如下1)上电模式可以转移到主模式、跟随模式、复位模式。测试时状态转移的触发输入 条件有65536种，离散时间约束值为24种，因此全部的测试案例有1572864种。2)跟随模式可以转移到复位模式、备模式，测试时状态转移的触发输入条件有 65536种，离散时间约束值为24种，因此全部的测试案例有1572864种。3)备模式可以转移到复位模式、主模式，测试时状态转移的触发输入条件有 65536种，离散时间约束值为24种，因此全部的测试案例有1572864种。4)主模式可以转移到复位模式、备模式，测试时状态转移的触发输入条件有65536种，离散时间约束值为24种，因此全部的测试案例有1572864种。5)复位模式可以转移到上电模式。测试时状态转移的触发输入条件有65536种， 无时间约束值，因此全部的测试案例有65536种。4、实时有限状态机的自动测试系统可以看到，即使经过化简后，完善测试仅5个状态的实时有限状态机仍需要有630 万个测试案例，根本不可能由人工测试完成，必须使用计算机自动测试完成。要完成对实时有限状态机的自动测试，首先需要基于白盒测试原则，完成测试案 例的编制，然后根据测试案例，测试案例的编制和测试序列的生成优选由计算机自动完成。白盒测试是把测试对象看作一个打开的盒子，按照测试对象内部的结构测试程 序，通过测试来检测测试对象内部动作是否按照设计规格说明书的规定正常进行，检验程 序中的每条通路是否都能按预定要求正确工作。实时有限状态机自动测试系统原理框图如图3所示，该测试系统由上位机、实时 控制器、待测电路板插箱或整机组成。该系统使用通用计算机作为上位机，上位机运行测试软件，通过实时控制器向电 路板或整机提供受控的电源和测试激励信号，按照测试案例，以全自动测试方式进行数字 逻辑器件中实时有限状态机的测试活动，实时控制器将测试结果发送给上位机测试软件生 成测试报告和测试日志。上位机运行的测试软件只负责发起某个或全部测试案例，并以图形化的方式提供 人机交互界面，生成测试报告和测试日志。实时控制器负责控制待测电路板或整机的电源，以确保测试时才开始向其供电。 同时实时控制器模拟实时有限状态机自动测试所需的全部测试激励信号，采集、判断测试 反馈信号，并向上位机输出。由于某些状态转移路径测试会使实时有限状态机进入“死” 状态，因此实时控制器可以通过关断待测电路板或整机的电源后再上电的方式完成后续测
试ο实时控制器必须满足测试实时性要求，优选使用实时操作系统的嵌入式计算机 (例如PC104模块)实现，测试时上位机只负责测试的发起，测试的执行完全由实时控制器 完成，其它测试的辅助工作由上位机完成，以充分发挥实时控制器的实时能力和上位机的 人际交互、界面、报告与日志生成、数据记录与查询等能力。基于计算机自动测试系统的测试流程如图4所示。本发明的技术关键点在于给出了实时有限状态机以状态节点为中心考虑状态转 移的化简方法；给出了实时有限状态机的状态转移触发输入条件时间约束值的离散化处理 方法；给出了实时有限状态机自动测试系统的原理组成和功能描述。本发明针对实时有限状态机的完善测试，基于状态转移化简和状态转移触发输入 条件时间约束值离散化处理，提供了减少测试案例数量的方法，同时给出了基于实时有限 状态机自动测试系统和方法，以全自动方式完成数字逻辑器件中实时有限状态机的测试工 作。该发明能够解决测试案例数量爆炸的问题，大大提高测试效率，能够迅速发现实时有限 状态机的漏洞与缺陷。以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人 员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变型，这些改进和变型
7也应视为本发明的保护范围。
权利要求
一种测试数字逻辑器件中实时有限状态机的方法，其特征在于，包括步骤S1，基于白盒测试原则，减少测试案例，在此基础上完成测试案例的编制，并生成测试序列；S2，上位机向实时控制器发送测试命令，实时控制器提供受控电源和测试激励信号，按照全自动测试方式进行测试，生成测试结果；S3，实时控制器采集测试结果，并将所述测试结果发送给上位机生成测试报告和测试日志。其中，所述步骤S1中，所述减少测试案例的过程包括步骤S1 1，从上电复位的初始状态S1开始，遍历该状态所有触发输入条件I1个，检查状态转移是否正确；S1 2，对初始状态按照正常触发方式转移的下一个状态Si，遍历所有触发输入条件Ii个，检查状态转移是否正确；S1 3，按照步骤S1 2的方式，对所有N个状态进行测试。S1 4，对于所述触发输入条件中的时间约束值，进行离散化处理。
2.如权利要求1所述的测试数字逻辑器件中实时有限状态机的方法，其特征在于，当 所述时间约束值最大为Tmax时，在W，2Tmax]之间，取值间隔选为Tmax/10 ；且 在[2Tmax，5Tmax]之间，取值间隔选为Tmax。
3.如权利要求1所述的测试数字逻辑器件中实时有限状态机的方法，其特征在于，当 所述时间约束值最小为Tmin时，在
之间，取值间隔选为3Tmin/10 ； 在[Tmin，2Tmin]之间，取值间隔选为Tmin/10 ；且 在[2Tmin，5Tmin]之间，取值间隔选为Tmin。
4.如权利要求1所述的测试数字逻辑器件中实时有限状态机的方法，其特征在于，当 所述时间约束值为[T1, T2]时，在
之间，取值间隔选为3V10 ； 在[T1, T2]之间，取值间隔选为(T2-T1VlO ； 在[T2，5T2]之间，取值间隔选为T2。
5.如权利要求1所述的测试数字逻辑器件中实时有限状态机的方法，其特征在于，当 所述时间约束值为单点值T时，在
之间，取值间隔选为Τ/10 ； 在[2Τ，5Τ]之间，取值间隔选为T0
全文摘要
本发明公开了一种测试数字逻辑器件中实时有限状态机的方法，包括步骤S1，减少测试案例、完成测试案例的编制，并生成测试序列；S2，按照全自动测试方式进行测试，生成测试结果；S3，采集测试结果，发送给上位机。其中，所述步骤S1具体包括S1-1，从上电复位的初始状态S1开始，遍历该状态所有触发输入条件I1个，检查状态转移是否正确；S1-2，对初始状态按照正常触发方式转移的下一个状态Si，遍历所有触发输入条件Ii个，检查状态转移是否正确；S1-3，按照步骤S1-2的方式，对所有N个状态进行测试。S1-4，对于所述触发输入条件中的时间约束值，进行离散化处理。该发明能够解决测试案例数量爆炸的问题，大大提高测试效率。
文档编号G01R31/317GK101915894SQ20101023538
公开日2010年12月15日 申请日期2010年7月22日 优先权日2010年7月22日
发明者王悉, 袁彬彬, 马连川 申请人:北京交通大学