A fast algorithm to reduce 2-dimensional assignment problems to 1-dimensional assignment problems for FPGA-based fault simulation

In this paper a polynomial time heuristic algorithm developed for the assignment optimization problem is introduced, which leads to an improved usage of field programmable gate array (FPGA) resources for hardware-based fault injection using an FPGA-based logic emulator. Logic emulation represents a new method of design validation utilizing a reprogrammable prototype of a digital circuit. In the past years various approaches to hardware-based fault injection using a hardware logic emulator have been presented. Some approaches insert additional functions at the fault location, while others utilize the reconfigurability of FPGAs. A common feature of each of these methods is the execution of hardware-based fault simulation using the stuck-at fault model at gate level.