Arithmetic Transform of Boolean Functions
Arithmetic Transform of Boolean Functions
复制标题
布尔函数的算术变换
DOI：
10.1007/978-1-4613-1385-4_6
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Jain
中科院分区：
文献类型：
--
作者：
J. Jain
在许多需要分析逻辑函数的应用中，如果我们将布尔（或切换）函数转换为算术函数，则会很有用。这样的算术变换可以让我们对解决一些有趣的问题有新的认识。例如，转换后的函数可以很容易地在整数或实数上求值（模拟）。通过这种算法模拟，我们可以对函数对进行概率验证，其置信度比二值布尔模拟高得多。任何布尔函数的算术变换都可以很容易地从它的BDD计算出来。为了帮助计算非二进制输入上的布尔函数，并表示具有整数系数的多变量线性多项式，可以使用像data structuresndd这样的BDD；对于许多算术表达式，sndd是一种非常紧凑的表示。这种对函数性质的概率验证的误差是可量化的，而且极低。而且，这些过程在计算上非常高效。使用实值或整数值表示，我们可以推导出数字电路元件的可测试性度量，或对各种网络进行可靠性分析。
In many applications where logic functions need to be analyzed it can be useful if we transform Boolean (or switching) functions to arithmetic functions. Such arithmetic transformations can give us new insight into solving some interesting problems. For example, the transformed functions can be easily evaluated (simulated) on integers or real numbers. Through such arithmetic simulation we can probabilistically verify a pair of functions with much more confidence than two-valued Boolean simulation. The arithmetic transform of any Boolean function can be easily computed from its BDD. To help evaluate a Boolean function on non-binary inputs, and to represent multi-variable linear polynomials with integer coefficients, a BDD like data structuresnDDcan be used; for many arithmetic expressions, snDDs are a very compact representation. The error in such probabilistic verification of property of a function is quantifiable and extremely low. Also, the procedures are computationally very efficient. Using a real-valued or integer-valued representation we can derive testability measures for elements of a digital circuit, or conduct the reliability analysis for various networks.