基于二叉树的时序电路测试序列设计

    在时序电路的设计或故障检测过程中，需要对电路进行状态验证，状态验证就是用一个事先设计的测试序列，对待测电路的输入端进行激励，同时检测电路的输出响应，判断电路是否具有全部设定状态，能否实现设定的状态转换。测试序列设计包括：描述电路状态转换信息；确定电路到达全部预定状态所需的输入测试码；将测试码以适当算法构成状态测试序列。使用测试序列对电路输入端进行激励，电路具
有设定的全部状态，能够实现设定的状态转换功能。则电路设计目的达到或电路无故障，反之设计目的未达到或电路有故障。
    有两类设计时序电路测试序列的方法：第一类称为迭代法，将时序电路等价为p维的组合电路迭代模型，考察i个时钟到来时pi维组合电路模型的输入输出响应，并按一定的迭代算法求出该时序电路的测试序列。第二类称为检测试验法，通过对待测时序电路进行试验性激励，导出一个测试序列，宏观地检查输出是否实现预定功能。
    前者需要建立多个电路模型，计算方法复杂。后者方法简单但是需要多次激励验证，特别是对于多层逻辑结构的电路，试验性激励将十分繁杂。通过对时序电路状态描述，建立电路状态二叉树，利用二叉树具有的数据元素(节点、分支)的非线性关系，设计时序电路的测试序列具有简单清晰的特点。

1 电路状态描述
    时序电路状态二叉树可以根据电路状态转换表的信息建立。在电路设计阶段，状态转换表可以由所需的状态转换图推出。在已知电路测试或故障诊断阶段，状态转换表可以通过电路状态分析推出。例如，图1所示的时序电路，由Q1、Q0两个JK触发器在同一时钟CLK控制下翻转，X为输入信号，Z为输出信号。由电路分析可知：
    电路的触发器驱动方程为：J1=K1=(XQ0)’；J0=X K0=(X’Q1)’
    电路的触发器状态方程为：；
    电路的输出方程为：
    电路的触发器位数N=2，状态数M=2N=4，4个状态分别为A=00、B=01、C=10、D=11。
    所以，图1所示时序电路的状态转换功能可以用如图2所示状态图描述。

    设：PS为初态，NS为现态，图1所示时序电路的状态转换功能也可以用如表1所示状态表来描述。

    状态表描述了电路在输入X作用下，输出Z以及电路状态NS与输入X之间的逻辑关系，包涵了电路状态验证和故障检测所需的全部测试码，原则上可以直接使用状态表的信息设计出电路的测试序列。但是，状态表中描述测试码与时序电路状态的逻辑层次关系不明显，没有直接反映出电路状态与输入的多层逻辑关系。所以，设计具有多层逻辑关系电路的输入测试序列，仅状态表信息有一定难度。[page]

2 电路二叉树构成
    二叉树是一种以节点(数据元素)按分支(树枝)关系组织，按分支层次关系定义的树型非线性数据结构。其基本特点是：第i层最多有2i-1个节点，i=1层只有一个节点称为根节点；每个节点最多有两个后继子树，除根节点外的所有节点都有且只有一个直接前驱；深度为k的的二叉树的最大节点数为2k-1。如图3是深度为3的二叉树。

    二叉树描述时序电路时，用二叉树节点Ni代表电路在i时刻的状态，电路初始(或复位)状态称为根节点。用二叉树两节点之间的树枝表示输入码的逻辑值，在节点Ni处输入码X=0构成左子树，输入码X=1构成右子树，两棵子树分别连接下一层的两个节点。所以，节点Ni到Ni+1之间树枝的遍历，在逻辑上代表了电路由状态Ni转换到状态Ni+1所需的输入序列Xi。其中，由根节点N01到节点Ni所经历的树枝，组成了电路的一个测试序列Xi。Xi的长度就是二叉树的层数，各层的节点数N=2i-1按指数规律增加。
    通电初始时刻图1时序电路在状态二叉树的根节点N01处，可能是A、B、C、D中的任意一个状态，可以用节点向量N01=(ABCD)表示，如图4所示。

    在根节点N01处：当输入X=0，形成根节点的左子树，连接到N11节点，如图4所示。由表1可知输入X=0时，若输出Z=1，电路发生了初态PS=C到现态NS=A的转换，记为C0→1A；若输出Z=0则电路可能发生D0→0B、A0→0C或B0→0C的状态转换。所以，节点N11处电路状态可用节点向量N11=(A)1(BCC)0表示。其中，节点向量的分量则表示电路在输入Xi作用下，当输出为Zi时的电路状态。例如，分量(A)1表示测得Z=1电路应为状态A；分量(BCC)0表示测得Z=0电路有可能是状态B或C。
    当输入X=1，形成根节点的右子树，连接到N12节点，如图4所示。由表1可知输入X=1时，若Z=0电路发生了C1→0B的状态转换；若输出Z=1则电路可能发生B1→1A、A1→1D或D1→1C的状态转换。用向量N12=(ACD)1(B)0表示。
    电路到达节点N11=(A)1(BCC)0后：再输入X=0(相当于在根节点N01处输入序列Xi=00)，电路到达节点N21=(C)10(C)00(AA)01处，如图4所示。其中，分量(C)10表示在输入序列X=00作用下，若输出序列Z=10电路状态为C；分量(C)00表示在输入序列X=00作用下，若输出序列Z=00电路状态也为C；分量(AA)01表示在输入序列X=00作用下，若输出序列Z=01电路状态为A。若再输入X=1(即N01处输入序列Xi=01)，电路到达节点N22=(D)11(A)01(BB)00处。
    同理，输入序列Xi=10，电路到达节点N23=(BC)10(A)11(C)00；输入序列Xi=11，电路到达节点N24=(CD)11(B)10(A)01。可见，当输入序列长度为2时，到达二叉树的第二层，有4棵子树对应4个节点N21、N22、N23、N24，如图4所示。
    依次由根节点N01处开始，输入序列为X=000、X=001、X=010、X=011、s=100、X=101、X=110、X=111，电路到达节点N31～N38，……即可以得到时序电路二叉树，如图4所示。其中，输入序列长度i是二叉树的层数，各层的节点数N=2i-1按指数规律增加。
    在构建电路二叉树过程中，当节点向量与前级某节点向量重复时，该节点是二叉树的一个终止节点。例如：N41与N21重复、N44与N31重复、N49与N35重复，二叉树不再从这些节点延伸。考虑到研究时序电路二叉树的目的是确定测试序列，当节点向量能够确定电路唯一状态(例如，节点N511处电路状态必为C)二叉树不再从这个节点延伸。当节点的输出序列Z能够区分电路全部状态，(例如，节点N38处电路向量N38=(B)110(C)111(A)101(D)011，表明在输入序列X=111作用下，若Z=110电路状态必为B，若Z=111电路状态必为C，若Z=101电路状态必为A，若Z=011电路状态必为D。)二叉树也不再从这个节点延伸。[page]

3 节点向量与输入序列
    电路二叉树的一个节点向量通常由多个分量组成，例如向量N11=(A)1(BCC)。由(A)1和(BCC)0两个分量构成。一个分量通常包含多个电路状态，例如分量(BCC)0包含B和C两个状态。有两个以上不同状态组成的分量称为非同类分量，由非同类分量构成的向量称为不确定向量，例如N01、N11、N12和N23。
    只包含一个状态或仅包含多个相同状态的分量(例如(A)1和(AA)00)称为同类分量，由同类分量构成的向量称为同类不确定向量(例如N21和N22)，在同类不确定向量节点处，总能根据电路的输出序列唯一地确定电路达到的状态。所以，由根节点到同类不确定向量节点，经历树枝构成的输入序列称为引导序列，记为Xh。例如，由N01到达N22的输入序列X=01就是图1电路的一个引导序列。在引导序列Xh=01作用下，若Z=00则状态必为B；Z=01状态必为A；Z=11状态必为D。
   只包含一个状态的同类分量(例如(A)1、(B)100和(C)10)又称为平凡不确定分量，全部由平凡不确定分量构成的向量称为平凡不确定向量(例如N38=(B)110(C)111(A)101(D)011)，在平凡不确定向量节点处，电路虽可能有多个不同状态，但根据输出序列可以确定电路当前状态。所以，由根节点到平凡不确定向量节点，经历树枝构成的输入序列称为区分序列，记为Xd。例如，由N01到达N38的输入序列X=111就是图1电路的区分序列。在区分序列Xd=111作用下，若输出序列Z=101，则电路状态由D到达A，记为D111→101A；若输出序列Z=110，则电路状态由A到达B，记为A111→110B；若输出序列Z=111，则电路状态由B到达C，记为B111→111C；若输出序列Z=011，则电路状态由C到达D，记为C111→ 011D。区分序列常用于验证或确定电路所处的状态，区分序列也是引导序列，但并不是每个时序电路都存在区分序列。
    利用区分序列可以生成表3是图1电路在区分序列Xd=111作用下的电路状态引导表。其中：IS是Xd作用前状态，FS是作用后的状态。
    全部由同一状态同类分量构成的向量(例如N511=(C)11010(C)01000(CC)00000)称为同类不确定向量，在同类平凡不确定向量节点处，电路虽可能有多个不同的输出序列，但电路状态是唯一的。所以，由根节点到同类不确定向量节点，经历树枝构成的输入序列称为同步序列，记为Xs。例如，由N01到N511的输入序列X=01010就是图1电路的一个同步序列，在同步序列Xs=01010的激励下电路由N01到达N511，无论输出序列Z=11010、Z=01000或Z=00000电路状态都为C。同步序列是一个特殊的引导序列，常用于把电路从未知状态引导到一个已知的状态起点。
    能够将电路从已知状态转换到预定状态的输入序列X称为转换序列记为Xt，转换序列由转换码构成。由状态转换图2中可见Xt0=0是图1电路C0→1A、A0→0C、B0→0C、D0→0B的转换码；Xt1=1是A1→1D、B1→1A、C1→0B、D1→1C的转换码。转换序列常用于核实电路状态转换功能，例如：当图1电路已确认引导到C状态后，在转换序列Xt10=Xt1-Xt0=10激励下，如果输出序列Z=00表明电路实现了C1→0B、B0→0C转换。

4 测试序列与状态验证
    时序电路状态验证过程通常包括：状态引导阶段，采用引导序列将电路从未知状态引导到预定状态。状态验证阶段，采用区分序列逐一核实电路具有全部状态。状态转换验证阶段，采用转换序列核实电路具有全部状态转换功能。能够完成状态验证全部过程的输入序列，称为测试序列。在实践中，测试序列可采用引导序列Xh、区分序列Xd以及必要的转换序列Xt组成测试序列，如测试序列可为X=Xh-Xd-Xt等。
    例如，图1所示电路最直观的测试序列可以是X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0。其中，同步序列Xs=01010将电路由来知引导到确定的状态C；4组区分序列Xd1=111分别验证电路具有D、A、B和C4个状态；转换序列4Xt1=1111分别验证电路有C1→0B、B1→1A、A1→1D、D1→1C状态转换功能；转换序列2Xt0=00分别验证电路有C1→0A、A0→0C状态转换功能；转换序列Xt10=10验证电路有C1→0A转换功能；区分序列Xd1=111将电路由C状态引导到D状态；转换序列2Xt0=00验证电路有D0→0B转换功能。至此，图1电路具有的所有状态和状态转换功能都得到验证。这样构成的测试序列X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0=01010 111 111 111 111 1111 0010 111 00长度达30层。
    实践中，在能够确认电路所有状态和状态转换功能的原则上，测试序列长度越短越好。对于图1电路的测试序列也可以是X=Xs-2Xt0-4Xt1-Xd。其中，同步序列Xs=01010引导电路到C，同时也验证了电路有C状态；转换序列2Xt0=00验证电路有C0→1A、A0→0C转换功能，同时也验证电路有A状态；转换序列4Xt1=1111验证电路有C1→0B、B1→1A转换功能，且验证电路有B状态，验证电路有A1→1D、D1→1C转换功能，且验证有D状态；区分序列Xd=111引导电路C111→011D到达状态D；转换序列2Xt0=00验证电路有D0→0B、B0→0C转换。这时测试序列X=01010 00 1111 111 00长度仅为16层。在该测试序列作用下，若电路输出序列为Z=XXXXX 10 0111 01100(前5个输出可能是11010或01000或00000之一)，则图1电路具有A、B、C、D 4个状态，并实现了图2设定全部状态转换功能。

5 结论
    通过建立时序电路的状态二叉树，可以得到该时序电路的测试序列X，在测试序列X的作用下，电路将产生一个输出序列Z。如果无故障电路在X作用下输出序列为Zo，有故障电路在X作用下的输出序列为Zf，显然Zo≠Zf。在正常序列Zo和故障序列Zf中0、1的个数和分布规律不同。因此，检测输出序列Z的0、1个数以及分布规律就可以确定电路是否有故障。在实践中并不是所有的时序电路都可以是先找到一个完整的测试序列，有时必须根据电路在前一个序列作用下的输出序列来决定继续检测所需的测试序列。