Assume a 32-bit write-only register resides in a black box module. As a silicon validation engineer, you have write access to the register through the 32-bit configuration bus, but you do not have read access. Instead, you know what is the bit-XOR value of all 32 bits from the black box. If there is a random bit of the register that has a stuck-at fault, how can you identify which bit has the fault?

**Linear Search**

The simplest approach is the linear search. In the 1st step, you can write 32’h0000_0001 to the register and get the bit-XOR value, and then write 32’h0000_0000 and get the bit-XOR value again. All possible read values are shown in the table below:

Write value | Bit-XOR value w/o stuck-at fault | Bit-XOR value when bit[0] is stuck@0 | Bit-XOR value when bit[0] is Stuck@1 | Bit-XOR value when bit[31:1] has stuck@0 fault | Bit-XOR value when bit[31:1] has stuck@1 fault |

32’h0000_0001 | 1 | 0 | 1 | 1 | 0 |

32’h0000_0000 | 0 | 0 | 1 | 0 | 1 |

If other bits has stuck-at fault, the bit-XOR value is either 1/0 or 0/1. Obviously, if we get 0/0 bit-XOR value from the black box, bit[0] has stuck@0 fault; if we get 1/1 bit-XOR value from the black box, bit[0] has stuck@1 fault.

We can repeat this process to check the remaining bits. Thus in total, we will need 32 x 2 = 64 patterns to check the stuck-at fault in the worst case scenario.

**Binary Search**

Although intuitive, linear search takes too many iterations to get the final results in the worst case. An optimized solution is to use binary search.

In the 1st step, you can write 32’hFFFF_FFFF to the register and get the bit-XOR value, and then write 32’hFFFF_0000 and get the bit-XOR value again. All possible read values are shown in the table below:

Write value | Bit-XOR value w/o stuck-at fault | Bit-XOR value when bit[15:0] has stuck@0 | Bit-XOR value when bit[15:0] has Stuck@1 | Bit-XOR value when bit[31:16] has stuck@0 fault | Bit-XOR value when bit[31:16] has stuck@1 fault |

32’hFFFF_FFFF | 0 | 1 | 0 | 1 | 0 |

32’hFFFF_0000 | 0 | 0 | 1 | 1 | 0 |

If bit[31:16] has stuck-at fault, the bit-XOR value is either 1/1 or 0/0, then we shall continue to binary search for bit[31:16].

If we get 1/0 bit-XOR value from the black box, bit[15:0] has stuck@0 fault; if we get 0/1 bit-XOR value from the black box, bit[15:0] has stuck@1 fault. Either case, we shall continue to binary search for bit [15:0].

In 2nd step, the search range is cut in half. Obviously, we will need to log2(32) = 5 steps, and 5 x 2 = 10 patterns to check the stuck-at fault in the worst case scenario.

As you can see, the binary search method greatly improves the iteration time and number of patterns required.

seems there doesn’t need x2 patterns in 2nd-5th step. because in first step the stuck type is already known.