Word-Level Multi-Fix Rectifiability of Finite Field Arithmetic Circuits

摘要

Deciding whether a faulty circuit can be rectified at a given set of nets to match its intended specification constitutes a critical problem in post-verification debugging and rectification. Contemporary approaches which utilize Boolean SAT and Craig Interpolation techniques are infeasible in proving the rectifiability of arithmetic circuits. This paper presents a novel approach using symbolic computer algebra to prove the rectifiability of a faulty finite field arithmetic circuit at a given set of m nets. Our approach uses a word-level polynomial model and an application of a Gröbner basis decision procedure. The finite fields corresponding to the datapath word-length (n) and the patch word-length (m) may not be compatible. We make new mathematical and algorithmic contributions which resolve this disparity by modeling the problem in an appropriate composite field. Experiments demonstrate the efficacy of our word-level approach to ascertain multi-fix rectifiability compared to contemporary approaches.