The most critical boolean formula for digital logic testing and Automatic Test Pattern Generation (ATPG) is the Boolean Difference (or Boolean Derivative). While standard boolean algebra simplifies logic gates, the Boolean Difference answers a specific hardware question: If input wire X fails, will the output F actually change? It mathematically isolates the observability of a fault, allowing engineers to generate exact test vectors for combinational circuits without brute-forcing truth tables.
The Core Formula: Boolean Difference and Symbol Definitions
The Boolean Difference of a logic function $F$ with respect to a specific input variable $x_i$ is defined by the exclusive-OR (XOR) of its positive and negative cofactors. The formula is written as:
$$ \frac{\partial F}{\partial x_i} = F(x_i = 1) \oplus F(x_i = 0) $$
Unlike continuous calculus, there are no limits or infinitesimals here. The "derivative" simply evaluates whether toggling $x_i$ toggles the output $F$. If the result is 1, the fault is observable at the output. If the result is 0, the fault is masked by the other inputs.
| Symbol | Term | Definition & Hardware Context |
|---|---|---|
| $F$ | Output Function | The final boolean expression of the combinational circuit (e.g., $F = AB + C$). |
| $x_i$ | Target Variable | The specific input pin or internal net being evaluated for a stuck-at fault. |
| $\frac{\partial F}{\partial x_i}$ | Boolean Difference | The observability function. Evaluates to 1 if $x_i$ controls $F$, and 0 if $F$ is independent of $x_i$. |
| $F(x_i = 1)$ | Positive Cofactor | The simplified boolean formula when $x_i$ is forced HIGH (logic 1 / $V_{CC}$). |
| $F(x_i = 0)$ | Negative Cofactor | The simplified boolean formula when $x_i$ is forced LOW (logic 0 / GND). |
| $\oplus$ | Exclusive-OR (XOR) | Bitwise XOR operation. Outputs 1 only if the two cofactors differ in logic state. |
Real-World Observability: Fault Propagation Matrix
To ground this formula in physical hardware, we must look at how standard logic families behave. The table below maps the Boolean Difference for common 74HC-series gates alongside their physical propagation delays ($t_{pd}$) at $V_{CC} = 5.0V$. This data is critical when setting up timing windows on an oscilloscope or logic analyzer to catch the fault transition.
| IC Part Number | Gate Type | Boolean Function ($F$) | Boolean Difference ($\frac{\partial F}{\partial A}$) | Typical $t_{pd}$ (ns) | Max $t_{pd}$ (ns) |
|---|---|---|---|---|---|
| SN74HC00 | 2-Input NAND | $(A \cdot B)'$ | $B$ | 18 ns | 28 ns |
| SN74HC02 | 2-Input NOR | $(A + B)'$ | $B'$ | 18 ns | 28 ns |
| SN74HC04 | Hex Inverter | $A'$ | $1$ (Always Observable) | 14 ns | 22 ns |
| SN74HC32 | 2-Input OR | $A + B$ | $B'$ | 18 ns | 28 ns |
| SN74HC86 | 2-Input XOR | $A \oplus B$ | $1$ (Always Observable) | 20 ns | 32 ns |
Note: Data derived from Texas Instruments SN74HC series datasheets at $V_{CC} = 5.0V$ and $C_L = 50pF$. For deeper hardware specifications, refer to the TI Designing with Logic Application Report.
Rearranged Forms: Isolating Cofactors and Fault Masks
While boolean algebra does not support traditional division, we can rearrange the Boolean Difference to solve for the individual cofactors or reconstruct the original function $F$. These rearranged forms are heavily used in logic synthesis and FPGA routing algorithms.
- Solve for the Positive Cofactor ($F_{x_i=1}$):
$F(x_i = 1) = \frac{\partial F}{\partial x_i} \oplus F(x_i = 0)$
Use case: You know the fault observability and the grounded state, and need to find the energized state. - Solve for the Negative Cofactor ($F_{x_i=0}$):
$F(x_i = 0) = \frac{\partial F}{\partial x_i} \oplus F(x_i = 1)$
Use case: You know the fault observability and the energized state, and need to find the grounded state. - Solve for the Output Function ($F$) via Shannon Expansion:
$F = (x_i \cdot F(x_i = 1)) + (x_i' \cdot F(x_i = 0))$
Use case: Reconstructing the full boolean formula from its isolated variable cofactors, essential for multiplexer-based logic mapping.
Worked Problems: State and Delay Tracking in Combinational Logic
Let us apply the formula to two distinct scenarios, explicitly tracking both the abstract logic states (0/1) and the physical hardware units (Voltage and Time).
Problem 1: Pure Boolean State Tracking
Given: A combinational circuit defined by $F = (A \cdot B) + C$.
Find: The Boolean Difference with respect to input $A$ ($\frac{\partial F}{\partial A}$).
- Calculate the Positive Cofactor ($F_{A=1}$):
Substitute $A = 1$ into the formula.
$F(1, B, C) = (1 \cdot B) + C = B + C$
State tracked: Logic 1 (HIGH). - Calculate the Negative Cofactor ($F_{A=0}$):
Substitute $A = 0$ into the formula.
$F(0, B, C) = (0 \cdot B) + C = 0 + C = C$
State tracked: Logic 0 (LOW). - Apply the XOR Operation ($\oplus$):
$\frac{\partial F}{\partial A} = (B + C) \oplus (C)$
Using boolean algebra rules for XOR ($X \oplus Y = X'Y + XY'$):
$= (B + C)' \cdot C + (B + C) \cdot C'$
$= (B' \cdot C') \cdot C + B \cdot C' + C \cdot C'$
$= 0 + B \cdot C' + 0 = B \cdot C'$ - Final Result & Interpretation:
$\frac{\partial F}{\partial A} = B \cdot C'$
Meaning: A fault on input $A$ will only propagate to the output if $B = 1$ AND $C = 0$. If $C = 1$, the OR gate masks the fault regardless of $A$ and $B$.
Problem 2: Hardware Test Vector Generation with Delay Tracking
Given: A physical SN74HC32 (2-Input OR gate) operating at $V_{CC} = 5.0V$. The function is $F = A + B$. We suspect a stuck-at-0 fault on input pin A.
Find: The required test vector (input voltages) to detect the fault, and the expected propagation delay window to measure on an oscilloscope.
- Determine the Boolean Difference:
From Table 2, we know $\frac{\partial F}{\partial A} = B'$.
Unit tracked: Boolean Observability (1 = Observable). - Establish the Fault Condition:
To detect a stuck-at-0 fault, we must drive the faulty node to the opposite state (Logic 1) so the fault forces an error.
Therefore, we must set $A = 1$.
Unit tracked: Voltage ($V_{IH} \ge 3.15V$ for 74HC at 5V). - Solve for the Sensitization Path (Masking inputs):
For the fault to propagate, the Boolean Difference must equal 1.
$B' = 1 \implies B = 0$.
Unit tracked: Voltage ($V_{IL} \le 1.35V$ for 74HC at 5V). - Calculate the Expected Output Transition & Delay:
With $A=1$ (faulty node reads 0) and $B=0$, the faulty output is $0 + 0 = 0$ (0V).
With $A=1$ (healthy node reads 1) and $B=0$, the healthy output is $1 + 0 = 1$ (5V).
We must toggle $A$ from 0 to 1 and look for a rising edge on $F$.
Unit tracked: Time. According to the SN74HC32 datasheet, typical $t_{pd}$ is 18 ns, max is 28 ns. Set oscilloscope trigger to capture a 5V rising edge between 15 ns and 30 ns after the $A$ transition.
Application Boundaries and Common Unit Mistakes
While the Boolean Difference is mathematically elegant, misapplying it in code or on the bench leads to failed test coverage. Keep these boundaries and common errors in mind.
When the Formula Applies (and When it Doesn't)
- Applies to: Strictly combinational logic (gates, multiplexers, decoders) where outputs depend only on current inputs.
- Assumptions: The pure mathematical formula assumes zero gate delay. In physical hardware, you must account for propagation delays ($t_{pd}$) to avoid sampling glitches.
- Does NOT apply to: Sequential logic (flip-flops, latches, state machines) without first unrolling the circuit across clock cycles. Feedback loops break the direct cofactor evaluation.
Unit and Syntax Mistakes That Break the Math
The most common failure mode when translating boolean formulas into microcontroller code (like C++ on an Arduino or ESP32) is confusing logical operators with bitwise operators.
- The XOR Mistake: The formula requires bitwise XOR ($\oplus$). In C/C++, this is the
^operator. If you mistakenly use the logical OR operator (||), the expression will evaluate totrue(1) for almost all non-zero inputs, destroying the masking logic. - The Continuous Derivative Mistake: Do not attempt to apply L'Hôpital's rule or continuous limits to the Boolean Difference. The domain is strictly $\{0, 1\}$. The "derivative" is simply a difference operator over the Galois Field GF(2).
- Active-Low Confusion: When dealing with physical ICs like the 74HC00 (NAND), remember that the physical output is inverted. A stuck-at-1 fault on a NAND input requires a different sensitization vector than a stuck-at-0 fault. Always map your boolean variables to the physical pin states, accounting for active-low chip selects or resets.
Realistic Answer Magnitudes
What should your final numbers look like?
For the Boolean Difference itself: The magnitude is strictly binary. It will always simplify to a boolean expression that evaluates to either 0 (fault masked) or 1 (fault observable).
For the physical manifestation: If you are measuring this on a bench, a successful fault propagation will manifest as a voltage swing (e.g., 0V to 5V for TTL/CMOS, or 0V to 3.3V for modern ARM logic) occurring within a specific time window. For standard 74HC logic at 5V, expect this transition to take between 10 ns and 30 ns. If your oscilloscope shows a transition taking 500 ns, you are likely looking at a capacitive loading issue or a degraded IC, not a clean boolean propagation.
For further reading on digital logic testing and boolean calculus, consult the Boolean Difference overview on Wikipedia or the comprehensive All About Circuits Digital Logic Textbook.
