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

We present a new model, derived from the Hidden Markov Model (HMM), to learn Boolean vector sequences. Our Hidden Markov Model 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 equiprobable, 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. Each simplification involves merging two states of the current HMMP, while keeping the likelihood as high as possible and the algorithm stops when the HMMP has a sufficiently small structure. 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 (computed using a specific tool) that covers most of the potential faults of the circuit at hand. Then, this HMMP is used as test sequence generator. Our experiments, carried out with classical microelectronic benchmark circuits, show that learned HMMPs have a very high fault coverage. Furthermore, their small sizes combined with their simplicity allow these models to be easily implemented on the circuits for self-testing purposes.