求最短区分序列(SDS)的并行算法

PARALLEL ALGORITHM FOR FINDING THE SHORTEST DISTINGUISH SEQUENCES (SDS)

本文在[1,2,5]的基础上,提出了求时序机的最短区分序列(SDS)的一个算法。文中只用到一个终止规则和向量逻辑乘及异或运算,程序设计十分简单。若时序机的DS存在,通过本算法能优选一条路径,求出SDS。从而使按(2~n)~r的指数计算复杂性降为r×2~n的计算关系。当DS的长度r增加时,本算法的优越性更为突出。

The operations of matrices is an effective tool for seeking distinguish sequences (DS). When the number of input variables is n and the length of input sequence is r, r × (2n)r times of matrices multiplications are needed to determine whether the input sequence is DS. When n and r are big, it is a uncomputational problem. So the parallel algorithm for finding the shortest distinguish sequences (SDS) is put forward and the computational complexity is decreased to r×2n.