Steve Bagley and David Brailsford on Data Compression
See Arithmetic coding.
See also Boolean Expression Diagrams by Henrik Reif Andersen and Henrik Hulgaard (Received January 31, 1998; published online April 22, 2002):
As another consequence, we observe that BEDs are exponentially more succinct than OBDDs. An example of this is the multiplier function. Bryant showed that for all variable orderings, the multiplier function requires BDDs of exponential size. However, since there are combinational circuits implementing this function using only a quadratic number of gates (and even less), there exists a BED of this size representing it. ... Fortunately, functions with exponentially sized BEDs do not seem to be of much interest in practice. Even complicated Boolean functions, representing for instance floating-point division, have polynomially sized circuits. This is also witnessed by the fact that it is very difficult to construct explicit examples of functions that provably require exponentially many gates. (The authors have been unable to find any examples in the literature.)
See also The Geometry of Markoff Numbers by Caroline Series.
Subscribe to Computerphile.
Comments
Post a Comment