Polynomial Formal Verification of Approximate Adders with Constant Cutwidth
Mohamed Nadeem, Chandan Kumar Jha, Rolf Drechsler · 2024
In the context of digital circuits, formal verification methods have been well-studied to ensure their functional correctness. However, several verification methods fail to provide an upper bound for the time and space complexity. Therefore, Polynomial Formal Verification (PFV) has been introduced to address this problem. Unlike prior works, which have shown that approximate circuits can be verified in polynomial time, we show that approximate circuits with a constant cutwidth can be verified even in linear time. Since approximate circuits have become ubiquitous in error-resilient applications, it becomes essential to guarantee their correctness. While prior works have been limited to formal error analysis, we use Answer Set Programming (ASP) based formal verification to guarantee that the approximate circuit matches its functional specification. In this paper, we first show that several approximate adder circuits exhibit a constant cutwidth. We then provide a PFV approach that relies on this cutwidth as a structural property of the circuits to guarantee a linear-time verification w.r.t. the bitwidth using ASP. Finally, we evaluate several approximate adders in terms of the upper bound of the cutwidth, and verification time.