Implementation of self-checking two-level combinational
logic on FPGA and CPLD circuits
Abstract
Very large scale integration (VLSI) technology has evolved to a level where large systems, previously implemented as printed circuit boards with discrete components, are integrated into a single integrated circuit (IC). But aggressive new chip design technologies frequently adversely affect chip reliability during functional operation. The use of a concurrent error detection (CED) scheme in order to achieve the high reliability requirement of modern computer systems is becoming an important design technique. The present paper describes implementations of separable codes for CED within VLSI ICs based on VHDL descriptions. Four schemes for concurrent error detection are analyzed: duplication of a combinational logic, Berger codes, Bose-Lin codes, and parity-check codes. Results concerning area overheads and operating speed decreases for 18 circuits, when they are implemented in FPGA and CPLD technologies, are reported.
1. Introduction
The detection of an error-producing fault is the necessary first step in most fault-tolerant systems. Classically, testing has been the mean by which faults have been detected. However, testing is not sufficient for the
many systems subject to failures which require high reliability and ease in maintainability. Testing is unlikely to detect the presence of short-lived transient faults [1]. Field studies indicate that such non-permanent faults
are the dominant cause of VLSI circuit/system failures (82–98%) [2]. With the current possibility of reduced voltage levels and the subsequent reduction in noise margins, circuit/system susceptibility to transient and
intermittent faults is likely to increase. If testing does indeed detect a fault, the latency between fault occurrence and fault detection is often sufficient to allow errors to propagate throughout the system and make
recovery difficult. The alternative to periodic testing (such as, for example, scan methods [3]) is the concurrent detection of errors during normal system operation. Concurrent error detection detects the first error produced
by a fault in the system and is therefore capable of detecting permanent and transient faults. Since the detection is concurrent with normal operation, the latency between fault occurrence and fault detection can be significantly reduced.
Concurrent (on-line or implicit) error detection techniques used in digital systems can be divided into two classes: circuit-level and system-level techniques. The use of single error correcting and double error detecting codes for memories, parity bits for data buses, residue (codes), Berger (codes), Bose-Lin (codes) and mout- of-n codes for arithmetic circuits, and self-checking sequential-circuits, are all examples of circuit-level techniques. Capability-based addressing, watchdog timers, fault-tolerant data structures and use of replication, such as FTMP and SIFT, and N-version programming are some examples of techniques used to detect errors at the system level [4]. Usually, techniques for concurrent error detection at the system level lead to considerable hardware overhead, performance degradation, or fault detection latency. In particular, their impact on circuit speed may not be tolerable for high performance applications.
Self-checking circuits can be used to ensure concurrent error detection by mean of hardware redundancy. The general structure of a self-checking circuit is given in Fig. 1. A self-checking circuit (SCC) consists of a functional block, which produces encoded output vectors, and a checker, which checks the vectors to determine if an error has occurred, i.e. to verify the outputs. The checker has the ability to give an error indication even when a fault occurs in the checker itself. The functional circuit can be either combinational or sequential. The goal to be reached by a self-checking circuit is often called the totally self-checking (TSC) goal; i.e. the first erroneous output of the functional block has to provide an error indication on the checker outputs.
Fig. 1. General structure of self-checking circuit.
A lot of work has been done in the area of selfchecking checker design for different codes [1,5–12]. However not so much attention has been paid to the VHDL based design and synthesis of checker circuits. Self-checking combinational circuit design methods were presented in [5,13,14]. Results in the area of self-checking sequential circuit design were presented in [6,7]. Applications of the self-checking concept to microprogrammed control units, PLAs, Braun array multipliers, finite state machines (FSM), etc., were presented in [7,11]. A theory of totally self-checking system design was presented in [1]. In most previous works on checker circuits, some constraints are involved which need to be satisfied to obtain a self-checking design. However, no attempt is made to evaluate the practicality of the design
in terms of area overhead, maximal operating frequency, and suitability for implementation under FPGA and CPLD technologies.
In the present paper we have considered the implementation of four different coding techniques (duplication, parity-check codes, Berger codes and Bose-Lin codes) into 18 combinational circuits in order to make these circuits self-checking. The hardware structure of the circuit is borrowed from data books of semiconductor companies like Texas Instruments, National
Semiconductor, Hewlett Packard, Toshiba or from textbooks dedicated to Computer Arithmetic [15]. In addition, the practicality of the design in term of area overhead, maximal operating frequency, and suitability of implementation with FPGA and CPLD is discussed.
2. Design strategies
Hardware-, information- and time-redundancy are three widespread strategies for VLSI ICs with concurrent error detection properties [16].
Information-redundancy, as a first approach, involves the use of coding techniques that enhance circuit capability for reliable operation. Numerous error detecting and correcting codes such as Berger codes, Bose-Lin codes, residue codes, parity-check codes, cyclic codes and others, have been proposed for storage, data transfer, data manipulation, and data control functions [16]. In some cases, where performance is not a bottleneck,
a second approach called time-redundancy can be used. It involves the use of the same hardware repeatedly in time for the same inputs and comparing the results. Examples of such approaches are recomputing with shifted operands, alternating logic, etc. [16]. A third approach to increase the reliability of circuits is to use hardware redundancy. The simplest hardware redundancy approach to designing a TSC circuit is duplication. Typically, the design implements two copies of the same circuit. The second copy produces output values complementing the value of the first copy, and a tree of two-rail code (TRC) checkers makes a bitwise comparison of the outputs. Whenever the natural and complementary outputs configurations differ from each other, or whenever a fault affects one of the self-checking TRC
checkers, the error signal reports the presence of fault. The advantage of this approach is that is applicable to any general function. Unfortunately, with duplication and comparison the area overheads are too high (more
than 100%).
One general approach for concurrent error detection is to encode the outputs of a circuit with an errordetecting code, and to have a checker that monitors the outputs and gives an error indication if a noncodeword occurs. Three types of systematic codes that are used for concurrent error detection are Berger codes, Bose-Lin codes and parity-check codes. The separable nature of these codes facilitates the derivation of efficient selfchecking
checkers.
The simplest scheme for error detection is parity checking. A parity-check code can be generated as a code in which each check bit is a parity check bit for a group of output bits. Each group of outputs that is
checked by a check bit is called a parity group. Synthesis techniques for generating multilevel circuits with concurrent error detection based on parity-check codes were presented in [1,12]. Efficient schemes have been developed for concurrent error detection in circuits with regular structures, as for example adders and multipliers [1,11,12].
Berger code encrypted information comprises the original information followed by the Berger check bits. The Berger check symbol of the information can adopt either the binary representation of the number of zeros in the information or the one-complement of the number of ones in the information. For I information bits there is a need for at least log2eI t 1T check bits. The Berger coding design technique for the purpose of the concurrent error detection utilizes a set of full-adder modules providing summation of the information bits.
Bose-Lin codes are systematic codes and require a fixed number of check bits, independent of the number of information bits. The codes are constructed by counting the number of ones or zeroes, similar to Berger
codes. The count is then modified depending on code parameter t. For t 2 and 3, the counts are performed by modulo 4 and 8, resulting in 2 and 3 check bits, respectively [10]. Bose-Lin codes with check-bits greater than 3 are explained in details in [1]. In [10] a procedure for synthesizing multilevel circuits with concurrent error detection based on Bose-Lin codes was considered.
In this paper we use a standard methodology to design totally self-checking systems specified in VHDL. At the start, the proposed method requires from the user the specification of the logical function of the original logic module in Boolean form. Then, that functional specification is enriched with check symbol generator and checker parts. After that, the expanded specification is converted into VHDL description and synthesized using commercial tools. This mean that, for each considered circuit, two VHDL versions exist. The first one relate to the original version, while the second to its selfchecking variant which involves the modification of the VHDL RTL description. FPGA or CPLD technologies are used for implementation.
In the sequel, the hardware structures of TSC checkers based on duplication, Berger codes, Bose-Lin codes, and parity-check codes will be described. For all four schemes the procedure for synthesizing and implementation of TSC combinational logic circuits is described. We use the Active HDL V. 3.5 and Xilinx ISE 4.2 as tools for designing, synthesizing and simulating these circuits. In addition, reports generated by the synthesis tool allow us to obtain design details concerning area overhead,
speed of operation, critical paths, etc.
The following 18 representative circuits are described in VHDL first, and after that their structure is modified in order to derive the hardware structure of the corresponding TSC circuits: (1–2)C1/2: 4/8-bits magnitude comparator based on SN7485; (3)C3: ASCII to seven segment decoder; (4)C4: ASCII to BCD decoder; (5–6)C5/6: 4/8-bits multiplier; (7)C7: 18 segment solid state alphanumeric display HDSP-6300; (8–9)C8/9: 8/16-bits ripple-carry adder; (10–11)C10/11: 8/16-bits carry lookahead adder;(12) C12: 32-bits funnel shifter; (13–15)C13/14/15: 6/8/12-bits binary to BCD converter; (16)C16: eight to three priority encoder; (17)C17: 16 to four
priority encoder; (18)C18: 3-line to 8-line decoder/demultiplexer.
(A) Duplication: For a given combinational logic circuit we synthesize duplicate circuit and logic for the TSC comparator (see Fig. 2a). The original part of the circuit has true, while its copy complemented
output values. Whenever the natural and complementary outputs configurations differ from each other, or whenever a fault affects one of the selfchecking
TRC two-rail checkers, the error signal reports the presence of fault. The procedure for generating logic for TSC comparator is adapted to the
number of signals to be compared.
(B) Berger codes: Let the original information consists of I bits. Berger code encryption requires log2 (I t 1) check bits [1]. The hardware structure of
Fig. 2. Self-checking circuits: (a) duplication; (b) Berger and Bose-Lin codes; (c) parity-check with 4 parity bits.
the check bits generator and the TSC two-rail checker is sketched in Fig. 2b following [1].
(C) Bose-Lin codes: In this scheme, the Bose-Lin code is used. Fig. 2b sketches the hardware structure of the check bits generator and the TSC two-railchecker.
(D) Parity-check codes: This coding approach consists of adding one check bit called the parity bit, to the information bits or to any group of the information bits. The parity bit is selected such that it is equal to the sum modulo 2 of the information bits or their complements. Several efficient methods proposed in [5,14] partion the outputs to form logic blocks in such a way that logic sharing within each block is maximized but not logic sharing between block is allowed. A block diagram of self-checking circuit using the technique with 4 parity-check bits is sketched in Fig. 2c.
3. Results
The goal of the proposed procedure was to select the VHDL code that will require the least area to implement a self-checking principle at maximal operating frequency. The area of the circuit is equal to the sum of the
area of the original function logic, CED logic, and checker. The area required by the original function logic depends on how much logic sharing is possible. The area required by the CED logic depends on the size of the checking function that must be implemented for each code. The area required by the checker depends on how many checking groups are there.
4. Conclusions
In this paper we have presented four schemes for synthesis of totally self-checking combinational circuits based on duplication, parity-check codes, Berger codes and Bose-Lin codes derived from a VHDL description.
We use a suitable approach for insertion of CED into synthesizable VHDL RTL description of the original circuit. Then we use a commercial synthesis tool to implement the corresponding TSC into FPGA or CPLD technology. We insert the concurrent error detection circuitry at the RTL level rather than at the gate level because insertion at the front-end of the synthesis process
has the following advantages: (a) The synthesis tool can take the error detection circuitry into account when satisfying timing constraints (as well as other constraints on power, testability, etc.). (b) Inserting the error detection circuitry at the RTL level can be easily and seamlessly incorporated into the standard design flow.
In order to make the presented results more realistic the number of synthesized combinational circuits have to be augmented, and combinational circuits of complex structure taken into account. But without loss of generality, the described synthesis procedure should be
identical to the proposed one.
