Este trabalho apresenta um sistema de Síntese de Alto Nível — geração automática de uma descrição estrutural no nível RT a partir de uma descrição comportamental algorítmica [MCF 88] —, abordando as tarefas de compilação para representação interna, transformações comportamentais, escalonamento, alocação, mapeamento e gera.são do controle. Sua principal contribuição esta na fase de transformações comportamentais, através da qual é possível explorar globalmente o paralelismo existente na descried° do sistema digital e, de maneira sistemática, pesquisar o espaço de projeto, ou seja, as possíveis implementações para o sistema digital, identificando a que melhor satisfaz as restrições especificadas pelo projetista. A Linguagem de Descried° de Hardware (HDL) usada no sistema de síntese é VHDL que oferece recursos para se descrever comportamento e estrutura, e se especificar restrições de projeto, alem de ter sido adotada como padrão pela IEEE. Parte-se da descried° algorítmica em VHDL comportamental do sistema digital. Tal descrição é compilada para uma representação interna baseada em grafos: cada bloco básico — seqüência de operações sem desvio — e representado por um Grafo de Fluxo de Dados (GFD); a transferência de controle entre blocos básicos — desvios condicionais e incondicionais — é representada pelo Grafo de Fluxo de Controle (GFC); e as relações de hierarquia — entidade, arquitetura, processos, subprogramas — são representadas pelo Grafo de Entidade (GE). O sistema de transformações é tal que a escolha e a ordem da aplicação das transformações possíveis (agrupa blocos consecutivos, agrupa ramos de if, desenrola laços) sobre um GFC gera uma Arvore — a Arvore de Transformações — cujos nodos folha representam os GFD's iniciais e os nodos internos os GFD's obtidos pela transformação aplicada sobre os seus nodos filhos. Construída a Arvore de Transformações, realiza-se um caminhamento em pós-ordem, determinando-se a melhor implementação possível para cada nodo da Arvore de Transformações. Por melhor implementação entenda-se a que, no mínimo, satisfaça as restrições de tempo ou de recursos especificadas pelo projetista. Para cada implementação, obtida usando-se algoritmos de escalonamento, alocação e mapeamento existentes, calcula-se um custo em fungi° dos recursos — unidades funcionais, registradores, interconexões — e do tempo — passos de controle — necessários implementação. Feito isso, caminha-se em pré-ordem pela árvore de Transformações comparando-se o custo da implementação do nodo pai com os custos de implementação dos seus nodos filhos: se o custo dos nodos filhos a maior que o do nodo pai, este é selecionado e seus nodos filhos não são visitados; caso contrario, a transformações que o gerou é descartada e visita-se os nodos filhos. Os nodos selecionados fardo parte da implementação final. O modelo de hardware utilizado adota a divisão clássica de sistema digital em Parte Operativa e Parte de Controle, como apresentada em [DAV 83]. Na implementação do prot6tipo do sistema de síntese escolheu-se, para o escalonamento e a alocação, o algoritmo Force-directed que possui complexidade linear — 0(n2 ) no pior caso — e tem mostrado bons resultados em comparação com os demais existentes [PAU 89]. Para o mapeamento de registradores adotou-se o algoritmo do programa REAL [KUR 87] também de complexidade linear; o mapeamento de unidades funcionais e interconexões baseia-se em [PAN 87]. 0 controlador a obtido diretamente do GFC final: cada nodo representa um estado e as arestas representam as transições entre estados. 0 protótipo foi aplicado a vários exemplos, relatados na literatura, mostrando resultados comparáveis. Aplicando-se o protótipo sobre exemplos com fluxo de controle mais complexo, verifica-se a eficiência do sistema de transformações na exploração do espaço de projeto. / High Level Synthesis is the automatic generation of a structural description of a circuit at the RT level from a behavioral description at the algorithm level [MCF 88]. In this work, a High Level Synthesis System which deals with the tasks of compilation to internal representation, behavioral transformations, scheduling, allocation, mapping and control generation is presented. Its main contribution is the behavioral transformation process. It makes possible the exploration of the global parallelism in the behavioral description and, systematically, to search the design space in order to find the structure that best fits the resource and timing constraints specified by the designer. The Hardware Description Language (HDL) used in the synthesis system is VHDL, HDL standardized by IEEE, which offers facilities for the behavior description, structure description and for the specification of design constraints. The input to the synthesis system is a behavioral algorithmic VHDL description of the digital system under design. This description is translated to an internal representation based on graphs: each basic block (sequence of operations without branches) is represented by a Data Flow Graph (DFG); the transfer of control between basic blocks (conditional and inconditional branches) is represented by a Control Flow Graph (CFG); the hierarchy of description (entity, architectural body, processes, subprograms) is represented by the Entity Graph (EG). The set of behavioral transformations is such that the selection and sequence of applicable transformations (Merge Consecutive Blocks, Merge If Branches, Unroll Loops, etc.) to a CFG can be represented by a tree, called Transformations Tree. In the Transformations Tree, the leaf nodes represent the initial DFGs and the internal nodes represent the DFGs obtained by the transformations applied on its son nodes. After the Transformation Tree has been generated, a transversal post-order is used to determine the best possible implementation for each node of the Transformations Tree. The best possible implementation is the one that, at least, satisfy the timing and resources constraints specified by the designer. A cost is determined in terms of the timing (control steps) and resources (functional units, registers, interconections, etc.) required by each implementation, which is produced using traditional algorithms for scheduling and allocation. Once the implementation for each node is done, a transversal pre-order is used to compare the implementation cost of a node, with the implementation costs of its son nodes: if the cost of its son nodes is greater, the father node is selected and its son nodes are not visited; otherwise the transformation that produced the father node is discarded, and the son nodes are visited. The selected nodes will be in the final implementation. The hardware model used in the synthesis system adopts the classical division of the digital system in a Data-Path and a Controller, such as presented in [DAV 83]. In the implementation of the synthesis system prototype, the Force-Directed algorithm [PAU 89] was adopted for scheduling and allocation, which has linear complexity — in the worst case 0(n2 ) — and produces good results when compared with other algorithms [PAU 91]. The algorithm of the REAL program [KUR 87] was used for the mapping of registers, which also has linear complexity. The mapping of functional units and interconections uses the ideas from [PAN 87]. The controller is directly obtained from the final GFC: each node represents a state and the transitions between states are represented by the edges. The prototype of the synthesis system, which is implemented in C, on SUN workstations, was applied to various examples of the literature and has showed comparable results. When applied to examples with more complex control flow, the efficiency of the set of behavioral transformations in the design space exploration can be verified.

Este trabalho propõe e avalia uma nova abordagem para projeto de circuitos dedicados utilizando matrizes pré-difundidas. A principal vantagem desta abordagem, denominada Marcela, reside na decomposição lógica do circuito a ser implementado em termos de primitivas disponíveis na matriz escolhida. Aplicando-se tal procedimento, alcança-se grande flexibilidade em termos de posicionamento e roteamento, levando a uma melhor taxa de ocupação. Primeiramente, é feito um levantamento das abordagens para pré-difundidos correntemente encontradas e uma taxonomia baseada nas características mais relevantes é definida. As principais características da metodologia TRANCA são também mostradas. Leiautes gerados com os módulos TRAMO e TRAGO são analisados e algumas modificações na metodologia são sugeridas, visando uma exploração mais eficiente dos dois níveis de metal. As bases para o desenvolvimento da abordagem Marcela são então descritas. A abordagem consiste de uma nova arquitetura para pré-difundidos e uma estratégia específica de ocupação. As principais características da matriz de propósito geral Marcela, primeira a ser definida, são a ausência de canais de roteamento, com as conexões sendo realizadas sobre as células, e a utilização de quatro tipos de células básicas, cada uma dedicada à implementação de uma função lógica primitiva. As células básicas estão organizadas em unidades básicas, as quais são repetidas regularmente para formar a matriz, numa abordagem denominada mar de células. O problema do assinalamento de células e suas particularidades são solucionados utilizando-se uma combinação entre alocação sequencial e técnicas de particionamento. Primeiro, é alocada a mínima superfície da matriz capaz de comportar o circuito em questão, numa fase chamada pré-assinalamento. Na fase de otimização, partições são geradas respeitando a integridade das unidades básicas e trocas de células são realizadas entre os blocos de cada nova partição, em dois passos: trocas individuais, enquanto o bloco de destino não estiver cheio, e trocas de pares. Para o roteamento, foi desenvolvida no CPGCC/UFRGS uma ferramenta específica para ser utilizada em leiautes gerados segundo a metodologia TRANCA. Esta ferramenta, denominada MARTE [JOH 92a][JOH 92b], emprega o algoritmo de Lee básico com algumas modificações, tal como a geração de doglegs para trocas entre trilhas adjacentes. Com a finalidade de validar a abordagem, foram implementados alguns circuitos utilizando a abordagem Marcela e uma abordagem sea-of-gates tradicional. Para circuitos pequenos, tal como um flip-flop D, Marcela produziu uma melhor distribuição de conexões, a qual resulta em aumento da transparência. Porém, a taxa de ocupação encontrada foi menor do que a do circuito projetado com sea-of-gates. Por outro lado, para circuitos de complexidade maior, a área ocupada pode resultar bem menor do que no caso de se usar sea-of-gates, desde que sejam realizadas transformações lógicas apropriadas sobre a descrição equivalente Marcela ou uma matriz conveniente seja escolhida. Exemplos de leiautes desenvolvidos mostram que taxas de ocupação tão altas quanto 75% são atingidas. Finalmente, da observação de circuitos gerados automaticamente, foram tiradas conclusões sobre modificações na arquitetura da matriz e nos algoritmos, de forma a melhorar as taxas de ocupação para qualquer tipo de circuito. / This work proposes and evaluates a new approach for the design of ASICs using prediffused masterslices. The main advantage of this approach, called Marcela, relles on logic decomposition of the circuit to be implemented into the chosen masterslice available primitives. By applying this procedure, a great placement and routing flexibility is achieved, thus leading to a better transistor utilization rate. First, a survey on current prediffused approaches is done and an specific taxonomy is defined based on the main important features encountered. Also the main features of TRANCA methodology are shown. Layouts generated using TRAGO and TRAMO modules are analyzed and some modifications in the methodology are suggested, in order to better exploit both first and second metal layers. Marcela approach development basis are described. The approach consists of a new prediffused architecture and an specific occupation strategy. The main architectural features of the general purpose Marcela masterslice are the absence of routing channels, with the connections running over the cells, and the utilization of four types of basic cells, each of them dedicated to perform one primitive logic function. Basic cells are organized into basic units, which are spread a11 over the masterslice, in a so called sea-of-cells approach. The assignment problem and its peculiarities are solved by using a combination of sequential cell allocation and quadrature partition techniques. But first of all, a minimum masterslice area is allocated in a phase called preassignment. In the optimization phase, partitions are generated respecting basic units integrity and cell interchanges are applied to each new partition, following two steps: individual changes, while the target block is not, full. and pairwise interchange. For the routing problem, an specific tool has been developed at CPGCC/UFRGS for any module generator in which TRANCA methodology is applied. This tool, called MARTE [JOH 92a][JOH 92b], employs a basic Lee algorithm with some modifications as dogleg generation for changes between adjacent tracks. In order to validate the approach, some circuits have been implemented using a traditional sea-of-gates and Marcela approaches. For small circuits, as a D flip-flop, Marcela approach has produced a better wiring distribution, which results in increase of transparency. But the occupation rate was found to be smaller than that of the sea-of-gates approach. On the other hand, for more complex circuits the amount of used area can be smaller than that of sea-of-gates case, since appropriate logic transformations are applied to the Marcela logic equivalent or a well suit masterslice is used. Implemented examples show that utilization rates as high as 0.75 are achieved. Finally, from the observation of automatically generated layouts some modifications in masterslice architecture and in the algorithms are figured out.

Este trabalho trata da aplicação de técnicas de minimização de consumo de potência para blocos digitais para o algoritmo de SAD e o decodificador H.264/AVC Intra-Only. Na descrição de hardware são acrescidas as técnicas de paralelismo e pipeline. Na síntese física e lógica, incluem-se as técnicas de inativação do relógio ( clock gating), múltiplas tensões de threshold, diferentes tecnologias e diferentes tensões de alimentação. A síntese é feita nas ferramentas da CadenceTM com exploração arquitetural e apresenta uma menor energia por operação, quando exigido desempenho equivalente (isoperformance ) para SAD, em baixa frequência, alto paralelismo e, principalmente, com um estágio de pipeline. Além disso, tecnologias CMOS mais avançadas diminuem o consumo de potência dinâmica e, em alguns casos, também diminuem a potência estática por gate equivalente, se utilizadas células High-VT e tensão de alimentação a menor possível. Outro fator a ser destacado é o uso do clock gating que no caso das arquiteturas de SAD, em vez de diminuir, aumenta o consumo de potência dinâmica. Neste trabalho foi realizada a síntese do decodificador Intra-Only. O decodificador com clock gating apresenta um menor consumo de potência, mostrando um caso em que esta técnica é benéfica. Além disso, a utilização de uma tecnologia CMOS 65 nm e, consequentemente, tensão de alimentação menor, levou a uma sensível diminuição no consumo de potência em relação a outros trabalhos similares. / This work presents low-power techniques applications to digital blocks in the SAD algorithm and in the Intra-Only H.264/AVC decoder. In the hardware description, we add parallelism and pipeline techniques. In the logical and physical synthesis exploration, includes the clock gating, multiple threshold voltage, different technologies and multiple supply voltage. The synthesis are done in the CadenceTM tools and show a smaller energy per operation in isoperformance for SAD at low frequency, high parallelism and, mainly, with one pipeline stage. In addition to that, more advanced CMOS technologies decrease the dynamic power consumption and, also, decrease the static power for equivalent gates, if using High-VT cells and lowest possible power supply. Another factor is the clock gating use that in the SAD architecture, instead of decreasing, increases the dynamic power consumption. In this work the design of an Intra-Only H.264/AVC Decoder was performed. This design with clock gating presents lower power consumption, showing a case in which this technique is beneficial in terms of dynamic power. Besides that, the 65 nm CMOS technology uses a lower power supply, resulting in lower power consumption in comparison to other related works.

A compressão de vídeo é essencial para aplicações que manipulam vídeos digitais, em função da enorme quantidade de informação necessária para representar um vídeo sem nenhum tipo de compressão. Esta tese apresenta o desenvolvimento de soluções arquiteturais dedicadas e de alto desempenho para a compressão de vídeos, com foco no padrão H.264/AVC. O padrão H.264/AVC é o mais novo padrão de compressão de vídeo da ITU-T e da ISO e atinge as mais elevadas taxas de compressão dentre todos os padrões de codificação de vídeo existentes. Este padrão também possui a maior complexidade computacional dentre os padrões atuais. Esta tese apresenta soluções arquiteturais para os módulos da estimação de movimento, da compensação de movimento, das transformadas diretas e inversas e da quantização direta e inversa. Inicialmente, são apresentados alguns conceitos básicos de compressão de vídeo e uma introdução ao padrão H.264/AVC, para embasar as explicações das soluções arquiteturais desenvolvidas. Então, as arquiteturas desenvolvidas para os módulos das transformadas diretas e inversas, da quantização direta e inversa, da estimação de movimento e da compensação de movimento são apresentadas. Todas as arquiteturas desenvolvidas foram descritas em VHDL e foram mapeadas para FPGAs Virtex-II Pro da Xilinx. Alguns dos módulos foram, também, sintetizados para standard-cells. Os resultados obtidos através da síntese destas arquiteturas são apresentados e discutidos. Para todos os casos, os resultados de síntese indicaram que as arquiteturas desenvolvidas estão aptas para atender as demandas de codecs H.264/AVC direcionados para vídeos de alta resolução. / Video coding is essential for applications based in digital videos, given the enormous amount of bits which are required to represent a video sequence without compression. This thesis presents the design of dedicated and high performance architectures for video compression, focusing in the H.264/AVC standard. The H.264/AVC standard is the latest ITU-T and ISO standard for video compression and it reaches the highest compression rates amongst all the current video coding standards. This standard has also the highest computational complexity among all of them. This thesis presents architectural solutions for the modules of motion estimation, motion compensation, forward and inverse transforms and forward and inverse quantization. Some concepts of video compression and an introduction to the H.264/AVC standard are presented and they serve as basis for the architectural developments. Then, the designed architectures for forward and inverse transforms, forward and inverse quantization, motion estimation and motion compensation are presented. All designed architectures were described in VHDL and they were mapped to Xilinx Virtex-II Pro FPGAs. Some modules were also synthesized into standard-cells. The synthesis results are presented and discussed. For all cases, the synthesis results indicated that the architectures developed in this work are able to meet the demands of H.264/AVC codecs targeting high resolution videos.

Este trabalho visa explorar técnicas de projeto de células que possibilitem a minimização dos efeitos da variabilidade de processo sobre o comportamento elétrico dos circuitos integrados. Para este trabalho foram abordados aspectos de regularidade, principalmente na camada de polisilício. A técnica de folding foi explorada em conjunto com a regularidade como possível metodologia de projeto voltada para a minimização dos efeitos da variabilidade de processo. Leiautes de portas lógicas complexas e básicas foram criadas utilizando tecnologia em 65nm. Os netlists dos leiautes extraídos foram simulados utilizando modelos que refletiam os efeitos da variabilidade sobre os parâmetros tecnológicos mais afetados pela variabilidade de processo. Os parâmetros selecionados para este experimento foram a largura (W) e comprimento (L) do canal do transistor, espessura do óxido de porta (Tox) e a mobilidade (μ0) das cargas. Os dados referentes ao pior caso envolvendo atraso e potência consumida de cada porta foram utilizados como métricas de comparação. Os resultados encontrados demonstram que a utilização da técnica de folding juntamente com aspectos de regularidade tornaram os experimentos menos sensíveis às variações do processos de manufatura de circuitos integrados. Essas reduções de sensibilidade chegaram em algumas situações à 33.22% para as portas básicas e de 28.96% para as portas complexas. A adição de folding e regularidade da camada de polisilício, trazem desvantagens significativas em área e potência consumida de cada porta. Pelos experimentos realizados é possível verificar aumento superior a 100% em área de algumas portas e de até 20.54% de aumento em potência. A união destas duas técnicas pode ser utilizada para tornar, por exemplo, o caminho crítico de um circuito integrado mais robusto quanto as variações de temporização e de potência. / This paper aims to explore for design techniques that allow the minimization of the effects of process variability on the electrical behavior of integrated circuits. To this work were discussed aspects of regularity, especially in poly-silicon layer. The technique of it folding was explored in conjunction with the regularity as possible design methodology aimed to minimizing the effects of process variability. Complex and basic layouts logic gates were built using 65nm technology. The it netlists extracted from layouts of the gates were simulated using models that reflected the effects of variability on the main technological parameters such as W, L, Tx, mu0 of the charges. The worst delay of each port and power consumption parameters were used for comparison in this work. The results show that using the it folding with regularity aspects of the experiments turns the layout gates less sensitive to process variations. These sensitivity reductions reached in some situations to 33.22 % for the basic gates and 28.96 % for the complex gates created. This techniques brings significant disadvantages in size and power consumption. For the experiments you can check increase of over 100% in area and up than 20,54% increase in power. These techniques should be used with discretion, especially on projects where there are area or consumption restrictions.

This thesis investigates architectures for multiplying elements in Galois rings of the size 4^m, where m is an integer. The main question is whether known architectures for multiplying in Galois fields can be used for Galois rings also, with small modifications, and the answer to that question is that they can. Different representations for elements in Galois rings are also explored, and the performance of multipliers for the different representations is investigated.

The development cost of any civil infrastructure is very high; during its life span, the civil structure undergoes a lot of physical loads and environmental effects which damage the structure. Failing to identify this damage at an early stage may result in severe property loss and may become a potential threat to people and the environment. Thus, there is a need to develop effective damage detection techniques to ensure the safety and integrity of the structure. One of the Structural Health Monitoring methods to evaluate a structure is by using statistical analysis. In this study, a civil structure measuring 8 feet in length, 3 feet in diameter, embedded with thermocouple sensors at 4 different levels is analyzed under controlled and variable conditions. With the help of statistical analysis, possible damage to the structure was analyzed. The analysis could detect the structural defects at various levels of the structure.

No description available.

En esta tesis se han investigado los algoritmos de decodificación para códigos de comprobación de paridad de baja densidad (LDPC) y las arquitecturas para la implementación hardware de éstos. El trabajo realizado se centra en los algoritmos del tipo de intercambio de mensajes para códigos estructurados los cuales se incluyen en varios estándares de comunicaciones. Inicialmente se han evaluado las prestaciones de los algoritmos existentes Sum-product, Min-Sum y las principales variantes de este último (Min-Sum con escalado y Min-Sum con offset). Además, se ha realizado un análisis de precisión finita utilizando los códigos LDPC de los estándares IEEE 802.3an, IEEE 802.11n e IEEE 802.16e. Posteriormente se han propuesto dos algoritmos basados en el algoritmo Min-Sum, denominados Min-Sum entero y Min-Sum modificado con corrección. La complejidad de éstos es menor que las de los algoritmos estudiados anteriormente y además permiten una implementación hardware eficiente. Por otra parte, se han estudiado diferentes métodos de actualización de los algoritmos de decodificación: por inundación, por capas horizontales (layered) y por capas verticales (shuffled), y se ha propuesto un nuevo método por capas verticales entrelazadas (x-shuffled) que consigue mejorar la tasa de decodificación. Tras el estudio algorítmico, se han realizado implementaciones hardwar} con diferentes arquitecturas para los algoritmos y métodos de actualización evaluados y propuestos. En la mayoría de algoritmos implementados se requiere el cálculo de los dos primeros mínimos, por lo que inicialmente se realiza un estudio de las arquitecturas hardware para realizar este cálculo y se ha propuesto una nueva arquitectura de menor complejidad. En segundo lugar se ha realizado una comparación de las prestaciones hardware de los diferentes algoritmos con las arquitecturas de referencia: completamente paralela y parcialmente paralela basada en memorias. También se han propuesto dos arquitecturas enfocadas a la alta velocidad, la cuales se implementan con el algoritmo Sum-Product. La primera es una modificación de la arquitectura Sliced Message-Passing que consigue una reducción en el área de la implementación, y la segunda, es una arquitectura específica para el método de actualización propuesto x-shuffled que alcanza tasas de decodificación muy altas. Finalmente, se han implementado los algoritmos propuestos con la arquitectura layered obteniendo implementaciones hardware eficientes con baja área y muy alta tasa de decodificación. Estas últimas consiguen un ratio entre tasa de decodificación y área mejor que las implementaciones existentes en la literatura. Por último, se ha evaluado el comportamiento de los algoritmos de decodificación estudiados en la zona de baja tasa de error, donde las prestaciones se suelen degradar debido a la aparición de un suelo de error. Para ello se ha implementado un simulador hardware usando dispositivos FPGA. La tasa de datos alcanzada con el simulador hardware diseñado es superior a la de otros simuladores documentados en la literatura. En la zona de baja tasa de error el algoritmo propuesto Min-Sum modificado con corrección presenta un mejor comportamiento que el resto de algoritmos evaluados, consiguiendo bajar el suelo de error varios órdenes de magnitud. / Angarita Preciado, FE. (2013). Diseño de decodificadores de altas prestaciones para código LDPC [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/31646 / TESIS

Given a logic circuit that fails a test, diagnosis is the process of narrowing down the possible locations of the defects. Diagnosis to locate defects in VLSI circuits has become very important during the yield ramp up process, especially for 90 nm and below technologies where physical failure analysis machines become less successful due to reduced defect visibility by the smaller feature size and larger leakage currents. Successful defect isolation relies heavily on the guidance from fault diagnosis and will depend even more for the future technologies. To assist a designer or a failure analysis engineer, the diagnosis tool tries to identify the possible locations of the failure effectively and quickly. While many defects reside in the logic part of a chip, defects in scan chains have become more and more common recently as typically 30%-50% logic gates impact the operation of scan chains in a scan design. Logic diagnosis and scan chain diagnosis are the two main fields of diagnosis research. The quality of diagnosis directly impacts the time-to-market and the total product cost. Volume diagnosis with statistical learning is important to discover systematic defects. An accurate diagnosis tool is required to diagnose large numbers of failing devices to aid statistical yield learning. In this work, we propose techniques to improve diagnosis accuracy and resolution, techniques to improve run-time performance. We consider the problem of determining the location of defects in scan chains and logic. We investigate a method to improve the diagnosability of production compressed test patterns for multiple scan chain failures. Then a method to generate special diagnostic patterns for scan chain failures was proposed. The method tries to generate a complete test pattern set to pinpoint the exact faulty scan cell when flush tests tell which scan chain is faulty. Next we studied the problem of diagnosis of multiple faults in the logic of circuits. First we propose a method to diagnose multiple practical physical defects using simple logic fault models. At last we propose a method based on fault-tuple equivalence trees to further improve diagnosis quality.