Communication based FPGA synthesis for multi-output Boolean functions

One of the crucial problems multi level logic synthesis techniques for multi output Boolean functions f=(f₁,...,f_m):{0,1}ⁿ→{0,1}^m have to deal with is finding sublogic which can be shared by different outputs, i.e., finding Boolean functions α=(α₁,...,α_h):{0,1}^p →{0,1}^h which can be used as common sublogic of good realizations of f₁,...,f_m. We present an efficient ROBDD based implementation of this common decomposition functions problem (CDF). Formally, CDF is defined as follows: given m Boolean functions f₁,...,f_m:{0,1}ⁿ→{0,1}, and two natural numbers p and h, find h Boolean functions α₁,..., α_h:{0, 1}^p→{0,1} such that ∀1⩽k⩽m there is a decomposition of f_k of the form: f_k(x₁,...x_n)=g^(k)(α ₁(x₁,...x_p),...,α_h(x ₁,...,x_p),α_h+1^(k)(x ₁,...,x_p),...,α(r_k)^(k) (x₁,...x_p),x_p+1,...,x_n ) using a minimal number r_k of single output Boolean decomposition functions. Experimental results applying the method to FPGA synthesis are promising