Testing VLSI circuits is a complex task that requires enormous amounts of resources. To decrease testing costs, testing issues are considered earlier in the design process. This is known as "design for testability" (DFT). Built-in Self Test (BIST) is one proposed DFT approach. BIST generally consists of incorporating additional circuitry on the chip to generate test patterns and compact the response of the circuit under test (CUT) into a reference signature. Compaction implies an information loss, introducing the possibility that a faulty circuit declares itself as good. Such errors are known as aliasing errors. Several BIST schemes have been proposed, and each have a particular performance in regard to aliasing. However, the schemes are often evaluated and compared with ill-defined measures for which the underlying assumptions are either not stated or understood clearly. Here, a novel classification for the measures of aliasing is proposed. By providing clear definitions of different possible measures, the proposed classification augments the understanding of the aliasing problem.

This dissertation focuses on the popular BIST scheme that consists of applying pseudorandom test patterns to a CUT and compacting the latter's response by a signature analysis register which is normally a linear feedback shift register(LFSR). Assessing the quality of such a scheme in regard to fault coverage is crucial. Fault coverage can be established by full fault simulation. However, high costs may preclude this approach. Other techniques, probabilistic in nature, have been proposed, but a lack of computationally feasible techniques for analyzing the aliasing problem under a reasonable model has left them elusive. Here, new and computationally feasible techniques are developed. More specifically, closed-form expressions for the probability of aliasing are derived for a certain type of LFSRs. Upper bounds are derived for LFSRs characterized by primitive polynomials. An iterative technique is developed for computing the exact probability of aliasing for LFSRs characterized by any feedback polynomial, and for any test sequence length. These new techniques enable better assessments of the quality of BIST schemes that use signature analysis for response compaction. In turn, they are useful for making important design decisions, e.g., determining the number of test patterns that should be applied to a CUT to achieve a certain test confidence;​ alternatively, deciding how long the signature analyzer should be, and what type of feedback it should possess to achieve a certain desired test confidence.

The techniques developed for computing the probability of aliasing in BIST are also useful in the context of coding theory. The iterative technique developed for computing the probability of aliasing may be used as an efficient technique for computing the probability of an undetected error for shortened versions of cyclic codes.

Le test des circuits intégrés à très grande échelle. i.e.. circuits VLSI, est un problème complexe qui exige une quantité considérable de ressources informatiques et humaines. Afin de réduire les coûts de test, il est nécessaire de considérer le test aussitôt que possible dans la phase de concéption d'un circuit. i.e.. pratiquer du "design for testability (DFT). Le test intégré, ou BIST (Built-In Self-Test), est un exemple de DFT Le BIST consiste à intégré avec le circuit original, un circuit generateur de tests. et un circuit qui sert à comprimer la réponse du circuit sous test. Cette compression implique une perte d'information qui introduit la possibilité qu'un circuit défectueux se déclare bon, soit une erreur de "aliasing" ou de "masking". Plusieurs types de BIST ont été proposés Tous ont une différente performance par rapport au "aliasing". Différentes mesures de "aliasing" sont aussi utilisées Malheureusement, ces mesures sont souvent ambigues, et prêtent à de mauvaises interprétations Cette dissertation présente une nouvelle classification de ces mesures. En soi, cette classification augmente la compréhension du problème de "aliasing".

Le type de BIST qui consiste à appliquer des tests pseudo-aléatoires et de comprimer la réponse du circuit avec un "signature anslysis register" ou "linear feed- back shift register" (LFSR) constitue une approche très populaire. Cette dernière est l'approche traitée içi. Il est essentiel d'établir la qualité d'un tel type de test. e.g.. par rapport à la proportion de pannes dé.ectées. Une technique bien connue qui sert à cette fin est la simulation de panne. Cependant, pour les circuits VLSI, la simula- tion de panne peut s'avérer très couteuse, et même impossible D'autres techniques. d'analyse probabilistique ont déjà été proposées. Malheureusement, jusqu'à ce jour, dû au manque de techniques d'analyse du problème de "aliasing" en BIST, la qualité de ces techniques probabilistiques est demeurée faible. Ici, de nouvelles techniques d'analyse du problème de "aliasing" sont dévelopées. Plus spécifiquement, des expréssions fermées pour la probabilité de “aliasing" sont obtenues pour un certain type de LFSR, et des bornes supérieures de la probabilité de “aliaising" sont obtenues pour les “signature analysis registers" (LFSR) charactérisés par des polynômes primitifs. Une technique d'analyse itérative a aussi été dévelopée. Cette dernière permet d'obtenir la probabilite de "aliasing" en fonction de la longueur de 'a séquence de test, pour tout type de LFSR Ces techniques permettent une meilleur estimation de la qualité du BIST utilisant “sig- nature analysis" comme technique de compréssion Ainsi, ces techniques sont utiles pour déterminer les paramètres tels que la longueur de test, et le type de compresseur requis, afin d'obtenir la qualité de test desirée.

Les techniques d'analyse dévelopées içi sont aussi utiles dans le contexte de la théorie du codage. La technique itérative dévelopée pour le calcul de la probabilite de "aliasing" constitue une technique efficace pour le calcul de la probabilité d'une ertent non detectée lorsque l'information est encodée par des codes cycliques.