Single- and Double-Output Embedded Checker Architectures for Systematic Unordered Codes<Superscript>∗</Superscript>

For the detection of all unidirectional errors, Berger codes have been found to be an optimal choice in the general case. But for some particular cases other systematic unordered codes are superior to Berger codes. We present checker architectures for Berger-type codes that are similar to Berger codes. They cover codes by Parhami so that the proposed checkers can also be used for these codes. We also describe new checker architectures for Bose AUED codes and Biswas-Sengupta AUED codes. The design of these checkers is based on translating the code words to words of a Berger-type code which are then checked by a Berger-type code checker. The translation circuits are very simple. All checkers can be tested with only a few code words, or achieve the self-testing property almost independent of the provided set of code words, and are therefore very suitable as embedded checkers. The proposed checkers can be designed to have a single periodic output or a two-rail encoded output. Further, our checkers are not code-disjoint in the common sense but able to detect all single and multiple unidirectional errors.Steffen Tarnick received the diploma degree in mathematics from the Dresden University of Technology, Dresden, Germany, in 1989, and the Dr. rer. nat. degree from the University of Potsdam, Germany, in 1995. From 1989 to 1991 he was a Research Assistant at the Institute of Cybernetics and Information Processes of the East German Academy of Sciences in Berlin. Then he spent one year as visiting scientist at the TIMA Laboratory in Grenoble, France. From 1992 to 1995 he was with the Max Planck Society Group for Fault-Tolerant Computing at the University of Potsdam, Germany. Until 2002 he was a research staff member at SATCON GmbH in Teltow, Germany. He is currently the head of the Secure Systems Department at 4TECH GmbH in Teltow, Germany. His main research interests include self-checking circuits design, built-in self-test, and cryptography.     

Design of Embedded Self-Testing Checkers for t-UED and BUED Codes

In this article we present a new method for designing self-testing checkers for t-UED and BUED codes. The main idea of this method is to map words of the considered code to words of a code of the same type in which the value of t or the number of check bits is reduced and repeating this with the obtained words until a parity code is obtained, or to translate the code words into words of a code for which such a mapping is possible. First we consider Borden codes for t = 2 ^k – 1, Bose, and Bose-Lin codes. The mapping operation is realized by averaging weights and check symbol values of the code words. The resulting checkers have a simple and regular structure. This structure is independent on the set of code words that is provided by the circuit under check. The checkers are very well suited for use as embedded checkers since they are self-testing with respect to single stuck-at faults under very weak assumptions. All three checker types can be tested with 2 or 3 code words. We also propose a novel approach to design checkers for Blaum codes that require much less code word tests than existing solutions.     

Self-Testing Embedded Borden t-UED Code Checkers for t = 2 k q − 1 with q = 2 m − 1

Borden codes are optimal nonsystematic t-unidirectional error detecting (t-UED) codes. A possible method to design a Borden code checker is to map the Borden code words to words of an AN arithmetic code and to check the obtained words with an appropriate AN code checker. For t = q − 1 with q = 2 ^m  − 1 we show how this method can be modified such that the Borden code checkers achieve the self-testing property under very weak conditions. It is only required that no checker input line gets a constant signal and that the Borden code words occur in a random order, making the proposed checkers very suitable for use as embedded checkers. Based on these checkers it is then possible to design embedded Borden t-UED code checkers for t = 2 ^k q − 1 with q = 2 ^m  − 1.

Intermediacy Prediction for High Speed Berger Code Checkers

We present an intermediacy prediction method that can be used to designhigh speed checkers for Berger codes, as well as for any other unordered code. In the proposed method, the received information and check bits are processed simultaneously toward an intermediate result. A two-rail code checker is then used to compare the two versions of such an intermediate result. Recall that, in conventional checkers for unordered codes, the received check bits remain idle until the received information bits are converted to the re-generated check bits. Therefore, our proposed intermediacy prediction method allows a checker's speed improvement. We show the application of our method to two well-Bergercode checker architectural solutions: (1) the threshold function based implementation, and (2) the Berger code partitioning design. We have verified that, as expected, the proposed method can improve the detecting speed of these existing solutions with moderate or minimum increase, and sometimes decrease, in hardware complexity.     

Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes

This paper presents a procedure for synthesizing sequential machines with concurrent error detection based on Bose-Lin codes. Bose-Lin codes are an efficient solution for providing concurrent error detection as they are separable codes and have a fixed number of check bits, independent of the number of information bits. Furthermore, Bose-Lin code checkers have a simple structure as they are based on modulo operations. Procedures are described for synthesizing circuits in a way that their structure ensures that all single-point faults can only cause errors that are detected by a Bose-Lin code. This paper presents an efficient scheme for concurrent error detection in sequential circuits with no constraint on the state encoding. Concurrent error detection for both the state bits and the output bits is based on a Bose-Lin code and their checking is combined such that one checker suffices. Results indicate low area overhead. The cost of concurrent error detection is reduced significantly compared to other methods based on other codes.     

Checkers’ No-Harm Alarms and Design Approaches to Tolerate Them

In this paper we analyze the probability that transient faults, multiple or single, affecting a checker of a self-checking circuit (with particular reference to the case of circuits using the two-rail code, the parity code, the Berger code and the Bose–Lin code) give rise to no-harm alarms, here defined as indications of errors neither denoting the presence of an incorrect word at the output of the functional block, nor denoting the presence of checker internal faults possibly compromising its ability to discriminate input codewords from input non-codewords. Differently from all other error indications, no-harm alarms could be conveniently ignored (or tolerated) by the system, with no need to adopt any recovery strategy upon their reception, otherwise for instance leading to exclude the self checking circuit from the whole system, or to degrade system’s performance. A new property (No-Harm Alarm Robustness) is defined for checkers, allowing to discriminate “true” error indications from no-harm alarms. A possible approach to design checkers featuring such a property is proposed. The behavior of the derived checkers has been verified by means of electrical level simulations, and their costs are discussed.     

An Analog Checker with Input-Relative Tolerance for Duplicate Signals

We discuss the design of a novel analog checker that monitors two duplicate signals and provides a digital error indication when their absolute difference is unacceptably large. The key feature of the proposed checker is that it establishes a test criterion that is dynamically adapted to the magnitude of its input signals, thus enhancing the accuracy of assessing their relative discrepancy. Consequently, when this checker is utilized in concurrent error detection, it diminishes the probability of both false negatives and false positives. Likewise, when employed for off-line test purposes, the checker supports both high yield and high fault coverage. In contrast, checkers implementing a static test criterion may only be tuned to achieve efficiently one of the aforementioned objectives.     

Single Output Distributed Two-Rail Checker with Diagnosing Capabilities for Bus Based Self-Checking Architectures

This paper proposes a distributed two-rail checker architecture which is specifically targeted to self-checking bus-based systems. The architecture makes use of a single bus line to provide error indication. With respect to conventional two-rail checkers additional diagnosing capabilities are provided. The checker is totally-self-checking with respect to stuck-at faults. It features also good self-testing properties with respect to parametric faults, such as bridgings and delay faults.     

Self-Testing Embedded Two-Rail Checkers

This paper presents a new simple and straightforward method for designing Completely Testable Embedded (CTE) parity trees, and Self-Testing Embedded (STE) two-rail checkers. In the design of CTE parity trees the two inputs XOR gate has been used as the building block. In the case of STE two-rail checkers with n input pairs the building block is the two-rail checker with 2 input pairs. During normal, fault free, operation each XOR gate receives all possible input vectors, while each two-rail checker with 2 input pairs receives all possible code input vectors. The great advantage of the proposed method is that it is the only one that gives in a simple and straightforward way an optimal CTE/STE tree realization with respect to the hardware (number of blocks) and the speed (number of block levels). Designing the two input two-rail checker as proposed by Lo in IEEE J. of Solid-State Circuits, 1993, we get optimal STE two-rail checkers taking into account realistic faults.     

Design for Low Power Testing of Computation Modules with Contiguous Subspace in VLSI

A kind of pseudo Gray code presentation of test patterns based on accumulation generators is presented and a low power test scheme is proposed to test computational function modules with contiguous subspace in very large scale integration （VLSI）, especially in digital signal processors （DSP）. If test patterns from accumulators for the modules are encoded in the pseudo Gray code presentation, the switching activities of the modules are reduced, and the decrease of the test power consumption is resulted in. Results of experimentation based on FPGA show that the test approach can reduce dynamic power consumption by an average of 17.40% for 8-bit ripple carry adder consisting of 3-2 counters. Then implementation of the low power test in hardware is exploited. Because of the reuse of adders, introduction of additional XOR logic gates is avoided successfully. The design minimizes additional hardware overhead for test and needs no adjustment of circuit structure. The low power test can detect any combinational stuck-at fault within the basic building block without any degradation of original circuit performance.     

Built-in Test with Modified-Booth High-Speed Pipelined Multipliers and Dividers

An embedded test pattern generator scheme for large-operand (unlimited bit length) multiplier and divider is presented by employing a simple digital circuit. This scheme is based on the generation of cyclic code polynomials from a characterized polynomials generator G(X) and incorporated with Modified-Booth algorithm. Due to the advantages of the former, the hardware complexity is simple, and moreover, the multiplier and divider can share the same hardware with a small change of control lines. Due to the advantages of latter's schemes, the numbers of sub/add operations are reduced to one half of the multiplicand for the result of final product. Therefore, the proposed pipelined multipliers permit very high throughput for arbitrary value of digit size. Only full adders/subtractors and shift registers are used in the proposed multiplier and divider hardware. The input data of the multiplier/divider can be processed in parallel or in pipelined without considering carry/borrow delays during the operations. The speed of computation has therefore been greatly improved by approximately a factor of 2. Since most parts of the components can be used for both the multiplier and divider, with full adders replaced by subtractors for switching from a multiplier to a divider, the structure is therefore tremendously reduced. In addition, these function units are involved with cyclic code generators, so that they can be used as a built-in self-test (BIST).     

Modular implementation of efficient self-checking checkers for the Berger code

A technique for designing efficient checkers for conventional Berger code is proposed in this paper. The check bits are derived by partitioning the information bits into two blocks, and then using an addition array to sum the number of 1's in each block. The check bit generator circuit uses a specially designed 4-input 1's counter. Two other types of 1's counters having 2 and 3 inputs are also used to realize checkers for variable length information bits. Several variations of 2-bit adder circuits are used to add the number of 1's. The check bit generator circuit uses gates with fan-in of less than or equal to 4 to simplify implementation in CMOS. The technique achieves significant improvement in gate count as well as speed over existing approaches.     

Self-Checking Carry-Select Adder Design Based on Two-Rail Encoding

Carry-select adders are one of the faster types of adders. This paper proposes a scheme that encodes the sum bits using two-rail codes; the encoded sum bits are then checked by self-checking checkers. The multiplexers used in the adder are also totally self-checking. The scheme is illustrated with the implementation of a 2-bit carry select adder that can detect all single stuck-at faults on-line; the detection of double faults is not guaranteed. Adders of arbitrary size can be constructed by cascading the appropriate number of such 2-bit adders. A range of adders from 4 to 128 bits is designed using this approach employing a 0.5-mum CMOS technology. The transistor overhead in implementing these self-checking adders varies from 19.51% to 20.94%, and the area overhead varies from 16.07% to 20.67% compared to adders without built-in self-checking capability.     

Design of Self-Testing Checkers for m-out-of-n Codes Using Parallel Counters

This paper extends the design method of self-testing checkers (STCs) for some m-out-of-n (m/n) codes, proposed recently in IEEE Trans. Comput., 1995 by Dimakopoulos et al. The checkers are built using a pair of parallel counters (composed of full-adders and half-adders) with a total of n inputs and a 2-rail STC. We show here how to build this type of checkers for a number of m/n codes for which previous methods failed.     

OP-Fibo: An efficient Forbidden Pattern Free CAC design

Occurring crosstalk fault between wires is among the significant reliability challenges in transferring data between Processing Elements (PEs). Crosstalk fault occurs due to inter-wire coupling capacitances based on the appeared transition patterns on the channel. Among these transition patterns, Triplet Opposite Direction (TOD) causes the worst crosstalk effects on the transferred flits in the channels of NoCs. Forbidden Pattern Free Crosstalk Avoidance Codes (FPF-CACs) can efficiently omit TODs. However, state-of-the-art FPF-CAC has ambiguity in its mapping algorithm. This problem leads to generating more than one code word for some data words. To solve this problem, this paper aims to reduce crosstalk fault by proposing a FPF-CAC called Omissive Penultimate-Fibo (OP-Fibo). OP-Fibo benefits ambiguity-free numerical system and mapping algorithm that can generate unique code words for all of the data words and can save additional wires. Evaluations indicate that the proposed numerical system can be utilized in wires with any arbitrary channel width and also, can significantly improve the reliability with better overheads with respect to recently proposed FPF-CAC.     

One-to-Many: Context-Oriented Code for Concurrent Error Detection

The paper deals with context-oriented codes for concurrent error detection. We consider a fault model for which, in the presence of a fault, the values on the circuit’s output are arbitrary. This model allows one to design an error detection code without analyzing sensitive parts or error cones in the synthesized circuit. Conventional coding schemes are based on a one-to-one mapping between an original output vector (information word) and a codeword. In this paper, we introduce a different approach, which we call one-to-many coding. In one-to-many code, each codeword comprises a predefined set of words. The functional unit is referred to as an encoder enabling each activation to map an information word to a different word. This flexible mapping system results in a lower implementation cost of the functional unit and its checker.     

Lowering power consumption in concurrent checkers via input ordering

This paper presents an efficient and scalable technique for lowering power consumption in checkers used for concurrent error detection. The basic idea is to exploit the functional symmetry of concurrent checkers with respect to their inputs, and to order the inputs such that switching activity (and hence power consumption) in the checker is minimized. The inputs of the checker are usually driven by the outputs of the function logic and check symbol generator logic-spatial correlations between these outputs are analyzed to compute an input order that minimizes power consumption. The reduction in power consumption comes at no additional impact to area or performance and does not require any alteration to the design flow. It is shown that the number of possible input orders increases exponentially in the number of inputs to the checker. As a result, the computational cost of determining the optimum input order can be very expensive as the number of inputs to the checker increases. This paper presents a very effective technique to build a reduced cost function to solve the optimization problem to find a near optimal input order. It scales well with increasing number of inputs to the checker, and the computational costs are independent of the complexity of the checker. Experimental results demonstrate that a reduction in power consumption of 16% on the average for several types of checkers can be obtained using the proposed technique.     

An erasure-based scheme for reduction of PAPR in spatial multiplexing MIMO-OFDM using Reed-Solomon codes over GF(216 + 1)

In this paper, a novel erasure-based scheme which uses long Reed-Solomon (RS) codes over GF(65537) is proposed for the reduction of the peak-to-average power ratio (PAPR) in coded orthogonal frequency division multiplexing (OFDM). The motivation for using the field GF(65537) is to generate long code words (up to 65536 symbols in just one code word). Using long codes results in greater flexibility to search for low PAPR OFDM frames within the subsets of symbols of a code word because RS codes are maximum distance separable and any subset of a high enough number of symbols is sufficient for the recovery of data. Over this field, the lengths of code words are exponents of 2. Hence, low-complexity radix-2 fast Fourier transform can be exploited. RS codes are deployed for both PAPR reduction and error correction. Simulation results show that in similar PAPR reduction performances, the proposed scheme outperforms the previously reported work with RS codes in both error correction and computation complexity. The proposed scheme can be applied to both single-input single-output and multi-input multi-output systems.     

Design of CMOS checkers with improved testability of bridging and transistor stuck-on faults

This work presents a design technique for CMOS static and dynamic checkers (to be used in self-checking circuits), that allows the detection of all internal single transistor stuck-on and bridging faults causing unacceptable degradations of the circuit dynamic performance (but not logical errors). Such a technique exploits simple voltage detector circuits to make sure that the intermediate faulty voltages inevitably produced by the faults of interest are always propagated at the checker output as logic errors.With the use of our technique, the main disadvantages of static checkers, so far preventing their use in practical applications, are overcome.The method has been applied to the particular case of two-rail (static as well as dynamic) checkers and its validity has been verified by means of electrical level simulations.     

Design of minimal-level PLA self-testing checkers for m-out-of-ncodes

This paper presents the design of minimal-level PLA self-testing checkers (STCs) for incomplete m-out-of-n (m/n) codes and 1-out-of-n (1/n) codes. All checkers are selftesting for three classes of typical PLA faults and hence they are all crosspoint irredundant. A number of various incomplete m/n codes which exhibit the two-closure property with balanced partitioning are constructed, which allow one to build two-level area optimal PLA STCs for incomplete m/n codes with virtually any capacity. These new PLA STC's for m/n codes are then used to build a family of efficient three-level PLA STCs for most 1/n codes. In most cases, the new checkers offer area and/or active device number reduction, compared to existing designs which rely upon m/2m codes only. Obviously, all new minimal-level checkers can be implemented using logic gates as well