Protocol conformance testing using multiple UIO sequences

Automatic generation of conformance test sequences for communication protocols by means of unique input/output (UIO) sequences is addressed. It is shown that if multiple minimum-length UIO sequences are computed for each state of the finite-state-machine (FSM) specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for assignment of the multiple UIO sequences is given. This algorithm, which is based on network flow, is polynomial in the number of states and transitions of the FSM and is effective in reducing the overall length of the test sequence     

An optimization technique for protocol conformance test generationbased on UIO sequences and rural Chinese postman tours

A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing     

Entropy Coding With Variable-Length Rewriting Systems

This paper describes a family of codes for entropy coding of memoryless sources. These codes are defined by sets of production rules of the form almacr rarr bmacr, where a is a source symbol, and lmacr, bmacr are sequences of bits. The coding process can be modeled as a finite-state machine (FSM). A method to construct codes which preserve the lexicographic order in the binary-coded representation is described. For a given constraint on the number of states for the coding process, this method allows the construction of codes with a better compression efficiency than the Hu-Tucker codes. A second method is proposed to construct codes such that the marginal bit probability of the compressed bitstream converges to 0.5 as the sequence length increases. This property is achieved even if the probability distribution function is not known by the encoder     

On the Wyner-Ziv problem for individual sequences

We consider a variation of the Wyner-Ziv (W-Z) problem pertaining to lossy compression of individual sequences using finite-state encoders and decoders. There are two main results in this paper. The first characterizes the relationship between the performance of the best M-state encoder-decoder pair to that of the best block code of size /spl lscr/ for every input sequence, and shows that the loss of the latter relative to the former (in terms of both rate and distortion) never exceeds the order of (logM)//spl lscr/, independently of the input sequence. Thus, in the limit of large M, the best rate-distortion performance of every infinite source sequence can be approached universally by a sequence of block codes (which are also implementable by finite-state machines). While this result assumes an asymptotic regime where the number of states is fixed, and only the length n of the input sequence grows without bound, we then consider the case where the number of states M=M/sub n/ is allowed to grow concurrently with n. Our second result is then about the critical growth rate of M/sub n/ such that the rate-distortion performance of M/sub n/-state encoder-decoder pairs can still be matched by a universal code. We show that this critical growth rate of M/sub n/ is linear in n.     

Support vector machine techniques for nonlinear equalization

The emerging machine learning technique called support vector machines is proposed as a method for performing nonlinear equalization in communication systems. The support vector machine has the advantage that a smaller number of parameters for the model can be identified in a manner that does not require the extent of prior information or heuristic assumptions that some previous techniques require. Furthermore, the optimization method of a support vector machine is quadratic programming, which is a well-studied and understood mathematical programming technique. Support vector machine simulations are carried out on nonlinear problems previously studied by other researchers using neural networks. This allows initial comparison against other techniques to determine the feasibility of using the proposed method for nonlinear detection. Results show that support vector machines perform as well as neural networks on the nonlinear problems investigated. A method is then proposed to introduce decision feedback processing to support vector machines to address the fact that intersymbol interference (ISI) data generates input vectors having temporal correlation, whereas a standard support vector machine assumes independent input vectors. Presenting the problem from the viewpoint of the pattern space illustrates the utility of a bank of support vector machines. This approach yields a nonlinear processing method that is somewhat different than the nonlinear decision feedback method whereby the linear feedback filter of the decision feedback equalizer is replaced by a Volterra filter. A simulation using a linear system shows that the proposed method performs equally to a conventional decision feedback equalizer for this problem     

Synchronizable test sequences based on multiple UIO sequences

A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system where both external synchronization and input/output operation costs are taken into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification; and an algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, namely, the transitions to be tested and the UIO sequences to be employed form a weakly-connected subgraph of the duplexU digraph, the proposed algorithm yields a minimum-cost test sequence. X.25 DTE and ISO Class 0 transport protocols are shown to possess this property. Otherwise, the algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 network-side protocol is shown to be the cost sum of an input/output operation pair and an external synchronization operation     

Synchronization and Specification Issues in Protocol Testing

Protocol testing for the purpose of certifying the implementation's adherence to the protocol specification can be done with a test architecture consisting of remote tester and local responder processes generating specific input stimuli, called test sequences, and observing the output produced by the implementation under test. It is possible to adapt test sequence generation techniques for finite state machines, such as transition tour, characterization, and checking sequence methods, to generate test sequences for protocols specified as incomplete finite state machines. For certain test sequences, the tester or responder processes are forced to consider the timing of an interaction in which they have not taken part; these test sequences are called nonsynchronizable. The three test sequence generation algorithms are modified to obtain synchronizable test sequences. The checking of a given protocol for intrinsic synchronization problems is also discussed. Complexities of synchronizable test sequence generation algorithms are given and complete testing of a protocol is shown to be infeasible. To extend the applicability of the characterization and checking sequences, different methods are proposed to enhance the protocol specifications: special test input interactions are defined and a methodology is developed to complete the protocol specifications.     

An iteration algorithm of coding internal states of finite-state machines for minimizing the power consumption

A heuristic iteration algorithm of coding internal states of finite-state machines for reducing the power consumption is considered. The proposed algorithm is universal and can be applied to any results of coding the internal states (including random) to minimize the power consumption of the finite-state machine. In addition, the user can select a trade-off between the problem-solving quality and algorithm-execution time by specifying the maximum number of iterations. The experimental studies showed that the proposed approach is intended to decrease the power consumption of the finite-state machines on average by a factor of 1.73, as compared with the NOVA algorithm (in separate cases, by a factor of 3.29), and by a factor of 1.40, compared to the JEDI algorithm (in separate cases, by a factor of 2.31).     

Coding theorems for individual sequences

A quantity called the {em finite-state} complexity is assigned to every infinite sequence of elements drawn from a finite sot. This quantity characterizes the largest compression ratio that can be achieved in accurate transmission of the sequence by any finite-state encoder (and decoder). Coding theorems and converses are derived for an individual sequence without any probabilistic characterization, and universal data compression algorithms are introduced that are asymptotically optimal for all sequences over a given alphabet. The finite-state complexity of a sequence plays a role similar to that of entropy in classical information theory (which deals with probabilistic ensembles of sequences rather than an individual sequence). For a probabilistic source, the expectation of the finite state complexity of its sequences is equal to the source's entropy. The finite state complexity is of particular interest when the source statistics are unspecified.     

Functional versus random test generation for sequential circuits

This article presents a test generation method for sequential circuits based on their synthesis specifications as finite state machines (FSM) and provides comparison with random test generation. The finite state machines are represented by their state transition graph (STG). The test generation method is performed in two phases. The first phase is functional. It generates a test sequence which is one of the shortest input sequences going through all the transitions of the state transition graph machine. This sequence provides a high fault coverage of stuck-at faults on the synthesized circuit compared to a randomly generated test sequence. This fault coverage is very close to the ones of other sequences derived by fault-oriented test generation approaches [9], [10], although these latter sequences are much longer.The trend of the fault coverage curve for different test sequences including progressively the transitions of the test sequence defined in the first phase is similar to the one of the fault coverage curve of a random sequence but for same lengths the first curve gives larger fault coverage. Both curves grow rapidly until a given ratio of faults is detected then continue to grow very slowly exhibiting low efficiency.The second phase of the test generation method is fault-oriented. It uses a fault simulation based approach in order to compute the test sequence for the remaining faults not detected by the first phase. At the end of this phase the test sequence for all the nonredundant faults is derived and, the combinationally redundant faults and the sequentially redundant faults are distinguished.     

Finite-memory universal prediction of individual sequences

The problem of predicting the next outcome of an individual binary sequence under the constraint that the universal predictor has a finite memory, is explored. In this analysis, the finite-memory universal predictors are either deterministic or random time-invariant finite-state (FS) machines with K states (K-state machines). The paper provides bounds on the asymptotic achievable regret of these constrained universal predictors as a function of K, the number of their states, for long enough sequences. The specific results are as follows. When the universal predictors are deterministic machines, the comparison class consists of constant predictors, and prediction is with respect to the 0-1 loss function (Hamming distance), we get tight bounds indicating that the optimal asymptotic regret is 1/(2K). In that case of K-state deterministic universal predictors, the constant predictors comparison class, but prediction is with respect to the self-information (code length) and the square-error loss functions, we show an upper bound on the regret (coding redundancy) of O(K/sup -2/3/) and a lower bound of /spl Theta/(K/sup -4/5/). For these loss functions, if the predictor is allowed to be a random K-state machine, i.e., a machine with random state transitions, we get a lower bound of /spl Theta/(1/K) on the regret, with a matching upper bound of O(1/K) for the square-error loss, and an upper bound of O(logK/K) Throughout the paper for the self-information loss. In addition, we provide results for all these loss functions in the case where the comparison class consists of all predictors that are order-L Markov machines.     

A model for sequential machine testing and diagnosis

A mathematical framework for the testing and diagnosis of sequential machines is developed. A very general fault model is used in which a faulty machine is represented as a sequential machine, possibly with state and output sets different from those of the good machine. A deterministic finite automaton, called observer, describes the process by which one gains information from the observation of the responses to test sequences. It generalizes the work of Hennie on distinguishing and homing sequences, by modelling all the possible conclusions that could be drawn from observing the circuit under test. A nondeterministic acceptor is derived from the observer; it accepts diagnosing sequences and can also be used to generate test sequences. We then associate probabilities with this nondeterministic acceptor which, together with a stochastic source of input symbols, provides a probabilistic diagnoser. As a particular application we consider the testing and diagnosis of random-access memories by random test sequences. Our model generalizes the work by David et al. on the calculation of the length of a random test sequence required to guarantee that the probability of detection of a fault exceeds a prescribed threshold.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Grants OGP0000871 and OGP0000243, and a grant from the Information Technology Research Centre of Ontario. Preliminary papers leading to this work have appeared earlier [1] [2].     

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

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

Simulation-Based Computation of Information Rates for Channels With Memory

The information rate of finite-state source/channel models can be accurately estimated by sampling both a long channel input sequence and the corresponding channel output sequence, followed by a forward sum-product recursion on the joint source/channel trellis. This method is extended to compute upper and lower bounds on the information rate of very general channels with memory by means of finite-state approximations. Further upper and lower bounds can be computed by reduced-state methods     

Evaluation and improvement of fault coverage of conformance testingby UIO sequences

The fault coverage of testing protocols using unique input/output (UIO) sequences is analyzed. UIO sequences can be efficiently employed in checking the conformance specifications of protocols by using transition testing. The test sequence is found using the rural Chinese postman tour algorithm. A comprehensive fault model is developed, and analytical expressions are given for the fault coverage. The conditions for undetectability are analyzed, and a new algorithm is proposed. Simulation results and illustrative examples are presented. Overhead issues are discussed, and significant improvements are shown for achieving 100% fault coverage. The major advantage of the proposed approach is that it provides the theoretical basis for fault coverage evaluation of protocol testing using UIO sequences     

On the generation of minimal-length conformance tests forcommunication protocols

A technique for generating a test sequence for conformance testing of communication protocols is presented. This approach shows that it is possible to generate optimal-length test sequences which include multiple unique input/output (UIO) sequences and overlapping under certain conditions. In the absence of the above-mentioned conditions, a heuristic technique is used to obtain suboptimal solutions which show significant improvement over optimal solutions without overlapping. The technique is illustrated by the example of the NBS Class 4 Transport Protocol (TP4). The computational complexity of the algorithm is compared with that of previous techniques. A brief discussion of bounds on test sequence length is presented, and the results are compared with these bounds     

Coding approaches to fault tolerance in linear dynamic systems

This paper discusses fault tolerance in discrete-time dynamic systems, such as finite-state controllers or computer simulations, with focus on the use of coding techniques to efficiently provide fault tolerance to linear finite-state machines (LFSMs). Unlike traditional fault tolerance schemes, which rely heavily-particularly for dynamic systems operating over extended time horizons-on the assumption that the error-correcting mechanism is fault free, we are interested in the case when all components of the implementation are fault prone. The paper starts with a paradigmatic fault tolerance scheme that systematically adds redundancy into a discrete-time dynamic system in a way that achieves tolerance to transient faults in both the state transition and the error-correcting mechanisms. By combining this methodology with low-complexity error-correcting coding, we then obtain an efficient way of providing fault tolerance to k identical unreliable LFSMs that operate in parallel on distinct input sequences. The overall construction requires only a constant amount of redundant hardware per machine (but sufficiently large k) to achieve an arbitrarily small probability of overall failure for any prespecified (finite) time interval, leading in this way to a lower bound on the computational capacity of unreliable LFSMs.     

Fault detection in sequential machines with increased fault coverage

This letter develops an approach for fault detection and checking sequence design of sequential machines based on the principle of machine modification through augmentation of extra input and extra outputs, taking into consideration the case where faults occurring in a machine may cause an increase in its number of states.     

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

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