NOTE: This item is not available outside the Texas A&M University network. Texas A&M affiliated users who are off campus can access the item through NetID and password authentication or by using TAMU VPN. Non-affiliated individuals should request a copy through their local library's interlibrary loan service.
Generation of Test Sequences for programmable logic array-based Finite State Machines
MetadataShow full item record
Entities on a network communicate with each other using protocols. Protocols are rigid specifications of rules which entities must follow to ensure proper operation and unambiguous exchange of information. Testing of protocols have taken many directions. Most of these include application of a Test Sequence and checking the implementation to verify that that it indeed confirms to its specification. Checking is done by applying the Test Sequence to the implementation and verifying that the responses generated to those inputs match the specification. The test sequence is constructed using a variety of methods, including, the Distinguishing Sequence Method, W-Set Method, and the UIO Method. One drawback of test sequences generated thus, is that the sequences are long and time-consuming to construct. A common method of specification of a protocol is the Finite State Machine model. Each of these methods assume that the specification is a minimal, strongly connected, deterministic Finite State Machine. This thesis introduces a method to minimize the length of the test sequence. The key to this approach is in the synthesis of the Finite State Machine. This approach proposes a that, if the combinatorial parts of the Finite State Machine, are implemented by a PLA, it is possible, using the UIO Method, to generate shorter-length test sequences. It also demonstrates that test sequences thus generated, cover a wide variety of faults. If, during the synthesis of the Finite State Machine, the combinatorial parts are implemented by a PLA, a Binary State Transition Graph, (Binary STG), can be easily realised. It is shown that this Binary STG may be partially enumerated to generate a Finite State Machine, with lesser number of edges. Since the partially enumerated Binary STG has a lesser number of edges, it is easy to see that shorter length test sequences can result. The UIO sequence for each state in the partially enumerated Binary STG is constructed. For such states for which no UIO sequence exists, a unique Signature Set is constructed. These UIO/signature sequences are then used to construct the Test Sequence, using the Shortest Path tour, going through every transition in the Finite State Machine. The test sequences generated, test for the core behavior of the implementation under test (IUT). Many real-life machines have been considered, some of which model, commercial protocols. Fault coverage and Fault simulation experiments have been performed on these specifications, the results of which are also included.
DescriptionDue to the character of the original source materials and the nature of batch digitization, quality control issues may be present in this document. Please report any quality issues you encounter to firstname.lastname@example.org, referencing the URI of the item.
Includes bibliographical references.
Sathyanarayana, Murali Kadaba (1994). Generation of Test Sequences for programmable logic array-based Finite State Machines. Master's thesis, Texas A&M University. Available electronically from
Request Open Access
This item and its contents are restricted. If this is your thesis or dissertation, you can make it open-access. This will allow all visitors to view the contents of the thesis.