An entropy measure for the complexity of multi-output Boolean functions

ABSTRACT

The complexity of a Boolean function can be expressed in terms of computational work. We present experimental data in support of the entropy definition of computational work based upon the input-output description of a Boolean function. Our data show a linear relationship between the computational work and the average number of literals in a multi-level implementation. The investigation includes single-output and multi-output function with and without don't care states. The experiments, conducted on a large number of randomly generated functions, showed that the effect of don't cares is to reduce the computational work. For several finite state machine benchmarks, the computational work gave a good estimate of the size of the circuit. Finally, circuit delay is shown to have a non-linear relationship to the computational work.

REFERENCES

• 1: L. HeIierman, "A Measure of Computational Work," IEEE Trans. Computers, vol. C-21, pp. 439-446, May 1972.
• 2: R.W. Cook and M. J. Flynn, "Logical Network Cost and Enu-opy," IEEE Trans. Computers, vol. C-22, pp. 823-826, September 1973.
• 3: E. Kellerman, "A Formula for Logical Network Cost," IEEE Trans. Computers, vol. C-17, pp. 881-884, September 1968.
• 4: N. Pi~ger, "'Information Theory and the Complexity of Boolean Functions ," Math. Syst. Theory, vol. 10, pp. 129-167, 1977.
• 5: V.D. Agrawal, "An Information Theoretic Approach to Digital Fault Testing," IEEE Trans. Computers, vol. C- 30, pp. 582-587, August 1981.
• 6: P.K. Lala, "An Algorithm for the State Assignment of Asynchronous Sequential Circuits," Electronics Letters, vol. 14, pp. 199-201, 1978.
• 7: C.R. Edwards and E. Eris, "State Assignment and Entropy," Electronics Letters, vol. 14, pp. 390-391, 1978.
• 8: R.K. Brayton et al, "MIS: A Multiple Level Logic Optimization System," IEEE Trans. CAD, vol. CAD-6, pp. 1062-1081, November 1987.
• 9: K. Mase, "Comments on A Measure of Computational Work and Logical Network Cost and Entropy," IEEE Trans. Computers, vol. C-27, pp. 94-95, January 1978.
• 10: R. Lisanke, "Finite state machine benchmark set," Prelintinary benchmark, collection, Sepu~mber 1987.
• 11: S. Devadas et al, "MUSTANG: State Assignment of Finite State Machines Targeting Multi-Level Logic Implementations," IEEE Trans. CAD, vol. CAD-'/, pp. 1290- 1300, December 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Experimentation