The redundancy ratio of a function is defined as the ratio of the length of its longest sum-of-products expression to the length of its shortest sum-of-products expression. For a given function f, its redundancy ratio will be denoted by rho(f). In T. Sasao and J. Butler's "Comparison of worst and best sum-of-product expressions for multiple-valued functions," it was shown that rho(f) is less than 2**n-1 for boolean functions, and in some cases is a linear function of the number of input variables. In this paper we prove that rho(f) less than or equal to 2n with high probability for a boolean function of
n-variables.
By: L. O'Connor
Published in: RZ3100 in 1999
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .