In the first half of this thesis, a novel approach for k-induction bounded model checking using signal domain constraints and property partitioning for proving unreachability of branches in Verilog RTL code is presented. To do this, it approach uses program slicing with respect to the variables of the property under test to generate small-sized SMT formulas that describe the change of variable values between consecutive cycles. Variable substitution is then used on these variables to generate the formula for the subsequent cycles without traversing the abstract syntax tree of the entire design. To reduce the approximation on the induction step, an addition of signal domain constraints is proposed. Moreover, we present the technique for splitting up the property in question to get a better model of the system. The later half of the thesis is concerned with presenting a technique for doing sequential vector compaction on test set generated during simulation based ATPG. Starting with a compaction framework for storing metadata and about the test vectors during generation, this work presented to methods for findind the solution of this compaction problem. The first of these two methods generate the optimum solution by converting the problem appropriate for an optimization solver. The latter method utilizes a heuristics based approach for solving the same problem which generates a comparable but sub-optimal solution while having magnitudes better time and computational efficiency. / Master of Science / Electronic circuits can be described with languages known a hardware description languages like Verilog. The first part of this thesis is concerned about automatically proving if parts of this code is actually useful or reachable when implemented on and actual circuit. The thesis builds up on a method known as bounded model checking which can automatically prove if a property holds or not for a given system. The key insight is obtained from the fact that various memory elements in a circuit is allowed to be only in a certain range of values during the design process. The later half of this thesis is gear towards generating minimum sized inputs values to a circuit required for testing it. This work uses large sized input values to circuits generated by a previously published tool and proposes a way to make them smaller. This can reduce cost immensely for testing circuits in the industry where even the smallest increase in testing time increases cost of development immensely. There are two such approaches presented, one of which gives the optimum result but takes a long time to run for larger circuits, while the other gives comparable but sub-optimal result in a much more time efficient manner.

Este trabalho consiste no projeto e implementação em CMOS de um circuito integrado digital para geração de sinais, denominado Oscilador Controlado Numericamente. O circuito será aplicado em um sistema de Espectroscopia por Bioimpedância Elétrica, utilizado como método para detecção precoce de câncer do colo do útero. Durante o trabalho, realizou-se o estudo dos requisitos do sistema de espectroscopia e as especificações dos tipos de sinais a serem gerados. Levantou-se, na bibliografia, algumas técnicas de codificação em linguagem de hardware para otimização do projeto nos quesitos área, potência dissipada e frequência máxima de funcionamento. Para implementar o circuito, também se pesquisou o fluxo de projeto de circuitos digitais, focando as etapas de codificação em linguagem de descrição de hardware Verilog e os resultados de síntese lógica e de layout. Foram avaliadas duas arquiteturas, empregando-se algumas das técnicas de codificação levantadas durante o estudo bibliográfico. Estas arquiteturas foram implementadas, verificadas em plataforma programável, sintetizadas e mapeadas em portas lógicas no processo TSMC 180 nm, onde foram comparados os resultados de área e dissipação de potência. Observou-se, nos resultados de síntese lógica, redução de área de 78% e redução de 83% na dissipação de potência total no circuito em que se aplicou uma das técnicas de otimização em comparação com o circuito implementado sem otimização, utilizando uma arquitetura CORDIC do tipo unrolled. A arquitetura com menor área utilizada - 0,017 mm2 - foi escolhida para fabricação em processo mapeado. Após fabricação e encapsulamento do circuito, o chip foi montado em uma placa de testes desenvolvida para avaliar os resultados qualitativos. Os resultados dos testes foram analisados e comparados aos obtidos em simulação, comprovando-se o funcionamento do circuito. Observou-se uma variação máxima de 0,00623% entre o valor da frequência do sinal de saída obtido nas simulações e o do circuito fabricado. / The aim of this work is the design of a digital integrated circuit for signal generation called Numerically Controlled Oscillator, designed in 180 nm CMOS technology. The application target is for Electrical Bioimpedance Spectroscopy system, and can be used as a method for early detection of cervical cancer. Throughout the work, the spectroscopy system requirements and specifications of the types of signals to be generated were studied. Furthermore, the research of some coding techniques in hardware language for design optimization in terms of area, power consumption and frequency operation was conducted looking into the bibliography. The digital design flow was studied focusing on the Verilog hardware description language and the results of logic synthesis and layout, in order to implement the circuit. Reviews of two architectures have been made, using some of the encoding techniques that have been raised during the bibliographical study. These architectures have been implemented, verified on programmable platform, synthesized and mapped to standard cells in TSMC 180 nm process, which compared the area and total power consumption of results. Based on the results of logic synthesis, a 78% area reduction and 83% power consumption reduction were obtained on the implemented circuit with encoding techniques for optimization in comparison with the another circuit using a CORDIC unrolled architecture. The architecture with smaller area - 0.017 mm2 - was chosen for implementation in the mapped process. After the circuit fabrication and packaging, the chip was mounted on an evaluation board designed to evaluate the functionality. The test results were analyzed and compared with the simulation results, showing that the circuit works as expected. The output signals were compared between theoretical and experimental results, showing a maximum deviation of 0.00623%.

A verificação funcional é o conjunto de tarefas destinado a descobrir erros gerados durante o projeto de circuitos integrados, e representa um importante desafio ao influenciar fortemente a eficiência do ciclo inteiro de produção. Estima-se que até 80% dos custos totais de projeto são devidos à verificação, tornando esta atividade o gargalo principal para reduzir o time-to-market. Tal problemática tem provocado a aparição de diversas estratégias para diminuir o esforço, ou para aumentar a capacidade de cobertura da verificação. Por um lado existe a simulação, que permite descobrir um número razoável de erros de projeto; porém, a lentidão da simulação de descrições RTL torna mínima a cobertura real de estados. Por outro lado, os métodos formais de verificação fornecem alta cobertura de estados. Um deles é a checagem de modelos, que checa a validade de um conjunto de propriedades para todos os estados do projeto sob verificação. No entanto, esta técnica padece do problema de explosão de estados, e da dificuldade de especificar um conjunto robusto de propriedades. Outra alternativa formal é a checagem de equivalência que, ao invés de verificar propriedades, compara o projeto com um modelo de referência. No entanto, a checagem de equivalência tradicional é aplicável, unicamente, a descrições no mesmo nível de abstração, e com interfaces idênticas. Como fato importante, não foram encontrados registros na literatura de sobre a verificação formal de descrições RTL, considerando ambos os aspectos computacionais (presentes no modelo de referência) e de comunicação às interfaces (provenientes da especificação funcional de protocolo). Neste trabalho apresenta-se uma metodologia de verificação formal, através do uso de técnicas de checagem de equivalência para determinar a validade de uma implementação em RTL, comparando-a com um modelo de referência em alto nível, e com um modelo formal do protocolo de comunicação. Para permitir tal checagem, a metodologia baseia-se no conceito de sequências de estados, ao invés de estados individuais como na checagem de equivalência tradicional. As discrepâncias entre níveis diferentes de abstração são consideradas, incluindo alfabetos diferentes, mapeamento entre estados, e dessemelhanças temporais. A caracterização e solução do problema são desenvolvidas através de um quadro teórico, onde se apresentam conceitos, e definições, cuja validade é provada formalmente. Uma ferramenta para aplicação prática da metodologia foi desenvolvida e aplicada sobre diferentes tipos de descrições RTL, escritas nas linguagens VHDL e SystemC. Os resultados demonstram efetividade e eficiência na verificação formal de circuitos digitais que incluem, mas não se limitam à correção de erros, encriptação, processamento de imagens, e funções matemáticas. Também, evidencia-se a capacidade da ferramenta para descobrir erros de tipo combinatório e sequencial injetados propositalmente, relacionados com a funcionalidade do modelo de referência, assim como, com a da especificação do protocolo de comunicação, dentro de tempos e número de iterações praticáveis em casos reais. / Functional verification is the group of tasks aiming the discovery of bugs created during integrated circuit design, and represents an important challenge by its strong influence on efficiency throughout production cycles. As an estimative, up to 80% of the whole design costs are due to verification, which makes verification the greatest bottleneck while attempting to reduce time-to-market. Such problem has given rise to a series of techniques to reduce the effort, or to increase verification coverage capability. On the one side, simulation allows finding a good number of bugs, but it is still far from reaching high state coverage because of RTL cycle-accurate slowness. On the other side, formal approaches supply high state coverage. Model checking, for instance, checks the validness of a set of properties for all designs states. However, a strong disadvantage resides in defining and determining the quality of the set of properties to verify, not to mention state explosion. Sequential equivalence checking, which instead of checking properties compares the design with a reference model. Nevertheless, traditionally it can only be applied between circuit descriptions where a one-to-one correspondence for states, as well as for memory elements, is expected. As a remarkable issue, no works were found in literature that dealt with formal verification of RTL designs, while taking care of both computational aspects, present in the high-level reference model, and interface communication aspects, which proceed from the protocol functional specification. This work presents a formal verification methodology, which uses equivalence checking techniques, to validate RTL descriptions through direct comparison with a high-level reference model, and with formal model of the communication protocol. It is based on extracting and comparing complete sequences of states, instead of single states as in traditional equivalence checking, in order to determine if the design intention is maintained in RTL implementation. The natural discrepancies between system level and RTL code are considered, including non-matching interface and memory elements, state mapping, and process concurrency. For the complete problem characterization and solution, a theoretical framework is introduced, where concepts and definitions are provided, and whose validity is formally proved. A tool to apply systematically the methodology was developed and applied on different types of RTL descriptions, written in VHDL and SystemC languages. The results show that the approach may be applied effectively and efficiently to verify formally digital circuits that include, but are not limited to error correction, encryption, image processing, and math functions. Also, evidence has been obtained about the capacity of the tool to discover both combinatory and sequential bugs injected on purpose, related with computational and protocol functionalities, on real scenarios.

A verificação funcional é o conjunto de tarefas destinado a descobrir erros gerados durante o projeto de circuitos integrados, e representa um importante desafio ao influenciar fortemente a eficiência do ciclo inteiro de produção. Estima-se que até 80% dos custos totais de projeto são devidos à verificação, tornando esta atividade o gargalo principal para reduzir o time-to-market. Tal problemática tem provocado a aparição de diversas estratégias para diminuir o esforço, ou para aumentar a capacidade de cobertura da verificação. Por um lado existe a simulação, que permite descobrir um número razoável de erros de projeto; porém, a lentidão da simulação de descrições RTL torna mínima a cobertura real de estados. Por outro lado, os métodos formais de verificação fornecem alta cobertura de estados. Um deles é a checagem de modelos, que checa a validade de um conjunto de propriedades para todos os estados do projeto sob verificação. No entanto, esta técnica padece do problema de explosão de estados, e da dificuldade de especificar um conjunto robusto de propriedades. Outra alternativa formal é a checagem de equivalência que, ao invés de verificar propriedades, compara o projeto com um modelo de referência. No entanto, a checagem de equivalência tradicional é aplicável, unicamente, a descrições no mesmo nível de abstração, e com interfaces idênticas. Como fato importante, não foram encontrados registros na literatura de sobre a verificação formal de descrições RTL, considerando ambos os aspectos computacionais (presentes no modelo de referência) e de comunicação às interfaces (provenientes da especificação funcional de protocolo). Neste trabalho apresenta-se uma metodologia de verificação formal, através do uso de técnicas de checagem de equivalência para determinar a validade de uma implementação em RTL, comparando-a com um modelo de referência em alto nível, e com um modelo formal do protocolo de comunicação. Para permitir tal checagem, a metodologia baseia-se no conceito de sequências de estados, ao invés de estados individuais como na checagem de equivalência tradicional. As discrepâncias entre níveis diferentes de abstração são consideradas, incluindo alfabetos diferentes, mapeamento entre estados, e dessemelhanças temporais. A caracterização e solução do problema são desenvolvidas através de um quadro teórico, onde se apresentam conceitos, e definições, cuja validade é provada formalmente. Uma ferramenta para aplicação prática da metodologia foi desenvolvida e aplicada sobre diferentes tipos de descrições RTL, escritas nas linguagens VHDL e SystemC. Os resultados demonstram efetividade e eficiência na verificação formal de circuitos digitais que incluem, mas não se limitam à correção de erros, encriptação, processamento de imagens, e funções matemáticas. Também, evidencia-se a capacidade da ferramenta para descobrir erros de tipo combinatório e sequencial injetados propositalmente, relacionados com a funcionalidade do modelo de referência, assim como, com a da especificação do protocolo de comunicação, dentro de tempos e número de iterações praticáveis em casos reais. / Functional verification is the group of tasks aiming the discovery of bugs created during integrated circuit design, and represents an important challenge by its strong influence on efficiency throughout production cycles. As an estimative, up to 80% of the whole design costs are due to verification, which makes verification the greatest bottleneck while attempting to reduce time-to-market. Such problem has given rise to a series of techniques to reduce the effort, or to increase verification coverage capability. On the one side, simulation allows finding a good number of bugs, but it is still far from reaching high state coverage because of RTL cycle-accurate slowness. On the other side, formal approaches supply high state coverage. Model checking, for instance, checks the validness of a set of properties for all designs states. However, a strong disadvantage resides in defining and determining the quality of the set of properties to verify, not to mention state explosion. Sequential equivalence checking, which instead of checking properties compares the design with a reference model. Nevertheless, traditionally it can only be applied between circuit descriptions where a one-to-one correspondence for states, as well as for memory elements, is expected. As a remarkable issue, no works were found in literature that dealt with formal verification of RTL designs, while taking care of both computational aspects, present in the high-level reference model, and interface communication aspects, which proceed from the protocol functional specification. This work presents a formal verification methodology, which uses equivalence checking techniques, to validate RTL descriptions through direct comparison with a high-level reference model, and with formal model of the communication protocol. It is based on extracting and comparing complete sequences of states, instead of single states as in traditional equivalence checking, in order to determine if the design intention is maintained in RTL implementation. The natural discrepancies between system level and RTL code are considered, including non-matching interface and memory elements, state mapping, and process concurrency. For the complete problem characterization and solution, a theoretical framework is introduced, where concepts and definitions are provided, and whose validity is formally proved. A tool to apply systematically the methodology was developed and applied on different types of RTL descriptions, written in VHDL and SystemC languages. The results show that the approach may be applied effectively and efficiently to verify formally digital circuits that include, but are not limited to error correction, encryption, image processing, and math functions. Also, evidence has been obtained about the capacity of the tool to discover both combinatory and sequential bugs injected on purpose, related with computational and protocol functionalities, on real scenarios.

Este trabalho consiste no projeto e implementação em CMOS de um circuito integrado digital para geração de sinais, denominado Oscilador Controlado Numericamente. O circuito será aplicado em um sistema de Espectroscopia por Bioimpedância Elétrica, utilizado como método para detecção precoce de câncer do colo do útero. Durante o trabalho, realizou-se o estudo dos requisitos do sistema de espectroscopia e as especificações dos tipos de sinais a serem gerados. Levantou-se, na bibliografia, algumas técnicas de codificação em linguagem de hardware para otimização do projeto nos quesitos área, potência dissipada e frequência máxima de funcionamento. Para implementar o circuito, também se pesquisou o fluxo de projeto de circuitos digitais, focando as etapas de codificação em linguagem de descrição de hardware Verilog e os resultados de síntese lógica e de layout. Foram avaliadas duas arquiteturas, empregando-se algumas das técnicas de codificação levantadas durante o estudo bibliográfico. Estas arquiteturas foram implementadas, verificadas em plataforma programável, sintetizadas e mapeadas em portas lógicas no processo TSMC 180 nm, onde foram comparados os resultados de área e dissipação de potência. Observou-se, nos resultados de síntese lógica, redução de área de 78% e redução de 83% na dissipação de potência total no circuito em que se aplicou uma das técnicas de otimização em comparação com o circuito implementado sem otimização, utilizando uma arquitetura CORDIC do tipo unrolled. A arquitetura com menor área utilizada - 0,017 mm2 - foi escolhida para fabricação em processo mapeado. Após fabricação e encapsulamento do circuito, o chip foi montado em uma placa de testes desenvolvida para avaliar os resultados qualitativos. Os resultados dos testes foram analisados e comparados aos obtidos em simulação, comprovando-se o funcionamento do circuito. Observou-se uma variação máxima de 0,00623% entre o valor da frequência do sinal de saída obtido nas simulações e o do circuito fabricado. / The aim of this work is the design of a digital integrated circuit for signal generation called Numerically Controlled Oscillator, designed in 180 nm CMOS technology. The application target is for Electrical Bioimpedance Spectroscopy system, and can be used as a method for early detection of cervical cancer. Throughout the work, the spectroscopy system requirements and specifications of the types of signals to be generated were studied. Furthermore, the research of some coding techniques in hardware language for design optimization in terms of area, power consumption and frequency operation was conducted looking into the bibliography. The digital design flow was studied focusing on the Verilog hardware description language and the results of logic synthesis and layout, in order to implement the circuit. Reviews of two architectures have been made, using some of the encoding techniques that have been raised during the bibliographical study. These architectures have been implemented, verified on programmable platform, synthesized and mapped to standard cells in TSMC 180 nm process, which compared the area and total power consumption of results. Based on the results of logic synthesis, a 78% area reduction and 83% power consumption reduction were obtained on the implemented circuit with encoding techniques for optimization in comparison with the another circuit using a CORDIC unrolled architecture. The architecture with smaller area - 0.017 mm2 - was chosen for implementation in the mapped process. After the circuit fabrication and packaging, the chip was mounted on an evaluation board designed to evaluate the functionality. The test results were analyzed and compared with the simulation results, showing that the circuit works as expected. The output signals were compared between theoretical and experimental results, showing a maximum deviation of 0.00623%.

No description available.

Le travail de cette thèse est à l'interface des dom aines de la recherche opérationnelle et de la micro -électronique. Il traite de l'utilisation des techniques d'optimisation combinatoire pour la DFT (Design For Test) des Circuits Intégrés (CI). Avec la croissance rapide et la complexité des CI actuels, la qualité ainsi que le coût du test sont devenus des paramètres importants dans l'industrie des semi-con ducteurs. Afin de s'assurer du bon fonctionnement du CI, l'étape de test est plus que jamais une étape essentielle et délicate dans le processus de fabrication d'un CI. Pour répondre aux exigences du marché, le test doit être rapide et efficace dans la révélation d'éventuels défauts. Pour cela, il devient incontournable d'appréhender la phase de test dès les étapes de conception du CI. Dans ce contexte, la conception testable plus connue sous l'appellation DFT vise à améliorer la testabilité des CI. Plusieurs problèmes d'optimisation et d'aide à la décision découlent de la micro-électronique. La plupart de ces travaux traitent des problèmes d'optimisation combinatoire pour le placement et routage des circuits. Nos travaux de recherche sont à un niveau de conception plus amont, la DFT en présynthèse au niveau transfert de registres ou RTL (Register Transfer Level). Cette thèse se découpe en trois parties. Dans la première partie nous introduisons les notions de bases de recherche opérationnelle, de conception et de test des CI. La démarche suivie ainsi que les outils de résolution utilisés dans le reste du document sont présentés dans cette partie. Dans la deuxième partie, nous nous intéressons au problème de l'optimisation de l'insertion des chaîne s de scan. A l'heure actuelle, le "scan interne" est une des techniques d'amélioration de testabilité ou de DFT les plus largement adoptées pour les circuits intégrés numériques. Il s'agit de chaîner les éléments mémoires ou bascules du circuit de sorte à former des chaînes de scan qui seront considérées pendant la phase de test comme points de contrôle et d'observation de la logique interne du circuit. L'objectif de notre travail est de développer des algorithmes permettant de générer pour un CI donné et dès le niveau RTL des chaînes de scan optimales en termes de surface, de temps de test et de consommation en puissance, tout en respectant des critères de performance purement fonctionnels. Ce problème a été modélisé comme la recherche de plus courtes chaînes dans un graphe pondéré. Les méthodes de résolution utilisées sont basées sur la recherche de chaînes hamiltoniennes de longueur minimale. Ces travaux ont été réalisés en collaboration avec la start-up DeFacTo Technologies. La troisième partie s'intéresse au problème de partage de blocs BIST (Built In Self Test) pour le test des mémoires. Le problème peut être formulé de la façon suivante : étant données des mémoires de différents types et tailles, ainsi que des règles de partage des colliers en série et en parallèle, il s'agit d'identifier des solutions au problème en associant à chaque mémoire un collier. La solution obtenue doit minimiser à la fois la surface, la consommation en puissance et le temps de test du CI. Pour résoudre ce problème, nous avons conçu un prototype nommé Memory BIST Optimizer (MBO). Il est constitué de deux phases de résolution et d'une phase de validation. La première phase consiste à créer des groupes de compatibilité de mémoires en tenant compte des règles de partage et d'abstraction des technologies utilisées. La deuxième phase utilise les algorithmes génétiques pour l'optimisation multi-objectifs afin d'obtenir un ensemble de solutions non dominées. Enfin, la validation permet de vérifier que la solution fourn ie est valide. De plus, elle affiche l'ensemble des solutions à travers une interface graphique ou textuelle. Cela permet à l'utilisateur de choisir la solution qui lui correspond le mieux. Actuellement, l'outil MBO est intégré dans un flot d'outils a ST-microelectronics pour une utilisation par ses clients.

No description available.

De nos jours la conception des IP (IP: Intellectual Property) peut bénéficier de nouvelles techniques de vérification symbolique: abstraction de donnée et analyse statique formelle. Nous pensons qu'il est nécessaire de séparer clairement le Contrôle des Données avant toute vérification automatique. Nous avons proposé une définition du contrôle qui repose sur l'idée intuitive qu'il a un impact sur le séquencement de données. Autour de cette idée, le travail a consisté à s'appuyer sur la sémantique des opérateurs booléens et proposer une extension qui exprime cette notion deséquencement. Ceci nous a mené à la conclusion que la séparation parfaite du contrôle et des données est illusoire car les calculs dépendent trop de la représentation syntaxique. Pour atteindre notre objectif, nous nous sommes alors basés sur la connaissance fournie par le concepteur: séparation a priori des entrées contrôle et des entrées données. De cela, nous avons proposé un algorithme de slicing pour partitionner le modèle. Une abstraction fut alors obtenue dans le cas où le contrôle est bien indépendant des données. Pour accélérer les simulations, nous avons remplacé le traitement de données, défini au niveau bit par un modèle d'exécution fonctionnel, tout en gardant inchangé la partie contrôle. Ce modèle intègre des aspects temporels qui permet de se greffer sur des outils de model checking. Nous introduisons la notion de significativité support des données intentionnelles dans les modèles IP. La significativité est utilisée pour représenter des dépendances de données booléennes en vue de vérifier formellement et statiquement les lots de données. Nous proposons plusieurs approximations qui mettent en oeuvre cette nouvelle notion.

Le contexte général de cette thèse se situe dans le domaine de la synthèse RTL (Register Transfer Level). Une spécification initiale en termes de transferts de registres décrite dans un langage de haut niveau (VHDL, Verilog) définit l'ordre des opérations. A partir de cette spécification, le système de synthèse RTL génère une description structurelle fonctionnellement équivalente interconnectant des portes de base et des macro blocs de la cible technologique. Le langage de description considéré ici est le langage VHDL standardisé par le groupe IEEE en 1987. Ce choix est justifié par une étude comparative entre différents langages. Les principales caractéristiques du langage VHDL ainsi que les améliorations apportées par la nouvelle norme de 1992 sont évoquées. Dans une seconde partie, les limitations du langage VHDL pour son utilisation en synthèse et le flot de conception à partir d'une spécification RTL sont présentés. Plusieurs modèles VHDL d'éléments simples et de macro blocs sont décrits pour la synthèse. Le flot général de conception utilisant ces macro blocs est analysé et détaillé pour deux cas pratiques: l'utilisation des générateurs XBLOX de Xilinx et ACTgen d'Actel dans le logiciel de synthèse ASYL+. La dernière partie s'attache plus précisément à la modélisation d'éléments de bibliothèques en vue de leur utilisation en synthèse. Un format de bibliothèque, permettant de décrire tout aussi bien des portes simples que des macro blocs, est défini. Le nouveau format de bibliothèque standard VITAL est analysé ainsi que ses perspectives d'utilisation en simulation et en synthèse. La norme LPM qui définit un ensemble d'éléments standards indépendants de la technologie est également présentée. Cette dernière partie a conduit à la définition d'un nouveau flot de synthèse unifié utilisant les macro blocs et à la mise en place de plusieurs optimisations basées sur la notion de dérivation