Co-design and testing of safety-critical embedded systems

3. Subject of Study:
Principles, methods and techniques in co-design and testing of S-CES.

4. Aims:
Acquisition of knowledge about methods and techniques in co-design and testing of S-CES and their components.

Object of Study:
Concepts of Safety-Critical Embedded Systems (S-CES): Co-design and Testing.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3

1.2. Standards regulating legislative of S-CES

1.3. Life-cycle of S-CES

1.1. Component approach

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

COTS-approach (Commercial-Off-The-Shelf) – reuse of commercial components.

CrOTS-approach (Critical-Off-The-Shelf) – reuse of components in critical applications.

Component approach constitutes the use of library components developed formerly and commonly employed in commercial and critical applications, including the components of one’s own design.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

DO 178-B (Avionics)
and
ISO 26262 (Automotive)

IEC 61513
(Nuclear power plants)
and
IEC 62061 (Machines)

IEC – International Electrotechnical Commission

This slide from presentation of M. Fusani ISTI - CNR, Pisa, Italy

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

IEC 61508-1:1998 ‘General requirements’

IEC 61508-2:2000 ‘Requirements to electrical, electronic and programmable systems’

IEC 61508-3:1998 ‘Requirements to software’

IEC 61508-4:1998 ‘Definitions to Abbreviations’

IEC 61508-5:1998 ‘Examples of methods for determining safety integrity levels’

IEC 61508-6:2000 ‘Guide for use of IEC 61508-2 and IEC 61508-3’

IEC 61508-7:2000 ‘Overview of techniques and measures’

1. The use of safety integrity levels concept – every unit of equipment is developed and analysed with contribution in safety of critical object.

2. Consideration of full life-cycle of S-CES

3. Positioning of software as essential S-CES component which is source of possible failures influencing on safety of critical object

4. Flexibility of requirements for the critical objects. It allows to be foundation for development of standards to specific areas of industry

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

ECSS – European Cooperation for Space Standardization

ECSS-E-10 ‘Space Engineering – System Development’

ECSS-E-40A ‘Space Engineering – Software Development’

ECSS-Q-20 ‘Guarantee Production Space Destination – Quality Assurance’

ECSS-Q-80B ‘Guarantee Production Space Destination – Quality Assurance of Software’

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

RTCA – Radio Technical Commission for Aeronautics

DO-178B:1992 ‘Consideration of software at certification of
on-board systems and equipments’

MIRA – Motor Industry Research Association

MISRA-C:2004 ‘Guide for use of language C++ in critical systems‘

CENELEC – European Committee for Electrotechnical Standardization

EN 50126 ‘Objects of railway transport. Requirements and validation of dependability, reliability, maintainability and safety‘

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

IAEA – International Atomic Energy Agency

IAEA NS-G-1.1 ‘Software and computer-based systems important to safety in nuclear power plants’

IAEA NS-G-1.2 ‘Safety assessment and verification for nuclear power plants’

IAEA NS-G-1.3 ‘Instrumentation and control systems important to safety in nuclear power plants’

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

IEC – International Technical Commission

IEC 60780:1998 ‘Nuclear power plants – Electrical equipment of the safety system - Qualification’

IEC 60880:2006 ‘Nuclear power plants – Instrumentation and control systems important to safety – Software aspects for computer-based systems performing category A functions’

IEC 60980:1989 ‘Recommended practices for seismic qualification of electrical equipment of the safety system for nuclear generating stations’

IEC 60987:2007 ‘Nuclear power plants – Instrumentation and control systems important to safety – Hardware design requirements for computer-based systems’

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

IEC – International Technical Commission

IEC 61226:2005 ‘Nuclear power plants – Instrumentation and control systems important to safety – Classification of instrumentation and control functions’

IEC 61513:2001 ‘Nuclear power plants – Instrumentation and control systems important to safety – General requirements for systems’

IEC 62138:2004 ‘Nuclear power plants – Instrumentation and control systems important to safety – Software aspects for computer-based systems performing category B or C functions’

IEC 62340:2007 ‘Nuclear power plants – Instrumentation and control systems important to safety – Requirements for coping with common cause failure’

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. Development of program models of control algorithms in CASE-tools environment.

3. Integration of signal formation algorithm block-diagram program models in CASE-tools environment.

4. Implementation of integrated digital component program models to FPGA.

CASE – Computer Aided Software / System Engineering

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. Program models of control algorithms in CASE-tools environment.

3. Integrated program model of control algorithms in CASE-tools environment.

4. FPGA with implemented integrated program model.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. Verification of program models of control algorithms in CASE-tools environment.

3. Verification of integrated program model in CASE-tools environment.

4. Verification of FPGA with implemented integrated program model.

1. Co-design of S-CES is based on traditional ideas such as Component approach, Standards regulating legislative and Life-cycle of S-CES

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3. The main standard is IEC 61508 – Safety of electrical, electronic and programmable systems important to safety.

4. Life-cycle of FPGA-based S-CES digital component contains 4 stages of development with verification of results obtained on every stage.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

22

2.2. Dependability Threats

2.3. Dependability Attributes

2.1. Introduction into dependability

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2.4. Dependability Measures

2.5. Safety and Reliability

2.6. Forms of Dependability Requirements

2.7. The Means to attain Dependability Techniques

Growth of computer system complexity

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2.1.1. Motivation of Dependability Consideration

Expansion of a set of tasks solved with use of computer systems including critical application areas

Amplification of interdependence and interaction between hardware and software of computer systems including processes of co-design S-CES on programmable elements.

Reasons:

1. Avizienis A., Laprie J.-C. Dependable Computing: From Concepts to Application // IEEE Transactions on Computers, 1986. Vol. 74, No. 5. P. 629-638.
Authors formulated the principle of “Dependable Computing” as computation resistant to hardware and software failures (caused by their defects brought in design and not revealed in the course of detected).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. Dobson I., Randell B. Building Reliable Secure Computing Systems out of Unreliable Insecure components // Proc. of IEEE Conference on Security and Privacy, Oakland, USA. 1986. P. 186-193.
Authors defined “Secure-Fault Tolerance” and proposed a principle of its realization for various types of computer systems.

3. Avizienis A., Laprie J.-C, Randell B., Landwehr C. Basic Concepts and Taxonomy of Dependable and Secure Computing // IEEE Transactions on Dependable and Secure Computing, 2004. Vol. 1. No. 1. P. 11-33.

Attributes - properties expected from the system and according to which assessment of service quality resulting from threats and means opposing to them is conducted.

Means - methods and techniques enabling
to provide service on which reliance can be placed
to have confidence in its ability.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Threats - undesired (not unexpected) circumstances causing or resulting from undependability (reliance cannot or will not any longer be placed on the service.

Faults: development ( design) or operational (phase of creation or occurrence),
internal or external (system boundaries),
hardware or software (domain),
natural or human-made (phenomenological case), accidental, non-malicious, deliberate or deliberately malicious (intent),
permanent or transient (persistence).

Faults: Development or Design Faults
Physical Faults
Interaction Faults

Development or Design Faults:
erroneous acts or decisions in system development bring to appearance of a fault in its design which becomes apparent in computer system operation under certain terms and causes an error in computation process, thus leading to a malfunction or failure (non-rendering of service)
software flaws,
malicious logics.

Physical Faults:
due to natural (internal) causes a fault appears bringing to an error in computation process, thus leading to a malfunction or failure.

Interaction Faults:
due to external information, physical or other effects a fault appears bringing to an error in computation process and then a computer system malfunction or failure.

Failures: content, early or late timing,
halt or erratic (domain),
signaled or unsignaled (detectability),
consistent or inconsistent (consistency),
minor or catastrophic (consequences).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This slide from presentation of Felicita Di Giandomenico ISTI - CNR, Pisa, Italy

Absence of catastrophic consequences on the users & env. – Safety.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Availability, Confidentiality, Integrity – Security.
Absence of unauthorized access to, or handling of, system state.

Absence of unauthorized disclosure of inf. – Confidentiality.

Absence of improper system alterations – Integrity.

Ability to undergo repairs and evolutions – Maintainability.

Reliability: a measure of the continuous delivery of correct service – or the time to failure;

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Maintainability: a measure of the time to service restoration since the last failure occurrence.

Availability: a measure of the delivery of correct service with respect to the alternation of correct and incorrect service;

• Safety is a measure of continuous safeness, or equivalently, of the time to catastrophic failure;

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Safety is thus Reliability with respect to catastrophic failures.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Other forms of requirements:
Fault tolerance: this system must provide uninterrupted service with up to one component failure, and fail safely if two fail;
Specific defensive mechanisms: "these data shall be held in duplicate on two disks.

Rate of occurrence of failures: – "the probability that a failure of a flight control system will cause an accident with fatalities or loss of aircraft must be less than 10-9 per hour of flight“.

Probability of surviving mission: – The probability that the flight and ordnance control system in a fighter plane are still operational at the end of a two hour mission must be more than...

• Fault prevention: how to prevent the occurrence or introduction of faults;

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Fault removal: how to reduce the number or severity of faults;

• Fault forecasting: how to estimate the present number, the future incidence and the likely consequences of faults.

• Fault tolerance: how to deliver correct service in the presence of faults.

• They include structured programming, information hiding, modularization, etc., for software, and rigorous design rules and selection of high-quality, mass-manufactured hardware components for hardware.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Simple design, possibly at the cost of constraining functionality or increasing cost

• Formal proof of important properties of the design

• Provision of appropriate operating environment (air conditioning, protection against mechanical damage) intend to prevent operational physical faults, while training, rigorous procedures for maintenance, ‘foolproof’ packages, intend to prevent interaction faults.

• During development it consists of three steps: verification, diagnosis, correction.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Verification is the process of checking whether the system adheres to given properties. If it does not, the other two steps follow:

• After correction, verification should be repeated to check that fault removal had no undesired consequences; the verification performed at this stage is usually termed non-regression verification.

• Checking the specification is usually referred to as validation.

• Without actual execution is static verification: static analysis (e.g., inspections or walk-through), model-checking, theorem proving.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Exercising the system is dynamic verification: either with symbolic inputs in the case of symbolic execution, or actual inputs in the case of testing.

• As well as verifying that the system cannot do more than what is specified important to safety and security.

• Important is the verification of fault tolerance mechanisms, especially a) formal static verification, and b) testing that includes faults or errors in the test patterns: fault injection.

• Corrective maintenance is aimed at removing faults that have produced one or more errors and have been reported.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Preventive maintenance is aimed to uncover and remove faults before they might cause errors during normal operation. a) physical faults that have occurred since the last preventive maintenance actions;
b) design faults that have led to errors in other similar systems.

• These forms of maintenance apply to non-fault-tolerant systems as well as fault-tolerant systems, that can be maintainable on-line (without interrupting service delivery) or off-line (during service outage).

• Qualitative Evaluation: aims to identify, classify, rank the failure modes, or the event combinations (component failures or environmental conditions) that would lead to system failures.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

• Qualitative Evaluation or probabilistic: which aims to evaluate in terms of probabilities the extent to which the relevant attributes of dependability are satisfied.

• Through either specific methods (e.g., FMEA for qualitative evaluation, or Markov chains and stochastic Petri nets for quantitative evaluation).

• Methods applicable to both forms of evaluation (e.g., reliability block diagrams, fault-trees).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3. Measures of Dependability are defined using Reliability, Availability and Maintainability

5. Means to attain Dependability contain 4 Techniques: Prevention, Removal, Forecasting and Tolerance of Faults.

4. Safety can be considered as an extension of reliability

6. Evolution of the Dependability concept: Resilience, Survivability and Trustworthiness (Reliability of Results).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.2. Error Detection

3.3. Recovery

3.1. Introduction into Fault Tolerance

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4. Dependability Measures

3.5. Fault Tolerant Technologies

Fault Tolerance is the main mechanism, instrument ensuring Dependability

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.1.1. Motivation of Fault Tolerance Consideration

Reasons:

Fault Tolerance ensures operative resistance to hardware and software failures

3. Lee P.A. and Anderson T., Fault Tolerance - Principles and Practice, second edition, Springer Verlag/Wien, 1990

2. Jean-Claude Laprie, Jean Arlat, Christian Beounes, Karama Kanoun and Catherine Hourtolle, Hardware and Software Fault Tolerance: Denition and Analysis of Architectural Solutions, in Proceedings FTCS 17, 1987

Effectiveness of Fault Tolerance: the effectiveness of error and fault handling mechanisms (their coverage) has a strong influence on Dependability Measures

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Fault Tolerance:
Error Detection
Recovery

Error detection originates an error signal or message within the system. An error that is present but not detected is a latent error.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Fault Tolerance is generally implemented by error detection and subsequent system recovery.

Recovery consists of
Error Handling
Fault Handling (Fault treatment).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Fault Handling involves four steps:
• Fault Diagnosis: identifies and records the cause(s) of error(s), in terms of both location and type;
• Fault Isolation: performs physical or logical exclusion of the faulty components from further participation in service delivery, i.e., it makes the fault dormant;
• System Reconfiguration: either switches in spare components or reassigns tasks among non-failed components;
• System Reinitialization: checks, updates and records the new configuration and updates system tables and records.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Fault-Tolerant Technologies based on various kinds of Redundancy and Reconfiguration.

Operative nature of the opposition to faults in safety-critical I&CS determines the important role of the methods and means of On-Line Testing in maintenance of Fault Tolerance.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.1.1. Residue Checking for Error Detection in arithmetic components

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.1.1. Residue Checking for Error Detection in arithmetic components

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.1.2. Hamming Correcting Code for Memory Recover

Generating Matrix of linear code

3.4.1.2. Hamming Correcting Code for Memory Recover

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Majority element calculates carry function of full adder C = 12∨13∨23

The errors caused by input faults are not detected

The version is defined as a method of system function realization. For embedded systems it can be hardware means to solve a computing task.

Multi-Version System are aimed to provide protection against failure due to common reason:
Errors of design;
Physical Defects of Manufactory;
Faults during Operation.

3.4.3. Multi-Version Systems

59

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

In regulatory documents the application of Version Redundancy goes under the name of “Principle of diversity”

3.4.3. Multi-Version Systems

60

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Nuclear engineering uses a class of MVS including two versions in accordance with international standards, such as:
IEC 61513:2001 ‘Nuclear power plants – Instrumentation and control systems important to safety – General requirements for systems’
IEC 62340:2007 ‘Nuclear power plants – Instrumentation and control systems important to safety – Requirements for coping with common cause failure’

Control signal Z (system output) is generated by solver in accordance with outputs of versions Z1 and Z2.
The solver may be realized as OR circuit if faulty version defines its output in ‘zero’ value.

3.4.3. Multi-Version Systems

61

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems
A Structure of two-version S-CES

Software diversity is the use of different programs designed and implemented by different development groups with different programming languages and tools to accomplish the same safety goals.

Equipment (hardware) diversity is the use of different equipment to perform similar safety functions in which different means sufficiently unlike as to significantly decrease vulnerability to common failure.

Human (life cycle) diversity is the use of different project groups with different key personnel to accomplish the same project goals.

Design diversity is the use of different approaches including both software and hardware, to solve the same or similar problem.

Signal diversity is the use of different sensed parameters to initiate protective action, In which any of parameters may independently indicate in abnormal condition, even if the other parameters fail to be sensed correctly.

Functional diversity is the use of different physical functions performing though they may have overlapping safety effects.

We offer a new set of MVS with strongly connected versions (SVS), which protects against failure due common reason having maximal common part of versions.

We revise requirement to undependability of versions and show that only common part of all versions should be absent for protecting against failure due common reason:

A1 ∩ … Ai ∩ … ∩ AN = ∅. (1)

65

3.4.4. Multi-Version Systems

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Let's designate addition to version Ai as

Then the determining attribute of SVS is that additions to versions do not include versions,

Ai = A \ Ai.

i.e. for i = 1 ÷ N and j = 1 ÷ N is carried out Ai ⊄ Aj. (2)

66

3.4.5. Computer Systems with Strongly Connected Versions

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Identical elements of initial CS are united in identical sections

The amount of additional sections in SVS is less than the amount of sections in a version.

Structure of SVS

CS

SVS

67

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

Structure of SVS

CS

SVS

SVS is simplified with increase of versions quantity

68

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

means of a choice of the true version.

the multitude of versions, that contains at least one true version;

Protection from Failure due to the Common Reason

69

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

QSVS = QIE + QCM,

where QIE – complexity of identical elements; QCM – complexity of choice means.

where R – quantity of identical elements in CS; K – quantity of identical elements in CS; λ – coefficient of proportionality.

QDC MIN = 2R (1+1/K 2).

K = √R/λ

70

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

a parallel choice of the true version;

71

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

The version can be checked up using two approaches.

internal, i.e. check of each version by its own means.

external, i.e. check of total system;

The check of the version can be:

indirect, which estimates its addition.

direct, which estimates the version itself;

72

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

Choice of the True Version

Direct check puts the true version into operation

Change of versions is carried out before detection of the true version.

A consecutive choice of the true version is based on external check of versions.

Indirect check disconnects the incorrect addition of the true version.

73

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3.4.5. Computer Systems with Strongly Connected Versions

Choice of the True Version

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5. Multi-Version System ensures resistance to failure due to common reason.

4. Fault-Tolerant Technologies based on various kinds of Redundancy and Reconfiguration using the methods and means of On-Line Testing.

6. Computer Systems with Strongly Connected Versions is simplified with increase of versions quantity.

2. Fault Tolerance of S-CES is executed by Error Detection and Recovery.

3. Recovery consists of Error Handling (rollback, compensation, rollforward) and Fault Treatment (Fault diagnosis and isolation, System reconfiguration and reinitialization).

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

77

4.3. Self-checking circuits

4.4. Purpose of on-line testing

4.2. Stages of on-line testing development

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.5. Model of exact data

4.6. Processing of exact and approximate data

4.7. Component on-line testing

4.1. Introduction into on-line testing

On-Line Testing is aimed to ensure reliability of the calculated results

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.1.1. Motivation of On-Line Testing Consideration

Reasons:

On-Line Testing ensures first response to hardware and software failures

5. Горяшко А. П. Синтез диагностируемых схем вычислительных устройств. – М.: Наука, 1987. – 288 c.

2. Touba N. A. and McCluskey E. J. Logic synthesis techniques for reduced area implementation of multilevel circuits with concurrent error detection // Proc. IEEE Inf. Conf. on Computer Aided Design. – 1994. – P. 651 – 654.

3. Metra C., Schiano L., Favalli M and Ricco B. Self-checking scheme for the on-line testing of power supply noise. – Proc. Design, Automation and Test in Europe Conf. Paris (France). – 2002. – P. 832 – 836.

4. Nicolaidis M. and Zorian Y. On-line testing for VLSI – a compendium of approaches // Electronic Testing: Theory and Application (JETTA). – 1998. – V. 12. – P. 7 – 20.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

On-line testing is considered to be the check of digital circuit operation correctness over working influences.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

In development of on-line testing it is possible to select three stages:

Data transmission on distance

4.2.1. Initial Stage of On-Line Testing Development

83

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Data transmission on distance

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Noise combating code

85

4.2.1. Initial Stage of On-Line Testing Development

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Data transmission on distance

86

4.2.1. Initial Stage of On-Line Testing Development

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Correcting code

87

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

88

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

Detecting code

For example,

89

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

90

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

For example, bit 4 is equal to the modulo 2 sum of the bits 2 and 3.

91

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

92

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

93

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.2.1. Initial Stage of On-Line Testing Development

It has been inherited by on-line testing, where the error detection circuits were used without checking while operation.

94

4.2.1. Initial Stage of On-Line Testing Development

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

To achieve this purpose, they have suggested to build the self-checking circuits.

It was the important step in development of on-line testing, which for the first time has been expanded on his error detection circuits.

95

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.3. Self-Checking Circuits

A circuit is self-testing for a set of faults F if for every fault in F the circuit produces a non-codeword at the output for at least an input codeword.

If the circuit is both fault-secure and self-testing it is said to be totally self-checking.

Definitions

96

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.3. Self-Checking Circuits

A code distance d between codewords of the pair is an amount of their bits with the differ value.

If fault generates the error in t bits and t < d then the circuit is fault-secure because it produces non-codeword that can not be incorrect codeword.

0

1

2

3

4

5

6

7

d = 3

d = 4

4.3. Self-Checking Circuits

Fault-secure circuit

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

97

A code distance d between codewords of the pair is an amount of their bits with the differ value.

If fault generates the error in t bits and t < d then the circuit is fault-secure because it produces non-codeword that can not be incorrect codeword.

4.3. Self-Checking Circuits

Fault-secure circuit

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Definition of fault-secure circuit determines how much information redundancy is needed to detect one fault.

98

This condition means that all input codewords should be obtained during the time-interval between faults f1 and f2 .

It is satisfied due to rare occurrence of faults.

operation cycle

4.3. Self-Checking Circuits

A circuit is self-testing for a set of faults F if for every fault in F the circuit produces a non-codeword at the output for at least an input codeword.

Self-Testing circuit

99

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This condition means that all input codewords should be obtained during the time-interval between faults f1 and f2 .

It is satisfied due to rare occurrence of faults.

4.3. Self-Checking Circuits

A circuit is self-testing for a set of faults F if for every fault in F the circuit produces a non-codeword at the output for at least an input codeword.

Self-Testing circuit

100

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This condition means that all input codewords should be obtained during the time-interval between faults f1 and f2 .

It is satisfied due to rare occurrence of faults and high-frequency operations of the computing circuits.

4.3. Self-Checking Circuits

A circuit is self-testing for a set of faults F if for every fault in F the circuit produces a non-codeword at the output for at least an input codeword.

Self-Testing circuit

101

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This condition means that all input codewords should be obtained during the time-interval between faults f1 and f2 .

The self-testing property is based on a high level of reliability and productivity of modern computing circuits.

4.3. Self-Checking Circuits

A circuit is self-testing for a set of faults F if for every fault in F the circuit produces a non-codeword at the output for at least an input codeword.

Self-Testing circuit

102

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4.3. Self-Checking Circuits

Non-Self-Testing circuit

103

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Such circuit is not self-testing and not self-checking in set of the stuck-at faults.

Stuck-at «0» fault in the points 2, 3 or 4 makes the error detection circuit also not self-checking.

4.3. Self-Checking Circuits

According to these definitions the designed circuit is not self-checking in a set of stuck-at faults.

Non-Self-Testing circuit

104

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Design of Self-Checking circuit

105

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

SELF-CHECKING CIRCUITS

4.3. Self-Checking Circuits

This circuit contains Carter's unit (UC), which will transform two pairs of inverse bits X1=¬X2 and Y1=¬Y2 to one pair of inverse bits F1=¬F2.

Design of Self-Checking circuit

106

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

SELF-CHECKING CIRCUITS

4.3. Self-Checking Circuits

This circuit contains Carter's unit (UC), which will transform two pairs of inverse bits X1=¬X2 and Y1=¬Y2 to one pair of inverse bits F1=¬F2.

Design of Self-Checking circuit

107

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

The self-checking circuit has two bits output E{1,2}.

Using parity, residue and other methods of checking, the self-checking circuits were designed:
self-checking combinational circuits;
self-checking asynchronous and synchronous sequential machines;
self-checking Adders and ALUS, Multiply and Divide Arrays.

4.3. Self-Checking Circuits

Design of Self-Checking circuit

108

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

There were determined:
conditions to detect faults using resources required for one error;
requirements to on-line testing methods to detect a fault using the first error produced in computed result;
high level reliability and productivity of modern computing circuits.

4.3. Self-Checking Circuits

Value of Self-Checking circuit

109

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

They have fixed the following dogmas:

Purpose of on-line testing is to detect a fault of the circuit.

On-line testing methods have to detect a fault using the first error produced in computed result.

The correct circuit calculates a reliable result, and non-reliable result is computed only on faulty circuit.

4.4. Purpose of On-Line Testing

Dogmas of Self-Checking Circuit Theory

110

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Is this truth?

the correct circuit is necessary only to calculate reliable result, and in itself is not meaningful.

The truth is that

4.4. Purpose of On-Line Testing

Dogmas of Self-Checking Circuit Theory

111

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Purpose of on-line testing is

to detect a fault of the circuit

to estimate reliability of the circuit

to answer a question “Is the circuit correct or not?”

during the main operations

using actual data.

or

4.4. Purpose of On-Line Testing

Dogmas of Self-Checking Circuit Theory

112

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This presentation will show that declared purpose

defies common sense

contradicts actual on-line testing application

is not achievable for self-checking circuits

during the main operations

using actual data.

and

4.4. Purpose of On-Line Testing

Dogmas of Self-Checking Circuit Theory

113

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Purpose of on-line testing is to detect a circuit fault during the main operations using actual data.

Declared purpose defies common sense.

Let’s consider computational process as a plane flight.

Detection of the plane faults should be carried out before the flight start.

Search for faults during the flight would extremely surprise the passengers.

Creation of the critical conditions is
the best way to detect a fault!

The fault can be much more efficiently detected using the off-line testing methods during pauses of the operations.

4.4. Purpose of On-Line Testing

114

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Faulty circuit can be considered as a mine field.

Test input words are minesweepers that detect mines before the main operations.

Actual data is a farmer working in the field.

Circuit fault is a mine.

4.4. Purpose of On-Line Testing

Purpose of on-line testing is to detect a circuit fault during the main operations using actual data.

Declared purpose defies common sense.

115

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Transient faults occur much more often than permanent faults.

Therefore, as a rule, the first detected error is produced by transient fault.

Transient faults are valid for a short period of time.

Therefore, after this period a circuit will be correct again.

That’s why on-line testing is not used for circuit fault detection.

4.4. Purpose of On-Line Testing

Purpose of on-line testing is to detect a circuit fault during the main operations using actual data.

116

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Declared purpose is not achievable for self-checking circuits

The first detected error can be produced
by either transient or permanent faults.

In case of transient fault
the conclusion that the circuit is faulty will not be true after a short period of time.

The first detect is not enough to identity the permanent fault. It requires to detect many errors.

Therefore, the first detected error cannot answer a question "Is the circuit faulty or not?"

4.4. Purpose of On-Line Testing

117

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

to estimate reliability of the calculated result

to answer a question “Is the result reliable or not?”

during the main operations using actual data.

or

4.4. Purpose of On-Line Testing

118

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Actual purpose of on-line testing can be derived from the practice of its application.

The correct circuit is only necessary to get a reliable result from actual data.

That is why reliability of the circuit by itself should not be the subject of estimation during the main operations.

is to estimate reliability of a circuit

Correct circuit is only required to get a reliable result from actual data

The result is checked to answer a question “Is a circuit correct or faulty”

Means to achieve purpose

PURPOSE

4.4. Purpose of On-Line Testing

119

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

What is the reason to declare incorrect purpose?

This reason is the Model of Exact Data

4.5. Model of Exact Data

120

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

The error is a difference between absolute and relative trues,
i.e. the universe is learnt by means of an error.

Development of the universe is carried out
by a trial and error method.

All exists within the limits of admissions.
The right to make an error is the right to exist.

Quantitative estimations of all things in the universe are numbers with admissions, which are their vital space.
These numbers are the approximated data.

4.5. Model of Exact Data

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

121

For example, 4-bits codeword has the following values and their ordinal numbers:

What is Exact Data?

The Exact Data enumerates elements of a set, i.e., it includes only “integers by nature”.

0 0 0 0

0

0 0 0 1

1

0 0 1 0

2

0 0 1 1

3

4.5. Model of Exact Data

122

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Many concepts
first of all connected to a computer,
are under influence of model of the exact data

4.5. Model of Exact Data

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

123

It is true only
in case of exact data.

self-checking circuit techniques to obtain reliable results on correct circuit only;

4.5. Model of Exact Data

124

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

This identifies the declared and actual purposes
for the case of exact data.

A detected error concurrently shows that the calculated result is non-reliable and the circuit has a fault.

4.5. Model of Exact Data

125

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

the declared on-line testing purpose to estimate reliability of a circuit through detection of its fault;

The first error detection allows to recalculate this result as soon as it is possible in case of exact data.

The first error detection is the fastest way to receive reliable results in case of exact data.

the main requirement to on-line testing methods: detect the first error produced by the circuit fault;

4.5. Model of Exact Data

126

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

On-line testing is based on the Model of Exact Data

the declared on-line testing purpose to estimate reliability of a circuit through detection of its fault;

the main requirement to on-line testing methods: detect the first error produced by the circuit fault;

the on-line testing development within the framework of the exact data processing only.

4.5. Model of Exact Data

127

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

On-line testing is based on the Model of Exact Data

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4. Self-checking circuits theory defines a purpose of on-line testing as estimation of the circuit reliability, however the actual purpose is checking the result reliability.

5. Model of exact data defines development of on-line testing within the framework of the exact data processing

2. In development of on-line testing it is possible to select three stages: the initial stage, stage of becoming – self-checking circuits development expanding the on-line testing for own means within the framework of the exact data processing, the present stage of on-line testing development for processing of the approximate data.

3. Totally self-checking circuits detect the faults using the first error of the calculated results

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.3. Complete and Truncated Operations

5.4. Features of Approximate Data Processing

5.2. Floating-point Formats and Arithmetic

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.5. Probability of an essential error

5.1. Introduction into Approximate Data Processing

131

Our Universe is approximate and all in it are structured under its realities including computer Processing

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.1.1. Motivation of Approximate Data Processing Consideration

Reasons:

That’s why Universe generates approximate data

132

5. Drozd A. On-line testing of computing circuits at approximate data processing / A. Drozd // Радіоелектроніка та інформатика. 2003. № 3. – С. 113 – 116.

2. ANSI/IEEE Std 754-1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE, New York, USA, 1985. – 18 c.

3. Рабинович З. Л., Раманаускас В. А. Типовые операции в вычислительных машинах. – Киев: Техника, 1980. – 264 c.

4. Савельев А. Я. Прикладная теория цифровых автоматов. – М.: Высш. шк., 1987. – 272 c.

133

6. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Физматгиз, 1966. – 664 с.

Sensors

Comparators

Processor

Sensors

Processor

Comparators

Two kinds of the S-CES:

5.1.3. Data processed in the S-CES

RM , RE and RA – are the results of measurements, exact and approximate data processing accordingly

Processor of the first kind of S-CES operates with exact data

Processor of the second kind of S-CES operates with approximate data

134

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

A significance of approximate data processing rapidly increases with the computers development.

For example, Intel processors 286 and 386 are complemented in PC by outside coprocessors 287 and 387 operating with floating-point formats.

Starting from processor Intel 486DX the inside coprocessors are used for operating with floating-point formats.

Pentium-processors have pipeline inside coprocessors.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.1.3. Approximate Data Processing

135

However it is necessary to solve a computing task in range
0 ÷ 1000.

For example, it needs to calculate 800 + 100.

This problem was decided using scale index kМ ≥ 1000 / 255

Initial data transforms from range of the computing task into range of the codeword:
kМ = 4: 800 / 4 = 200; 100 / 4 = 25; 200 + 25 = 225;
Restoring range of the computing task: 225 × 4 = 900.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.2. Floating-point Formats and Arithmetic

136

The exact data are represented in true form using one component because volume of range and accuracy strongly connected between themselves by size of the codeword.

Approximate data are represented in normal form using two components by reason of significantly different requirements advanced to volume of range and accuracy.

Size of mantissa determines accuracy and exponent size – range.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.2. Floating-point Formats and Arithmetic

137

That’s why
multiplication is presented in all operations executed with mantissas;
operations with mantissas and their results inherits the properties and features of a multiplication and a product accordingly

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.2. Floating-point Formats and Arithmetic

138

For example,
an addition of mantissas is executed by matching the exponents shifting one of the mantissas, where shift is special case of multiplication.
a results of two-place operation has double size

139

Standard IEEE-754 (1985)

Base Formats

Single Formats

Double Formats

Single and Double

140

Standard IEEE-754 (1985)

141

Standard IEEE-754 (1985)

142

Standard IEEE-754 (1985)

Real number in true form

A{1 ÷ n}:

B{1 ÷ n}:

V{1 ÷ 2n}:

n = 8

V{1 ÷ 2n – k}:

V{1 ÷ k}:

k

k = n – log2n

k = 5

Truncated multiplication with mantissas reduces almost twice hardware overhead
and time operation without lowering an accuracy

145

Truncated restoring division

Truncated restoring division with mantissas reduces almost twice hardware overhead
and time operation without lowering an accuracy

146

Truncated non-restoring division

Truncated non-restoring division with mantissas reduces almost twice hardware overhead
and time operation without lowering an accuracy

147

Truncated operation of shift in mantissa addition

Truncated operation of mantissas shift
twice reduces hardware overhead
without lowering an accuracy

A product of two operands doubles a size of the result.

Therefore, the main floating-point formats have a single precision.

According to the error theory, a number of exact bits in a result does not exceed a number of exact bits in the operand.

148

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.4. Features of approximate data processing

Addition of one million to a unit renders the result of one million because the unit is lost during the exponents matching.
One million of such operations also renders the result equal to the first number, which is one million.

5.4. Features of approximate data processing

2. Data processing in extended formats

149

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.4. Features of approximate data processing

2. Data processing in extended formats

150

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Addition of one million with one million of units by implementing the binary operations with codeword size n < 20

Mantissa of the number with the smaller exponent is shifted down with loss of least significant bits (LSB).
Then, the LSB in the result of all previous operations are eliminated from further calculations.

5.4. Features of approximate data processing

3.1. Denormalization of an operand mantissa at the matching the exponents

151

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Mantissa of the result is cyclic shifted to the left with filling the low position by LSB.
Then, the result of all following operations contain the additional LSB.

5.4. Features of approximate data processing

3.2. Normalization of the result mantissa

152

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Definition:

An approximate result has exact most significant bits (MSB) and non-exact LSB:

5.5. Probability of an Essential Error

Essential and Inessential Errors

153

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Eliminated errors are inessential.

A half of all errors is inessential.

Factor K1 defines a share of errors remained after elimination of LSB.

n and nс are numbers of kept and total calculated bits.

The factors lowering a probability of essential error

154

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

5.5. Probability of an Essential Error

Factor K2 defines a share of essential errors in extended format.

In the formats for floating-point arithmetic on PC size of mantissa increases 2.7 times from 24 bits in a single format up to 64 bits in a double extended format.

5.5. Probability of an Essential Error

The factors lowering a probability of essential error

2. Increase of a share of inessential errors with use of the extended formats

155

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

For series of denormalization, K3 is defined as a product of the factors K3.1 calculated for each of these operations.

5.5. Probability of an Essential Error

The factors lowering a probability of essential error

3.2. Elimination of errors in results of all previous operations

156

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

For series of normalization, K3 is defined as a product of the factors K3.2 calculated for each of these operations.

5.5. Probability of an Essential Error

The factors lowering a probability of essential error

3.2. Reducing the essential errors amount in results of operations following after normalization

157

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

with inessential errors in results of all next operations

5.5. Probability of an Essential Error

The factors lowering a probability of essential error

158

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

4. The truncated operations are the main methods for processing mantissas in floating-point formats.

5. The errors produced by the circuit faults in MSB and LSB of approximated results are essential and inessential accordingly

2. Approximate data contain results of measurements and are processed in normal form using the floating-point formats, such as Standard IEEE 754 formats.

3. Approximate data are represented using two components by reason of significantly different requirements advanced to volume of range and accuracy: size of mantissa determines accuracy and exponent size – range.

6. Features of approximate data processing determine factors significantly lowering a probability of an essential error which is the general parameter of on-line testing objects.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.4. Residue checking a truncated multiplication

6.5. Residue checking a truncated division of mantissas

6.2. The ways for increasing on-line testing reliability

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.6. Residue checking a truncated operation of shift

6.1. Reliability of traditional on-line testing methods

162

6.3. The first way for increasing on-line testing reliability

Our universe is approximate and all in it are structured under its realities including on-line testing methods

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.1.1. Motivation of traditional on-line testing methods reliability consideration

Reasons:

Traditional on-line testing methods have been developed for exact data processing and was estimated within framework of Exact Data Model.

163

2. Щербаков Н. С. Достоверность работы цифровых устройств. – М.: Машиностроение, 1989. – 224 c.

4. Рабинович З. Л., Раманаускас В. А. Типовые операции в вычислительных машинах. – Киев: Техника, 1980. – 264 c.

5. Савельев А. Я. Прикладная теория цифровых автоматов. – М.: Высш. шк., 1987. – 272 c.

164

6. Граф Ш., Гессель М. Схемы поиска неисправностей. – М.: Энергоатомиздат, 1989. – 144 с.

3. Согомонян Е. С., Слабаков Е. В. Самопроверяемые устройства и отказоустойчивые системы. – М.: Радио и связь, 1989. – 208 с.

6.1.3. What is reliability of on-line testing methods?

Such view on reliability of on-line testing method does not take into account features of on-line testing objects:

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

165

Reliability of on-line testing method should be considered using two parameters:
probability of error detection characterizing an on-line testing method;
probability of essential error characterizing an on-line testing object.

6.1.3. What is reliability of on-line testing methods?

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

166

РE is a probability of an essential error

PDN is a probability of inessential error detection.

РE

РN
РD
РS

PDE is a probability of essential error detection.

РD is a probability of error detection

PSN is a probability of inessential error skipping.

PSE is a probability of essential error skipping.

РN is a probability of an inessential error РN = 1 – РE

РS is a probability of error skipping РS = 1 – РD

PDE +
+ PDN +
+ PSE +
+ PSN = 1

6.1.3. What is reliability of on-line testing methods?

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

167

РE

РN
РD
РS

Estimation of on-line testing method Reliability as a Probability of error detection ignoring a Probability of essential error follows from the Model of Exact Data.

According to declared purpose of on-line testing a method is reliable if the circuit fault is detected irrespectively of error type (essential or inessential).

RDR = PDE + PDN =
= PD

6.1.3. What is reliability of on-line testing methods?

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

168

РE

РN
РD
РS

According to actual purpose of on-line testing a method is reliable if correctly estimates a calculated result as reliable or non-reliable.

RAR = PDE + PSN =
= PD PE + (1 - PD) (1 - PE)

An on-line testing method defines a result as non-reliable by the error detection. However an actual tag of non-reliable result is essential error occurrence.

it states the truth about the result: detects the essential errors in case of non-reliable result and skip inessential ones otherwise.

Reliability of on-line testing method is consist of the checking the results

Exact results have probability PE = 1.

Traditional on-line testing methods demonstrate high reliability in checking the exact results.

6.1.4. Reliability of on-line testing methods for exact data
РD

РS

1
РDE

3 РSE

RAR = PDE + PSN = PD PE + (1 - PD) (1 - PE)

РE

169

RAR = PD

RAR → 1.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

РE

РN
РS
РD

6.1.5. Low reliability of traditional on-line testing methods

RAR = PDE + PSN = PD PE + (1 - PD) (1 - PE)

2. Approximate results have low probability of essential error PE

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

170

Reliability of traditional on-line testing methods contains low parts 1 and 4 of unit-side square: RAR → 0.

РE

РN
РS
РD

6.1.5. Low reliability of traditional on-line testing methods

New property of on-line testing methods

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

171

An on-line testing method becomes approximate as our Universe.

1. A difference between declared and actual purpose of on-line testing is defined by the part 2 describing a probability of inessential error.

2. This part 2 is largest in unit-side square and its area is close to unit: PDN → 1

NEW VIEW
Existing on-line testing is applicable to the exact data only.
A purpose of on-line testing is to estimate reliability of computation result.
Processed numbers are in most cases approximate data.
Basically, the errors are inessential.
Traditional on-line testing methods have low reliability of result checking: mainly detect inessential errors. 

172

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.1.5. Low reliability of traditional on-line testing methods

COMPARISON

D↑= РD ↑ Р E ↑ или РS↓ Р N ↓

2. РE < 0,5

3. РD-E > РD-N

173

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.2. The ways for increasing on-line testing reliability

174

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.2. The ways for increasing on-line testing reliability

1. The first way is increasing the part 1 of unit-side square raising a probability of essential error

175

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.3. The first way for increasing on-line testing reliability

3. This way provides the high probability of essential error detection

2. The first way allows to develop the on-line testing methods with traditionally high probability of error detection

High probability of essential error
РE > 0,5
can be achieved only for
truncated operations

Residue checking is the main on-line testing method for arithmetic of complete operations

That’s why residue checking is rationally to extend on truncated operations

1. Residue checking of truncated operations

V1

V2

V3

V6

V8

V9

V10

V11

V5

V7

V4

177

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

6.4. Residue checking a truncated multiplication

The method is based on a decomposition of high part of the product conjunction array (PCA) into fragments.

A fragment is defined as a part of PCA described with a product
Vi = ±Ai Bi ,
where Ai and Bi are operands A and B or their parts.

For example, fragment V1:
V1= –A{5 ÷8} B{11 ÷14} 2–22,
A1= A{5 ÷8} 2–8; B1=B{11÷14} 2–14

The method compares the check codes of truncated product calculated by two ways:
using truncated product;
using operands.

High part of the PCA can be represented as a sum of fragments:

The method uses definition of a fragment and representation of a truncated product in check codes:

Blocks BA and BB check the operands A and B by computing the check codes KA and KB and comparing them with the input check codes KA and KB. Results of comparison are the error indication codes KA and KB.
The check codes KAi and KBi are composed of operand bits or computed during the generation of the check codes KA and KB.

Block M computes the check codes KVi, i=1÷k-1, of the fragments by the formula (1). Block A calculates the check code KVT of the truncated product by the formula (2).
The block G generates the check code KVS of the excluded bits VS. Block S computes the check code of the result KVV.
Block BV checks the result VR by comparing it with the check code KVV. Result of comparison is the error indication code KV.

The method of residue checking a truncated multiplication defines the following steps:
Choice of the PCA decomposition into fragments;
Description of fragments;
Description of the check codes KAi and KBi composed of operands bits;
Definition of formulas for calculated check codes KAi and KBi;
Design of the blocks BA and BB in accordance with obtained formulas;
Design of the blocks M and A taking into account the descriptions of fragments and check codes KAi, KBi;
Design of the blocks G and S using values of n and k;
Design of the block BV as a block BA for the following error detection circuit where result is used as operand.

Choice of the PCA decomposition into fragments should be aimed to design a high quality error detection circuit.

Hardware overhead of the error detection circuit is mainly defined by complexity of the blocks BA and BB which as compaction scheme does not depend in complexity on the PCA decomposition.

Time of check can be reduced using the following procedure for defining the PCA decomposition.

Decomposition is defined specifying a sequence of central - symmetric fragments.

The first central - symmetric fragment
Vi = –A{n-Li+1 ÷ n} B{n-Li+1 ÷ n}2-2n
has size Li=2 Е(k/4+1).

It defines high and low parts like the PCA high part with k = k – Li. Process is following before k>1.

Blocks of the error detection circuit are developed taking into account decomposition of the PCA into fragments.

Development
of the block BB

Sequence of Computations
KB1= B{11÷14} mod 3;
KB7= B{5÷8} mod 3;
KB5= KB1+B{9, 10};
KB11= KB5+KB7+B{1÷4} mod 3

Adders 1 ÷ 7 by modulo 3

Hardware overhead
of Error Detection Circuit:
HEDC = 4n + k (in FA – full adder)
of Multiplier:
HMUL = n2 – k2 / 2 (in FA)
Relative
HE / M = (8n + 2k) / (2n2 – k2)

Correlation of truncated multiplication and division

A truncated non-restoring division is an inverse operation for truncated multiplication of the binary divisor on quotient represented in notation 1,1.

Truncated multiplication of divisor D = d{1 ÷ n}⋅2-n on quotient Q = q{0 ÷ n}⋅2-n determines left part 1 of Conjunctions Array (CA).
Truncated (2n – k)-bits product
VTR = V{1 ÷ 2n – k}⋅2–(2n–k),
is calculated on this part as VTR = A – RTR, where A=a{1 ÷ n}⋅2-n is dividend; RTR=r{1 ÷ n–k}⋅2–(n–k) is truncated remainder.

CA for product of divisor on quotient

Decomposition of the CA left part on k+1 fragments Vi = Di ⋅ Qi , i = 1 ÷ k+1 (k=3, i = 1 ÷ 4)

V1 = D{1÷3} ⋅ Q{6}⋅ 2-9;
V2 = D{1÷4} ⋅ Q{5}⋅2-9;
V3 = D{1÷5} ⋅ Q{4}⋅ 2-9;
V4 = D{1÷6} ⋅ Q{0÷3}⋅2-9.

KD1 = – D{1÷3} mod 3;
KD2 = (KD1 + D{4}) mod 3;
KD3 = (KD2 – D{5}) mod 3;
KD4 = (KD3 + D{6}) mod 3;

KQ1 = Q{6};
KQ2 = –Q{5};
KQ3 = (Q{6};
KQ4 = – Q{0÷3} mod 3;

Error Drtection circuit

Blocks 1 and 2 check the input numbers: dividend A and divisor D.
Blocks 3 and 4 generate check codes KQ and KR of quotient Q and residue R.
Blocks 5 and 6 calculate check codes КVTR and КVTR*.
Block 7 compares check codes КVTR, КVTR* and calculates indicate code КQ.

A

D

КA

КD

2

1

3

4

RTR

Q

5

6

7

KQi

KRTR

KQ

KDl

KVTR

KVTR*

KQ

KA

KD

КA

Truncated shift is executed in floating-point addition

1. Definition of operation C=A+B,
where A=a1⋅2a2; B=b1⋅2b2; C=c1⋅2c2.

2. Execution of operation

2.2. Processing the mantissas
a1 SHIFT = a1⋅2-da;
b1 SHIFT = b1⋅2-db;
c1 = a1 SHIFT + b1 SHIFT.

2.1. Processing the exponents
c2 = max (a2, b2);
da = c2 - a2; db = c2 - b2.

1

2

3

a1 SHIFT

b1 SHIFT

c2

c1

b2

a2

a1

b1

da

db

3. The floating-point adder consists of
the block 1 for the exponent processing,
barrel-shifters 2 and 3,
adder 4.

Arithmetic shift of a mantissa

An operation of arithmetic shift contains three actions: aSHIFT = a⋅2-d - a0 + as.
1. The reduction of the bit weights for the mantissa a in 2d times.
2. The truncation of the d low bits of the mantissa a (the code a0=a{n-d+1÷n}).
3. The sign bit padding in the position with bit weights 2-1÷2-d for complement code of the mantissa a. Sign bits sa … sa compose the code as.

Arithmetic shift is executed using the Barrel-shifter

The Barrel-shifter contains n of n-to-1 multiplexers.
The multiplexer hardware overhead q is proportional to the operand size n.
The barrel-shifter hardware overhead QSHIFT=nq is proportional to the square of the operand size n and makes the main hardware overhead of the floating-point adder.
Barrel-shifter executes a truncated operation, which reduces twice the hardware overhead in comparison with the long shifter computing complete 2n-bit result aC=aSHIFT{1÷2n}2-2n.

Shift matrix

Conversion a0 into a01 = a0⋅2d

Conversion a01 into a02 with keeping the bit weights by mod 3

Conversion a01 into a02 with calculating the check codes

ka4÷7{2,1}=
a{4÷7}mod3

ka12÷15{2,1}=
a{12÷15}mod3

ka8÷15{2,1}=
(a{8÷11}+
ka12÷15{2,1})
mod3

Simplification of the checking computation

1. Conversion of the restricted bits a0 in the code a01 simplifies the unit 3 in σ01 = 1.5 times.

kaSHIFT

Ka

ka

2

1

a

ka

3

d

4

d{1}

7

sa

a03

5

kad

kas1

kaV

6

ka03

2. Conversion of the code a01 in a02 simplifies the unit 3 in σ02=2n/r times. For n=15 σ02=7,5.

3. Conversion of the code a02 in a03 simplifies the unit 3 in σ03=2n/3 times and the unit 6 in σ=n/(2r-1) times. For n=15 σ03=10, σ =2.1.

The checking hardware overhead reduces from square dependence on the operand size to linear one.

Unit 1: modulo-3 generator Unit 3: generator of the check code ka03
Unit 2: modulo-3 comparator Unit 4: generator of the check code kas1

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

3. The firs way can be realized using truncated operations only because only these operations can have the high probability of essential error.

4. The first way allows to develop the on-line testing methods with traditionally high probability of error detection

2. On-line testing reliability can be increased by three ways: increasing a probability of essential error; reducing a probability of error detection and also detecting essential and inessential errors with different probabilities.

5. The truncated multiplication can be checked by modulo using decomposition of product conjunction array into fragments.

6. The another truncated operations can be checked using fragment approach as well as they inherit the properties of multiplication.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.4. Checking of a squarer

7.5. Checking by simplified operation

7.2. Checking with use of natural information redundancy

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.6. The models of operation simplification

7.1. The second way for increasing on-line testing reliability

199

7.3. The use of product information redundancy

7.7. Execution of check calculations

The second way increases on-line testing reliability using a low probability of essential error.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.1.1. Motivation of increasing an on-line testing reliability by the second way

Reasons:

On-line testing objects, as a rule, have a low probability of essential error.

200

2. Сушкевич А. К. Теория чисел. – Харьков: Изд. ХГУ, 1956.

201

4. Граф Ш., Гессель М. Схемы поиска неисправностей. – М.: Энергоатомиздат, 1989. – 144 с.

3. Селлерс Ф. Методы обнаружения ошибок в работе ЭЦВМ. – М.: Мир, 1972. – 310 c.

Reduction requirements to error detection promote simplification of the check circuits.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.1.3. Features of the second way

202

Earlier reduction of an error detection probability has been aimed at simplification of the on-line testing means.
However now the goal is increase of reliability of the on-line testing methods. This goal can be achieved with simplification of the check circuits.

Every probable fault should be detected at least an input codeword.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.1.3. Features of the second way

203

The probable fault distorts a result at the output of single-step arithmetic circuits on the weight of any one bit.
The error looks like ±2r, where r is number of the result bit.

The set of faults detected by residue checking (modulo three) can be used as the comparison templet of set of the probable faults.

Natural information redundancy is alternative to information redundancy created by expansion of a code introducing the additional bits.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.2.1. Natural information redundancy

204

Considered checking methods use natural information redundancy of the arithmetic operation results.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

A product of complete operation has natural information redundancy.

205

Both sets of input and output words of multiplication have the same capacity 22n, where n is size of operands.

However the same output word can correspond to several input words.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

206

A prime number С = 2n + 1 cannot be a product of two n-bit binary factors.

Euler (1707-1783) refuted of
Fermat statement for x = 5, but the statement are true for x < 5
including the cases of wide-spread word size n = 8 and n = 16.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

207

These words compose double code G(n, n) without zero-word.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

208

Error is detected, if only one of two conditions performs:
(A{1 ÷ n} ≠ 0) & (B{1 ÷ n} ≠ 0);
V{1 ÷ n} = V{n + 1 ÷ 2n}.

Every probable fault of iterative array multiplier is detected at least on one input word: A{1 ÷ n} B{1 ÷ n} ± 2r = k (2n + 1).
It is proved by factorization of the formula k (2n + 1) ± 2r on multipliers A{1 ÷ n} and B{1 ÷ n} at least for one value k.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

209

The first block B1 consists of two n-bits gates OR 1.1 and 1.2 which check the conditions A{1 ÷ n} ≠0 and B{1 ÷ n} ≠ 0, and gate AND 1.3 computes the bit E{1} from condition, that both of the factors are not zero.
The second block B2 is comparator of the low and high product bits. It computes the bit E{2}.

The code E{1, 2} = 002, if at least one of factors is zero and the product is not zero: the low and high parts of product are different.
The code E{1, 2} = 112, if both of the factors are not zero and the product assumes forbidden word: the low and high bits of product are equal.
The code E{1, 2} = 012, if at least one of the factors is zero and the low and high bits of product are equal: V{1 ÷ 2n} = 0.
The code E{1, 2} = 102, if both of the factors are not zero and the low and high parts of non-zero product are different.

If E{1, 2} = 002 or 112 then fault is detected;
If work is correct then E{1, 2} = 01 or 10.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

210

Such range excludes zero as a value of a product.

The checker contains only the comparator (Block B2) which can be designed on Carter's units.

This peculiarity eliminates a check of factors to be equal to zero and eliminates the block B1 of the checker.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

211

Time of permanent fault detection T = ln 2 / PD,
Tn=8 = 59; Tn=16 = 15142 (clock units);

The checker based on use of prime numbers is simplest for multipliers. It is simpler of the residue checker more than 5,3 times.

A reliability of the checking method R = 1 – PE,
R = 0,9 for PE = 0,1.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

212

This checking method can be extended on another size of word using prime number C* = 2n – 1.

A prime number С* = 2n – 1 can be a product of two n-bit binary factors only in case the factor is equal to С*.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

213

These words compose double code G(n, ¬n) with inverse part without words which are equal to С* in their high part.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

214

Error is detected, if only one of two conditions performs:
(A{1 ÷ n} ≠ C*) & (B{1 ÷ n} ≠ C*) for A{1 ÷ n}, (B{1 ÷ n} ≠ 0
V{1 ÷ n} = ¬ V{n + 1 ÷ 2n}.

Every probable fault of iterative array multiplier is detected at least on one input word: A{1 ÷ n} B{1 ÷ n} ± 2r = k (2n – 1).
It is proved by factorization of the formula k (2n – 1) ± 2r on multipliers A{1 ÷ n} and B{1 ÷ n} at least for one value k.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

215

The first block B1 consists of two n-bits gates AND 1.1 and 1.2 which check the conditions A{1 ÷ n} = C* or B{1 ÷ n} = C*, and gate OR 1.3 computes the bit E{1} from condition, that at least one of the factors is equal to C*.
The second block B2 is comparator of the low and inverse high product bits with inverse output. It computes the bit E{2}.

The code E{1, 2} = 112, if at least one of factors is C* and the low and high parts of product are not inverse.
The code E{1, 2} = 002, if both of the factors are not equal to C* and the low and high bits of product are inverse.
The code E{1, 2} = 012, if at least one of the factors is C* and the low and high bits of product are inverse.
The code E{1, 2} = 012, if both of the factors are not equal to C* and the low and high parts of non-zero product are not inverse.

If E{1, 2} = 002 or 112 then fault is detected;
If work is correct then E{1, 2} = 01 or 10.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

216

Both the checking method and checker are quite correct for mantissa processing taking into account a range of the normalized mantissa codeword: 2n – 1 ÷ 2n – 1.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Checking the products using prime numbers

217

Time of permanent fault detection T = ln 2 / PD,
Tn=7 = 30; Tn=8 = 30284 (clock units);

The checker based on use of prime numbers is simplest for multipliers. It is simpler of the residue checker more than 5,3 times.

A reliability of the checking method R = 1 – PE,
R = 0,9 for PE = 0,1.

A
Squarer
B1
B2

S

E

Error detection circuit

Block B2 calculates check code E which identifies the forbidden values of residue R.

Way 2. Decrease of PD 

218

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.4. Checking of a squarer

Error detection circuit of squarer

m = 15

3. Creation of a set Z of the forbidden values z;

Estimation of error detection probability

2. Creation of a set X of the allowed values x for the residue R and an index F of their occurrences for values of an operand on the period А = 0 ÷ m – 1.

219

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.4. Checking of a squarer

Estimation of error detection probability

220

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.4. Checking of a squarer

4.1 A set Y of the typical error y = ± 2r by modulo m is finite: positive errors not more m and negative errors not more m.

4.2 The typical error y = ± 2r by modulo m can be obtained duplicating value of the error by modulo m from 1 before 1 or – 1.

4.3 This process can be considered in detail on example m = 13.

20=1, 1×2=2, 2×2=4, 4×2=8, 8×2=16: 16 mod 15 = 1.

20=1, 1×2=2, 2×2=4, 4×2=8, 8×2=16:
–13
3, 3×2=6, 6×2=12
–13
–1

m = 13

Y {1, 2, 4, 8, 3, 6}.

6. Calculation of maximal PH and minimal PL error detection probabilities:
PH = SumMAX / (m Y*);
PL = SumMIN / (m Y*),
where SumMAX is the sum of all elements of the table;
SumMIN is the least sum of lines which elements cover all columns;
Y* is amount of elements in set Y.

PD H = 0,75

PD L = 0,15

SumMAX = 90

SumMIN = 18 for z = 11 and z = 14

Y* = 8

221

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

m = 15

7.4. Checking of a squarer

Estimation of error detection probability

222

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.4. Checking of a squarer

Estimation of the checking method reliability

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Simplification of operation

223

Such solution is not correct: the probable faults – shorts between the same bits of the factors – are do not detected.

This solution can be improved using the factors which are equal by modulo 3.

For example, a multiplier can be checked as squarer on input words composed of equal factors.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Limiting conditions

224

Simplification bottom-up: limiting conditions imposed upon operands determine limiting condition for the result.

Simplification top-down: limiting condition imposed upon result determine limiting conditions for the operands.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

The models of the Operation Simplification

225

Composite LC is LC for operands composed of some LC.

The LC for operands can be dependent or independent determining equal or different LC for the result accordingly.

In order to keep a set of the detected fault
the dependent LC should be processed only using logic operations OR or XOR;
the independent LC should be processed only using logic operations AND.

Object of
on-line testing
B2
B3

V

E

Error detection circuit

B

A
B1

226

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

7.5. Checking by simplified operation

Structure of the Error detection circuit

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

The models of execution of the check calculations

227

The codes of LC are formed by modulo 3 keeping a set of the faults detected if the residue checking.

Both the logic operation OR with allowed values and AND with forbidden values of the LC codes are executed on a Carter's unit.

The codes of LC can take allowed values 012 or 102 and forbidden values 002 or 112.

The logic operation NOT transforms the allowed values to forbidden one’s or on the contrary inverting one of code bits by NOT-unit.

The Carter's and NOT units allow to execute any logic operation as well as OR, AND, NOT compose functionally complete basis.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

Design of the Checker

228

For example, the LC for multiplier checker (complete operation) with low PD = 0,07 can be determined as follows.
G is a set of total inputs word

Design of the Checker

229

M – the generator of residue code;
UC – the Carter’s unit;
UN – the NOT-unit;
– the inverse output;
BD – the block forming the dependent LC;
BI – the block forming the independent LC;
BL – the block executing the logic operation with the codes of LC;
KL – the composite code of dependent LC;
KC – the composite code of independent LC;
KM– the code of error indication

КA = A mod 3; КV1 = V1 mod 3;
КB = B mod 3; КV2 = V2 mod 3;
КR* = R mod* 3.

Estimation of the method

230

Reliability of the checking by simplified operation in comparison with the residue checking method

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. The natural information redundancy of a complete product can be realized using the prime numbers.

4. The squarer can be effectively checked using the forbidden values of a residue by modulo.

5. The checking by simplified operation determines and forms by modulo the limiting conditions for operands and result and also executes the logic operation with these conditions.

6. The second way for increasing a reliability of on-line testing methods reduces a probability of error detection without truncating a set of the detected faults.

3. The use of the prime numbers allows to design the simplest checkers for on-line testing of the iterative array multiplier.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

8.4. The checking by segments

8.2. The logarithm checking

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

8.1. The third way for increasing on-line testing reliability

234

8.3. The checking by inequalities

The third way is directly aimed at distinction of essential and inessential errors taking into account a size of the error.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

8.1.1. Motivation of increasing an on-line testing reliability by the third way

Reasons:

235

2. Журавлев Ю. П., Котелюк Л. А., Циклинский Н. И. Надежность и контроль ЭВМ. – М.: Советское радио, 1978. – 416 c.

236

4. Тоценко В. Г., Киселев И.М. Метод повышения эффективности диагностирования дискретных устройств с регулярной структурой // Управляющие системы и машины. – 1977. – № 5. – С. 97 – 102.

3. Моллов В. К. Структурно-функциональные методы оперативного контроля и диагностики цифровых устройств управляющих систем: Автореф. дис. . . канд. техн. наук: 05.13.13 / Киевск. политехн. ин-т – Киев, 1989. – 16 с.

5. Байда Н. П., Кузьмин И., Шпилевой В. Микропроцессорные системы поэлементного диагностирования РЭА. – М.: Радио и связь, 1987. – 256 c.

The third way increases on-line testing reliability estimating a size of the result and its error.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

8.1.3. Features of the third way

237

The methods of a third way difference the essential and inessential errors as well as well detect an error in high and low bits of the result.

8.2. The logarithm checking

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

238

0

0

0

0

0

1

0

0

0

0

1

0

1

NIR

NIR

1. Fixed-point format

2. Floating-point format

8.2.1. The use of the Natural Information Redundancy

8.2. The logarithm checking

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

239

1. Fixed-point format

2. Floating-point format

KA

KA

8.2.2. Definition of the check code of a number or mantissa

KA = Int (log 2 A) for A > 0;
KA = 0 for A = 0.

Check code КА of mantissa A is equal to amount of bits of a check part of this mantissa.

KA = Int (log 2 (A-1) for A > 0.

8.2. The logarithm checking

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

240

8.2.3. Calculation of the check code of a number or a mantissa

1. Filling the most significant (check) part by the units;

2. Calculation of units amount.

241

8.2.3.1. Filling the most significant (check) part by the units

0

0

0

0

1

1

1

1

1

1

1

1

1

1

A

B

1

1

1

A{15}

A{14}

A{13}

A{12}

A{11}

A{10}

A{9}

A{8}

A{7}

A{6}

A{5}

A{4}

A{3}

A{1}

1

1

1

1

1

1

1

1

1

1

B{15}

B{14}

B{13}

B{12}

B{11}

B{10}

B{9}

B{8}

B{7}

B{6}

B{5}

B{4}

B{3}

B{1}

1

242

8.2.3.1. Filling the most significant (check) part by the units

A circuit with a serial-group calculation of the code B

A circuit with a serial calculation of the bits in groups of the code B

243

8.2.3.2. Calculation of units amount

B{1÷15}

11

23

1

8

3

21

1

1

20

1

1

0

22

0

3

0

2

  ∙  For addition S = A + B, A ≥ 0 and B ≥ 0: KS = KS* + α, where KS* = max(KA, KB); α = 0 or α = 1.

∙  For multiplication P = A⋅B, A > 0 and B > 0: KP = KP* – α, where KP* = KA + KB; α = 0 or α = 1.

∙   For division Q = A / B, A > 0 and B > 0: KQ = KQ* + α, where KQ* = KA – KB; α = 0 or α = 1.

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

244

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

245

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

KA

KB

KS

KA

KB

KS

α = 0

α = 1

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

246

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

KAR = KA ∧ ¬U1 ∨ KB ∧ U1; KBR = KB ∧ ¬ U2 ∨ KS ∧ U2; KSR = KA ∧ U1 ∨ KS ∧ ¬ U2 ∨ KB ∧ U3,
where U1 = Sign A ⊕ Sign S, U2 = Sign A ⊕ Sign B, U3 = Sign A ⊕ Sign S.

 2 KA – 1 ≤ A < 2 KA

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

247

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

 2 KP – 1 ≤ P < 2 KP

 For KA = 3: 1002 ≤ A < 10002

 KP – 1 = (KA – 1) + (KB – 1)

 KP = KA + KB – 1

 KP = KA + KB

 2 KB – 1 ≤ B < 2 KB

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

248

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

249

8.2. The logarithm checking

8.2.4. The check equations for the arithmetic operations

 2 KQ – 1 ≤ Q < 2 KQ

KQ – 1 = (KA – 1) – KB

 KQ = KA – KB

 KQ = KA – (KB – 1)

 2 KB – 1 ≤ B < 2 KB

∙   For division: Q = A / B, A > 0 and B > 0, KQ = KQ* + α, where KQ* = KA – KB; α = 0 or α = 1.

 KQ = KA – KB + 1

8.2.4. The check equations for the arithmetic operations

∙   For division: Q = A / B, A  ≥ 0 and B > 0,
KQ = KQ* + α ;
KQ* = KA – KB;
where α = 0 or α = 1;
ZA – tag of zero for A;
ZA = 0 if A = 0 and ZA = 1 if A ≠ 0;

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

251

8.2. The logarithm checking

8.2.5. Circuits of the check

0→1

252

8.2.6. Error detection

8.2. The logarithm checking

γ

1→0

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

2. The error 1 → 0 in the bit γ is detected with PD = 2 – n + j – 2

253

8.2.6. Error detection

8.2. The logarithm checking

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

The error detection probability is proportional to value 2 – j of an error in the bit γ.

n – j + 2

n – j + 1

8.3. Checking by inequalities

Master Course. Co-Design and Testing of Safety-Critical Embedded Systems

254

1. Definition and calculation of high and low boards of the result