In recent years parallel computing has been widely employed for both science research and commercial applications. For parallel systems such as many-core or computer clusters, it is inevitable to have one or more computing node failures due to random errors or injected attacks. Usually a diagnosis mechanism is able to locate several defective nodes through a number of tests and the analysis of those test signatures (syndromes). Although this covers the cases caused by random errors, sophisticated attacks are still able to manipulate the outputs of each node, so that they will be masked and pass the diagnosis. Therefore in this paper we propose a hybrid self-diagnosis mechanism. We adopt a new type of analysis with the linear syndromes, which are able to locate up to a certain number of defective nodes caused by random errors. In addition to this, we introduce a new type of robust analysis of the non-linear syndromes, which is capable of detecting the attacks undetectable by the linear syndromes at a probability close to one. Moreover, since this hybrid self-diagnosis mechanism is on the data level which makes little distinction among different operating systems and programming languages, it can be migrated onto any other platforms conveniently.

Shamir's secret sharing scheme is an effective way to distribute secret to a group of shareholders. The security of the unprotected sharing scheme, however, can be easily broken by cheaters or attackers who maliciously feed incorrect shares during the secret recovery stage or inject faults into hardware computing the secret. In this paper, we propose cheater detection and identification schemes based on robust and algebraic manipulation detection (AMD) codes and m-disjunct matrices (superimposed codes). We present the constructions of codes for cheater detection and identification and describe how the cheater identification problem can be related to the classic group testing algorithms based on m-disjunct matrices. Simulation and synthesis results show that the proposed architecture can improve the security level significantly even under strong cheating attack models with reasonable area and timing overheads.

Most cache designs support single or double bit-level error detection and correction in cache lines. However, a single error may distort a whole byte or even more, resulting in much higher decoding complexity than that of bit-level distortions. Thereby this paper proposes a new group testing based error correcting code (GTB code) for byte-level error locating and correcting which provides much stronger protection for memories. This new class of non-binary GTB codes is generated from binary superimposed codes. Since it is encoded and decoded by binary matrices, no complicated Galois Field computations in GF(Q) such as multiplications and inversions are involved. Comparing with popular non-binary error correcting codes (ECC) such as Hamming, Reed-Solomon and interleaved codes, the GTB codes achieves up to 42% reduction of the decoding complexity (hardware cost × latency) for single-byte error correction, and up to 98% reduction for double-byte error correction. Moreover, given the length of codewords (e.g. 512 bits for cache lines), as the size of each Q-ary digit (byte) increases, the saving increases.

Security-oriented error-detecting codes are used to detect fault injection attacks on cryptographic devices. These codes are usually designed for uniformly distributed codewords, i.e., for codes that have maximal entropy. In practice, the codewords are not uniformly distributed; thus, their entropy is smaller and their efficiency in detecting attacks degrades. This paper analyzes the relation between the entropy of a code and its worst error masking probability. Based on this relation, a method for determining the rate and structure of a code that provides the required error masking probability is presented.

The security of communication or computational systems protected by traditional error detecting codes rely on the assumption that the information bits of the message (output of the device-under-attack) are not known to attackers or the error patterns are not controllable by external forces. For applications where the assumption is not valid, e.g., secure cryptographic devices, secret sharing, etc, the security of systems protected by traditional error detecting codes can be easily compromised by an attacker. In this paper, we present constructions for strongly secure codes based on the nonlinear encoding functions. For$(\mbi {k},\mbi {m},\mbi {r})$strongly secure codes, a message contains three parts:$\mbi {k}$-bit information data$\mbi {y}$,$\mbi {m}$-bit random data$\mbi {x}$, and$\mbi {r}$-bit redundancy$\mbi {f}(\mbi {y},\mbi {x})$. For any error$\mbi {e}$and information$\mbi {y}$, the fraction of$\mbi {x}$that masks the error$\mbi {e}$is less than 1. In this paper, we describe lower and upper bounds on the proposed codes and show that the presented constructions can generate optimal or close to optimal codes. An efficient encoding and decoding method for the codes minimizing the number of multipliers using the multivariate Horner scheme is presented.

The reliability and security of memories are crucial considerations in the modern digital system design. Traditional codes usually concentrate on detecting and correcting errors of certain types, e.g. errors with small multiplicities or byte errors, and cannot detect or correct unanticipated errors. In this paper we present a reliable and secure memory architecture based on robust Algebraic Manipulation Correction codes. These codes can provide a guaranteed error detection probability and can correct any error regardless of its multiplicity as long as the error stays for several consecutive clock cycles. The construction and the error correction procedure for the code will be described. The probability that an error can be successfully detected and/or corrected and the hardware overhead of the memory architecture based on these codes will be estimated.

Public-key cryptographic devices are vulnerable to fault-injection attacks. As countermeasures, a number of secure architectures based on linear and nonlinear error detecting codes were proposed. Linear codes provide protection only against primitive adversaries with limited attack capabilities. On the other hand nonlinear codes provide protection against strong adversaries, but at the price of high area overhead (200%-400%). In this paper we propose a novel error detection technique based on the random selection of linear arithmetic codes and explore the use of this technique for the protection of the multiplier, which is a basic block in many public-key cryptographic devices. The error detection technique does not imply any limitations on the types of errors at the output of the device, e.g., the multiplicity of the error does not have to be small. Under mild assumptions the proposed construction achieves near nonlinear code error detection performance at a lower cost (at most 50% area overhead for the protection of multipliers) due to the fact that no nonlinear operations are needed for the encoder and decoder.

Multi-level cell (MLC) nand flash memories are popular storage media because of their power efficiency and large storage density. Conventional reliable MLC nand flash memories based on BCH codes or Reed-Solomon (RS) codes have a large number of undetectable and miscorrected errors. Moreover, standard decoders for BCH and RS codes cannot be easily modified to correct errors beyond their error correcting capabilityt=[(d-1/2)], wheredis the Hamming distance of the code. In this paper, we propose two general constructions of nonlinear multi-error correcting codes based on concatenations or generalized from Vasil'ev codes. The proposed constructions can generate nonlinear bit-error correcting or digit-error correcting codes with very few or even no errors undetected or miscorrected for all codewords. Moreover, codes generated by the generalized Vasil'ev construction can correct some errors with multiplicities larger thantwithout any extra overhead in area, latency, and power consumption compared to schemes where only errors with multiplicity up totare corrected. The design of reliable MLC nand flash architectures can be based on the proposed nonlinear multi-error correcting codes. The reliability, area overhead and the penalty in latency and power consumption of the architectures based on the proposed codes are compared to architectures based on BCH codes and RS codes. The results show that using the proposed nonlinear error correcting codes for the protection of MLC nand flash memories can reduce the number of errors undetected or miscorrected for all codewords to be almost 0 at the cost of less than 20% increase in power and area compared to architectures based on BCH codes and RS codes.

Carbon nanotubes (CNTs) are considered as a possible successor to the CMOS technology. The adoption of these nanodevices for designing large VLSI systems, however, is limited by the unreliable manufacturing process. In this paper, we investigate the possibility of using CNTFETs to build SRAM arrays. We analyze the error mechanisms and show how stuck-at faults and pattern sensitive faults are caused by metallic tubes in different transistors of a 6-T SRAM cell. The results indicate the need of stronger error detecting codes than the widely used single-error-correcting, double-error-detecting codes in CMOS SRAMs.

Cryptographic devices are vulnerable to fault injection attacks. All previous countermeasures against fault injection attacks based on error detecting codes assume that the attacker cannot simultaneously control the fault-free outputs of a device-under-attack and error patterns. For advanced attackers who are able to control both of the above two aspects, traditional protections can be easily compromised. In this paper, we propose optimal algebraic manipulation detection (AMD) codes based on the nonlinear encoding functions and the random number generators. The proposed codes can provide a guaranteed high error detecting probability even if the attacker can fully control the fault-free outputs of a device-under-attack as well as the error patterns. As a case study, we present the protection architectures based on AMD codes for multipliers in Galois fields used for the elliptic curve cryptography. The results show that the proposed architecture can provide a very low error masking probability at the cost of a reasonable area overhead. The protected multiplier has no latency penalty when the predictor is pipelined.

For many devices and circuits, even a single fault can result in errors of a large Hamming weight at the output of a device, complicating the task of error detection and correction. Traditional error detection and correction techniques are based on linear error-detecting codes that are designed to detect or correct errors of a small multiplicity or burst errors. The authors present codes and architectures suitable for both online and offline error detection and correction which can detect and correct any error of any multiplicity by exploiting the laziness of error manifestation. Faults in many combinational circuits can lead to ‘lazy’ or repeating errors at the outputs of a device to be protected. The proposed decoding algorithms can correct any error of any Hamming weight if the same error affects at least three different consecutive distorted output vectors of a protected device for binary algebraic errors. Likewise, the proposed decoding algorithms can correct any error of any Hamming weight if the same error affects two different output vectors of a protected device for arithmetic errors.

Multi-level cell (MLC) NAND flash memories are very popular storage media because of their power efficiency and big storage density. This paper proposes to use nonlinear t-error-correcting codes to replace linear BCH codes for error detection and correction in MLC NAND flash memories. Compared to linear BCH codes with the same bit-error correcting capability t, the proposed codes have less errors miscorrected by all codewords and nearly no undetectable errors. For example, the proposed (8281, 8201, 11) 5-error-correcting code has no errors of multiplicity six miscorrected by all codewords while the widely used (8262, 8192, 11) linear shortened BCH code has 11 over 6 × A11errors in this class, where A11≈ 1014is the number of codewords of Hamming weight eleven in the shortened BCH code. Moreover, in spite of the fact that the Hamming distance of the proposed code is 2t+1, it can also correct some errors of multiplicity t+1 and t+2 requiring no extra hardware overhead and latency penalty. In this paper, the constructions and the error correction algorithm for the nonlinear t-error-correcting codes are presented. The architecture of the encoder and the decoder for the codes are shown. The error correcting capabilities, the hardware overhead, the latency and the power consumption for the encoder and the decoder will be analyzed and compared to that of the linear BCH codes to demonstrate the advantages of the proposed codes for error detection and correction in MLC NAND flash memories.

The security of the cryptographic device may be compromised if the FSM of the system is not properly protected. FSM protection architectures based on linear codes cannot provide a guaranteed level of protection under the assumption of a strong attack model. In this paper, we propose secure FSM architectures based on the idea of randomly selecting one code from a set of codes for each encoding and decoding operation. Assuming that the attacker is able to inject specific error patterns, randomly selecting one code from L codes as described in the paper can reduce the chance for the attacker to conduct a successful attack by a factor of L. The proposed techniques can achieve much higher security level than architectures based on linear codes with reasonable hardware overhead for cryptography applications (120% - 130% for the protection of the FSM for the Montgomery ladder algorithm). The security level of the proposed architectures can be increased by increasing L and the number of information bits k of the codes.

The problem of preventing deadlocks and livelocks in computer communication networks, in particular, those with wormhole routing, is considered. The method to prevent deadlocks is to prohibit certain turns (i.e., the use of certain pairs of connected edges) in the routing process, in such a way that eliminates all cycles in the graph. We propose a new algorithm that constructs a minimal (irreducible) set of turns that breaks all cycles and preserves connectivity of the graph. The algorithm is tree-free and is considerably simpler than earlier cycle-breaking algorithms. We prove its properties and present lower and upper bounds for minimum cardinalities of cycle-breaking connectivity preserving sets for graphs of general topology as well as for planar graphs. In particular, the algorithm guarantees that not more than 1/3 of all turns in the network become prohibited. We also present experimental results on the fraction of prohibited turns, the distance dilation, as well as on the message delivery times and saturation loads for the proposed algorithm in comparison with known tree-based algorithms. The proposed algorithm outperforms substantially the tree-based algorithms in all characteristics considered.

Linear single-error-correcting, double-error-detecting (SEC-DED) codes used in the design of reliable memories cannot detect and can miscorrect errors with large Hamming weights. We propose protection for memory devices based on extended Vasil'ev codes. These nonlinear SECDED codes have a minimum distance of four, fewer undetectable errors and fewer errors that are miscorrected than linear codes with the same dimension and redundancy. The extended Vasil'ev codes can provide for higher reliability in the presence of repeating errors or high rate of multibitupsets. As far as we know, our paper is the only one discussing application of efficient nonlinear codes for design of reliable memories. The proposed approach can be applied to RAM, ROM, FLASH and disk memories with relatively low hardware overhead.

The paper deals with designing fault tolerant finite state machines (FSMs) by nanoelectronic programmable logic arrays (PLAs). Two main critical parameters of the fault tolerant nano-PLAs, the area and the number of crosspoint devices, are considered as optimization criteria for the synthesis. The paper introduces a method for synthesizing fault tolerant nano-PLA based FSMs. The method is based on decomposing an initial PLA description of the FSM into a three interacting portions. The proposed solution provides significant reduction of the area without meaningful increasing of a number of crosspoint devices in comparison with known solutions and provides a trade-off between the area and the number of devices in designing FSMs by PLAs.

We propose an efficient technique for the detection of errors in cryptographic circuits introduced by strong adversaries. Previously a number of linear and non-linear error detection schemes were proposed. Linear codes provide protection only against primitive adversaries which no longer represents practice. On the other hand non-linear codes provide protection against strong adversaries, but at the price of high overhead. Here we propose a novel error detection technique, based on the random selection of linear codes. Under mild assumptions the proposed construction achieves near non-linear code error detection performance at much lower cost due to the fact that no non-linear operations are needed for the encoder and decoder.

In this paper we consider the problem of constructing minimal cycle-breaking sets of turns for graphs that model communication networks, as a method to prevent deadlocks in the networks. We present a new cycle-breaking algorithm called simple cycle-breaking or SCB algorithm that is considerably simpler than earlier algorithms. The SCB algorithm guarantees that the fraction of prohibited turns does not exceed 1/3. Experimental simulation results for the SCB algorithm are shown.

The adaptive and active nature of fault based side-channel attacks along with the large arsenal of fault injection methods complicates the design of effective countermeasures. To overcome the unpredictability of fault attackers protection methods based on robust codes were proposed which can provide uniform error detection against all errors eliminating possible weaknesses in the protection. In this paper we evaluate and compare the error detection properties and hardware overheads of architectures based on robust, partially robust, and minimum distance robust codes for both public and private key cryptosystems.

Existing methods for gate level power attack countermeasures depend on exact capacitance matching of the dual-rail data outputs of each gate. Process variability and a lack of design tools make this requirement very difficult to satisfy in practice. We present a novel asynchronous dual-rail gate design which is power balanced, does not require capacitance matching of the data outputs, and is tolerant to process variability on the routed interconnect between gates.

The early propagation effect found in many logic gates is a potential source of data-dependent power consumption. We show that the effect and the corresponding power dependency can be targeted for successful power analysis attacks in cryptographic hardware. Many of the current balanced gate designs did not directly consider the effect and are vulnerable to power analysis attacks

A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.

We present a method of protecting a hardware implementation of the advanced encryption standard (AES) against a side-channel attack known as differential fault analysis attack. The method uses systematic nonlinear (cubic) robust error detecting codes. Error-detecting capabilities of these codes depend not just on error patterns (as in the case of linear codes) but also on data at the output of the device which is protected by the code and this data is unknown to the attacker since it depends on the secret key. In addition to this, the proposed nonlinear (n,k)-codes reduce the fraction of undetectable errors from 2/sup -r/ to 2/sup -2r/ as compared to the corresponding (n,k) linear code (where n - k = r and k >= r). We also present results on a FPGA implementation of the proposed protection scheme for AES as well as simulation results on efficiency of the robust codes.

Ethernet networks rely on the so-called spanning tree protocol (IEEE 802.1d) in order to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones, since it makes inefficient use of expensive fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach, based on the novel theory of turn-prohibition. Specifically, we introduce, analyze and evaluate a new algorithm, called tree-based turn-prohibition (TBTP). We show that this polynomial-time algorithm maintains backward-compatibility with the IEEE 802.1d standard and never prohibits more than 1/2 of the turns in the network, for any given graph and any given spanning tree. Through extensive simulations on a variety of graph topologies, we show that it can lead to an order of magnitude improvement over the spanning tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

A code C detects error e with probability 1-Q(e),ifQ(e) is a fraction of codewords y such that y, y+e/spl isin/C. We present a class of optimal nonlinear q-ary systematic (n, q/sup k/)-codes (robust codes) minimizing over all (n, q/sup k/)-codes the maximum of Q(e) for nonzero e. We also show that any linear (n, q/sup k/)-code V with n /spl les/2k can be modified into a nonlinear (n, q/sup k/)-code C/sub v/ with simple encoding and decoding procedures, such that the set E={e|Q(e)=1} of undetected errors for C/sub v/ is a (k-r)-dimensional subspace of V (|E|=q/sup k-r/ instead of q/sup k/ for V). For the remaining q/sup n/-q/sup k-r/ nonzero errors, Q(e)/spl les/q/sup -r/for q/spl ges/3 and Q(e)/spl les/ 2/sup -r+1/ for q=2.

This paper discusses optimization of decisions diagrams (DDs) by total autocorrelation functions. We present an efficient algorithm for construction of linearly transformed binary decision diagrams (LT-BDDs) and Linearly transformed multiterminal BDDs (LT-MTBDDs) for systems of Boolean functions, based on linearization of these functions by the corresponding autocorrelation functions. Then, we present a method for reduction of sizes of DDs by a level-by-level reduction of the width of DDs using the total autocorrelation functions. The approach provides for a simple procedure for minimization of LT-BDDs and LT-MTBDDs and upper bounds on their sizes. Experimental results for benchmarks illustrate that the proposed method on average is very efficient.

We consider the problem of data reconciliation, which we model as two separate multisets of data that must be reconciled with minimum communication. Under this model, we show that the problem of reconciliation is equivalent to a variant of the graph coloring problem and provide consequent upper and lower bounds on the communication complexity of reconciliation. Further, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding error-correcting codes for a general class of errors. Under this equivalence, reconciling with little communication is linked to codes with large size, and vice versa. We show analogous results for the problem of multiset verification, in which we wish to determine whether two multisets are equal using minimum communication. As a result, a wide body of literature in coding theory may be applied to the problems of reconciliation and verification.

Network calculus is known to apply in general only to feedforward routing networks, i.e., networks where routes do not create cycles of interdependent packet flows. We address the problem of using network calculus in networks of arbitrary topology. For this purpose, we introduce a novel graph-theoretic algorithm, called turn-prohibition (TP), that breaks all the cycles in a network and, thus, prevents any interdependence between flows. We prove that the TP-algorithm prohibits the use of at most 1/3 of the total number of turns in a network, for any network topology. Using analysis and simulation, we show that the TP-algorithm significantly outperforms other approaches for breaking cycles, such as the spanning tree and up/down routing algorithms, in terms of network utilization and delay bounds. Our simulation results also show that the network utilization achieved with the TP-algorithm is within a factor of two of the maximum theoretical network utilization, for networks of up to 50 nodes of degree four. Thus, in many practical cases, the restriction of network calculus to feedforward routing networks may not represent a too significant limitation.

In this paper we deal with totally self-checking (TSC) synchronous sequential circuits (SSCs), that are able to recover after an occurrence of a fault. We call SSC owing this property as a self-healing SSC. A concept of a partially monotonic SSC is used in the paper. It is shown that the partially monotonic SSCs satisfy the self-healing property. A novel reduced m-out-of-n code is developed. It is proposed applying this code to the synthesis of a TSC checker for the state monotonic SSCs. The proposed method of synthesis is based on a LUT implementation of monotonic functions.For most circuits in a standard benchmark set, the proposed approach leads to a reduction of about 10-20% of the overhead as compared with the traditional methods.

Network calculus is known to apply in general only to feedforward routing networks, i.e., networks where routes do not create cycles of interdependent packet flows. We address the problem of using network calculus in networks of arbitrary topology. For this purpose, we introduce a novel algorithm, called turn-prohibition (TP), that breaks all the cycles in a network and thus prevents any interdependence between flows. We prove that the TP-algorithm prohibits the use of at most 1/3 of the total number turns in a network, for any network topology. Using analysis and simulation, we show that the TP-algorithm significantly outperforms other approaches for breaking cycles, such as the spanning tree and up/down routing algorithms, in terms of network utilization and delay bounds. Our simulation results also show that the network utilization achieved with the TP-algorithm is within a factor of two of the maximum theoretical network utilization, for networks of up to 50 nodes of degree four. Thus, in many practical cases, the restriction of network calculus to feed-forward routing networks may not represent a significant limitation.

In this paper we present a new technique for on-line checking of FPGA-based sequential devices defined by their algorithmic state machines (ASMs). The technique utilizes specific properties of ASMs for achieving the totally self-checking goal with a low hardware overhead. This technique is based on the architecture that consists of two portions: a self-checking sequential device and a separate totally self-checking (TSC) checker. Each of these portions is implemented as a combination of an "evolution" block and an "execution" block. Comparison of code vectors transferred between these blocks provides for the totally self-checking property. The proposed technique does not require any redundant encoding of output words and uses a one-rail design, thereby drastically decreasing the required overhead. The paper presents overhead estimations and results for benchmarks for the proposed architecture.

We investigate a new class of codes for the optimal covering of vertices in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it. We define a ball of radius t centered on a vertex /spl upsi/ to be the set of vertices in G that are at distance at most t from /spl upsi/. The vertex /spl upsi/ is then said to cover itself and every other vertex in the ball with center /spl upsi/. Our formal problem statement is as follows: given an undirected graph G and an integer t/spl ges/1, find a (minimal) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of vertices thus obtained constitutes a code for vertex identification. We first develop topology-independent bounds on the size of C. We then develop methods for constructing C for several specific topologies such as binary cubes, nonbinary cubes, and trees. We also describe the identification of sets of vertices using covering codes that uniquely identify single vertices. We develop methods for constructing optimal topologies that yield identifying codes with a minimum number of codewords. Finally, we describe an application of the theory developed in this paper to fault diagnosis of multiprocessor systems.

Off-line testing of large multiprocessor networks or VLSI chips with many outputs requires a large volume of memory for reference data storage. Space compaction combined with time compression of test responses can essentially reduce an overhead required for testing and diagnosis. In this paper, we discuss the problem of optimal design for space compressors (compactors), to minimize the number of observation points for detection of single faulty components in multiprocessor networks. A space compactor is assumed to be followed by a time compressor, to detect a fault not necessarily manifesting itself for a single test pattern. We formulate the rules of design for a space compaction matrix for the topology of the circuit-under-test (CUT) modeled by an arbitrary acyclic graph. Tree arrays and Fourier transform networks are considered as examples. The lower and upper bounds on the number of space compactor outputs are obtained, and optimal space compaction matrices are determined for above mentioned CUT topologies. Simple procedures for design of off-line testing devices with built-in self-testing are presented. Estimations on a complexity of proposed designs are given.>

This paper presents a new methodology for RAM testing based on PS(n, k) fault model (the k out of n pattern sensitive fault model). According to the model the contents of any memory cell which belongs to an n-bit memory block, or ability to change the contents, is influenced by the contents of any k-1 cells from this block. This paper includes the investigation of memory testing approaches based on the transparent pseudoexhaustive testing and its approximations by pseudorandom circular tests, which can be used for periodic and manufacturing testing and require lower hardware and time overheads than the standard approaches.

Proposes a new approach for identification of faulty processing elements based on an analysis of the compressed test response of the system. The test response is compressed first in space and then in time, and faulty processing elements are identified by hard decision decoding of the corresponding space-time signature. The approach results in considerable savings in hardware required for diagnostics.>

A new design approach, based on multiple signature analysis, for self-diagnostic boards is presented. For this approach, test responses from all chips on the board are compressed into space-time signatures using nonbinary multiple error-correcting codes, and faulty chips are identified by analyzing relations between distortions in these signatures. This approach results in a considerable reduction of a hardware overhead, required for diagnostics, as compared with the straightforward approach where separate signatures are computed for each chip on the board. The diagnostic approach presented can also be used for identification of faulty boards in a system or for faulty processors in a multiprocessor environment.>

Presents two different methodologies for built-in self-diagnostic of boards and systems by space-time compression of test responses. The first method, soft decision, uses nonbinary multiple error-correcting codes to obtain space-time signatures. These obtained signatures and the corresponding precomputed references are compared and magnitudes of distortions in signatures are analyzed to identify faulty components. The second method, hard decision, makes use of the information indicating whether the corresponding signatures are distorted or not. Both approaches show considerable savings in hardware overheads when compared with a straightforward approach where a separate signature is required for every component. A transition from the soft to hard decision approach results in an increase in the number of signatures required for diagnostic but at the same time it results in a decrease in the complexity of a fault locating algorithm. Results pertaining to VLSI implementations are presented where the hardware overhead is estimated in terms of two-input equivalent gates.>

A finite-field algebraic description of a built-in self-test (BIST) design based on primitive feedback shift registers (LFSRs) implementing the test generator and the signature analyzer (SA) is presented. That the BIST schemes that use the TG and the SA with the same feedback polynomial detect errors which distort the output functions of the circuits-under-test for a set of the input vectors forming a coset of a subspace. The authors term this type of error the 'single coset error'. Signature schemes which detect the coset errors of multiplicity r are further described, (r>

A number of methods have been proposed to study aliasing in MISR compression. However, most of the methods can compute aliasing probability only for specific test lengths and/or specific error models. Recently, a GLFSR structure [15] was introduced which admits coding theory formulation. The conventional signature analyzers such as LFSR and MISR form special cases of this GLFSR structure. Using this formulation, a general result is now presented which computes the exact aliasing probability for MISRs with primitive feedback polynomials, for any test length and for any error model. The framework is then extended to study the probability of correct diagnosis when faulty signature is used to identify the faulty CUT in the STUMPS environment. Specifically, the results in [7, 15, 161 are extended by proposing two new error models, a general error model which subsumes all the commonly used models, and a fixed magnitude error model which is shown to be useful for fault diagnosis. It is shown how statistical simulation can be used to determine the general error model, for a given CUT. Aliasing for some benchmark circuits, for various error models and test lengths is studied.

An analysis and design of a pseudorandom pattern generator, (PRPG), based on a linear recurrence, for built-in self-test (BIST) boundary scan design is presented. The authors present for the case when r>or=s, a design of an s-stage PRPG capable of producing 2/sup s/-1 distinct r-bit patterns within 2/sup s/-1 clock pulses independent of the hardware realization of the PRPG. For the case when r>

A novel approach to the identification of a faulty processing element, based on an analysis of the compressed response of the system, is proposed. The test response is compressed first in space and then in time, and a faulty processing element is identified by a hard-decision decoding of the corresponding space-time signature. The overhead analysis and the solution for the hardware minimization problem are presented for several important classes of systems. The proposed method results in considerable hardware savings.>

A compression of test responses technique for a built-in self-test (BIST) VLSI design is presented. The authors introduce the notion of a robust compression technique which incorporates prior knowledge of the statistics of fault-free responses under pseudorandom testing to achieve a guaranteed error detectability independent of a distribution of errors. The presented robust quadratic compressor requires two r-bit registers (r-bit signature) more than a multiple-input linear feedback shift register; however, it provides for equal protection against all error patterns. Therefore, quadratic compressors are optimal and robust with respect to a statistics of errors in a device under test.>

Single and multiple multiple-input-signature-register (MISR) aliasing probability expressions are presented for arbitrary test lengths. A framework, based on algebraic codes, is developed for the analysis and synthesis of MISR-based test response compressors for BIST. This framework is used to develop closed-form expressions for the aliasing probability of MISR for arbitrary test length. An error model, based on q-ary symmetric channel, is proposed using more realistic assumptions. Results are presented that provide the weight distributions for q-ary codes (q=2/sup m/, where the circuit under test has m outputs). These results are used to compute the aliasing probability for the MISR compression technique for arbitrary test lengths. This result is extended to compression using two different MISRs. It is shown that significant improvements can be obtained by using two signature analyzers instead of one. The weight distribution of a class of codes of arbitrary length is also given.>

A new approach for fault detection in combinational networks based on Reed-Muller (RM) transforms is presented. An upper bound on the number of RM spectral coefficients required to be verified for detection of multiple stuck-at-faults and single bridging faults at the input lines of an n-input network is shown to be n. The time complexity (time required to test a network) for detection of multiple terminal faults and the storage required for storing the test are determined. An upper bound is found for the minimum number of test patterns required to detect a fault. The authors present standard tests based on this result, with a simple test generation procedure and upper bounds on minimal numbers of test patterns.>

Nonlinear quadratic codes that are optimal for the minimax error detection are presented. Characteristic functions for these codes are asymptotically bent. For a given block size n and the number of codewords mod C mod , these codes minimize max Q(e), e not=0, where Q(e) is the conditional error-masking probability, given the error pattern e. The codewords are blocks of n symbols from GF(q). Encoding and decoding procedures for the codes are described.>

Board-level diagnostic techniques by signature analysis based on single-error-correcting Hamming codes over GF(2/sup M/) (where M is the number of outputs per chip) are presented. Two techniques are considered: the space-time compressor technique for the case when responses from N chips on the board are wired to the compressor; and the time compressor technique for the case when test responses from each chip are transferred to the compressor via system bus. Assuming a single-faulty-chip model, a faulty chip on the board under test is located by an analysis of the relationship between the distortions in the obtained signatures. Both techniques for board-level diagnosis require less hardware than the straightforward diagnostic techniques using a built-in signature analyzer for every chip or selective testing of each chip via the system bus, hence offering an efficient approach for a design of a built-in-self-test board for for manufacturing testing.>

A data compression technique called self-testable and error-propagating space compression is proposed and analyzed. Faults in a realization of Exclusive-OR and Exclusive-NOR gates are analyzed, and the use of these gates in the design of self-testing and error propagating space compressors is discussed. It is argued that the proposed data-compression technique reduce the hardware complexity in built-in self-test (BIST) logic designs using external tester environments.>

In this correspondence we present a design technique for implementation of systems of Boolean functions in the form of multilevel AND-OR networks. We show that for a given system of Boolean functions, the transition from the traditional two-level AND-OR implementation to multilevel AND-OR implementations results in considerable savings in gate counts and delays. We discuss gate-array implementations of these multilevel networks and their space and time complexities. Experimental data for 11 different components of peripheral control units for VAX computers indicate that the transition from the two-level implementations to multilevel implementations results in average savings of about 40 percent in gate counts, of about 25 percent in required silicon areas and of about 25 percent in delays, which illustrate a good potential of the proposed techniques for design of cost-efficient gate arrays.

A class of suboptimal Wiener filters is considered, and their computational and statistical performances (and the trade-off between the two) are studied and compared with those for known classes of suboptimal Wiener filters. A general model of a suboptimal Wiener filter over a group is defined, which includes, as special cases, the known filters based on the discrete Fourier transform (DFT) in the case of a cyclic group and the Walsh-Hadamard transform (WHT) in the case of a dyadic group. Statistical and computational performances of various group filters are investigated. The cyclic and the dyadic group filters are known to be computationally the best ones among all the group filters. However, they are not always the best ones statistically and other (not necessarily Abelian) group filters are studied. Results are compared with those for the cyclic group filters (DFT), and the general problem of selecting the best group filter is posed. That problem is solved numerically for small-size signals(\leq 64)for the first-order Markov process and random sine wave corrupted by white noise. For the first-order Markov process with the covariance matrixB^{(S,l)} = \rho^{|s-l|}as\rhoincreases, the use of various non-Abelian groups results in improved statistical performance of the filter as compared to the DFT. Similarly, for the random sine wave with covariance matrixB^{(s,l)} = \cos \lambda (s - l)as\lambdadecreases, non-Abelian groups result in a better statistical performance of the filter than the DFT does. However, that is compensated for by the increased number of computations to perform the filtering.

All known results on covering radius are presented, as well as some new results. There are a number of upper and lower bounds, including asymptotic results, a few exact determinations of covering radius, some extensive relations with other aspects of coding theory through the Reed-Muller codes, and new results on the least covering radius of any linear[n,k]code. There is also a recent result on the complexity of computing the covering radius.

In this correspondence we present universal tests for detection of single and multiple stuck-at and bridging faults in combinational and sequential networks.

We consider methods of error detection and/or error correction in software and hardware of a distributed system computing values of numerical functions. These methods are based on software and hardware redundancy for the computation of additional check functions. The check functions are easily derived for any given multiplicity of errors. The redundancy does not depend on the number of processors in the original system and depends only on the multiplicity of errors. We describe methods for the construction of optimal checks, required software and hardware redundancy, and implementation of the corresponding error detecting/correcting procedures by a distributed system.

LetVbed binary linear(n,k)code defined by a check matrixHand leth(x)be the characteristic function for the set of columns ofH. Connections between the Walsh transform ofh(x)and the weight distributions of all translates of the code are obtained. Explicit formulas for the weight distributions of translates are given for small weightsi(i<8). The computation of the weight distribution of all translates (including the code itself) fori<8requires at most7(n-k)2^{n-k}additions and subtractions,6 \cdot 2^{n-k}multiplications and2^{n-k+l}memory cells. This method may be very effective if there is an analytic expression forh(x). A simple method for computing the covering radius of the code by the Walsh transform ofh(x)is described. The implementation of this method requires for largenat most2^{n-k}(n-k) \log_{2}(n-k)arithmetical operations and2^{n-k+1}memory cells. We define the conceptL-perfect for codes, whereLis a set of weights. After describing several linear and nonlinearL-perfect codes, necessary and sufficient conditions for a code to beL-perfect in terms of the Walsh transform ofh(x)are established. An analog of the Lloyd theorem for such codes is proved.

Due to the advances in the integrated circuit technology, there is an increasing importance in testing bridging (short circuit) failures in digital networks. Unfortunately, very little work has been done in this area. This paper presents the schemes for the detection of feedback bridgings between the inputs and outputs through the observation of oscillation and asynchronous behavior of sequential networks created by bridging faults. The lower and upper bounds on the number of tests for detecting all feedback bridging faults are given. Conditions for the undetectability of input bridgings are given and a method for testing input bridgings is presented. The results are generalized to detect bridging and stuck-at faults in the input and output lines of a multiple-output network. Finally, the complete test sets are given for detecting input, output and feedback bridgings as well as stuck-at faults at the input and output pins of the standard integrated circuit chips including shift registers, counters, decoders, multiplexers, adders/subtracters, multipliers, dividers and RAM.

The study of short circuits between conducting paths (bridging faults) has become increasingly important. Yet very little work has been done in this area. In this paper, conditions for feedback bridging (short circuit) faults to generate oscillation and asynchronous behavior are given for short circuits among input lines and the primary output. The lower and upper bounds on the number of tests for detecting all feedback bridging faults are given. Necessary and sufficient conditions for the undetectability of input bridgings are presented. It is found that any test detecting single bridging fault e will also detect all multiple bridgings containing e. Complete test sets for locating either all input or all feedback bridgings of any multiplicities for networks implementing several classes of functions are given.

LetVbe a binary linear(n,k)-code defined by a check matrixHwith columnsh_{1}, \cdots ,h_{n}, and leth(x) = 1ifx \in {h_{1}, \cdots , h_{n}, andh(x) = 0ifx \in \neq {h_{1}, \cdots ,h_{n}}. A combinatorial argument relates the Walsh transform ofh(x)with the weight distributionA(i)of the codeVfor smalli(i< 7). This leads to another proof of the Plessith power moment identities fori < 7. This relation also provides a simple method for computing the weight distributionA(i)for smalli. The implementation of this method requires at most(n-k+ 1)2^{n-k}additions and subtractions,5.2^{n-k}multiplications, and2^{n-k}memory cells. The method may be very effective if there is an analytic expression for the characteristic Boolean functionh(x). This situation will be illustrated by several examples.

A method is proposed for error detection in digital devices and computer programs calculating the values of functions f(x), where x ∈ G and G is a finite commutative group. For the case of network implementation of the method, "errors" are catastrophic structural failures; for the case of program implementation, they are errors in the text of the program.

Recent works [1]-[9] were devoted to the properties and application of Fourier transforms over finite Abelian groups and fast Fourier transforms for calculation of the corresponding spectra. In this correspondence we describe Fourier transforms on finite non-Abelian groups and appropriate algorithms of fast Fourier transforms.