Synthesis of two-layer threshold-element circuits

A Boolean function \(f(x_1,x_2,\ldots,x_n)\) can be represented in the form \[ f(x_1,x_2,\ldots,x_n = \sum_{i=0}^{N_1} \sum_{j=0}^{N_2} \varphi_{ij}(x_1,x_2,\ldots,x_n) - \sum_{j=1}^{N_2} \psi_j(x_1,x_2,\ldots,x_r), \tag{1} \] where \(N_1 = 2^{n-r} - 1\), \(N_2 = 2^r/r\), \(r = 2^{[\log_2 n]}\) and the summation and minus signs denote ordinary arithmetic operations. All the vectors \(\tilde\sigma = (\sigma_1, \ldots, \sigma_r,\sigma_{r+1}. \ldots, \sigma_n)\) on which the given Boolean function is defined are divided into \(2^{n-r}\) sets of vectors \(\Gamma_0,\Gamma_1,\ldots, \Gamma_{N_1}\) such that each set contains all vectors of length \(n\) having the same last \((n-r)\) elements and then each set \(\Gamma_i\) is divided into \(N_2\) mutually nonintersecting subsets called unit spheres. The center of a unit sphere \(\Phi_{ij}\) is a vector \(\tilde\pi_j\) which differs from each vector of this sphere in exactly one element. For each unit sphere \(\Phi_{ij}\) a function \(\varphi_{ij}\) is constructed which is identical to the given function \(f\) on all vectors of \(\Phi_{ij}\), equal to one in the center of \(\Phi_{ij}\) and zero on all the other vectors. The \(N_2\) functions \(\psi_j\) are defined by \(\psi_j(x_1,x_2,\ldots,x_r) =1\) if and only if \((x_1,x_2,\ldots,x_r) =\tilde\pi_j\). The above form of \(f\) is called the spherical representation of \(f\). Then it is shown in lemmas 2 and 3 that any of the functions \(\varphi_{ij}\) and \(\psi_j\) is very simply realizable by a single threshold element (TE) having the magnitude of its weights \(\le 2\). Since the sum and difference in (1) can be computed by a single TE, too, it results that the spherical representation of \(f\) leads directly to a 2-level TE network realizing \(f\). Then it is proved that \[ 2^{n-1} \lesssim L_2(n) \le 7\cdot 2^{n-1} + 2^{n/2} + \frac{2^{n+1} + 2^{n/2+1}}{n} \] \((\alpha(n)\lesssim \beta(n)\) denotes that \(\varlimsup \alpha(n)/\beta(n)\le 1)\) where \(L_2(n) = \operatorname{Max}L_2(f)\) (the maximum is taken over all functions of \(n\) variables) and \(L_2(f)\) is the minimum complexity of the 2-level TE network obtained from (1) and realizing \(f\). The complexity of a TE is defined by \(p = \sum_{i=1}^n \vert\omega_i\vert\) where \(\omega_i\) are the weights and the complexity of the network is defined as the sum of the complexities of all TE's.

Recommendations

Cited in

(8)

This page was built for publication: Synthesis of two-layer threshold-element circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2538854)