# Circuit Fault Diagnosis¶

Fault diagnosis is the combinational problem of quickly localizing failures as soon as they are detected in systems. Circuit fault diagnosis (CFD) is the problem of identifying a minimum-sized set of gates that, if faulty, explains an observation of incorrect outputs given a set of inputs.

A Half Adder made up of an XOR gate and an AND gate.

The following example demonstrates some of the techniques available to formulate a given problem so it can be solved on the D-Wave system.

## Circuit Fault Diagnosis with Explicit Fault Variables¶

We can construct the constraints for the circuit fault diagnosis in the following way:

• Each input/output/wire in the circuit is represented by a binary variable in the problem.

• Each gate can either be:
• Healthy, in which case it behaves according to it’s normal truth table.

• Faulty, in which case it does not.

To build these constraints, we start with the truth table for the gate we wish to encode, say an AND gate:

A

B

Output

0

0

0

1

0

0

0

1

0

1

1

1

We then add a new explicit fault variable, which encodes whether the gate is faulty or now.

A

B

Output

Faulty

0

0

0

0

1

0

0

0

0

1

0

0

1

1

1

0

0

0

1

1

1

0

1

1

0

1

1

1

1

1

0

1

This new truth table with the explicit fault variable allows the CSP to be satisfied even when the gate is not healthy.

### Example Code¶

The following code demonstrates how to find both fault diagnoses and minimum fault diagnoses for the above Full Adder.

```import dwavebinarycsp

from dimod import ExactSolver

def xor_fault(a, b, out, fault):
"""Returns True if XOR(a, b) == out and fault == 0 or XOR(a, b) != out and fault == 1."""
if (a != b) == out:
return fault == 0
else:
return fault == 1

def and_fault(a, b, out, fault):
"""Returns True if AND(a, b) == out and fault == 0 or AND(a, b) != out and fault == 1."""
if (a and b) == out:
return fault == 0
else:
return fault == 1

def or_fault(a, b, out, fault):
"""Returns True if OR(a, b) == out and fault == 0 or OR(a, b) != out and fault == 1."""
if (a or b) == out:
return fault == 0
else:
return fault == 1

csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)

# finally the AND gate

# now, say that the behaviour we witnessed was HA(0, 1, 0) -> 1, 1.
# The 'A' input to the circuit is 'A1'
csp.fix_variable('A1', 0)
# The 'B' input to the circuit is 'B1'
csp.fix_variable('B1', 1)
# the 'Cin' input to the circuit is 'B2'
csp.fix_variable('B2', 0)
# the sum output of the circuit is 'S2'
csp.fix_variable('S2', 1)
# the carry output of the circuit is 'ORout'
csp.fix_variable('ORout', 1)

# convert the csp to a bqm. We specify that the energy gap between the valid configurations and
# the invalid ones must be at least 2.0
bqm = dwavebinarycsp.stitch(csp, min_classical_gap=2.0)

# set up any dimod solver. In this case we use the ExactSolver but any unstructured solver would
# work.
sampler = ExactSolver()

# we can determine the minimum and maximum number of faults that will induce this behavior
response = sampler.sample(bqm)
min_energy = min(response.data_vectors['energy'])

fault_counts = []
for sample, energy in response.data(['sample', 'energy']):
if csp.check(sample):
n_faults = sum(sample[v] for v in sample if 'fault' in v)
fault_counts.append(n_faults)
else:
# if the CSP is not satisfied, the energy should be above ground
assert energy > min_energy

print('Minimum number of faults: ', min(fault_counts))
print('Maximum number of faults: ', max(fault_counts))

# If, instead of the ground states corresponding to all possible fault configurations, we
# instead only wanted to sample from minimum fault configurations, we need to bias against
# higher fault cardinalities. To do this, we add a small linear bias to the fault variables.
# We also make sure that the bias we add is less than 2.0, or else we would affect the energy
# levels.

# now the samples that satisfy the csp and are minimum energy should be exactly the fault
# diagnosis with only a single fault
response = sampler.sample(bqm)
min_energy = min(response.data_vectors['energy'])

min_fault_diagnoses = []
for sample, energy in response.data(['sample', 'energy']):
if csp.check(sample) and energy == min_energy:
min_fault_diagnoses.append([v for v in sample if ('fault' in v and sample[v])])
else:
# if the CSP is not satisfied, the energy should be above ground
assert energy > min_energy

print('min fault diagnoses: ', min_fault_diagnoses)
```