Abstract Hardware trojans are malicious circuits which compromise the functionality and security of an integrated circuit (IC). These circuits are manufactured directly into the silicon and cannot be fixed by security patches like software. The solution would require a costly product recall by replacing the IC and hence, early detection in the design process is essential. Hardware detection at best provides statistically based solutions with many false positives and false negatives. These detection methods require more thorough explainable analysis to filter out false indicators. Existing explainability methods developed for general domains like image classification do not always provide the actionable insights hardware engineers need. A question remains: how do domain-aware property analysis, model-agnostic case-based reasoning, and model-agnostic feature attribution techniques compare for hardware security applications? This work compares three categories of explainability for gate-level hardware trojan detection on the Trust-Hub benchmark dataset: (1) domain-aware property-based analysis of 31 circuit-specific features derived from gate fanin patterns, flip-flop distances, and primary Input/Output (I/O) connectivity; (2) model-agnostic case-based reasoning using k-nearest neighbors for precedent-based explanations; and (3) model-agnostic feature attribution methods (Local Interpretable Model-agnostic Explanations (LIME), SHapley Additive exPlanations (SHAP), gradient) that provide generic importance scores without circuit-level context. The findings show that different explainability approaches offer distinct advantages for hardware security practitioners. The domain-aware property-based method analyzes 31 circuit properties. Detection decisions are explained through familiar concepts like “high fanin complexity near outputs indicates potential trojan triggers.” Case-based reasoning (k-nearest neighbors) achieves 96.51% correspondence between predictions and training exemplars. In contrast, LIME and SHAP show only moderate per-gate agreement (Spearman $$\varvec{\rho = 0.30}$$ mean over $$\varvec{n = 11{,}392}$$ gates, 95% bootstrap CI $$\varvec{[0.29, 0.31]}$$ ; global concatenated $$\varvec{\rho = 0.31}$$ , $$\varvec{p \ll 10}^{\varvec{-300}}$$ ), and yield generic feature importance scores that lack circuit-level context for validation or remediation planning. Detection performance using eXtreme Gradient Boosting (XGBoost) classification with optimized threshold achieves 48.08% precision and 69.44% recall on 11,392 held-out test gates (F1 = 0.568, Matthews Correlation Coefficient (MCC) = 0.575, area under the precision-recall curve (AUPRC) = 0.637) at the optimized threshold of 0.940. This represents a 4.25-fold precision improvement over a support vector machine (SVM) baseline reimplemented under identical experimental conditions (11.33% precision, 70.83% recall, F1 = 0.195 at threshold 0.050) with a 7.4-fold reduction in false-positive density (4.74 vs. 35.0 FP per 1,000 gates). Random Forest achieves comparable F1 (0.555, 58.46% precision, 52.78% recall) with half the false-positive density of XGBoost (2.37 vs. 4.74 FP per 1,000 gates), confirming that the explainable AI (XAI) findings generalize across classifier choices. Additionally, gradient-based feature attribution (Simonyan et al., 2013), with a speedup factor of 7 over SHAP, yields the same model-agnostic feature weights as SHAP and LIME, confirming that computational efficiency alone cannot substitute for domain-aware interpretability. This work provides empirical evidence comparing domain-aware property analysis, model-agnostic case-based reasoning, and model-agnostic feature attribution techniques for hardware security applications. The results show that property-based and case-based approaches offer complementary advantages: domain alignment and precedent-based interpretability, respectively, compared to generic feature rankings. These findings have implications for XAI deployment across domains where practitioners must validate and act on Machine Learning (ML) predictions.

Integrated Circuits (IC) are typically designed based on tradeoffs among performance, power and cost. Designers perceive electromigration as a failure mechanism or as a sign-off rule rather than as an additional tradeoff parameter. This paper describes a design methodology to perform tradeoffs driven by lifetime concerns due to electromigration.

The integration of reusable IP blocks/cores is a common process in system-on-chip design and involves manually comparing/mapping IP specifications against system requirements. The informal nature of specification limits its automatic analysis. Existing techniques fail to utilize the underlying conceptual information embedded in specifications. In this paper, we present a methodology for specification analysis, which involves concept mining of specifications to generate domain ontologies. We employ a semi-supervised expert system with semantic analysis capability to create a collaborative framework for cumulative knowledge acquisition. Our system then uses the generated ontologies to perform component retrieval, drop-in-replacement analysis and design vs. test-plan comparisons. We demonstrate our approach by evaluating several IP specifications.

Semiconductor companies often use 3rd party IPs in order to improve their design productivity. In practice, there are risks involved in using a 3rd party IP as bugs may creep in due to versioning issues, poor documentation, and mismatches between specification and RTL. As a result of this, 3rd party IP specification and RTL must be carefully evaluated. Our methodology addresses this issue, which cross-correlates specification and RTL to discover these discrepancies. The key innovative ideas in our approach are to use prior and trusted experience about designs, which include their specs and RTL code. Also, we have captured this trusted experience into two knowledge bases (KB), Spec-KB and RTL-KB. Finally, knowledge base rules are used to cross-correlate the RTL blocks to the specs. We have tested our approach by analyzing several 3rd party IPs. We have defined metrics for specification coverage and RTL identification coverage to quantify our results.

Hardware lint tools based on static analysis techniques only check for structural, coding and consistency problems in RTL code. They have the limitation that they do not perform behavioral analysis and have a predefined rule-base that is not enhanced by users to capture human expertise. We present RTL-CLIPS, an RTL simulation environment based on CLIPS, an open-source expert system shell. In our approach, we do a semantically equivalent translation of RTL code into CLIPS facts. The simulator can be used by an heuristic rule-base to perform dynamic analysis of RTL code. Our method can better approximate design behavior by augmenting the pattern-matching capability of the CLIPS expert system with an environment for RTL simulation. We demonstrate our approach by analyzing ITC99 benchmark circuits. We discuss how our approach supports the reverse engineering of design behavior from RTL code.

In a component based engineering approach, a system can be envisioned as an assembly of reusable and independently developed components. In order to produce automated tools to support the selection and assembly of components, precise selection and retrieval strategies based on product specifications are needed. Conventional approaches use keyword based models for automatically retrieving specification documents that match a set of requirements. These approaches typically fail to mine relationships and spotlight excessively on injective matching. In this paper, we propose a Neuro-fuzzy Concept based Inference System (NEFCIS) which is a novel hybrid expert system approach targeted to extract concepts and retrieve relevant information using the excerpted concepts rather than only keywords. By infusing fuzzy logic into our model, we can process the queries with greater precision and produce deeper knowledge inferences. We describe the basic principles of the proposed methodology and illustrate it with example scenarios.

The number of Soft-IP vendors and designsbecoming available on the global market is growing at aphenomenal rate. The current practice of evaluating Soft IPsusing their specification is a time consuming manual process. A specification document is primarily written in English, which serves as a common language for internal product development teams as well as customers. Designers have a preference for writing specifications in an informal natural language using text and notations, including diagrams, charts and tables. The lack of formality of specification documents is a limiting factor intheir analysis. The current state-of-the-art in hardware design lacks any specification analysis technique. In this paper, we present a knowledge-guided methodology for specification analysis that can automatically analyze specification documents. Our approach avoids formal specification. Instead we rely on domain-based ontologies to capture design behavior. We tested our approach by analyzing floating point specification from several third party IP vendors. We define spec coverage and requirement coverage metrics to quantify our results.

Hardware Trojan attack in the form of malicious modification of a design has emerged as a major security threat. Sidechannel analysis has been investigated as an alternative to conventional logic testing to detect the presence of hardware Trojans. However, these techniques suffer from decreased sensitivity toward small Trojans, especially because of the large process variations present in modern nanometer technologies. In this paper, we propose a novel noninvasive, multiple-parameter side-channel analysisbased Trojan detection approach. We use the intrinsic relationship between dynamic current and maximum operating frequency of a circuit to isolate the effect of a Trojan circuit from process noise. We propose a vector generation approach and several design/test techniques to improve the detection sensitivity. Simulation results with two large circuits, a 32-bit integer execution unit (IEU) and a 128-bit advanced encryption standard (AES) cipher, show a detection resolution of 1.12 percent amidst ±20 percent parameter variations. The approach is also validated with experimental results. Finally, the use of a combined side-channel analysis and logic testing approach is shown to provide high overall detection coverage for hardware Trojan circuits of varying types and sizes.

Decimal arithmetic has received considerable attention recently due to its suitability for many financial and commercial applications. In particular, numerous algorithms have been recently proposed for decimal multiplication. A major approach to decimal multiplication shaped by these proposals is based on performing the decimal digit-by-digit multiplication in binary, converting the binary partial product back to decimal, and then adding the decimal partial products as appropriate to form the final product in decimal. With this approach, the efficiency of binary-to-BCD partial product conversion is critical for the efficiency of the overall multiplication process. A recently proposed algorithm for this conversion is based on splitting the binary partial product into two parts (i.e., two groups of bits), and then computing the contributions of the two parts to the partial BCD result in parallel. This paper proposes two new algorithms (Three-Four split and Four-Three split) based on this principle. We present our proposed architectures that implement these algorithms and compare them to existing algorithms. The synthesis results show that the Three-Four split algorithm runs 15%faster and occupies 26.1%less area than the best performing equivalent circuit found in the literature. Furthermore, the Four-Three split algorithm occupies 37.5% less area than the state of the art equivalent circuit.

Aggressive technology scaling has resulted in stability reduction for classic SRAM designs. This is especially problematic for large integrated circuits. The stability of SRAM cells can be affected by noise during a read operation and by radiation during the standby mode. In this paper, we present an approach to address the gradual stability reduction in SRAM designs. We present an SRAM design tradeoffs approach to improve the characteristics of SRAM by modulating the transistor sizing ratio, β. We test our approach on various SRAM designs in 32nm technology. We optimize the SRAM designs with β for various constraints in power consumption, performance, radiation tolerance and data stability. We discuss different design trends produced by the extensive approach analysis.

This paper presents a novel SRAM design for nanoscale CMOS. The new design addresses the problem of low radiation tolerance and high instability for SRAM memories at feature size of 32 nm. The novelty of our approach originates from the synergetic functional component separation, where each component serves its unique operational function and has minimal effect on performance of others. The design consists of three different components: the first component is used to store the data, the second one is designed to protect the data at the most vulnerable state and last component serves to extract the data from the SRAM cell. We performed comparative analysis of our design against conventional radiation-tolerant designs in terms of power consumption, level of radiation tolerance, performance, area and stability. The benefits of our new design (high radiation tolerance, high stability, fast performance) were confirmed by extensive simulations in different 32 nm technology environments (low power, high performance, bulk).

Hardware Trust is an emerging problem in semiconductor integrated circuit (IC) security due to widespread outsourcing and the stealthy nature of hardware Trojans. Conventional post-manufacturing testing, test generation algorithms and test coverage metrics cannot be readily extended to hardware Trojan detection. As a result there is a need to develop approaches that will ensure trusted in-field operation of ICs, and more generally trust in computing. We present a distributed software scheduling prototype, TADS (Trojan Aware Distributed Scheduling), to achieve a Trojan-activation tolerant trustworthy computing system in a multi-core processor potentially containing hardware Trojans. TADS is designed to be transparent to applications and can run on general purpose multicore PEs without modifications to the operating system or underlying hardware. TADS can, with high confidence, continue to correctly execute its specified queue of job subtasks in the presence of hardware Trojans in the multi-core PEs while learning the individual trustworthiness of the individual PEs. Specially crafted self-checking subtasks called bounty hunters are introduced to accelerate PE trust learning. Also, by learning and maintaining individual PE trustworthiness, the scheduler is able to achieve Trojan containment by scheduling subsequent job subtasks to PEs with high learned trust.

RFID tags will supplant barcodes for product identification in the supply chain. The capability of a tag to be read without a line of sight is its principal benefit, but compromises the privacy of the tag owner. Public key cryptography can restore this privacy. Because of the extreme economic constraints of the application, die area and power consumption for cryptographic functions must be minimized. Elliptic curve processors efficiently provide the cryptographic capability needed for RFID. This paper proposes efficient architectures for elliptic curve processors in GF(2m). One design requires six m-bit registers and six Galois field multiply operations per key bit. The other design requires five m-bit registers and seven Galois field multiply operations per key bit. These processors require a small number of circuit elements and clock cycles while providing protection from simple side-channel attacks. Synthesis results are presented for power, area, and delay in 250, 130 and 90 nm technologies. Compared with prior designs from the literature, the proposed processors require less area and energy. For the B-163 curve, with bit-serial multiplier, the first proposed design synthesized in an IBM low-power 130 nm technology requires an area of 9613 gate equivalents, 163,355 cycles and 4.14 ¿J for an elliptic curve point multiplication. The other proposed design requires 8756 gate equivalents, 190,570 cycles and 4.19 ¿J.

There has been ongoing debate regarding the use of voltage overscaling along with error resilience techniques for ultra low power operation of scaled CMOS logic. The issue is whether to build enough design margin into future electronic systems so that errors do not impact the Quality of Service of the end application or to allow errors to occur and correct them using error tolerance mechanisms. Specific signal processing algorithms have been shown to be inherently tolerant to errors. However, large general purpose processors experience virtually zero errors under supply voltage scaling up to a certain scaling level and then exhibit “massive errors” or “complete breakdown”. The problem is made worse by the fact that low power design methodologies force devices to be sized in such a way as to make a large number of circuit paths “critical”. Under all of the above constraints, what is the best way to build low power systems of the future using deeply scaled CMOS technologies? Is the use of voltage overscaling along with error resilience techniques realistic? Can we allow errors to occur and compensate for them with high confidence? Under what conditions will design guardbanding be absolutely necessary? If we do let errors occur periodically, will customers buy the associated products and is there a marketplace for such error-resilient ICs?

A new SRAM cell model, SRAMT, is presented providing a scalable solution to soft error for various energy levels of protection with minimal power consumption and write time penalties. Our model is based on a classic 6 transistor inner core SRAM cell and an outer core consisting of enhanced tri-state inverters. The outer core will absorb a particle strike at a sensitive node of the SRAM cell without a major impact on write time performance or area overhead. The model provides an on-demand protection due to the fact that the outer core can be shut off during non-essential operating mode. The on-demand aspect of the design provides a much more favorable power consumption overhead compared to the existing hardening technique. The gains in power consumption overhead reduction increase as we scale down the process technology from 90 nm to 32 nm. We simulated extensively our model and provided results for various energy levels of soft error protection. We also compared our method to the standard hardening technique in terms of layout area, performance and power consumption overhead for for 90 nm, 65 nm, 45 nm and 32 nm process technologies.

There have been serious concerns recently about the security of microchips from hardware trojan horse insertion during manufacturing. This issue has been raised recently due to outsourcing of the chip manufacturing processes to reduce cost. This is an important consideration especially in critical applications such as avionics, communications, military, industrial and so on. A trojan is inserted into a main circuit at manufacturing and is mostly inactive unless it is triggered by a rare value or time event; then it produces a payload error in the circuit, potentially catastrophic. Because of its nature, a trojan may not be easily detected by functional or ATPG testing. The problem of trojan detection has been addressed only recently in very few works. Our work analyzes and formulates the trojan detection problem based on a frequency analysis under rare trigger values and provides procedures to generate input trigger vectors and trojan test vectors to detect trojan effects. We also provide experimental results.

This paper presents a new radix-4 multiplexer-based array multiplier, based on a multiplication scheme shown in a previous work, where 4-to-1 multiplexers are used for the computation of partial products. In the proposed design, the rows of the array are reduced to the half, compared to the initial multiplexer-based scheme, as two bits from both operands are processed at each step. The proposed scheme is compared to the Modified-Booth array multiplier and to the initial multiplexer-based array scheme. The compared designs are coded in VHDL and synthesized using the TSMC 0.13¼m technology library. The synthesis results of critical time and area show 11-22% improvement in critical time delay compared to the Modified-Booth array, in the expense of an area overhead of 3.8-16%. Compared to the initial multiplexer-based scheme, there is a significant improvement in terms of area and critical time.

Semantic scene classification, robotic state recognition, and many other real-world applications involve multi-label classification with imbalanced data. In this paper, we address these problems by using an enrichment process in neural net training. The enrichment process can manage the imbalanced data and train the neural net with high classification accuracy. Experimental results on a robotic arm controller show that our method has better generalization performance than traditional neural net training in solving the multi-label and imbalanced data problems.

There have been many solutions to create a soft error immune SRAM cell. These solutions can be broken down into three categories: a) hardening, b) recovery, c) protection. Hardening techniques insert circuitry in an SRAM cell possibly duplicating the number of transistors. Recovery techniques insert current monitors in SRAMs to detect SEUs and they employ error correcting codes or redundancy to mitigate these effects. These techniques do not scale very well. Protection methods use capacitors in SRAM cells to absorb the excessive charge. Although they provide sufficient protection, they affect adversely the write time.

In this paper we present an efficient design technique for implementing the elliptic curve cryptographic (ECC) scheme in FPGAs. Our technique is based on a novel and efficient implementation of modular multiplication which is the core operation of ECC. To implement large bit-length multiplications we used a novel partitioning and pipeline folding scheme to fit at least 256-bit modular multiplications on a single Virtex-4 FPGA. Comparisons to several other schemes are presented.

In this paper, we present an analysis methodology to compute circuit node sensitivity due to charged particle induced delay (timing) errors, soft delay errors (SDE). We define node sensitivity metric and describe a step by step procedure to compute node sensitivity. We use mixed-mode simulations to extract accurate current pulses for the characterization of SDE. A technique for logic cell library characterization for SDE is described. Our approach is orders of magnitude faster than using Spice based analysis and its accuracy is close to Spice. Using our approach, we provide distribution of nodes sensitivity for various ISCAS85 circuits and two adders. Such analysis is important to employ node hardening techniques on selected nodes to increase the reliability of CMOS circuits. We use two test circuits to apply a node hardening technique on the highly sensitive nodes which were determined by our approach. Results are provided for the reduction of the circuit sensitivity

A dynamic coarse-grained reconfigurable architecture which targets computationally intensive applications like multimedia and wireless applications is presented. Fundamental features of the architecture are an interconnection matrix, switch buffers, functional units, and a controller. Important aspects of the architecture is dynamic datapath reconfiguration over each control step of the application. Simulations of several classes of applications with results are also presented. Results of Xilinx Virtex 4 Implementations are provided

High secure cryptographic systems require large bit-length encryption keys which presents a challenge to their efficient hardware implementation especially in embedded devices. Modular multiplication is the core operation in well known cryptosystems like RSA and elliptic curve (ECC). Therefore, it is important to employ efficient modular multiplications techniques to improve the overall performance of the cryptographic system. We present a modular multiplier based on the ordinary Montgomery's multiplication algorithm and a new array multiplication scheme to perform the multiplication. The new modular multiplier is scalable and can be used for large bit-lengths. We also implement the modular multiplier into the Virtex4 FPGA devices and we show that our technique has better performance when compared with other schemes. To implement large bit-length multiplications we used a novel partitioning and pipeline folding scheme to fit at least 512-bit modular multiplications on a single FPGA.

This paper presents a built-in test method targeting interconnect defects using I/sub DDT/ testing, delay testing, and boundary scan. It was learned that I/sub DDT/ testing is an effective way to detect open and short defects. Boundary scan can provide accessibility to internal buses inside a chip. A statistical analysis method eases the uncertain factors due to process variations and power fluctuation. This paper also includes the experimental data using the proposed techniques to detect shorts, opens, or the other non-stuck-at fault type defects.

We propose a new built-in current sensor (BICS) to detect single event upsets (SEUs) in SRAM. The BICS is designed and validated for 100 nm process technology. The BICS reliability analysis is provided for process, voltage and temperature variations, and power supply noise. The BICS detects various shapes of current pulses generated due to particle strike. The BICS power consumption and area overhead are also provided. The BICS is found to be very reliable for process, voltage and temperature variations and under stringent noise conditions.

Mutual information-based 3D image Registration algorithm is shown to be an accurate, robust and more general registration method for medical image processing. However, its potential application in clinic is jeopardized by its high computational costs. Like many other 3D imaging algorithms, 3D registration needs to process vast amount of image data. The intrinsic computing characteristics of the mutual information-based registration algorithm make it even more difficult to manage and cache the input data. In this paper, we introduce our FPGA-based computing platform and detail its application in accelerating the mutual information-based 3D image registration. This platform is designed to accelerate a series of 3D medical imaging algorithms dominated by local operations. It is a System-on-Chip (SoC) architecture with an intelligent data caching system for efficient data fetching and buffering. A reconfigurable multi-pipeline execution unit in the platform is designed to perform high-speed parallel computation. This unit can be customized according to different algorithm requirements to achieve high performance. The simulation results for accelerating the mutual information based registration with our platform show that a speed-up of about 30 can be achieved when compared to a single-CPU computer. Moreover, the platform can be easily reconfigured to accelerate other 3D medical imaging algorithms.

In this paper, the authors introduced an approach for single-word multiple-bit upsets (SMU) correction in SRAM. This approach uses the combination of built in current sensor (BICS) and Hamming single error correction/double error detection (SEC/DED) codes. The BICS is used with memory columns for online detection of upsets. When the upset is detected by the BICS, an immediate error correction is performed by the ECC. If ECC gives flag for uncorrectable error i.e. double or more errors in single word, then information from BICS is used to invert the data read from columns flagged by the BICS.

In this paper, we introduce an approach for computing soft error susceptibility of nodes in large CMOS circuits at the transistor level. The node sensitivity depends on the electrical, logic, and timing masking. An efficient technique is developed to compute the electrical masking of nodes using characterization tables and inverse pulse propagation. We generated these tables for every logic cell of the library using Spice simulations for a 100 nm process technology. An additional technique to compute the logic masking of the transistor nodes using an automatic test pattern generation tool is described. Our results show that our approach has Spice like accuracy but it is several orders of magnitude faster than Spice. This approach can be used to analyze the vulnerability of circuits to single event upsets at the chip level. Results are provided for ISCAS85 benchmark circuits

This paper describes a self test program design technique for embedded DSP cores. The method requires minimal knowledge of the core's internals and minimal insertion of external LFSR hardware, without scan insertions. The test program consists of a small set of instructions which operate iteratively on pseudorandom data generated by the LFSRs to fully test the DSP core components. The method uses instruction-based test metrics and a program template as a blueprint to generate the test program. The self test scheme has been successfully applied on an industrial-strength DSP core and the results compare favorably to other methods using ATPG and pseudorandom BIST.

We present a new decompression architecture suitable for embedded cores in SoCs which focuses on improving the download time by avoiding higher internal-to-ATE clock ratios and by exploiting hardware parallelism. The bounded Huffman compression facilitates decompression hardware tradeoffs. Our technique is scalable in that the downloadable RAM-based decode table and accommodates for different SoC cores with different characteristics such as the number of scan chains and test set data distributions.

This paper deals with the reconfigurable SoC (system-on-chip) architecture and a 3D caching scheme targeted to Virtex II Pro FPGAs, to accelerate a broad range of 3D medical imaging algorithms. To achieve high computational bandwidth, architectural parallelisms are exploited at three different levels: brick operation cycle, multiple parallel data-stream processing and deep pipeline architecture for data-stream processing.

Single event upsets (SEUs) are due to high energetic particle strike at sensitive nodes of CMOS combinational circuits. In this paper, we introduce a type of soft errors which manifests as soft delay. The soft delay is temporary delay in CMOS combinational circuits due to high energetic particle strike. We describe soft delay model which enables us to examine delay in CMOS combinational circuits due to particle strike. As technology scales down, the delay due to particle strike increases, and other factors such as V/sub dd/ scaling, fanout and transistor strength also contribute to increase the soft delay in CMOS combinational circuits.

In this paper we present a new test data compression technique and an associated decompression scheme for testing VLSI chips. Our method is based on our novel use of the much utilized, in software, LZW, particularly LZ77 algorithm. We adapt LZ77 to accommodate bit strings rather than character sets. Moreover, we exploit the large presence of don't cares in the uncompressed test sets that we generated using commercial ATPG tools. Our decompression scheme makes effective use of the on chip boundary scan during decompression and then feeding the internal multiple scan chains for testing. The hardware overhead cost for this scheme is minimal. Experimental results are provided.

In this paper, we present an accurate delay-estimation algorithm at the register-transfer level. We study three important sources of false paths in register-transfer-level (RTL) structures, i.e., 1) resource binding; 2) interdependent conditions; and 3) datapath-controller path mismatching. The existence and creation of such paths and their effects in delay analysis are discussed. We show that in a RTL datapath structure the accuracy of the delay estimators is affected by the existence of false paths. Specifically, the accuracy drops significantly for structures synthesized from condition-dominated behaviors. We propose a mechanism to efficiently avoid false paths in delay analysis. This is achieved by introducing the propagation delay graph (PDG), whose traversal for delay analysis is equivalent to the traversal of sensitizable paths in the datapath. Comparison with the timing verifier in commercial computer-aided design (CAD) tools, show that estimated delays are within 14% accuracy of those reported by CAD tools.

The proposed BIST-based DFT method target testability problems caused by three constructs. The first construct is reconvergent fanout in a circuit behavior, which causes correlation. The second construct, control statements, also cause correlation and relational operations degrade observability. The third construct is random-pattern-resistant RTL modules, which cannot be tested effectively with random patterns. Test strategies are presented that overcome the testability problems by modigying the circuit behavior. An analysis and insertion scheme that systematically identifies the problems and applies the strategies is described. Experimental results from seven examples show that this scheme improves fault coverage while minimizing the impact on area and critical delay.

This paper presents a systematic test methodology targeting bus line interconnect defects using IDDT testing and Boundary Scan. Traditional test is unable to detect all possible defects, especially timing-related faults. Open and short defects on interconnects between embedded modules can be detected by IDDT testing. Boundary Scan can provide accessibility to internal buses. A statistical analysis is presented discussing the uncertain factors due to process variations and power fluctuation. The effectiveness of the proposed technique on shorts, opens or the other non stuck-at fault type defects is also illustrated.

A BIST-based design-for-test method targeting correlation in circuit behaviors is proposed. Correlation introduced by reconvergent fanout and conditional statements is considered. Testability problems caused by correlation are described and behavioral modification techniques to implicitly break the correlation are presented. An analysis and insertion scheme is proposed that systematically identifies testability problems in a circuit and modifies the circuit to resolve these problems. Experimental results from five examples show that this scheme improves the fault coverage of circuits with correlated signals while minimizing the impact on area and critical delay.

In systems consisting of interacting datapaths and controllers and utilizing built-in self test (BIST), the datapaths and controllers are traditionally tested separately by isolating each component from the environment of the system during test. This work facilitates the testing of datapath/controller pairs in an integrated fashion . The key to the approach is the addition of logic to the system that interacts with the existing controller to push the effects of controller faults into the data flow , so that they can be observed at the datapath registers rather than directly at the controller outputs. The result is to reduce the BIST overhead over what is needed if the datapath and controller are tested independently, and to allow a more complete test of the interface between datapath and controller, including the faults that do not manifest themselves in isolation. Fault coverage and overhead results are given for four example circuits.

A method for high level synthesis-for-testability of controller-datapath pairs that use gated clocks is developed. It uses a register allocation technique that improves the observability of the controller through the datapath, and takes advantage of the unique testability properties of one-hot-encoded controllers. The resulting controller can be fully tested without isolating it from the system. Area, fault coverage, and power consumption are reported for three example circuits.

In systems consisting of interacting datapaths and controllers, the datapaths and controllers are traditionally tested separately by isolating each component from the environment of the system during test. This is not possible when the controller-datapath pair is an embedded system designed as a hard core. This work facilitates the testing of controller-datapath pairs in a truly integrated fashion. The key to the approach is a careful examination of the types of gate level stuck-at faults that can occur within the controller. A class of faults that are undetectable in an integrated test by traditional means is identified. These faults create faulty but functional circuits. The effect of these faults on power consumption is explored, and a method based on power analysis is given for detecting these faults. Analysis is given for three example systems.

We present an optimization method that complies with IEEE P1500 draft standard and deals with modeling and design of the test access mechanism for the SoCs. The basic goal is to develop a global design for the test methodology and optimization technique for testing a core-based SoC in its entirety. We propose an ILP formulation to minimize the hardware cost or the overall access time which also produces the test access schedule.

This paper presents new algorithms for the scheduling and allocation phases in high-level synthesis under time and resource constraints. This is achieved by formulating these problems in terms of Liapunov's stability theorem using a transformation technique between the design space and the dynamic system space. These algorithms are based on moves in the design space, which correspond to the moves toward the equilibrium point in the dynamic system space. The scheduling algorithm (MFS) takes care of mutually exclusive operations, loop folding, multicycle operations, chained operations, and pipelining (structural and functional). The mixed scheduling-allocation algorithm (MFSA) can handle all of the above scheduling applications as well as simultaneously performing allocation of functional units, registers, and interconnects while minimizing the overall cost.

The purpose of this paper is to develop a exible design for test methodology for testing a core-based system on chip (SOC). The novel feature of the approach is the use an embedded microprocessor/memory pair to test the remaining components of the SOC. Test data is downloaded using DMA techniques directly into memory while the microprocessor uses the test data to test the core. The test results are tranferred to a MISR for evaluation. The approach has several important advantages over conventional ATPG such as achieving at-speed testing, not limiting the chip speed to the tester speed during test and achieving great exibility since most of the testing process is based on software. Experimental results on an example system are discussed. 1

This work facilitates the testing of datapath-controller pairs in an integrated fashion, with datapath and controller tested together in a single test session. Such an approach requires less test overhead than an approach that isolates datapath and controller from each other during test. The ability to do an integrated test is especially important when testing core-based embedded systems. The key to the approach is a careful examination of the relationship between techniques for controller synthesis and the types of gate level controller faults that can occur. A method for controller synthesis is outlined that results in a fully testable controller, so that full fault coverage of the controller can be achieved without any need for isolation during test.

This paper describes a design or redesign technique to reduce the control path delay and thus improve the performance of an RTL circuit. The basic idea is to replace an existing centralized controller of an RTL circuit with a distributed controller structure which is made up of multiple local controllers. By placing local controllers close to the datapath resources they control reduces the control wire length which in turn increases the circuit performance, especially at higher frequencies where interconnect delays are dominant. The approach begins with a datapath partitioning into distinct functional blocks, local controller extraction algorithm, followed by hierarchical floor planning. Two local controller styles are presented, the communicating and the and non-communicating local controller, respectively.

Access to embedded processor cores for application of test has greatly complicated the testability of large systems on silicon. Scan based testing methods cannot be applied to processor cores which cannot be modified to meet the design requirements for scan insertion. Instruction Randomization Self Test (IRST) achieves stuck-at-fault coverage for an embedded processor core without the need for scan insertion or mux isolation for application of test patterns. This is a new built-in self test method which combines the execution of microprocessor instructions with a small amount of on-chip test hardware which is used to randomize those instructions. IRST is well suited for meeting the challenges of testing ASIC systems which contain embedded processor cores.

This paper presents a resource allocation technique to design low-power register-transfer-level datapaths. The basis of this technique is to use a multiple clocking scheme of n nonoverlapping clocks, by dividing the frequency f of a single clock into n cycles, to partition the circuit into n disjoint modules and assign each module to a distinct clock, and to operate each module only during its corresponding duty cycle, thus clocking each module by a frequency f/n to reduce power. However, the overall effective frequency of the circuit remains f, i.e., the single clock frequency. Further power reduction is also obtained by tradeoffs between voltage, power, and delay across multiple clock partitions. Power savings up to 50% of the proposed multiple clocking scheme in comparison to single gated clock designs are also reported.

We present a global design for test methodology for testing a core-based system in its entirety. This is achieved by introducing a "bypass" mode for each core by which the data can be transferred from a core input port to the output port without interfering with the core circuitry itself. The interconnections are thoroughly tested since they are used to propagate test data (patterns or signatures) in the system. The system is modeled as a directed weighted graph in which the core accessibility is solved as a shortest path problem.

This paper presents a new method for the testing of the datapath of DSP cores based on self-test program. During the test, random patterns are loaded into the core, exercise different components of the core, and then are loaded out of the core for observation under the control of the self-test programs. We propose a systematic approach to generate the self-test program based on two metrics. One is the structural coverage and the other is the testability metric. Experimental results show the self-test program obtained by this approach con reach very high fault coverage in programmable core testing.

We present a global design for test methodology for testing a core-based system in its entirety. This is achieved by introducing a "bypass" mode for each core by which the data can be transferred from a core input port to the output port without interfering the core circuitry itself. The interconnections are thoroughly tested since they are used to propagate test data (patterns or signatures) in the system. The system is modeled as a directed weighted graph in which the core accessibility is solved as a shortest path problem.

In this paper we will show how high level test synthesis can achieve higher testability for BIST oriented test methodologies. Our results show considering testability during high-level synthesis, better testability can be obtained when compared to DFT at low level.

In systems consisting of interacting datapaths and controllersand utilizing built-in self test (BIST), the datapaths andcontrollers are traditionally tested separately by isolatingeach component from the environment of the system duringtest.This work facilitates the testing of datapath-controllerpairs in an integrated fashion.The key to the approach isthe addition of logic to the system that interacts with theexisting controller to push the effects of controller faults intothe data flow, so that they can be observed at the datapathregisters rather than directly at the controller outputs.Theresult is to reduce the BIST overhead over what is neededif the datapath and controller are tested independently, andto allow a more complete test of the interface between datapathand controller.Fault coverage and overhead resultsare given for four example circuits.

This paper presents a test synthesis technique for behavioral descriptions. The technique is guided by two testability metrics which quantify the controllability and observability of behavioral variables and structural signals. The method is based on utilizing redundant register transfers in the data path to produce a test behavior with better controllability and observability properties. This approach can avoid unnecessary insertions of test structures in the data path. A test scheme for conditional statements has been developed involving minimal changes in the controller. Our experimental results show improvements in fault coverage at modest hardware overhead.

High level test synthesis (HLTS), a term introduced in recent years, promises automatic enhancement of testability of a circuit. The authors show how HLTS can achieve higher testability for BIST oriented test methodologies. Their results show considering testability during high-level synthesis, better testability can be obtained when compared to DFT at low level. Transformation for testability, which allows behavioral modification for testability, is a very powerful HLTS technique.

A high-level test synthesis methodology based on BIST is proposed. This methodology targets the conditional if-then-else statements in a behavioral description because such statements can introduce testability problems in the resulting circuit. How well the operations in each branch of a conditional statement can be tested depends on the probability of taking each branch and the quality of the test patterns used in each branch. Behavioral modifications are presented that can resolve these testability issues. Experimental results from three practical examples show that this technique is effective.

A systematic methodology for testability analysis and enhancement of sequential circuit designs using Built-In Self-Test (BIST) is described. Inter-modular test insertions is applied to improve controllability as well as observability in a system level circuit. Circuit partitioning based on functionality has been applied to reduce the computation complexity. This methodology has been successfully applied to test system level circuits consisting of sequential circuit modules to do post-design re-synthesis improving overall testability. This methodology has achieved 99% fault coverage level for several different types of system level circuits from industry.

In this paper, we outline general design steps of our synthesis tool to realize application specific co-processors such that for a given scientific application having intensive iterative computations especially with recurrences, a VLIW type of coprocessor is synthesized and realized, and an accompanying parallel code is generated.We introduce a novel register file model, Shifting Register File (SRF), based on cyclic regularity of register file accesses; and a simple method, Expansion Scheduling, for scheduling iterative computations, which is based on cyclic regularity of loops.We also present a variable-register file allocation method and show how simple logic units can be used to activate proper registers at run time through an example.

This paper presents an effective technique of low power design for RTL circuits and microarchitectures. The basis of this technique is: a) to use a multiple clocking scheme of n nonoverlapping clocks, by dividing the frequency f of a single clock into n cycles; b) to partition the circuit into disjoint modules and assign each module to a distinct clock with frequency f=n. However, the overall effective frequency of the circuit remains f the single clock frequency. The results show that our multiple clocking scheme provides more effective power management (power savings up to 50%) at the RTL in comparison to conventional power management techniques based on gated clocks. 1. Introduction A major feature of currently proliferating portable applications is their requirement for low power consumption because they use battery voltage. Considering "power" rather than area or speed as the main optimization factor requires a second look at the entire VLSI design technologies, techniques, archi...

Design with cores has become popular recently because it can decrease the design time and ease the complexity of the design process. This paper presents a new method for the design of DSP cores based on multiple behaviors. This method uses redesign technique based on reallocation transformations to extract those RTL components in an initial RTL structure which are highly reusable and uses them to construct a DSP core. Experimental results are provided to illustrate the high reusability of core, extracted from given behaviors, when it accommodates new behaviors.

Because of programmability of Application Specific Programmable Processors (ASPPs), microcode-based control is effectively used to drive ASPP datapaths for different applications. In ASPPs, each application needs a separate microprogram resulting in large microcode memory. This paper proposes a distributed microcode memory model in which only distinct microcodes are stored in each separate memory module to save memory area. A hierarchical clustering approach is also proposed for the design of this distributed microcode memory. Experimental results indicate this approach is especially well suited for ASPP microcode memory design because of the existence of repetitive microcodes across multiple behaviors.

A testability analysis technique for built-in self-test (BIST) at the system level is presented. While based on previous approaches, the model has several significant new features, including an iterative technique for modeling indirect feedback and an extension to the circular BIST methodology. Additionally, a new preprocessing transformation enables the correct modeling of word-level correlation. Examples validate the model, and demonstrate its applicability to test point insertion.

A method for test synthesis in the behavioral domain is described. The approach is based on the addition of test behavior, which is the behavior of the design in test mode. The normal-mode design behavior and test-mode test behavior are combined and synthesized together to produce a testable design with inserted BIST structures. Derivation of an appropriate test behavior uses analysis based on metrics that quantify the testability of signals embedded within behaviors. The synthesized circuit is tested using a behavioral test scheme which allows the test controller to be easily embedded within the system controller, and the entire datapath and controller to be easily tested together. Results show that when the testability insertion procedure is used to modify a behavior before synthesis, the resulting synthesized physical implementation is indeed more easily tested than an implementation synthesized directly from the original behavior.

Constraints on the structure of circular self-test paths in register transfer level (RTL) circuits with circular Built-In Self Test (BIST) features are discussed. These constraints arise from the desire to avoid bit-level correlation, which can have a devastating effect on test quality. Two causes of bit-level correlation are examined, with examples demonstrating the resulting degradation in test quality. The first cause, register adjacency, is a byproduct of the ordering of the registers within the circular self test path. The second cause, a correlation inherent in circular BIST, stems from the shifting nature of the circular self-test path.

In this paper, we present a circuit partitioning and test pattern generation technique for pseudo-exhaustive built-in self-testing of VLSI circuits. The circuit partitioning process divides a given circuit into a set of subcircuits which can be exhaustively tested, while the test pattern generation process generates reduced exhaustive test patterns for each subcircuit using a linear feedback shift register (LFSR). In conventional approaches, these two problems are considered separately. However, in this paper, both problems are considered and solved in the same phase. A graph theoretic model of VLSI circuits is proposed. Based on this model, a circuit partitioning algorithm using the concept of minimum vertex cut is devised to partition the circuit into a set of exhaustively testable subcircuits with restricted hardware overhead. Each time a subcircuit is generated by the partitioning algorithm, the test pattern generation problem is considered. A new algorithm, based on the subcircuit modification technique, is proposed with the objective of generating reduced exhaustive test patterns of limited length (e.g., /spl les/2/sup 20/) using LFSR's, for each of the subcircuits. This task is embedded in the circuit partitioning process itself, leading to an efficient and well-coordinated solution. Experiments using ISCAS benchmark circuit simulation have been conducted. The results demonstrate that the proposed method is very good.>

Constraints on the structure of circular self-test paths in register transfer level (RTL) circuits with circular built-in self test (BIST) features are discussed. These constraints arise from the desire to avoid bit-level correlation, which can have a devastating effect on test quality. Two causes of bit-level correlation are examined, with examples demonstrating the resulting degradation in test quality. The first cause, register adjacency, is a byproduct of the ordering of the registers within the circular self test path. The second cause, a correlation inherent in circular BIST, stems from the shifting nature of the circular self-test path.>

This paper presents a fast and efficient algorithm to estimate the area cost of a given RTL datapath.This is achieved by considering

A new method of redesign at the registertransfer level using a transformational process is proposed. The redesign approach by reallocation takes into consideration ALU and interconnect cost in addition to layout area estimation. The idea is to start with a design, possibly generated by a synthesis system, and iteratively improve it by means of the reallocation process. The method is based on a set of reallocation transformations along with systematic strategies as to how to apply them together with a layout estimation model. I. INTRODUCTION High Level Synthesis is the automatic generation of a register transfer level (RTL) design (datapath/controller) from a behavioral level description, subject to a set of constraints. The datapath is usually synthesized in two steps --- operation scheduling and resource allocation. One of the main tasks of high-level synthesis is to find the structure that best meets the constraints while minimizing other costs [6]. The actual circuit layout can be...

A method for high level synthesis with testability is presented with the objective to generate self-testable RTL datapath structures. We base our approach on a new improved testability model that generates various testable design styles while reducing the circuit sequential depth from controllable to observable registers. We follow the allocation method with an automatic test point selection algorithm and with an interactive tradeoff scheme which trades design area and delay with test quality. The method has been implemented and design comparisons are reported.

Recent progress of data path synthesis has manifested the need to consider design for testability during, not after, the synthesis process. Motivated by the above requirement, the paper describes a partial scan cost estimation scheme for random testing using module level primitives. Starting from interpreting testability at the register transfer level, a model is developed for estimating the required partial scan configuration under a user specified testing time. A mixed integer programming formulation is then presented to derive the location and amount of scan needed. Experimental results have shown the same level of fault coverage as that of the full scan path under the given test time constraint.>

This paper presents a new technique for software pipelining using the Petri nets. Our technique called the Petri Net Pacemaker (PNP) can create near optimal pipelines with less algorithmic effort than other techniques. The pacemaker is a novel idea which exploits the behavior of Petri nets to model the problem of scheduling operations of a loop body for software pipelining.>

A scheme for vertical migration of algorithms and functions with complex sequencing structure from software through firmware into microcoded VLSI structures is discussed. The expected benefits of migration are gains in speed, reliability, and stability. The scheme employs a migration model that is based on microcode modularity and is supported by a hardware microcontroller with enhanced sequencing capability. The basic idea is to capture, using effective compilation techniques, the explicit or implicit sequencing structure of a function. Migration is then effected by sequencing calls into a library of microcode modules of a target machine architecture. The modularity of the migration system is well suited for generating VLSI microcode. The experimental results from an environment consisting of several firmware development tools show substantial time performance improvements in comparison to software implementations. Comparisons to traditional migration approaches indicate that the proposed scheme is faster and requires less memory space for the migration of software algorithms into firmware.>

A multiprocessor architecture called ALMP, which specifically suits loop pipelining, is proposed. The processors in ALMP work like machines in an assembly line in a plant. An assembly line scheduling method (ALMap) has also been developed. ALMP enables processors to communicate with each other through memory modules that shift from processor to processor as if they are on a conveyor belt. The scheduling method is briefly described, and architectural issues are examined.>

The Athena model is a tree-like net for pattern classification. This paper presents the formalisms on which the model's internal representations and function are based. It also presents an adaptive algorithm to be used with this model. The adaptation is based on entropy optimization. The difficult problem of the optimization is handled by use of Fisher's multiple discriminants method. A method is also presented by which confidence values are produced for the overall classification decision. Finally, a data flow architecture using optical processing elements is considered for the model's implementation.

The recent progress of high level synthesis has illuminated an effective aid for system designers.To keep pace with the development of such an environment, there is a need to consider design for testability (DFT) during the synthesis process.ThM paper proposes a DFT scheme

Article Free Access Share on A data path synthesis method for self-testable designs Authors: Christos A. Papachristou Department of Computer Engineering, Case Western Reserve University, Cleveland, Ohio Department of Computer Engineering, Case Western Reserve University, Cleveland, OhioView Profile , Scott Chiu Department of Computer Engineering, Case Western Reserve University, Cleveland, Ohio Department of Computer Engineering, Case Western Reserve University, Cleveland, OhioView Profile , Haidar Harmanani Department of Computer Engineering, Case Western Reserve University, Cleveland, Ohio Department of Computer Engineering, Case Western Reserve University, Cleveland, OhioView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 378–384https://doi.org/10.1145/127601.127698Online:01 June 1991Publication History 102citation242DownloadsMetricsTotal Citations102Total Downloads242Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A built-in self-test (BIST) hardware insertion technique is addressed. Applying to register transfer level designs, this technique utilizes not only the circuit structure but also the module functionality in reducing test hardware overhead. Experimental results have shown up to 38% reduction in area overhead over other system level BIST techniques.>

The article introduces a new high-level synthesis method for self-testable RTL designs. A basic feature of this method is a structural testability model which treats testability as a structural design style integrated in the design process. The main objective is to develop a system-level synthesis tool set mapping a behavioral description onto an optimized and testable RTL design subject to user-defined constraints. The approach involves several major components within the following system-level iteration: scheduling and allocation, constraint estimation, and testability tradeoffs.>

A new method for high level synthesis is reported whose basic feature is the tight interaction and coupling of the scheduling and allocation phases providing a global direction to synthesis. A linear program based allocation is proposed which uses multifunction ALU cost estimation, and iteratively drives a tree search for scheduling. A major contribution of this paper is a new interconnect optimization algorithm which is based on several interconnect transformations for multiplexer input collapsing and merging. Several other important synthesis aspects are included, e.g. register and interconnect bindings, operation chaining and operation multicycling. The method has been implemented in C on a Sun 3/60,

A novel programmable logic array (PLA) design that is very effective when it applies to control tables, i.e. structured tables representing functions of control nature, is presented. The PLA synthesis of control tables is achieved by the techniques of partition and fusion under area and time-delay design constraints. The partition technique exploits the data sparsity by splitting the control table along its columns into several smaller parts using heuristic breadth-first directed graph search. The fusion process takes advantage of the data multiplicity by sharing common symbolic PLA fields into distinct fields using a new encoding scheme. The partition process is performed only on the OR array of the symbolic PLA, whereas the fusion process performs the mutually exclusive encoding in the AND arrays of the partitioned PLA parts. A final channel routing of the PLA parts is also provided to reduce the routing area overhead required. The PLA synthesis of control tables scheme has been implemented in C and runs in Unix on VAX, Apollo, and Sun machines. An experiment using randomly generated data tables was very encouraging, particularly for large PLAs having a sparse and multiple personalization.>

In this work, we propose a circuit partitioning and test pattern generation algorithm for built-in pseudoexhaustive self-testing of VLSI circuits. The circuit partitioning process is to partition a given circuit into a set of subcircuits such that pseudoexhaustive self-testing will be possible, while the test pattern generation process is to generate the pseudoexhaustive test patterns for each subcircuit using a linear feedback shift register (LFSR). Both problems are considered and solved in the same phase and lead to an efficient and well-coordinated solution. Experiments using computer simulation have been conducted. The results demonstrate that the proposed method is very good, especially for circuits that are highly locally connected.

This paper presents a test scheduling method, called overlaying concurrent testing, for built-in testing of VLSI circuits. The scheme is based on a resource-conflict analysis of of subcircuits and a scheduling algorithm. The algorithm fully exploits test parallelism by overlaying the test intervals of compatible subcircuits to test as many of them as possible concurrently. The technique is supported by a test hardware architecture whose design is well coordinated with the test scheduling leading to a considerable reduction of testing time, as demonstrated by simulation experiments.

This paper investigates the complexity of multioperand residue addition and multiplication implemented by associative table lookup processing. The complexity measure used is the size of the associative memory, that is, the number of matching words in memory. This measure largely depends on the residue recurrencies, or multiplicities, in the addition and multiplication tables module M . The major effort in this work is to evaluate the recurrencies in simultaneous multioperand residue addition and multiplication. The evaluation is simple in case of addition mod M , and also in multiplication mod M if M is prime. To treat the more difficult case of M nonprime, a recursive procedure was developed for computing the 2-operand multiplication recurrencies mod M . The basis of this technique is the precedence relationships associated with a tree representation of the factors of M . It is then shown that the general D -operand multiplication mod M, D > 2 and M nonprime, can be reduced to the 2-operand case by isomorphic transformation. Computation results of 2-operand residue arithmetic operations are provided. Applications to RNS arithmetic implementation are discussed.

In this paper an approach to residue arithmetic is presented using Read-Only-Associative-Memories (ROAMs), such as PLAs. These memories have considerable advantages for table lookup arithimoetic processing over the conventional ROMs in terms of their storage and time efficiency. In residue arithmetic, the ROAM storage required largely depends on the residue recurrencies in arithmetic tables modulo M. After reviewing recent results on the computation of recurrencies, a scheme is proposed for implementing residue arithmetic based on ROAMs. The efficiency of the scheme is established by comparison to conventional ROM-based table lookup techniques. Applications to residue-to-binary number system conversion are also discussed.

This paper presents an efficient test procedure for the detection of simultaneously present functional faults in semi-conductor random access memories (RAM's). The proposed procedure detects modeled types of functional faults using 36N + 24N log2N operations, which is an improvement over existing techniques. The testing process is twofold: first, it detects simple functional faults by a linear address marching. Second, it detects more complex types of functional faults by a nonlinear address sequencing approach. Simulation results to support the testing procedure are also presented.

This paper presents a technique for direct truth table implementation of residue-based functions by an encoding scheme that employs programmable array logic (PAL) technology. The scheme models the basic associative memory operation, i.e., the detection of matchings between input patterns and prestored information in the PAL's. The complexity of this model is related to the amount of stored logic, i.e., the P-terms in the logic arrays. A linear programming approach is proposed for the encoding of the residue set with the objective of minimizing the complexity of addition and multiplication, modulo M, simultaneously. It is shown that the addition is more complex than the multiplication modulo M, with both (two-operand) operations being upper bounded by O(M2). Results produced using the optimal encoding compare favorably to corresponding results regarding the usual binary representation of residues. Practical constraints are also considered such as limitations on the number of pins, the number of P-terms, and the chip area, with the latter shown to be more efficiently utilized in the PAL scheme than in a ROM-or PLA-based implementation. The encoding technique is also applicable to the functions of discrete logic, in general.

This paper presents two related algorithms for implementing parallel n-bit binary addition and evaluating n-th degree polynomials, respectively. The approach taken makes use of an iterative construction, the computation tree. The algorithms are particularly effective for moderate values of n and are in accord with well-known asymptotic bounds. In the case of n-bit addition, the implementations constitute look-ahead tree circuits of r-input standard logic elements. Extensions to modular tree structures for lookahead adders are also considered. In the case of parallel polynomial evaluation, the operations of ordinary addition and multiplication are assumed with the capability to employ r arguments simultaneously.

This paper is concerned with optimal synthesis of switching logic by a limited depth tree-like network, the NAND cascade. This cascade consists of a number of complete three-level, fan-in restricted NAND trees feeding a NAND collector. The goal of the proposed synthesis is to minimize the number of NAND trees of the cascade, which in turn will minimize its overall depth, i.e., the delay time of the cascade.