Easily Testable Sequential Machines with Extra Inputs

Hideo Fujiwara, Tsutomu Sasao, Kozo Kinoshita

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)


In this paper, an easily testable machine is defined as one which possesses: 1) a distinguishing sequence of length log2n] which forces the machine into a specific state S1, and 2) transfer sequences of length at most [log2n] to carry the machine from state S1 to state Si for all i. A design procedure is presented in which an arbitrary machine is augmented to an easily testable machine by adding two special input symbols to the original machine. An efficient procedure is also described for designing checking experiments for the easily testable machines. For an n-state, m-input symbol machine, this procedure gives a bound on the length of the checking experiment that is approximately mn[log2n]. n]. Furthermore, the total checking experiments are preset.

Original languageEnglish
Pages (from-to)821-826
Number of pages6
JournalIEEE Transactions on Computers
Issue number8
Publication statusPublished - Aug 1975


  • Checking experiments
  • distinguishing sequences
  • easily testable machines
  • fault detection
  • sequential machines
  • shift register
  • transition checking


Dive into the research topics of 'Easily Testable Sequential Machines with Extra Inputs'. Together they form a unique fingerprint.

Cite this