Development of the methods of Boolean differential calculus for arithmetic logic
The author first recalls several representations of a Boolean function \(f:\{0,1\}^n\to \{0,1\}\). Let \(I=\{0,1,\dots,2^n-1\}\) and choose an arbitrary \(c\in I\). For every \(j\in I\) let \(j_1 \dots j_n\) denote its binary representation. Define the Boolean partial derivatives by \[ {\partial f\over \partial x_k} (x)=f(x_1,\dots,x_n)\oplus f(x_1,\dots,\overline{x}_k,\dots,x_n) \] for \(k=1,\dots,n\). For \(a\in \{0,1,\partial x_1,\dots,\partial x_n\}\) set \(a^1=a\) and \(a^0=1\). Then the logical polynomial form of the function \(f\) is \[ f(x)=\underset i\in {I}{\overline\sum} f^{(i)}_c (x_1\oplus c_1)^{i_1}\cdots (x_n\oplus c_n)^{i_n}, \] where for every \(i\in I\), \(f^{(i)}_c=\partial^q f/\partial x^{i_1}_1\dots \partial x^{i_n}_n\), where \(q\) is the number of units in \(i_1 \dots i_n\). Alternatively, the coefficients \(f^{(i)}_c\) can be obtained from the orthogonal transformation \[ {\mathbf f}^T_c =(K_2^{(c_1)}\otimes\cdots \otimes K^{(c_n)}_2)\cdot {\mathbf f}^T \pmod 2, \] where \({\mathbf f}_c=(f^{(0)}_c,\dots,f^{(2^n-1)}_c)\), \({\mathbf f}=(f(0),\dots,f(2^n-1))\), \(K^{(0)}_2={1\;0 \brack 1\;1}\), \(K^{(1)}_2={0\;1\brack 1\;1}\) and \(\otimes\) is the Kronecker product. Another representation, called arithmetical polynomial form, is obtained by taking the real sum \(\sum\) instead of the modulo 2 sum \(\overline\sum\), by taking \(K^{(0)}_2={1\;0\brack -1\;1}\), \(K^{(1)}_2={0\;1\brack 1\;-1}\) and by performing ordinary matrix multiplication. Now the author shows that the coefficients of the arithmetical polynomial form can be also obtained as iterates of the arithmetical partial derivative \[ {\widetilde\partial f\over \widetilde\partial x_k}(x)=-f(x_1,\dots,x_n)+ f(x_1,\dots,\overline{x}_k,\dots,x_n), \] for \(k=1,\dots,n\). An analogue of a matrix procedure for determining the Boolean partial derivatives is obtained for the arithmetical partial derivative. The paper concludes with the description of linear systolic arrays for computing partial derivatives. Reviewer's remarks. 1) The main monograph in the field is missing from the bibliography: it is \textit{M. Davio, J.-P. Deschamps} and \textit{A. Thayse}, Discrete and Switching Functions, New York: McGraw Hill (1978; Zbl 0385.94020). 2) Page 715: \textit{P. L. Ivănescu} is the same as \textit{P. L. Hammer}. Formula (7): the derivative is computed at \(X=c\). Page 722: lines 8 and 12, the coefficient of \(f(x_1,\dots,0,\dots,x_n)\) is \(\overline{x}_k\); line 15, change \(x_k\) to \(\overline{x}_k\). 3) Replace analog by analogue and the adjectives logic and arithmetic by logical and arithmetical, respectively.
- Parallel algorithms for evaluation of directional Boolean derivatives of multivalued logic functions
- A new calculation for Boolean derivative using Cheng product
- Algebraic method for calculating the c-derivative, the c-partial derivative and their application in detecting special Boolean function
- Derivation of Boolean functions by the blocks method
- scientific article; zbMATH DE number 4145848 (Why is no real title available?)
- scientific article; zbMATH DE number 4170846 (Why is no real title available?)
- scientific article; zbMATH DE number 52225 (Why is no real title available?)
- BOOLEAN DERIVATIVES AND COMPUTATION OF CELLULAR AUTOMATA
- An algorithm for calculating the high-order Boolean e-partial derivative of logic function
- Derivation of vector-valued Boolean functions
- Derivative Operations for Classes C N $$\mathcal {C}_N$$ of Boolean Functions
This page was built for publication: Development of the methods of Boolean differential calculus for arithmetic logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1914366)
