Compact Binary Tree Representation of Logic Function with Enhanced Throughput

An effective approach for realizing the binary tree structure, representing a combinational logic functionality with enhanced throughput, is discussed in this paper. The optimization in maximum operating frequency was achieved through delay minimization, which in turn was possible by means of reducing the depth of the binary network. The proposed synthesis methodology has been validated by experimentation with FPGA as the target technology. Though our proposal is technology independent, yet the heuristic enables better optimization in throughput even after technology mapping for such Boolean functionality; whose reduced CNF form is associated with a lesser literal cost than its reduced DNF form at the Boolean equation level. For cases otherwise, our method converges to similar results as that of [12]. The practical results obtained for a variety of case studies demonstrate an improvement in the maximum throughput rate for Spartan IIE (XC2S50E-7FT256) and Spartan 3 (XC3S50-4PQ144) FPGA logic families by 10.49% and 13.68% respectively. With respect to the LUTs and IOBUFs required for physical implementation of the requisite non-regenerative logic functionality, the proposed method enabled savings to the tune of 44.35% and 44.67% respectively, over the existing efficient method available in literature [12].

• Padmanabhan Balasubramanian
• C. Ardil

• Binary logic tree
• FPGA based design
• Boolean function
• Throughput rate
• CNF
• DNF.

[1] R. Ashenhurst, "The decomposition of switching functions," Proc. of
International Symposium. on Switching Theory, 1959, pp. 74-116.
[2] J. Baer, and D. Bovet, "Compilation of arithmetic expressions for
parallel computations," Proc. of IFIP Congress, 1968, pp. 340-346.
[3] J. Beatty, "An axiomatic approach to code optimization for expressions,"
Journal of ACM, vol. 19(4), 1972, pp. 613-640.
[4] R. Brayton, and C. McMullen, "The decomposition and factorization of
Boolean expressions," Proc. of International Symposium on Circuits and
Systems, 1982, pp. 49-54.
[5] J. Vasudevamurthy, and J. Rajski, "A method for concurrent
decomposition and factorization of Boolean expressions," Proc. of
International Conf. on Computed-Aided Design, 1990, pp. 510-513.
[6] D. Kuck, The Structure of Computers and Computation, Wiley, 1978.
[7] K. Singh, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli,
"Timing optimization of combinational logic," Proc. of IEEE/ACM
International Conf. on Computer-Aided Design, 1988, pp. 282-285.
[8] K. Chen, and S. Muroga, "Timing optimization for multi-level
combinational circuits," Proc. of ACM/IEEE Design Automation Conf.,
1990, pp. 339-344.
[9] H.Touati, H.Savoj, and R.Brayton, "Delay optimization of
combinational circuits by clustering and partial collapsing," Proc. of
IEEE/ACM International Conf. on Computer-Aided Design, 1991, pp.
188-191.
[10] Eric Lehman, and Yosinori Watanabe, "Logic Decomposition during
Technology Mapping," Proc. of IEEE/ACM International Conf. on
Computer-Aided Design, 1995, pp. 264-271.
[11] E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic
decomposition during technology mapping," IEEE Transactions on CAD
of Integrated Circuits and Systems, vol. 16(8), August 1997, pp. 813-
834.
[12] J. Cortadella, "Timing-Driven Logic Bi-Decomposition," IEEE
Transactions on CAD of Integrated Circuits and Systems, vol. 22(6),
June 2003, pp. 675-685.
[13] S. Yamashita, H. Sawada, and A. Nagoya, "New methods to find
optimal nondisjoint bi-decompositions," Proc. of ACM/IEEE Design
Automation Conf., 1998, pp. 59-68.
[14] A. Mishchenko, B. Steinbach, and M. Perkowski, "An algorithm for bidecomposition
of logic functions," Proc. of ACM/IEEE Design
Automation Conf., 2001, pp. 282-285.
[15] Zvi Kohavi, Switching and Finite Automata Theory, McGraw Hill, 1999.
[16] Srinivas Devadas, Abhijit Ghosh, and Kurt Kuetzer, Logic Synthesis
McGraw-Hill series on Computer Engineering, 1994.
[17] P.C. McGeer, J.V. Sanghavi, R.K. Brayton, and A.L. Sangiovanni-
Vincentelli, "ESPRESSO-SIGNATURE: a new exact minimizer for
logic functions," IEEE Transactions on VLSI Systems, vol. 1(4),
December 1993, pp. 432-440.
[18] S.P. Tomaszewski, I.U. Celik, and G.E. Antoniou, "www based Boolean
function minimization," International Journal of Applied Mathematics
and Computer Science, vol. 13(4), 2003, pp. 577-583.
[19] Available: http://www.xilinx.com/support/mysupport.htm#Spartan-3