Browse Prior Art Database

Online Fault Detection and Diagnosis of Statistical Automata

IP.com Disclosure Number: IPCOM000082595D
Original Publication Date: 1975-Jan-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 8 page(s) / 180K

Publishing Venue

IBM

Related People

Kerchmar, K: AUTHOR

Abstract

This arrangement relates to the diagnosis of finite automata which process statistical (random) information. The observed tolerable input sequences contain certain conventional information which meaning the automata has to recognize. The infinite number of such semiinfinite long sequences can be obtained from a pattern scanner, which extracts information in black-white bit form from a document.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 31% of the total text.

Page 1 of 8

Online Fault Detection and Diagnosis of Statistical Automata

This arrangement relates to the diagnosis of finite automata which process statistical (random) information. The observed tolerable input sequences contain certain conventional information which meaning the automata has to recognize. The infinite number of such semiinfinite long sequences can be obtained from a pattern scanner, which extracts information in black-white bit form from a document.

Algorithms have been developed which process the variety of the random input sequences extracted by the scanner from the documents. Due to the random nature of these sequences, the hardware embodiments of the algorithms are sizable sequential circuits. The problem that occurs is how to diagnose such large sequential circuits satisfying the following test requirements:

a. Test has to allow all possible stuck at 0 (s-a-0) and stuck at 1 (s-a-1) faults as well as multiple faults in circuits.
b. Test must not require laboratory environment (oscilloscopes, meters, etc.).
c. Test must be fast.
d. Test must not require skilled personnel.
e. Test has to allocate fault(s) to one or more replaceable units.
f. The CPU (or microprocessor) has to be available.
g. There must be available at least one good automata improved by the designer.

Most of the known fault diagnostic algorithms (procedures) are of the offline nature and are limited to small combinational and sequential circuits, and cannot be applied to large systems or machines. In order to test large sequential machines, the new algorithm is developed on the basis of the online test set-up as shown in Fig. 1.

Suppose that the correct operational physical automata is presented. The question that arises is, does this automata at any given time still operate correctly, or have components, wires, or cable failures changed the original automata into some different automata? The answer to the above question can be given at any time by the following test equation:

(Image Omitted)

Difference delta A = (good automata) (bad automata) Eq 1 where the symbol is the exclusive OR operation.

If the difference delta A = 0 then "test automata" (assumed bad automata) is a good operational automata. Contrary, if delta A = 1 then "tested automata" malfunctions and diagnosis should proceed until fault is located. The test algorithm starts here. The algorithm is defined with a set of rules and theoretically illustrated with an example at the end, applied to the one of the recognition algorithms.

Rules for test transition states selection and hardware partitioning. a. Using the transition state map of Fig. 2a, define fault diagnostic state transition table for

1

Page 2 of 8

automata on test (Figs. 2b and 2c). This table must contain all possible transitions between automata states of the importance. Note, fault diagnostic state transition table and the number of states in the fault diagnostic table, depends on the number of the automata's final states and con...