Hidden Markov models with patterns to learn Boolean vector sequences and applications to the built-in self-test for integrated circuits

Abstract

We present a new model, derived from the hidden Markov model (HMM), to learn Boolean vector sequences. Our HMM with patterns (HMMP) is a simple, hybrid, and interpretable model that uses Boolean patterns to define emission probability distributions attached to states. Vectors consistent with a given pattern are equally probable, while inconsistent ones have probability zero to be emitted. We define an efficient learning algorithm for this model, which relies on the maximum likelihood principle, and proceeds by iteratively simplifying the structure and updating the parameters of an initial specific HMMP that represents the learning sequences. HMMPs and our learning algorithm are applied to the built-in self-test (BIST) for integrated circuits, which is one of the key microelectronic problems. An HMMP is learned from a test sequence set that covers most of the potential faults of the circuit at hand. Then, this HMMP is used as test sequence generator. The experiments carried out show that learned HMMPs have a very high fault coverage.