Manikandan Pandiyan

Geetha Mani
email: geethamr@gmail.com

Wearable ECG SoC for Wireless Body Area Networks: Implementation with Fuzzy Decision Making Chip

The work aims to present an ultra-low power Electrocardiogram (ECG) on a chip with an integrated Fuzzy Decision Making (FDM) chip for Wireless Body Sensor Networks (WBSN) applications. The developed device is portable, wearable, long battery life, and small in size. The device comprises two designed chips, ECG System-on-Chip and Fuzzy Decision Maker chip. The ECG on-chip contains an analog front end circuit and a 12-bit SAR ADC for signal conditioning, a QRS detector, and relevant control circuitry and interfaces for processing. The analog ECG frontend circuits precisely measure and digitize the raw ECG signal. The QRS complex with a sampling frequency of 256 Hz is extracted after filtering. The extracted QRS details are sent to the decision maker chip, where abnormalities/anomalies in patient's health are detected and an alert signal is sent to the patient via wireless communication protocol. The patient's ECG data is wirelessly transmitted to a PC, using ZigBee or a mobile phone. The chip is prototyped and employed in a standard 0.35µm CMOS process. The operating voltage of Static RAM and digital circuits and analog core circuits are 3.3 Volts and 1 Volt, respectively. The total area of the device is about 6𝑐𝑚 # and consumes about 8.5µW. Small size and low power consumption show the effectiveness of the proposed design, suitable for wireless wearable ECG monitoring devices.

Introduction

According to World Health Organization (WHO), cardiovascular and modern human behavior-related diseases are the major cause of mortality worldwide. These types of cardiovascular related-diseases, like Cardiac arrhythmias, Atrial fibrillation, and Coronary heart diseases, can be monitored and controlled with continuous personal healthcare supervision [START_REF] Chen | A Low-Power Bio-Potential Acquisition System with Flexible PDMS Dry Electrodes for Portable Ubiquitous Healthcare Applications[END_REF][START_REF] Pandiyan | Integrating wearable low power CMOS ECG acquisition SoC with decision making system for WSBN applications[END_REF]. Electrocardiogram (ECG) embodies the cardiovascular condition, therefore, is considered one of the most important human physiological signals. In applying measurement of physiological signals for continuous monitoring, patients usually cannot carry a bulky instrument, which restricts their mobility and makes them uncomfortable, with so many electrodes and cables attached to their bodies. Therefore, there is growing demand for a compact wearable ECG acquisition system [START_REF] Pandiyan | Integrating wearable low power CMOS ECG acquisition SoC with decision making system for WSBN applications[END_REF]. Wearable monitoring devices can record physiological variables, like ECG, blood pressure, etc. for several hours and store them in the memory for future use. The stored ECG data can then be utilized by clinicians or cardiologists for further diagnosis. The graphical embodiment of a wearable system for continuous remote monitoring is illustrated in Fig. 1. Wearable sensors/electrodes (deployment in accordance with the clinical application) collect the physiological signals for monitoring the patient's health status. These wearable sensors continuously monitor vital signs, like heart rate and blood pressure, when the patient with chronic heart disease is undergoing clinical involvement. Wearable devices are also applied in home-based rehabilitation interventions for continuous personal health monitoring. Wireless protocols can be integrated with wearable systems to facilitate long-term health monitoring for patients diagnosed with cardiac diseases. The wireless communication is relied upon and used to transmit the physiological data continuously to a central place (an access point or a mobile) and to remote central (server or emergency centre) via internet. In emergency situations, an alarm/alert signal can be transmitted to the remote emergency centre for facilitating medical assistance to patients. Family members or clinicians are also alarmed when the patient is in an emergency condition through the technology and enabled to monitor the patient's medical status continuously. Even though there are advantages of wearable devices, many future challenges should be addressed. This primarily requires the support of innovative sensor technologies, especially Wireless Body Sensor Networks (WBSN), formed with various wearable biomedical sensors. Since the constraints on battery life and form factor are crucial, these sensors have a very stringent power requirement. To aid low cost, ultra-low power design is essential for developing wearable devices. In terms of cost, size, and performance, System-on-Chip (SoC) implementation is an attractive option.

In this chapter, the development and deployment of the wearable ECG SoC monitoring system are studied, regarding key technology perspective. The following sections present the prior art and essential components of wearable devices, System overview, Proposed ECG SoC, and Fuzzy Decision Maker Chip. Concluding remarks, observations, and future reservations are discussed in the final section.

Prior Art

Wireless Body Area Network (WBAN) is the fundamental component of a wireless ECG monitoring system. WBAN allows the integration of various other components, like intelligent systems, miniaturized components, low-power sensor nodes, etc. Therefore, the combination of SoC concepts, wearable technology, Wireless Sensor Network (WSN), and research in artificial intelligence produce novel approaches, resulting in better health care services. System-on-a-chip (SoC) is a felicitous option for device development because of its small size, low power consumption, and lower cost features. Developing SoC for Wireless Body Area Network applications intends to carry healthcare monitoring closer from clinical intervention to domiciles. It allows physiological signal monitoring to be conducted more regularly than limiting it to hospitals or clinics. WBSN is foreseen as the next generation health care monitoring platform, as it is considered a reliable, low-cost high-patient-safety health care monitoring system. In recent years, the development of ECG SoC for WSBN applications has attracted much attention [START_REF] Pandiyan | Integrating wearable low power CMOS ECG acquisition SoC with decision making system for WSBN applications[END_REF][START_REF] Lopez | E-textile and wireless-sensor-network-based platform for healthcare monitoring in future hospital environments[END_REF]. A wearable monitoring system is proposed in [START_REF] Pandian | Wearable multi-parameter remote physiological monitoring system[END_REF] to monitor various physiological variables, such as ECG, blood pressure, and temperature. Also, the Global Positioning System (GPS) co-ordinates of patient or wearer with the acquired variables are transmitted wirelessly to a remote station.

Targeting patients with chronic high-risk heart/respiratory diseases, a wrist worn wearable medical monitoring and alert system (AMON) monitors physiological variables. For terrestrial and space applications, physiological parameters of the astronauts in space should be monitored continuously. To address the mentioned problem, a wearable system, called 'Life Guard', is proposed [START_REF] Anliker | AMON: a wearable multi parameter medical monitoring and alert system[END_REF] to monitor the health status of astronauts. The deployment of a biopatch with integrated low-power SoC prototype is proposed by Yang et al. [START_REF] Yang | Bio-patch design and implementation based on a low-power system-on-chip and paper-based inkjet printing technology[END_REF] to facilitate features, such as a three-stage front-end signal conditioning circuit, 8-bit successive-approximation-register (SAR) ADC, and a digital core. An integrated wireless ECG SoC for WBSN applications is proposed in [START_REF] Khayatzadeh | A 0.7-V 17.4-µW3-lead wireless ECG SoC[END_REF], which comprises a two-channel ECG front-end, an 8-bit SAR-ADC, a simple micro-controller, a SRAM memory, and RF-transceivers. Many ECG SoCs implementations for WBSN applications employ a microcontroller or microprocessor to establish the remote gateway [START_REF] Halin | The Life Shirt system for wireless patient monitoring in the operating room[END_REF][START_REF] Lopez | E-textile and wireless-sensor-network-based platform for healthcare monitoring in future hospital environments[END_REF]. In worst cases, there is a need for an artificial intelligence approach, integrated with wearable ECG SoC, when abnormal ECG episodes are to be detected instantly. This solution addresses diseases, like cardiac arrhythmia or silent myocardial ischemia, to be easily identified for clinical treatment. This increases the need for low cost and easy to use wearable wireless ECG sensors with integrated decision making to alert personnel. The following sections narrate about an ultralow power ECG on Chip with integrated CMOS Fuzzy Decision Making Chip that addresses the issues in existing solutions.

Wearable ECG System: With Decision Making

System Overview

The proposed health care architecture includes two parts: (a) Main unit and (b) Remote unit, as shown in Fig. 2. The Main unit contains wearable textile electrodes, designed ECG front-end chip, FDM chip, a controller, and a ZigBee transceiver. The remote unit (personal gateway) can be a mobile phone or a personal computer with an USB interface. The main unit records the ECG from wearable textile electrodes and wirelessly transfers the data to a remote unit. The designed ECG acquisition chip for low power use is described in the next sub-section. The ECG acquisition chip comprises: (1) specially designed textile electrodes for acquiring the ECG; (2) a miniature printed circuit board with ECG front end circuits; (3) Analog to Digital Conversion unit; (4) QRS Detection; and (4) System control unit. The ECG data is buffered, using low power microcontroller internal memory to minimize power consumption before wirelessly sending it to the remote unit. The main unit also performs the other tasks, such as system initialization, data buffering, and scheduling wireless communication. The Fuzzy Decision Making (FDM) chip (3×3 fuzzy controller; nine rules are accessible) takes decisions when necessary. Depending on applications, control voltages set on IC pins change the rules of fuzzy inference. The study of the Fuzzy chip is explained in detail in subsequent sections. ZigBee protocol is chosen as a wireless communication protocol (TI CC2420) to provide reasonable power consumption and adequate data rate. The prototype uses a low power TI MSP430 microcontroller for data management, wireless ZigBee baseband, and routing management. The prototype model is designed for patients, regarding comfort and ease of use, thus, not affecting regular activities of patients. In addition, the entire unit is sealed within a smart textile shirt. So, the patient can wear and remove it easily. For various medical applications, the acquired physiological variables should be analyzed continuously. The remote unit (personal gateway) can be a mobile phone or a personal computer with an USB interface. The important functions of the remote unit are receiving the data wirelessly, database management, ECG analysis, graphical user interface (GUI) interface, and customization. To avoid signal interference from other wireless devices, the remote unit has specific authentication to process the received data. In addition, there are several options in the GUI interface for customization.

ECG on Chip

A. ECG Analog Front-end Amplifier

The ECG front-end amplifier is mainly responsible for noise suppression, signal conditioning, and amplification, which comprises two phases as shown in Fig. 3, namely, low noise AFG with band pass function and a programmable gain amplifier (PGA) to amplify the acquired ECG signals (from textile electrodes), with amplitude in a few millivolts, adopting a flip-over-capacitor technique. The Low noise amplifier not only acts as a preamplifier, but also acts as a band pass filter function with bandwidth between 0.3 and 100 Hertz. In the AFG design, two switches (S1 and S2) are integrated to settle down quicker when power is applied, due to the large resistance by the pseudo-resistors. The speeding up of the AFG is done by a reset signal with an appropriate switch during startup of the system.

B. Analog to Digital Converter (ADC)

Successive Approximation Register (SAR) ADC is chosen for this WBSN application because of its moderate accuracy and low power overhead.

C. Heart Rate Calculation and QRS Detection

The morphological filter [START_REF] Peyravi | Design of an analog CMOS fuzzy logic controller chip[END_REF] is adopted to reduce the noise artifacts present in the ECG data and to detect\estimate the QRS complex details and R-R intervals. The filter comprises a pair of Opening and Closing operations, using dilation and erosion operators, which suppress peaks and valleys. The flowchart for QRS complex detection is illustrated in Fig. 5. The impacts of wandering baseline drift are eradicated by subtracting the mean result of operations (opening and closing) with the original input. The ECG samples are loaded serially into the shift register and then added/subtracted (for dilation/erosion respectively) with the structure element g(x) [START_REF] Peyravi | Design of an analog CMOS fuzzy logic controller chip[END_REF].

The results are compared continuously, using a comparator tree to find the minimum/maximum (for dilation/erosion respectively). A moving average filter (serial structured) is used to reduce the impulse noises and smooth the filtered signal. The received signals are continuously compared against the adaptive threshold and monitored to detect the R-peaks. The current threshold is updated regularly when a new Rpeak is identified. By counting the number of clocks between R peaks using a binary counter, R-R interval is measured. The Heart Rate (HR) variable is also calculated by simply counting the number of R-peaks in the last sixty seconds. A parallel-to-serial converter is integrated with the wearable system for transmitting the HR variable through the SPI interface.

D. System Control Unit and SPI Interface

System Control Unit (SCU) is solely responsible for generating the interface control signals, based on the host or main controller commands for all the blocks in ECG on-chip. Data framing, CPU interrupt handling, etc. are done by the SCU system, based on control signals, which are generated by state machine. In-order to interface the chip with various host CPUs, the System Control Unit uses an asynchronous FIFO with 8 Kb buffers. Data from the ADC and QRS block is continuously written into the FIFO at the sampling frequency of 256Hz. Based on the FIFO status, FIFO write/read controllers generate many status signals, which are "full", "nearly full", "empty", and "nearly empty." A microcontroller is employed externally to communicate with the proposed wearable device via a duplex SPI communication interface. The data link transmits QRS complex codes and ECG details with the internal FIFO status flags.

The control vector from external microcontroller is delivered to the internal control registers by the command link.

Fuzzy Decision Making Chip: Concepts, Design and Implementation

In real world worst-case scenarios, there is a need for an artificial intelligence approach, integrated with a wearable ECG SoC, for detecting abnormal ECG episodes instantly. Especially, diseases like cardiac arrhythmia or silent myocardial ischemia should be identified immediately to alert the clinicians/family members for assistance. Therefore, a Fuzzy Classifier chip meets the critical requirements of medical applications: no delay in response, reliable, high-safety, and low cost. The functional blocks of the FDM chip are detailed in the following sections. It comprises three parts: fuzzifier, inference engine, and defuzzifier. In the fuzzifier, input variables (non-fuzzy) are mapped to the input membership functions. The inference engine handles fuzzy inference, depending on the inference method. Finally, the defuzzifier is used to convert the fuzzy output values from inference engine to non-fuzzy values.

Fuzzy Interface. The implemented architecture is a two-input one-output fuzzy supervisor. Each input has three trapezoidal membership functions or linguistic terms abbreviated as L (Low), M (Medium), and H (High), while the output variable is characterized by singletons. The parameters used for determining membership functions (𝑉 %& ,𝑉 %' ,𝑉 (& ,𝑉 (' ) are calibrated by voltages applied on FDM IC pins. Since input membership functions have three parts, architecture is a 3×3 fuzzy controller, and nine rules are accessible. Depending on various applications, Control voltages set on IC pins can change these rules. The controller architecture in Fig. 6 is constructed with CMOS components, such as Membership function generator (MFG), MIN circuits and a defuzzifier (D blocks) circuit. A ramp function generation circuit is used for MFG. In fuzzy interface, three basic circuits are used: a ramp generator (RG) circuit [START_REF] Peyravi | Design of an analog CMOS fuzzy logic controller chip[END_REF], a minimum circuit, and a fuzzy complementary circuit. The membership functions for input and output variables of a controller are built, using two ramp functions. In Fig. 7, a form of trapezoidal membership function, using a ramp function and its parameters, is depicted. To construct a fuzzifier with desirable capabilities, Set 𝑣 %,' = 𝑣 %#' . A reverse triangular in the positive region of vertical axis will be formed as shown in fig. 7. By clipping this triangular area with a constant value E, a controllable membership function can be obtained.

In this case,

𝑎 = 𝑣| Q U SW = 𝑛 # -𝐸 𝑚 # = 𝑣 %#' - 𝐸 𝑘𝑣 (#' , 𝑏 = 𝑣| Q R SW = 𝐸 -𝑛 , 𝑚 , = 𝐸 𝑘𝑣 (,& -𝑣 %,' ,
Varying 𝑣 (, and 𝑣 (# results in a change in 𝑎 and 𝑏. For 𝑣 %, = 𝑣 %# , it will also be variable. The position of the membership function can be changed. Note that a trapezoidal membership function is obtained when 𝑣 (&Y 𝑣 (' and in this case, 𝑐 = 𝑣 (' and 𝑑 = 𝑣 (& . Considering these points, it is necessary that 𝑐 and 𝑑 are selected equal to 𝑣 %, and 𝑣 %# , respectively, and then by changing 𝑣 This result 𝑣 ; (8[\) specifies that the offset voltage is about 1 Volt. To compensate the offset voltage, 𝑣 ;QQ a negative level shifter circuit is necessary. The Negative shift is achieved by a fuzzy complement circuit with a reference voltage of E. The complementary membership function must be converted to an ordinary membership function, achieved by a fuzzy complementary circuit of two 𝑔 8 circuits.

From Fig. 10, assuming the reference voltage E = 0,

𝑣 (;8h = 𝑅 [ = 𝑅 𝑖 , + 𝑖 # = 𝑅 -𝑔 8 𝑣 [\ -𝑔 8 𝑣 (;8h
Therefore, this is opposite to the input voltage. The complement of the membership function is 𝐸 ≠ 0, 𝑣 (;8h = 𝐸 -𝑣 [\ 𝑖𝑓 𝑅𝑔 8 ≫ 1 Note that, in the final fuzzifier structure, E must be set to compensate offset voltage, associated with the minimum circuit. The attenuation is due to the limited gain of 𝑅𝑔 8 that is equal to -𝑅𝑔 8 =1 + 𝑅𝑔 8 . This attenuation is the same in each one of the fuzzifiers used in the controller, and the error due to attenuation does not affect fuzzy processing considerably. If the input signal has a negative DC value, then E must be chosen to be greater than the Supremum value by |𝑉 k( |. Inference Engine. With Mamdani's inference technique, the inference engine is accomplished by a set of intersection and union operations [START_REF] Pandiyan | Embedded low power analog CMOS Fuzzy Logic Controller chip for industrial applications[END_REF][START_REF] P Manikandan | Weighted fuzzy fault tolerant model predictive control[END_REF]. The Min-Product inference method is chosen for inferencing in which a minimum of two inputs can be specified. Nine two-input minimum circuits in the inference engine are needed. Therefore, the controller has two inputs with three membership functions. The Min blocks [START_REF] Pandiyan | Embedded low power analog CMOS Fuzzy Logic Controller chip for industrial applications[END_REF] and their synthesis in the complete controller structure will do the inferencing.

Defuzzification.

A novel defuzzifier is used [START_REF] Peyravi | Design of an analog CMOS fuzzy logic controller chip[END_REF][START_REF] Pandiyan | Embedded low power analog CMOS Fuzzy Logic Controller chip for industrial applications[END_REF] in which the center of the area is calculated without employing a division circuit. Therefore, it occupies a small chip area. The main idea is based on parallel conductances 𝑔 \ , stating implicitly that the output voltage of the defuzzifier circuit is the average value of the inputs. The contribution of each input to the output is weighted by the conductance 𝑔 [ that is a controllable variable. The below equation provides a non-fuzzy or defuzzifier output.

Results and Discussion

The wearable ECG sensor node system fits perfectly on a shirt. The main unit provides a versatile framework for incorporating sensing, monitoring, and information processing devices. The designed wearable device can be deployed in a variety of applications, such as public safety, health monitoring, and sports. The vital signal monitoring functionality of the smart shirt is tested in real time. The inference performance test is done, based on physical activity under various conditions. The abnormal ECG signal is measured and stored in the fuzzy inference engine. The fuzzy decision making rules are framed in such a way that, when an abnormal ECG signal is detected, an alert signal is sent promptly to the remote gateway via microcontroller. A wearable smart shirt transfers the physiological ECG signals over a wireless sensor network at the test. The following sections depict the important results of the proposed system.

ECG Acquisition

To ensure comfort, the clothing is designed from a knitted conductive textile fabric for reducing flammability. Rectangles of electrically conductive textile fabric in knitted design were stitched on the position of the pectoral muscles [START_REF] Vojtch | Wearable Textile Electrodes for ECG Measurement[END_REF]. The conductive textile fabric is realized from a blended yarn of the composite containing silver nanoparticles, which provide electrical conductivity of the yarn and the resultant knitted fabric. The content of silver nanoparticles provides corrosion resistance of textile electrodes, antibacterial and anti-allergic properties, and mechanical and electrical stability when exposed to sweat. The design of blended conductive textile fabric, made from conductive yarn, enables traditional maintenance of T-shirts (washing, ironing) and long-term stability of surface conductivity of the electrodes with a high number of wash cycles. The designed conductive textile fabrics are circular in shape, with dimensions 5 × 5 cm. Fig. 12 shows the wearable electrodes, which comprise a conductive fabric electrode pair and the wearable sensor node system placed on the wearer's chest placement. To provide a sufficient potential difference, the electrodes are positioned 100 mm apart. The ECG measurements are obtained through wearable textile electrodes (Zero Resistance, 100% Silver fiber for conductive part), and the acquired ECG signals are processed, using other modules in this health architecture for decision making.

Fuzzy Decision Making

In the FDM module, the Heart rate variability (HRV) is computed from the time series R-R intervals (R-peak to R-peak), converted into a uniformly sampled timespaced sequence. As the physiological condition (wakefulness state, sleep state, etc.) of a patient changes, the power spectral density (PSD) of heart rate differs. The lowto-high (L/H) frequency ratio is considered an effective assessment and indicator of such change, because it reflects the balancing action of the sympathetic and parasympathetic nervous-system branches. Power Spectral Density of HR variations is calculated, and the three frequency bands, such as Very low frequencies (VLF: 0-0.04 Hz), Low frequencies (LF: 0.04-0.15 Hz), and High frequencies (HF: 0.15-0. 13 shows the major difference between normal and abnormal ECG signals, noting that an abnormal ECG data has an elevated T wave.

Performance Evaluation

The status is continuously sent to the remote unit every 2 minutes or preset time in the controller. The results of the experiments, as shown in Table 1, confirmed our hypothesis that human health status can be predicted by the FDM module through extracted ECG features. Detection succeeds, based on ECG signal captured from the wearable textile electrodes. When the signal is sensed, the system detects the status, and if abnormal, an alert signal is transmitted. Measurement accuracy of Fuzzy based ECG classification confirms to be robust enough to perform over 95% successful early detections. Therefore, the proposed system can make decisions, based on the acquired ECG data. Fig. 14 depicts the designed graphical user interface for the proposed architecture. Timing of the early detection capability of each system is also evaluated during the tests.

Concluding remarks

A wireless ECG on a chip with an integrated Fuzzy Decision making system is proposed for real-time ECG health monitoring. The proposed wearable device is small, user-friendly, has a long battery life, and is capable of wirelessly transmitting ECG data continuously to a remote station for detailed diagnosis. The FDM chip is integrated with ECG on Chip to take the decisions for alerting the patients when necessary. The designed FDM responds immediately when anomalies are found in ECG data. The proposed device has already been tested with a reference high-quality measurement system for verification of accuracy and showed that the accuracy of the proposed device is good enough, and the variation in key ECG parameters obtained from the proposed device and the reference device is acceptable for clinical usage.

Fig. 1 .

 1 Fig. 1. Graphical Illustration of wearable health care monitoring

Fig. 2 .

 2 Fig. 2. Block diagram of proposed healthcare architecture

Fig. 3 .

 3 Fig. 3. Typical circuit diagram of ECG Front-end low noise amplifier

Fig. 4

 4 depicts the architecture of the SAR ADC, adopted from literature. The analog ECG output is driven directly by the preceding buffer stage, without the need of an additional hold amplifier, sampled through a bootstrapped switch and held in the capacitive 12 bit DAC, and is then used by open-loop Sample/Hold. The reason for open-loop Sample/Hold is to obtain low power, low cost, fast settling, and less offset error. The obtained analog ECG data are being compared with a reference (REF) and then levelshifted by the DAC. The fixed reference REF helps to compensate the dynamic offset error at the comparator. An on-chip crystal oscillator is used to drive the logic and timing sequence for achieving low power consumption and low jitter. The resultant digital codes are passed to a System Control Unit (SCU) after level conversion and to QRS complex detector for data processing.

Fig. 4 .

 4 Fig. 4. Schematic Architecture of Successive Approximation ADC

Fig. 5 .

 5 Fig. 5. Flow process for QRS Detection and HRV Calculation

Fig. 6 .

 6 Fig. 6. Block diagram of Fuzzy Classifier

Fig. 7 .Fig. 8 .

 78 Fig. 7. Trapezoidal membership function and its parameters

Fig. 9 .

 9 Fig. 9. Schematic representation of Minimum Circuit Minimum circuits can be used to clip the extra curves and then reverse it by a fuzzy complementary circuit (FCC). Fig.10. illustrates the circuit diagram of a fuzzy complementary circuit. In FCC, the two inputs are connected to the gates of the transistors. A multi-input minimum circuit with over two transistors is needed in applications, such as three-input fuzzy controllers. As illustrated in Fig.9, the output voltage 𝑣 ;(8[\) always takes the smaller value of two inputs 𝑣 [\, and 𝑣 [\# with a positive offset voltage 𝑣 ;QQ/a< . 𝑣 ;(8[\) = min( 𝑣 𝑖𝑛1 , 𝑣 𝑖𝑛2 ) + 𝑣 𝑜𝑓𝑓𝑠𝑒𝑡

Fig. 10 .

 10 Fig. 10. Schematic diagram of Fuzzy Complementary Circuit

  𝑉 kaQMll = 𝑔 , 𝑉 , + 𝑔 # 𝑉 # + ⋯ + 𝑔 \ 𝑉 \ 𝑔 , + 𝑔 # … … + 𝑔 \ 𝑔 k/ = 𝑘 𝑣 :/ -𝑣 < ; 𝑘 = 1 2 𝜇𝑐 ;p 𝑊 𝐿 Level shifter circuit (LSC) is used to compensate offset voltage [8]. The complete schematic diagram of defuzzifier is depicted in Fig.11.

Fig. 11 .

 11 Fig. 11. Schematic Illustration of Defuzzifier

Fig. 12 .

 12 Fig. 12. Placement of wearable textile electrodes

Fig. 13 .

 13 Fig. 13. Measured sample ECG data for Inference Engine

Fig. 14 .

 14 Fig.14. Designed Graphical User Interface for testing and measurements

  RG circuit, the output current 𝑖 * is a function of 𝑣 , and 𝑣 # . Considering 𝐼 // fixed, and M3, M4, M5, and M6 are matched, The RG circuit can generate both a positive and negative slope ramp function. Suppose 𝑣 (' = 0, 𝑣 (& and 𝑣 %' are constant, then 𝑖 * = 𝑘 𝑣 %& -𝑣 %' 𝑣 & = 𝑘𝑣 (& 𝑣 %' -𝑘𝑣 (& 𝑣 %' = 𝑚𝑣 %& -𝑛 Where, 𝑚 = 𝑘𝑣 (& , 𝑛 = 𝑘𝑣 (& 𝑣 %' Thus, a positive slope ramp is generated. Similarly, if 𝑣 (& = 0, and let 𝑣 (' , 𝑣 %' be constant, then 𝑖 * = 𝑘 𝑣 %& -𝑣 %' -𝑣 (' = -𝑘𝑣 (' 𝑣 %& + 𝑘𝑣 (' 𝑣 %' = -𝑚𝑣 %& -𝑛 Therefore, by changing 𝑣 %& , 𝑣 %' and 𝑣 ( , different ramp functions are generated. It is evident that the output voltage of RG circuit 𝑣 * = 𝑅 ;M< 𝑖 ;M< Where 𝑅 ;M< is output resistance.Two ramp functions 𝑓 , and 𝑓 # with positive and negative slopes, respectively, are shown in Fig.7. Assuming RG circuit has generated these functions, 𝑓 , and 𝑓 # can be When 𝑓 , = 𝑓 # , can be written as 𝑚 , 𝑐 -𝑛 , = -𝑛 # + 𝑚 # 𝑐

	equated as below
	𝑖 * = 𝑖 1 + 𝑖 3 -𝑖 5 + 𝑖 6 = 𝑔 81 𝑓 , = 𝑚 , 𝑣 -𝑛 , 𝑣 % 2 -𝑔 83 𝑓 # = 𝑛 # -𝑚 # 𝑣 = 𝑣 % 2 𝐼 , 𝑣 :/;1 -𝑣 < -𝐼 # 𝑣 :/;3 -𝑣 < + 𝑣 :/;5 -𝑣 < 𝑣 % 2 -𝑔 85 𝐼 , -To construct a tunable membership function, 𝑓 , 0 = -𝑛 , = -𝑘𝑣 %,' 𝑣 (,& 𝑣 :/;3 -𝑣 < 𝑣 % 2 + 𝑔 86 𝐼 # = 𝑣 % 2 2𝐼 , 𝑣 :/;1 -𝑣 < -𝑓 # 0 = 𝑛 , = 𝑘𝑣 %#' 𝑣 (#' 2𝐼 # 𝑣 :/;3 -𝑣 < , 𝑎 = 𝑣| Q R S* = 𝑛 , 𝑚 , = 𝑘𝑣 %,' 𝑣 (,& 𝑘𝑣 (,& = 𝑣 %,' ,	𝑣 % 2
	Where, all 𝑣 :/; ′𝑠 are gate to source voltages in quiescent point, and also 𝐼 , = 𝐼 // @ A # 𝑣 :/;, -𝑣 < -𝐼 // @ A 𝑏 = 𝑣| Q U S* = 𝑛 # 𝑚 # = 𝑘𝑣 %#' 𝑣 (#& = 𝑣 %#' , 𝑘𝑣 (#& # , 𝐼 # = 𝑣 :/;# -𝑣 < Therefore, Using previous equations, assuming M1 and M2 are also matched, then 𝑖 * = 𝐼 // 𝑣 :/;, -𝑣 < 1 𝑣 :/;1 -𝑣 < + 1 𝑣 :/;3 -𝑣 < 𝑐 = 𝑛 , -𝑛 # 𝑚 , -𝑚 # 𝑣 %,' 𝑣 (,& -𝑣 %#' 𝑣 (#' = 𝑣 (,& -𝑣 (#' With this value for 𝑐, 𝑓 𝑐 = 𝑓 , 𝑐 𝑣 % 𝑣 , @ CDEF '@ G approximately constant. = 𝑓 # 𝑐 = 𝑘𝑣 (,& 𝑣 (#' 𝑣 (,& -𝑣 (#' 𝑣 %,' -𝑣 %#'	+	, @ CDEH '@ G	is
	Therefore, 𝑖 * = 𝑘𝑣 , 𝑣 #
	Where,
	𝑘 =	𝐼 // 𝑣 :/;, -𝑣 <	1 𝑣 :/;1 -𝑣 <	+	1 𝑣 :/;3 -𝑣 <
	Where,
		𝑚 = 𝑘𝑣 (' , 𝑛 = 𝑘𝑣 (' 𝑣 %'

(

Assuming 𝑣 ( is set to be a constant value, hence 𝑣 :/;, -𝑣 < is constant. Also, changes of 𝑣 :/;1 -𝑣 < and 𝑣 :/;3 -𝑣 < are in opposite directions. So

  5 Hz), have been utilized. The features extracted from HRV and PSD are used to feed the fuzzy logic engine that computes epoch-by-epoch (30 or 60 seconds per period) inferences. The fuzzy inference rules are based on the observed details of normal and abnormal ECG signals. The inputs of FDM chip are details of QRS complex and PSD results. The ranges of membership functions are tunable by changing the voltages of FDM IC pins, which is done by the developer via microcontroller.The FDM chip provides the index values (i.e., defuzzified output in the range of 0 -2), which is sent to the microcontroller. Hence, there are output states, such as normal, sleep onset/fatigue, and abnormal, decoded by microcontroller unit. A set of meaningful rules has been framed. The following are the strongest:IFHR Variability is Low AND LF/HF ratio is Medium THEN the Output signal is SLEEP_ ONSET IF HR Variability is High AND LF/HF ratio is High THEN the Output signal is NOR_WAKE IF HR Variability is Low AND LF/HF ratio is Low THEN the Output signal is DROWSY Fig.

Table 1 .

 1 Performance Evaluation of Fuzzy Decision Making in the proposed system

	Rule-Check	Clinical datasets
	Number of	Number of	Number of data	Accuracy
	data sets	data sets	sets wrongly	(%)
	used for	correctly	classified
	testing	classified
	Drowsiness 21	19	2	90
	Sleep Onset 19	18	1	94

Acknowledgement

This research was financially supported by International Society of Automation (ISA) Educational Foundation Scholarship 2014. We would like to show our heartfelt gratitude to editors and reviewers for sharing their pearls of wisdom with us during manuscript preparation. We also thank Natarajan Sivaraman, Asst. Prof., Dept. of ICE, PSG Tech for the valuable comments that greatly improved the manuscript.


Raimund Ubar

Lembit Jürimägi
email: lembit.jyrimagi@gmail.com

Elmet Orasson

Jaan Raik

Fault Collapsing in Digital Circuits using Fast Fault Dominance and Equivalence Analysis with SSBDDs

Keywords: combinational circuits, fault collapsing, fault equivalence and dominance, Binary Decision Diagrams, lower and higher bounds

The paper presents a new method and an algorithm for structural fault collapsing to reduce the search space for test generation, to speed up fault simulation and to make the fault diagnosis easier in digital circuits. The proposed method is based on hierarchical topology analysis of the circuit description at two levels. First, the gate-level circuit will be converted into a macrolevel network of Fan-out Free Regions (FFR) each of them represented as a special type of structural BDD. This conversion procedure represents as a sideeffect the first step of fault collapsing, resulting in a compressed Structurally Synthesized BDD (SSBDD) model explicitly representing the collapsed set of representative fault sites. The paper presents an algorithm which implements a complementary step of further fault collapsing. This algorithm is carried out at the macro-level FFR-network by topological reasoning of equivalence and dominance relations between the nodes of the SSBDDs. The algorithm has linear complexity and is implemented as a continuous scalable fault eliminating procedure. We introduce higher and lower bounds for fault collapsing and provide statistics of distribution of fault collapsing results over a broad set of benchmark circuits. Experimental research has demonstrated considerably better results of structural fault collapsing in comparison with state-of-the-art.

Introduction

Fault collapsing is a procedure which is applied to reduce the number of faults of a given circuit to be targeted for testing purposes. Using a reduced set of only representative faults instead of a full set of faults has the goal to minimize the efforts in many test related tasks like test pattern generation, fault simulation for test quality evaluation, fault diagnosis, circuit testability evaluation etc. The methods of fault collapsing are classified as structural and functional. Structural fault collapsing uses only the topology of the circuit whereas functional fault collapsing uses the circuit functional properties inherent in the circuit.

There are two classical ways used for structural fault collapsing: fault equivalence based and fault dominance based collapsing [START_REF] Bushnell | Essentials of Electronic Testing[END_REF]. A fault f j is said to dominate a fault f i if every test that detects f i also detects f j . If f j dominates f i , only f i needs to be considered during test generation. When two faults dominate each other, they are called equivalent. If two faults are equivalent, only one of them needs to be considered during test gene-ration or fault diagnosis. Structural fault collapsing uses the topology of the circuit structure. For example, a stuck-at 0 fault (SAF y/0) at the output y of AND gate is equivalent to all of the SAF x/0 faults at its inputs x i . In a similar way, SAF y/1 at the output of AND gate dominates all the input SAF x/1 faults. The classical structural approaches to fault collapsing are based on gate-level circuit processing. An approach based on fault-folding was introduced in [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF] for structural collapsing faults, using the iterative analysis of gate fault equivalence and dominance relations. Since structural fault collapsing is very fast, it is employed in many Automated Test Pattern Generators (ATPG) [START_REF] Niermann | HITEC: A Test Generation Package for Sequential Circuits[END_REF][START_REF] Kelsey | An Efficient Algorithm for Sequential Circuit Test Generation[END_REF].

Functional fault collapsing uses the circuit's functional information to establish equivalence and dominance relations. Two faults are functionally equivalent if they produce identical faulty functions [START_REF] Raja | Using Hierarchy in Design Automation:The Fault Collapsing Problem[END_REF] or we can say, two faults are functionally equivalent if we cannot distinguish them at the Primary Outputs (PO) with any input test vector [START_REF] Veneris | Functional Fault Equivalence and Diagnostic Test Generation in Combinational Logic Circuits Using Conventional ATPG[END_REF]. Functional fault collapsing is generally regarded as very difficult to compute because it deals with the whole function of the circuit under test. In [START_REF] Lioy | Advanced Fault Collapsing[END_REF] it has been shown that the algorithmic complexity for identifying functionally equivalent faults is similar to that of ATPG.

Approximate fault collapsing via simulation has been proposed in [START_REF] Al-Assad | Simulation Based Approximate Global Fault Collapsing[END_REF]. In [START_REF] Pomeranz | Level of Similarity: a Metric for Fault Collapsing[END_REF], a metric called level of similarity has been introduced and is efficiently used to improve the level of approximation. The fault collapsing suffers from the danger that if a fault in the collapsed fault set remains undetected then all other faults equivalent or dominating this fault removed from the collapsed fault set remain undetected as well. In [START_REF] Pomeranz | Safe Fault Collapsing Based on Dominance Relations[END_REF], a safety parameter s to restrict the use of the dominance relation is introduced, and a safe fault collapsing method with a level of safety s is proposed.

The potentials of hierarchical fault collapsing were discussed in [START_REF] Hahn | A Hierarchical Approach to Fault Collapsing[END_REF]. It was shown that hierarchical approach to fault collapsing gives more possibilities to increase the efficiency compared to the non-hierarchical one. An algorithm based on transitive closures on the dominance graphs has been proposed [START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF][START_REF] Sethuram | Fault Nodes in Implication Graph for Equivalence Dominance Collapsing, and Identifying Untestable and Independent Faults[END_REF], which enables more efficient hierarchical fault collapsing. It is a graph theoretic, fault independent and polynomial technique for functional fault collapsing.

In [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF], functional dominance has been used to collapse the fault sets. However, this technique requires quadratic number of ATPG runs to obtain the collapsed fault set. An improvement was proposed in [START_REF] Sandireddy | Diagnostic and Detection Fault Collapsing for Multiple OUtput Circuits[END_REF], which has the linear complexity regarding the number of ATPG runs. Since ATPG itself is used for learning functional dominance relations, both these techniques are suitable for small circuits only, but they can be helpful when combined with hierarchical fault collapsing. In [START_REF] Lioy | Advanced Fault Collapsing[END_REF] two theorems were introduced based on unique requirements and D-Frontiers of faults to extract equivalence and dominance relations. Similar approach was used in [START_REF] Amyeen | Fault Equivalent Identification in Combinational Circuits Using Implication and Evaluation Techniques[END_REF] based on the dominator theory for identifying more functionally equivalent fault pairs. In [START_REF] Vimjam | Efficient Fault Collapsing via Generalized Dominance Relations[END_REF] a generalized dominance approach requires similar or lower run-times than that of [START_REF] Lioy | Advanced Fault Collapsing[END_REF].

A collapsed fault set helps generating smaller test sets for achieving the desired fault coverage, and it contributes to fault diagnosis as well. Since fault diagnosis deals with fault pairs, a linear reduction of the number of faults would result in a quadratic reduction of the target pairs.

In [START_REF] Raja | Using Hierarchy in Design Automation:The Fault Collapsing Problem[END_REF][START_REF] Sandireddy | Diagnostic and Detection Fault Collapsing for Multiple OUtput Circuits[END_REF], a novel diagnostic fault equivalence and dominance technique was proposed. A new method for fault collapsing for diagnosis called dominance with subfaults was proposed in [START_REF] Adapa | Sub-Faults Identification for Collapsing in Diagnosis[END_REF]. The method allows reducing the diagnosis search space. A framework where equivalence and dominance relations are defined for fault pairs is introduced in [START_REF] Pomeranz | Equivalence and Dominance Relations Between Fault Pairs and Their Use in Fault Pair Collapsing for Fault Diagnosis[END_REF]. A fault pair collapsing is described, where fault pairs are removed from consideration under diagnostic fault simulation and test generation, since they are guaranteed to be distinguished when other pairs are distinguished. A technique to speed-up diagnosis via dominance relations between sets of faults using functionbased techniques was proposed in [START_REF] Adapa | Accelerating Diagnosis via Dominance Relations between Sets of Faults[END_REF]. Due to the high memory and time complexity this approach is applicable for small circuits only. All the listed techniques are fault oriented approaches, i.e. they consider a fault-pair at a time and use ATPG for identification of equivalence or dominance relations. In [START_REF] Pomeranz | Safe Fault Collapsing Based on Dominance Relations[END_REF], a dynamic fault collapsing procedure is presented for fault diagnosis, where the faults are collapsed during the diagnostic test pattern generation contrary to the traditional static approaches described above where the faults are collapsed before test generation.

One of the main limitations of the described methods is that there is no evidence that investing more effort in fault collapsing reduces the total test generation time [START_REF] Pomeranz | Safe Fault Collapsing Based on Dominance Relations[END_REF]. The reason is that most of the methods are using ATPG itself as a tool for fault collapsing, or they are usable only for small circuits because of the high computing complexity.

In this paper we concentrate on the structural fault-independent fault collapsing based on the topology analysis of the circuit. We target the minimal necessary set of representative faults as objectives for both, test generation and fault simulation. To cope with the complexity problem in case of big circuits, we use a hierarchical approach to structural fault collapsing, which is based on the topology analysis of the circuit at two levels -gate-and macro-levels, where the Fan-out-Free Regions (FFR) are regarded as macros. The proposed method is characterized at both levels by linear complexity which allows achieving high speed in fault collapsing, and provides smaller collapsed representative fault sets compared to other known structural methods. Due to low complexity, the method is well scalable and is therefore usable for large circuits where the functional fault collapsing methods give up because of the complexity.

The approach we propose consists of two consecutive procedures. During the first procedure, fault collapsing is carried out at the gate level by superposition of Binary Decision Diagrams (BDD) [START_REF] Bryant | Graph-Based Algorithms for Boolean Function Manipulation[END_REF] of logic gates with the main goal of constructing a higher macro-level model of the circuit in form of Structurally Synthesized BDDs (SSBDD) [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF][START_REF] Ubar | Design and Test Technology for Dependable Systems-on-Chip[END_REF] where to each FFR an SSBDD corresponds. The fault collapsing can be regarded here as a side-effect (byproduct) of the SSBDD model synthesis. The second procedure, complementary part of the approach, is carried out at the higher macro-level by topological analysis of SSBDDs. Both parts of the fault collapsing procedure have linear complexity. It has been shown that SSBDDs can be efficiently used for fault simulation, outperforming in the speed state-of-the-art fault simulators [START_REF] Ubar | Parallel X-Fault Simulation with Critical Path Tracing Technique[END_REF][START_REF] Gorev | Fault Simulation with Parallel Exact Critical Path Tracing in Multiple Core Environment[END_REF]. In this paper we show the possibility of additional fault collapsing using SSBDDs, which in turn can lead to further speed-up of fault simulation.

The paper is organized as follows. In Section 2 we give an overview of SSBDDs and in Section 3 we describe the synthesis of SSBDDs as the first step of gate-level fault collapsing. Section 4 presents the main theoretical concepts for the analysis of equivalence and dominance relations between the faults in the higher level FFRnetworks modeled with SSBDDs, and Section 5 describes the algorithm of fault collapsing with SSBDDs. In Section 6, lower and higher bounds for fault collapsing are given. Section 7 presents experimental data, and Section 8 concludes the paper.

Structurally Synthesized BDD

Binary Decision Diagrams (BDD) have become by today a state-of-the-art data structure in VLSI CAD for representation and manipulation of Boolean functions. BDDs were first introduced for logic simulation in [START_REF] Lee | Representation of Switching Circuits by Binary Decision Diagrams[END_REF], and for test generation in [START_REF] Ubar | Test Generation for Digital Circuits Using Alternative Graphs[END_REF][START_REF] Akers | Binary Decision Diagrams[END_REF]. In 1986, Bryant proposed a new data structure called Reduced Ordered BDDs (ROBDDs) [START_REF] Bryant | Graph-Based Algorithms for Boolean Function Manipulation[END_REF]. He showed simplicity of the graph manipulation and proved the model canonicity that made BDDs one of the most popular representations of Boolean functions. This model, however, suffers from the memory explosion problem, which limits its usability for large designs. Moreover, it cannot be used as a model for representing structural information about the design like representation of faults directly in the model. In [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF][START_REF] Ubar | Test Generation for Digital Circuits Using Alternative Graphs[END_REF][START_REF] Ubar | Multi-Valued Simulation of Digital Circuits with Structurally Synthesized BDDs[END_REF], Structurally Synthesized BDDs (SSBDDs) were proposed with the goal to represent the structural features of circuits. The most significant difference between the function-based BDDs [START_REF] Bryant | Graph-Based Algorithms for Boolean Function Manipulation[END_REF] and SSBDDs [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF] is the method how they are generated. While BDDs are generated on the functional basis by Shannon's expansions, which handle only the Boolean function of the logic circuit, the SSBDD models are generated by a superposition procedure that extracts both, functions and data about structural signal paths of the circuit. The linear complexity of the SSBDD model results from the fact that a digital circuit is represented as a system of SSBDDs, where for each FFR a separate SSBDD is generated. SSBDDs are generated by iterative superposition of library BDDs for simple or complex gates, guided by the structure of the given circuit. To avoid the explosion of the complexity of the SSBDD model, and to keep its size as minimal as possible, the superposition of BDDs is stopped at fan-out stems of the circuit. Using this restriction, to each FFR in the circuit an SSBDD will be created where a signal path in the FFR corresponds to each node in an SSBDD. Example 1. An example of a combinational circuit and its SSBDD is depicted in Fig. 1. The SSBDD represents an FFR of the circuit obtained after cutting all the input fan-out branches of the circuit. This FFR can be described by the following Boolean expression:

𝑦 = 𝑓 𝑋 = 𝑥 ! 𝑥 !" ∨ 𝑥 !! 𝑥 ! ∨ 𝑥 ! 𝑥 ! ∨ 𝑥 !" 𝑥 !" 𝑥 !" ∨ 𝑥 !" 𝑥 ! 𝑥 !" ∨ 𝑥 !" 𝑥 !"
The non-terminal (internal) nodes of the SSBDD are labeled by the input variables of the FFR. To differentiate the fan-out branch variables from the fan-out stem variable we introduce for each of them a second subscript. The node variables may be inverted. Example 2. For the circuit in Fig. 1 with function y = f(X) the output signal y for the given input pattern X t in Fig. 2 will be y = 1. During simulation of this pattern on the SSBDD, the following nodes are traversed: x 1 , x 22 , x 3 , ¬x 71 , x 81 , #1 (shown by bold lines).

SSBDD model has several features that make it attractive compared to other commonly used mathematical models, such as conventional BDDs or gate-level netlists [START_REF] Jutman | SSBDDs: Advantageous Model and Efficient Algorithms for Digital Circuit Modeling[END_REF][START_REF] Ubar | Overview about Low-Level and High-Level Decision Diagrams for Diagnostic Modeling of Digital Systems[END_REF]. The worst-case complexity (time) of generating SSBDD model from a circuit's netlist is linear in respect to the number of gates, while it is exponential for common BDDs. The size of the SSBDD model is always linear in respect to the circuit size (BDDs can be of exponential size). Compared to the gate-level representa-tion, SSBDDs help to reduce the complexity of the circuit by representing them as FFR (SSBDD) networks whereas the algorithms of processing the network components do not need dedicated treatment of the components described usually by design libraries. Moreover, instead of considering each gate separately, it deals with macros -FFRs represented by SSBDDs.

The most important feature of the SSBDD model is that it preserves structural information about the circuit while traditional BDDs do not. This is why differently from traditional BDDs, SSBDDs support structural test generation [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF][START_REF] Ubar | Test Generation for Digital Circuits Using Alternative Graphs[END_REF] and fault simulation [START_REF] Ubar | Parallel X-Fault Simulation with Critical Path Tracing Technique[END_REF][START_REF] Gorev | Fault Simulation with Parallel Exact Critical Path Tracing in Multiple Core Environment[END_REF][START_REF] Ubar | Multi-Valued Simulation of Digital Circuits with Structurally Synthesized BDDs[END_REF] for gate-level structural faults in terms of faulty signal paths with representing the faulty paths explicitly in the model. Each node in the SSBDD represents a signal path in the corresponding circuit, and the faults of the nodes represent the faults in signal paths.

For example, the SSBDD in Fig. 1 consists of 14 internal nodes where each of them represents a corresponding signal path of the total 14 paths in the circuit in Fig. 1 (the correspondence is shown by the variables x where x i denote input signals, and x ij denote the signals at the fan-out branches). The one-to-one mapping between the nodes in SSBDD and the paths in the circuit is the result of the SSBDD synthesis from the netlist of the given circuit. The synthesis process is presented in Section 3.

Note, that the SSBDD model in Fig. 1 represents only the FFR of the circuit. The faults of the input fan-out stems x 2 , x 6 , x 7 and x 8 should be handled separately, either by introducing trivial single-node BDDs to represent the input fan-out stems, or by modeling the stem faults as multiple faults in the nodes which represent the fan-out branches.

Synthesis of SSBDDs

Consider first, the following graph theory related definitions of the BDDs (SSBDDs). We use the graph theory notations instead of traditional ite expressions [START_REF] Bryant | Graph-Based Algorithms for Boolean Function Manipulation[END_REF] because all the test related procedures based on SSBDDs are based on the topological reasoning rather than on symbolic manipulations as is traditionally the case for BDDs. Definition 1. A BDD that represents a Boolean function y=f(X), X = (x 1 ,x 2 , … , x n ), is a directed acyclic graph G y = (y,M,Γ,X) with a set of nodes M and mapping Γ from M to M. Γ(m) ⊂ M denotes the set of successor nodes of m ∈ M, and Γ - 1 (m) ⊂ M denotes the set of predecessor nodes of m. M consists of two types of nodes: internal (non-terminal) M N and terminal M T . For terminal nodes m T we have Γ (m T ) = ∅. There is a single node m 0 ∈ M where Γ -1 (m) = ∅ called the root node. A terminal node m T ∈{m T,0 , m T,1 } is labeled by a constant x(m T ) ∈{0,1} and is called leaf, while all the nodes m ∈ M N are labeled by Boolean variables x(m) ∈ X, and have exactly two successor nodes Γ (m) = {m 0 , m 1 } .

Definition 2. We say, the edge l(m, m e ) between nodes m and m e ∈ Γ (m) is activated when the node variable x(m) is assigned to one of the values e ∈ {0,1}. We say, a path l(m i , m j ) between the nodes m i and m j is activated if all the edges which form the path are activated. Definition 3. We say that a BDD G y = (y,M,Γ,X) represents a Boolean function y=f(X), iff for every possible vector X t ∈ {0,1} n , a path l(m 0 , m T ) is activated so that y = f(X t ) = x(m T ).

Fig. 3. Superposition of two SSBDDs

The main idea of superposition of BDDs as the basis procedure of SSBDDs proposed first in [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF][START_REF] Ubar | Test Generation for Digital Circuits Using Alternative Graphs[END_REF], is illustrated in Example 3.

Example 3. Let us have in Fig. 3 a network of two components y and x 3 in Fig3, connected by the wire x 3 . The components implement the following functions:

𝑦 = 𝑥 ! 𝑥 ! ∨ 𝑥 ! ∨ 𝑥 ! 𝑥 ! , 𝑥 ! = 𝑥 ! 𝑥 ! ∨ 𝑥 ! 𝑥 !
The components y and x 3 are represented by the SSBDDs y and x 3 , respectively. For simplicity, we have omitted in SSBDDs the terminal nodes, with introducing the agreement that leaving the graph to the right means entering the terminal node #1, and leaving the graph down means entering the terminal node #0. Superposition of the two graphs y and x 3 is equivalent of merging the two components y and x 3 into a single component y* which implements the function:

𝑦 * = 𝑥 ! 𝑥 ! ∨ 𝑥 ! 𝑥 ! ∨ 𝑥 ! 𝑥 ! ∨ 𝑥 ! 𝑥 !
To carry out this operation we have to substitute the node x 3 in the graph y with the graph x 3 . To do that, we:

(1) connect the incoming edges of the node x 3 in graph y with the root node x 6 of graph x 3 ; (2) connect all the nodes in the graph x 3 , which enter into #1, with the right-hand neighbor of x 3 in graph y and (3) connect all the nodes in the graph x 3 , which enter into #0, with the down-hand neighbor of x 3 in graph y. The new SSBDD y* represents the function of the network with two merged components y and x 3 .

Let us have, in general case, a gate-level circuit C where each gate is represented by an elementary BDD. The procedure of generating the SSBDD model G(C) for C starts from the BDD of an output gate, and uses iteratively the superposition procedure where a node in a BDD is replaced by another BDD [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF].

Consider two BDDs, G y for the output gate g y ∈ C with output y, and G x for the gate g x connected to the input x of g y . Let us call further, for simplicity, a node in a BDD labeled by a variable z as a "node z". By substitution of the node x in G y with the BDD G x we create from G y a new SSBDD G y ' which represents now the extended network consisting of g y and g x . We call the new graph as SSBDD because the new nodes z in G y ' which belonged to G x represent the signal paths from the inputs z of the gate g x via the connection line x between the two gates up to the output y of the gate g y .

The procedure of the superposition of a node m labeled by x in BDD G y with BDD G x can be presented as follows.

Procedure 1. Superposition of BDDs [START_REF] Bushnell | Essentials of Electronic Testing[END_REF] The node m labeled by x is removed from G y .

(2) All the edges in G x connected to terminal nodes m T,e in G x will be cut and then connected, respectively, to the successors m e of the node m in G y .

(3) All the incoming edges of m in G y will be now incoming edges for the root node m 0 in G x .

By applying Procedure 1 for two BDDs, we reduce the current model by one node and by one BDD. Suppose, the label variable x of a node m in a BDD G y corresponds to the output of the gate g x with k output branches. This means that the variable x is used as a label for k different nodes in the initial model as a set of BDDs. If we would proceed the superposition of graphs beyond the fan-out stem x, and would try to replace all the k nodes labeled by x with the BDD G x , the complexity of the model would increase instead of reduction, i.e. the k nodes will be replaced by k BDDs G x . Therefore, to keep the complexity of the final SSBDD model linear with the size of the circuit, and to reach the maximum compression of the initial model given as a set of elementary BDDs, we generate SSBDDs only for FFRs. Hence, at each fan-out stem we start a new superposition procedure for the next FFR. Definition 4. A BDD which is constructed for a given FFR by Procedure 1 is called structurally synthesized BDD (SSBDD).

Corollary 1. It is easy to conclude from Procedure 1 that in the SSBDD G y generated for the given FFR C y with a function y = f (x 1 ,x 2 , … , x n ), there are exactly n nodes with labels x 1 ,x 2 , … , x n , and the node m with label x i represents a unique signal path in C y from the input x i to the output y.

Corollary 2. Since all the SAF faults at the inputs of FFR according to the approach of fault folding [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF] form the collapsed fault set of the FFR, and since all these faults are represented by the faults at the nodes of the corresponding SSBDD, then the creation of the SSBDD is equivalent to the fault collapsing procedure similar to fault folding.

Theorem 1. Let G(C) be the SSBDD model generated for the combinational circuit C by Procedure 1. Then, any set of tests that checks all the SAF faults at the nodes of G(C) checks all the SAF faults in C.

Proof. The proof follows from Corollaries 1 and 2, and from Theorem 5 in [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF].

Unlike the traditional gate level approaches to test generation and fault simulation that use the collapsed fault list apart from the simulation model, the SSBDD based test generation and fault simulation are carried out on the macro-level (FFRs as macros) with direct representation of the faults in the model. Therefore there is no need for separate fault list to be used during test generation and fault simulation.

Example 4. The node x 22 in the SSBDD represents the path from x 22 to y in the circuit shown by bold lines in Fig. 1. On the other hand, the stuck-at faults SAF y/0 and SAF y/1 dominate the faults x 22 /0 and x 22 /1, respectively. The same dominance relation stands for all the faults along the bold path from x 22 to y, regarding to the faults at x 22 . From this dominance relation, it results that all the faults along the signal path from x 22 to y, except x 22 /0 and x 22 /1, can be collapsed. The two faults at x 22 will form the representative fault subset for the full signal path from x 22 to y. But, exactly these faults are represented in the SSBDD as the faults of the node x 22 .

From above it follows that the SSBDD model can be regarded as the model where all the collapsed faults are removed and the fault sites are not visible either. This fault collapsing result is similar to that of fault folding method presented in [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF].

The minimum size of SSBDDs, generated with Procedure 1 is always fixed and determined by the circuit structure. Let us denote N SSBDD as the number of nodes in the SSBDD model, as the size characteristic of SSBDDs. Let N Signals be the number of lines, and N G is the number of gates in the circuit represented by SSBDD. In [START_REF] Amyeen | Fault Equivalent Identification in Combinational Circuits Using Implication and Evaluation Techniques[END_REF] it has been shown that the number of nodes in SSBDDs can be calculated as

𝑁 !!"## = 𝑁 !"#$%&' -𝑁 !
Since a digital circuit can be represented both by gate-level and by FFR-level SSBDDs, then in order to compare the gain in fault collapsing we get from translating the gate level SSBDD into FFR-level SSBDD, let us use the same units for measuring the size of SSBDDs in both cases -the number of SSBDD nodes in the model.

Denote s -as the number of inputs of the circuit, s 0 -as the number of inputs with no fan-outs , s 1 -as the number of internal lines with no fan-outs, s k -as the number of nets in the circuit with k fan-outs (k >1), n -as the number of outputs, and m -as the maximum number of fan-out branches over all fan-out stems in the circuit.

In [START_REF] Mironov | Lower Bounds of the Size of Shared Structurally Synthesized BDDs[END_REF] we have developed the following estimations for the sizes of SSBDDS for the gate-level N gate and for FFR-level N SSBDD cases:

𝑁 !"#$ = 𝑠 ! + 𝑠 ! + 𝑠 ! 𝑘 + 1 ! !!! 𝑁 !!"!! = 𝑠 + 𝑠 ! 𝑘 + 0 ! !!!
Since in both cases for the stuck-at fault model, the number of nodes must be doubled to get the number of faults, then the ratio N gate / N SSBDD will characterize the gain in fault collapsing as the side-effect of FFR-level SSBDD synthesis from the initial gate-level SSBDD model, and the subtraction N gate -N SSBDD gives the exact number of collapsed faults thanks to the SSBDD synthesis.

Example 5. For the FFR of the circuit and its SSBDD in Fig. 1 we get N gate = 30 and N SSBDD = 18. The values of the arguments of the formulas for N gate and N SSBDD are depicted in Table 1. Hence, the gain in the SSBDD sizes, in this example, is 1.7, and the number of collapsed faults is 12. Note, the SSBDD with 14 nodes in Fig. 1 represents only the FFR part of the circuit. To get the full FFR-level SSBDD model, we have to include 4 single node SSBDDs for representing the 4 fan-out inputs in the circuit. To summarize, the procedure of SSBDD synthesis can be regarded as the first part of fault collapsing for the given circuit. In the next section we will discuss the possibility of additional fault collapsing directly on the SSBDD model.

Fault Equivalence and Fault Dominance on the SSBDD Model

The second part of fault collapsing will consist of the processing of the SSBDD model with the goal to find additional set of faults which may be collapsed using the equivalence and dominance relationship on the SSBDD level. Since the nodes of SSBDDs represent signal paths on the gate-level circuit then each node related fault on the SSBDD to be collapsed is equivalent to all the related gate-level faults on the signal path represented by the node. Whereas the first part of fault collapsing was carried out by tracing the signal paths in the gate-level circuit level, then the second part concentrates on the path analysis at the higher FFR-level by tracing the paths on the SSBDDs Definition 5. Let us call a path L(a, b) in the SSBDD between two nodes a and b, activated by a given input pattern X t , if by traversing the graph under guidance of X t , the node b will be reached from a.

In SSBDD-based test generation the targets are node related faults. As explained in [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF], to test a node m in an SSBDD we have to activate three paths in it: (1) L(m 0 , m) from the root node m 0 to m, (2) L(m 1 , #1) from the neighbor m 1 of m to the terminal node #1, and (3) L(m 0 , #0) from m 0 to #0. Example 6. To test the node x 22 in the SSBDD in Fig. 1 we have to activate three paths in it: (1) L(x 1 , x 22 ) from the root node x 1 to x 22 , (2) L(x 3 , #1) from x 3 to the terminal node #1, and (3) L(x 4 , #0) from x 4 to #0. When we assign x 22 = 1 then the activa-tion of the listed paths produce a test pattern X t which detects the fault SAF x 22 ≡ 0.

The pattern X t which activates these paths (bold lines in Fig. 1) is depicted in Fig. 2. Definition 6. Let us call the path which is activated from the root node up to the one of the terminal nodes, the full activated path in SSBDD. The full activated path which terminates in the node #1 (#0) is called 1-path (0-path). The nodes traversed along the 1-path (0-path) in direction to 1 (0), are called 1-nodes (0-nodes).

Example 7. The path L(x 1 , #1) = (x 1 , x 22 , x 3 , ¬x 7 , x 81 , #1) in Fig. 1, activated by the pattern in Fig. 2, is 1-path, the node x 1 on this path is 0-node, and all other nodes are 1nodes.

Property 1. If a test vector X t activates in SSBDD a 0-path (1-path), then only 0nodes (1-nodes) have to be considered as candidate fault sites [START_REF] Ubar | Overview about Low-Level and High-Level Decision Diagrams for Diagnostic Modeling of Digital Systems[END_REF].

The Property 1 can be taken into account to speed-up fault simulation. According to Property 1, the analysis of the 1-path in Fig. 2 shows us that all the nodes, except x 1 , may be qualified as candidate fault sites. However, further analysis is needed to confirm which of the candidate nodes are in fact detectable by the pattern. Since the faults at all 1-nodes for X t (in Fig. 2), will cause the direction change during graph traversing, then the faults at all 1-nodes are detectable by X t .

Example 8. In the path L(x 1 , #1) activated by the test in Fig2, according to Property 1, the nodes x 22 , x 3 , ¬x 7 , and x 81 are the candidates of fault sites. By additional simulation -by inverting the values of these variables, and by tracing the related paths L(x 22 , #0), L(x 3 , #0), L(¬x 7 , #0), L(x 81 , #0) for each of these nodes, we can find that the test pattern in Fig. 2 detects the faults: x 22 ≡ 0, x 3 ≡ 0, ¬x 7 ≡ 0, and x 81 ≡ 0, respectively.

Theorem 2. The faults at two connected SSBDD nodes a and b are equivalent iff the following two conditions are satisfied: (1) the nodes have the same neighbor c, and (2) the node b has a single incoming edge from a.

Proof. The first condition refers to the fact that both nodes can be tested by the same test pattern which activates the paths L(Root,a), L(a,#e) where e∈{0,1}, and the path L(c,#(¬e)). The second condition refers to that this test pattern is the only one which can test both of the node faults a/¬ e and b/¬ e. Example 9. For example the faults x 22 /0 and x 3 /0 are equivalent, because the related nodes x 22 and x 3 have the same neighbor node x 4 , and a single entry edge into x 22 , hence, one of these faults can be collapsed. In a similar way, using Theorem 2, it is easy to find in the SSBDD in Fig. 1 other equivalent faults: x 1 /0 ≡ x 21 /0, x 5 /0 ≡ x 61 /0 (or ¬x 5 /1 ≡ ¬x 61 /1, according to the notation in the SSBDD), x 8,2 /0 ≡ x 9 /0, and x 72 /1 ≡ x 62 /0. On the other hand, the faults ¬x 71 /0 and x 81 /0 are not equivalent. Despite of having the same neighbor x 82 , the node ¬x 71 has three entry edges, and the single entry requirement of Theorem 2 is not satisfied.

𝑦 = 𝑥 !! 𝑥 !" ∨ 𝑥 !" 𝑥 !" ∨ 𝑥 ! ∨ 𝑥 !" 𝑥 !! 𝑥 !"
Theorem 3. The fault b/0 dominates a/0 (or b/1 dominates a/1), iff the following conditions are satisfied: (1) there exists a single 1-path (or a single 0-path) through the nodes for detecting both of these faults, (2) a < b, and (3) the node b has more than 1 incoming edges. Proof. The first condition demands that these faults can be detected by a single test pattern (the condition of the equivalency). The second condition demands that there will be no other path for testing a and not testing b. The third condition is needed to give the possibility to test b and not to test a. From satisfying these conditions, it follows that any test for a must detect the related fault as well at b. Hence, the fault at a is dominated by b. If the third condition is not fulfilled, the related node faults at the nodes a and b are equivalent.

Example 10. In Fig. 1, the faults ¬x 71 /0 and x 81 /0 dominate x 22 /0, and, according to Theorem 3, can be collapsed. Based on this result and taking into account Example 7, we can collapse 3 faults on the activated path L(x 1 ,#1): x 3 /0, ¬x 71 /0 and x 81 /0. Corollary 3. The fault a/0 dominates b/0 (a/1 dominates b/1) iff the following conditions are satisfied: (1) there exists a single 1-path (0-path) through the nodes for detecting both of these faults, (2) a < b, and (3) the node a can be tested by activating another path where b is not tested.

Proof. The proof results directly from Theorem 3 after transforming the SSBDD, so that the ranking of nodes a and b involved in the dominance relation will be swapped (see Fig. 5

and Example 10).

Example 11. In Fig. 5 two different SSBDDs are shown which represent the same digital circuit, and correspond to the following two Boolean expressions:

𝑦 = 𝑥 !! 𝑥 !" ∨ 𝑥 !" 𝑥 !" ∨ 𝑥 ! = 𝑥 !! 𝑥 !" ∨ 𝑥 !" ∨ 𝑥 ! 𝑥 !"
The graphs represent the following rankings R1: x 12 < x 31 < x 4 and R2: x 31 < x 4 < x 12 , respectively, according to the Hamiltonian paths in the SSBDDs. In the SSBDD with node ranking R2, we determine that the node x 12 dominates both, x 31 and x 4 , according to Theorem 3, and the same result we get for the SSBDD with node ranking R1, according to Corollary 3.

Using Theorems 2, 3 and Corollary 3 may directly lead to a simple algorithm of fault collapsing by systematic pairwise analysis of the equivalence and dominance relationships. However, in the worst case, such a pairwise analysis may lead to a quadratic complexity of SSBDD tracing. On the other hand, taking into account the possibility of mapping sub-graphs in the SSBDD into the sub-circuits of the gate network, it would be possible to develop an algorithm of fault collapsing which will use only a single trace through the SSBDD with local analysis of proximate node pairs, and which would provide linear complexity of the algorithm.

Fault Equivalence and Fault Dominance Fast Reasoning on the SSBDD Model

From the definition of the SSBDDs [START_REF] Ubar | Overview about Low-Level and High-Level Decision Diagrams for Diagnostic Modeling of Digital Systems[END_REF] we can derive the following rules for recognition of gates and sub-circuits in the SSBDD model, which will help us to develop a fault collapsing algorithm on SSBDDs with linear complexity. Definition 7. Let us call the consecutive nodes on the Hamiltonian path of SSBDD as a group if they all have the same neighbor node, and all these nodes except the first one have a single incoming edge.

Example 12. Consider a circuit and its SSBDD model in Fig. 1. The two consecutive nodes x 22 and x 3 , and the nodes ¬x 5 and ¬x 61 form two groups in the SSBDD in Fig. 3. No more groups exist in this graph. The nodes ¬x 61 and ¬x 71 don't form a group.

Rule 1. A group of two nodes connected by horizontal edges (vertical edges) represents AND (OR) gate, and due to the fault equivalence, a fault at one of the inputs can be collapsed. The Rule 1 results directly from the method of synthesis SSBDDs by superposition of BDDs of gates [START_REF] Ubar | Test Synthesis with Alternative Graphs[END_REF].

Example 13. The nodes x 22 and x 3 in the SSBDD in Fig. 6 represent AND gate, and ¬x 5 with ¬x 61 represent OR gate. These gates can be recognized in the circuit. According to Rule 1, the faults x 22 /0 (or x 3 /0) and ¬x 5 /1 (or ¬x 61 /1) can be collapsed. The Rules 1 and 2 help to understand, how the fault equivalence and dominance relations in SSBDDs can be related to the similar equivalence and dominance relations in the gate-level circuit. If we have recognized a gate in SSBDD, the equivalence relations overlap for SSBDD and the circuit. The dominance relation in an SSBDD for a node with several incoming edges can be explained by transitive closure of dominance relations. For example, the dominance ¬x 71 /0 → ¬x 61 /0 (or x 71 /1→x 61 /1 in the circuit) in the SSBDD in Fig. 6 can be explained by the following transitive closures in the circuit: x 71 /0 ≡ d/0 ≡ c/0, and c/0 → b/1 → a/0 → x 61 /1, from which x 71 /1 → x 61 /1 results (x 71 /1 dominates x 61 /1).

Algorithm 1 presents a procedure for fault collapsing in circuits which are represented by the SSBDD model. The algorithm is based on pairwise checking of Rule 1 (for equivalence) and Rule 2 (for dominance) by traversing along the Hamiltonian path in SSBDD. The algorithm has linear complexity.

Example 15. Consider the fault collapsing in the SSBDD in Fig. 1 according to Algorithm 1. The SSBDD represents the FFR region of the circuit in Fig. 1 where the fan-out inputs are not included. The initial number of the gate level SAF faults in the FFR in Fig. 1 is 52 (2 faults per each of 26 lines). By synthesizing the SSBDD for the FFR of the circuit according to Procedure 1 we reduce the number of representative faults from all 52 faults to 28 faults (2 faults per each of 14 nodes in the SSBDD). By using Algorithm 1, we further collapse 10 faults (x 1 /0, x 22 /0, x 4 /0, x 5 /0, x 71 /1, x 81 /0, x 82 /0, x 9 /0, x 72 /1, x 10 /1) which results in the total number of remaining 18 representative faults, i.e. 3 times reduction compared to the initial number of faults.

Table 2 shows which node faults in the SSBDD in Fig. 1 are collapsed on the basis of equivalence relation and which faults on the basis of dominance relation.

- -----------------------------------------------------------------------ALGORITHM 1: Fault collapsing on SSBDDs - ---------------------------------------------------------------------- -----------------------------------------------------------------------1: for all SSBDDs in the model 2:

for all nodes m in the current SSBDD 3:

if m < M then go to 6 end if Theorem 4. The effect of fault collapsing in the SSBDD model of the given digital circuit will be always in the boundary 1/2 < R/2N ≤ 5/6. For a single FFR of any given digital circuit the effect of fault collapsing in the related single SSBDD will be always in the boundary 1/2 < R/2N ≤ 3/4.

4: if m = M then C(m) = ¬IN(m) end if 5: go to 28 6: if m(¬d) = n(¬d) then (checking of Rule 1) 7: if FI(n) ≠ 1 then (checking of Rule 2) 8: if [(IN(m)>1) & (IN(m) = OUT(m))] or D(m) = 1 then 9: D(n) = 1 end if 10: if n = M then 11: if IN(m)>1 or D(m) = 1 then C(n) = ¬d(m),
Proof. Any tree-like circuit with N inputs can be represented by SSBDD with N nodes. Examples of such circuits, with fan-outs only in inputs, and the related SSBDDs for the FFRs are depicted in Fig. 7 and Fig. 8, respectively.

In the simplest tree, a single gate with N inputs (gate y in Fig. 7 and SSBDD y in Fig. 8), we can collapse N-1 faults. Hence, R = 2N -(N -1) = N + 1. Any partitioning of the set of inputs for more than one gate in this tree will reduce the total C by one fault per added gate and, hence, increase R. When increasing N, the lower bound for R/2N is:

lim !→! 𝑅 + 𝑛 2𝑁 + 2𝑛 = lim !→! 𝑁 + 𝑛 + 1 2𝑁 + 2𝑛 = lim !→! 𝑛 2𝑛 = 1 2
On the other hand, consider formally (neglecting the redundancy) a single-input logic gate y 1 in Fig. 7. The SSBDD model of the gate has N=3 nodes representing the fan-out stem with 2 branches. The SSBDD for only the FFR of this gate has 2 nodes. There are two equivalent faults at the gate inputs where one of them can be collapsed. Hence, the number of representative faults in this circuit will be R=2N-1=5, and R/2N = 5/6. Similarly, the SSBDD for the FFR has only R=2N-1=3, and R/2N = 3/4.

Consider now the tree-like circuit y 2 in Fig. 7 with two 2-input gates and two fanout nodes. The SSBDD model of the circuit has N=6 nodes. There are again two equivalent faults at the gate inputs where one of them can be collapsed. Hence, the number of representative faults after fault collapsing will be R = 2N -2 = 10, and again we get R/2N = 5/6. Similarly, for the SSBDD representing only the FFR in this circuit, we get N = 4, R = 2N -2 = 6, and R/2N = 3/4.

The circuit y 4 in Fig. 7 illustrates how we can generalize the series of two circuits y 1 and y 2 into a series of expanding circuits y n , n = 1,2,3,4…, where each circuit will consist of an input sub-circuit IN n as a chain of n 2-input gates, and a tree-like sub-circuit F n . In each such a circuit, the ratio R/2N = 5/6 remains constant. In IN n for each gate, only a single fault can be collapsed resulting in total in n collapsed faults.

It is easy to realize that any structural change inside the sub-circuit F n will not change the ratio R/2N = 5/6. The reason is that all the faults in F n will dominate the faults in IN n . On the other hand, by adding n = 1, 2,… non-fan-out inputs to the subcircuit IN n we get R/2N*= (R+n)/(2N+2n), and by adding n fan-out inputs with 2 branches to IN n we will get R/2N** = (R+2n)/(2N+6n). Each addition of a fan-out branch is equivalent to the case of adding a single input node where no faults can be collapsed.

From above it follows that for the case of digital circuits as networks of FFRs the higher bound (the worst case of remaining representative faults) for the ratio R/2N will be:

𝑅/2𝑁 * * < 𝑅/2𝑁 * < 𝑅/2𝑁 ≤ 5/6
Hence, the range between lower and higher bounds for the ratio R/2N characterizing the number of remaining representative faults after using Algorithm 1 for fault collapsing will be:

1/2 < 𝑅/2𝑁 ≤ 5/6
Extending the same analysis for a single sub-circuit as an FFR, we will have the range between lower and higher bounds for the ratio R/2N as:

1/2 < 𝑅/2𝑁 ≤ 3/4
Corollary 4. From Theorem 4, it directly follows that for the SSBDD model of the given digital circuit with N nodes in the model, the number of collapsed faults C = 2N -R belong will always to the interval N/3 ≤ C < N. Hence, N/3 will serve as the lower bound for the number of collapsed faults achievable in the SSBDD model.

Corollary 5. From Theorem 4, it directly follows that for the SSBDD with N nodes which represents any FFR in digital circuits, the number of collapsed faults C = 2N -R will always belong to the interval N/2 ≤ C < N. Hence, N/2 will serve as the lower bound for the number of collapsed faults achievable in any single SSBDD created for the given FFR.

Example 16. Consider again the digital circuit and the FFR of the circuit in Fig. 1. In Example 15 we found the number of collapsed faults C = 10, and the numbers of remaining representative faults for the case of FFR R FFR = 18, and for the full circuits (with the SSBDD for FFR and additional 4 single-node SSBDDs for 4 inputs with fan-outs) R circuit = 26. For FFR we get N/2 = 7 ≤ C = 10 < N = 14, whereas for the full model we have N/3 = 6 ≤ C = 10 < N = 18.

The result shows that the interval between lower and upper bounds for a single FFR is smaller compared to the interval for whole circuit. More discussion in that topic follows in the experimental part of the paper.

Experimental Data

The fault collapsing experiments were carried out with Intel Core i5 3570 Quad Core 3.4 GHz, 8 GB RAM, using ISCAS'85, ISCAS'89 and ITC'99 benchmark circuits. The experimental results are presented in Tables 3 and4. In Table 3, the sizes of fault sets after fault collapsing for the proposed method (New) with previous structural [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF][START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF][START_REF] Ubar | Structural Fault Collapsing by Superposition of BDDs for Test Generation in Digital Circuits[END_REF] and functional [START_REF] Adapa | Sub-Faults Identification for Collapsing in Diagnosis[END_REF] methods are compared. The new proposed method has better results in fault collapsing than the previous structural methods. The functional method [START_REF] Adapa | Sub-Faults Identification for Collapsing in Diagnosis[END_REF] is very slow and not scalable due to high computational cost of calculating transitive closures on dominance graphs whereas the proposed method has a very high speed due to the linear complexity and is well scalable. As an example, the difference in time costs for c3540 and c6288 in case of [START_REF] Adapa | Sub-Faults Identification for Collapsing in Diagnosis[END_REF] is 200 times whereas for the proposed method the difference is 2 times.

Due to different computing frameworks the speeds of the algorithms [START_REF] Adapa | Sub-Faults Identification for Collapsing in Diagnosis[END_REF] and developed in this paper cannot be directly compared. On the other hand, the time cost needed for the first part of fault collapsing as a side effect of SSBDD synthesis was not included into the CPU time data in Table 3.

The experimental results for larger ISCAS'89 and ITC'99 circuits (R* is the number of remaining faults after collapsing) are depicted in Table 4. The column R*/R shows the gain (1.2 times in average) of the achieved fault collapse (in the column R(New)) compared to the results in [START_REF] Brglez | Combinational Profiles of Sequential Benchmark Circuits[END_REF]36]. The last column shows that Algorithm 1 has linear complexity, is well scalable and can be efficiently used for large circuits. The linear complexity of the method is explained by the fact that the fault equivalence and dominance reasoning is reduced only to the local pairwise analysis of the neighbor nodes during traversing the Hamiltonian path of the SSBDD. The number of pairs to be analyzed, as it results from Algorithm 1, is in the interval (N-1, N/2+1) where the lower bound refers to the extreme case of the logic gate with N inputs, and the higher bound refers to the extreme case of the two-level AND-OR (OR-AND) circuits with 2 inputs for the 1st level AND (OR) gates, plus one additional input for the 2-nd level gate.

Note, that according to Theorem 4, the higher bound for R/2N is 83% and the lower bound is 50%. The best result of fault collapsing -73.0 % of remaining faults, the worst result -77.9% and the average of 74.1% all fit well into the interval between the bounds. However the results are considerably closer to the higher bound of 83.3% of remaining representative faults than the lower bound of 50%. In Fig. 9 we show statistical data collected from the fault collapse experiments with SSBDDs in 0.5 million tree-like sub-circuits (FFRs) in 111 different circuits of ISCAS'85, ISCAS'89 and ITC'99 families. Fig. 6 presents a plot of different subcircuit cases characterized by the number of nodes N in SSBDDs and the results of fault collapsing R/2N. Two extreme cases are highlighted: single-gate circuits (the best fault collapsing case) and the circuits with 2-input gates at the first level of treelike circuits -the worst fault collapsing case where the higher bound for the remaining representative faults R/2N = 3/4 was reached, respectively the lower bound (the minimum number) of faults collapsing C = N/2.

Conclusions

In this paper we proposed a new structural fault collapsing method and an algorithm with linear complexity. The method is based on using SSBDD model for representing gate-level circuits as higher FFR-level networks. The synthesis of SSBDDs presents the first step of fault collapsing in FFR-s, and the resulting collapsed fault set can be regarded as a side-effect of SSBDD synthesis. We have introduced the concepts of fault equivalence and dominance relations between the faults on the SSBDD model, and present an algorithm for systematic fault collapsing in SSBDDs as a process of creating of the representative fault set defined at the higher level communication network of FFRs. We developed the lower and higher bounds of the SSBDD based fault collapsing, and showed that the number of collapsed faults C in the SSBDD model of an arbitrary digital circuits belongs to the interval N/3 ≤ C < N where N is the number of nodes in the SSBDD model.

Experiments showed that the proposed method is more efficient than the previous structural fault collapsing methods and due to high scalability makes it very promising for large circuits.

Fig. 1 .

 1 Fig. 1. Combinational circuit with a single output and its representation as an SSBDD

Fig. 2 .

 2 Fig. 2.Test pattern for detecting selected faults SAF/0 or SAF/1 for the circuit in Fig.1

Fig. 4 .

 4 Fig. 4. Hamiltonian path in two presentations of the same SSBDDs Property 2. SSBDDs have always a single Hamiltonian path that visits all the nodes (except #0 and #1), and which determines a unique ranking of the nodes. The nodes a and b are in the relationship a < b if the node a will be traversed before b along the Hamiltonian path [32]. Fig.4. depicts an example of two possible presentations of the same SSBDD which represents the following Boolean expression:

Fig. 5 .

 5 Fig. 5. Transformation of SSBDDs by swapping the nodes or subgraphs

Rule 2 .

 2 If a node b in SSBDD has at least two or more incoming edges, it represents a path to a gate G where all the paths, represented by a subset of nodes S(b) = {a | a < b}, are joining. The fault of b dominates over the related faults of the nodes a ∈ S(b), since the conditions of Theorem 3 are satisfied.

Fig. 6 .

 6 Fig. 6. Mapping SSBDD subgraphs into the circuit

  -Input: SSBDD model for a given circuit Output: Set of collapsed faults C Notations: M -the number of all nodes m -the number of the first node of the current node pair n -the number of the second node, n = m + 1, n* =n+1 d(m) -direction from node m to n n(d) -the neighbor of the node n in direction d(m) C(m) -the type of the collapsed fault C(m) ∈ {0,1} IN(m) / OUT(m) -directions of incoming/outgoing edges FI(m) -flag to remember the multiple fan-in for m D(m) -flag to remember the direction of multiple fan-in -

  Denote by N the number of all nodes in the SSBDD model of a circuit and by C the number of collapsed faults. The number of all SAF faults is 2N, the number of representative faults after fault collapsing will be R = 2N -C, and the effect from fault collapsing can be expressed by the ratio R/2N.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Tree-like circuits with fan-out inputs of increasing complexity

Fig. 9 .

 9 Fig. 9. Distribution of SSBDD cases with different characteristics (N, R/2N)

Table 1 .

 1 Calculation of the number of nodes for 2 types of SSBDDs

		s 0	s 1	s k	m	s	N
	N gate	6	12	4	2	-	N gate = 6 + 12 +4*3 = 30
	N SSBDD	-	-	4	2	10	N SSBDD = 10 + 4*2 = 18

go to 13 end if

	12:	if OUT(m) ≠ OUT (n) then	(checking of Rule 1)
	13:	C(m) = ¬d(m)
	14:	if n(¬d) ≠ ∅ then FI(n(¬d)) = 1 end if
	15:	m = m + 2, go to 3
		else
	16:	if FI(n*) = 1 then go to 13 end if
	17:	if n(¬d) = n*(¬d) then	(checking of Rule 1)
	18:	C(m) = ¬d(m), m = m + 1, go to 3
	19:	else C(n) = ¬d(m),

go to 15 end if end if end if 20: else go to 23 end if

	21:	else if FI(m) = 1 then	(checking of Rule 2)
	22:	if FI(n) = 1 then	(checking of Rule 2)
	23:	C(m) = ¬IN(m)
	24:	if m(¬d) ≠ ∅ then FI(m(¬d)) = 1 end if
	25:	m = m + 1, go to 3
	26:	else C(m) = ¬d(m), go to 24 end if
	27:	else go to 26 end if
	28:	end if
	29:	end for
	30: end for

Table 2 .

 2 Fault collapsing results for the SSBDD in Fig.1

	Node	Collapsed fault	Comments
	x 1	SAF x 1 /0	Equivalent with x 21 /0
	x 21	No collapse
	x 22	SAF x 22 /0	Equivalent with x 3 /0
	x 3	No collapse
	x 4	SAF x 4 /0	Dominates x 5 /1, x 61 /1,
	¬x 5	SAF x 5 /0	Equivalent with x 61 /0
	¬x 61	No collapse
	¬x 71	SAF x 71 /1	Dominates x 22 /0, x 3 /0, x 22 /0, x 5 /1, x 61 /1
	x 81	SAF x 81 /0	Dominates x 22 /0, x 3 /0, x 22 /0, x 5 /1, x 61 /1, x 1 /0, x 21 /0, x 71 /1
	x 82	SAF 82 /0	Equivalent with x 9 /0
	x 9	SAF 9 /0	Dominates x 82 /0
	x 72	SAF x 72 /1	Equivalent with x 62 /0
	¬x 62	No collapse
	¬x 10	SAF x 10 /1	Dominates x 72 /0, x 62 /1, x 9 /0, x 82 /0
	6

Lower and Higher Bounds for Fault Collapsing

Table 3 .

 3 Comparison with other methods

	Circuit	# Faults	[2]	Fault set size [14] [34] [18] New [18] CPU time, s New
	c1355 2710 1234 1210 1100 808 1210	46	0.003
	c1908 3816 1568 1566 1286 753 1243	14	0.008
	c2670 5340 2324 2317 2046 1853 1989 110 0.009
	c3540 7080 2882 2786 2584 2092 2340 831 0.010
	c5315 10630 4530 4492 4404 3443 3900	72	0.012
	c6288 12576 5840 5824 4832 5824 5824	4	0.019
	c7552 15104 6163 6132 5480 4707 5156 232 0.016

Table 4 .

 4 Fault collapsing for ISCAS'89 and ITC'99 circuits

	Circ	# Gates	R* [35,36]	2N	R (New) R/2N %	Gain R*/R	Time s
	s13207 24882	9815	10456	7933	75.9	1.24	0.04
	s15850 29682 11727 12150	9178	75.5	1.28	0.04
	s35932 65248 39094 39094 29797	76.2	1.31	0.26
	s38417 69662 31180 32320 25162	77.9	1.24	0.20
	s38584 72346 36305 38358 28016	73.0	1.30	0.18
	b15	47414 21072 23498 17439	74.2	1.21	0.04
	b17	154220 68037 81330 60684	74.6	1.12	0.12
	b18	463570 206736 277978 205866	74.1	1.00	0.42
	b18_1 453088 202812 264244 196179	74.2	1.03	0.40
	b19 1345442 533142 560704 415251	74.1	1.28	0.84
	b19_1 1275720 507476 534184 396151	74.2	1.28	0.80
	b21	79556 35994 48182 35169	73.0	1.02	0.08
	b21_1 63732 29091 34510 25359	73.5	1.15	0.06
	b22	113308 51277 70464 51511	73.1	1.00	0.11
	b22_1 98006 44771 52172 38359	73.5	1.17	0.08
	Aver 290392 121902 138643 102804	74.1	1.2	0.24

ACKNOWLEDGMENTS

The work has been supported by EU FP7 STREP project BASTION, and HORIZON 2020 RIA project IMMORTAL.