We define and study a new class of regular boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller ...
详细信息
We define and study a new class of regular boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller than n. We show that the D-reducibility property can be efficiently tested, in time polynomial in the representation of f, that is, an initial SOP form of f. A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DredSOP. This form is shown here to be generally smaller than the corresponding minimum SOP form. Our experiments have also shown that a great number of functions of practical importance are indeed D-reducible, thus validating the overall interest of our approach.
Approximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, within the error tolerance of a given application, to reduce the complexity of the final implementati...
详细信息
Approximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, within the error tolerance of a given application, to reduce the complexity of the final implementation. We attack the problem by exploiting the allowed flexibility in order to maximize the regularity of the specified booleanfunctions. Specifically, we consider two types of regularity: symmetry and D-reducibility, and contribute two algorithms to find, respectively, a symmetric and a D-reducible approximation of a given target function f, within the given error rate threshold if possible. When targeting symmetry, we characterize and compute polynomially the closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original incompletely specified boolean function, with an unbounded number of errors;then, we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Finally, we present a polynomial heuristic algorithm to compute a D-reducible approximation of an incompletely specified target function, under a bit error metric. Experimental results on classical and new benchmarks confirm the effectiveness of the proposed approaches.
XOR-AND Graphs (XAGs) are an enrichment of the classical AND-Inverter Graphs (AIGs) with XOR nodes. In particular, XAGs are networks composed by ANDs, XORs, and inverters. Besides several emerging technologies applica...
详细信息
XOR-AND Graphs (XAGs) are an enrichment of the classical AND-Inverter Graphs (AIGs) with XOR nodes. In particular, XAGs are networks composed by ANDs, XORs, and inverters. Besides several emerging technologies applications, XAGs are often exploited in cryptography-related applications based on the multiplicative complexity of a boolean function. The multiplicative complexity of a function is the minimum number of AND gates (i.e., multiplications) that are sufficient to represent the function over the basis {AND, XOR, NOT}. In fact, the minimization of the number of AND gates is important for high-level cryptography protocols such as secure multiparty computation, where processing AND gates is more expensive than processing XOR gates. Moreover, it is an indicator of the degree of vulnerability of the circuit, as a small number of AND gates corresponds to a high vulnerability to algebraic attacks. In this paper we study the multiplicative complexity of booleanfunctions characterized by two particular regularities, called autosymmetry and D-reducibility. Moreover, we exploit these regularities for decreasing the number of AND nodes in XAGs. The experimental results validate the proposed approaches.
In logic synthesis, the "regularity" of a boolean function can be exploited with the purpose of decreasing the cost of the corresponding algebraic expression or its minimization time. In this paper we study ...
详细信息
ISBN:
(纸本)9781424464708
In logic synthesis, the "regularity" of a boolean function can be exploited with the purpose of decreasing the cost of the corresponding algebraic expression or its minimization time. In this paper we study the synthesis of a class of regular boolean functions called D-reducible. We propose two compact and testable representations of D-reducible non completely specified functions, called DRedSOP and 2DRedSOP. The experimental results show that a large percentage (about 70%) of the benchmark functions have at least a D-reducible output. The gain in area of the synthesized networks for such functions is, on average, 27% for DRedSOPs and 28% for 2DRedSOPs.
暂无评论