Binary-Decision-Diagram based method to determine the data transport in a finite function
Publication Date: 2011-Jun-30
The IP.com Prior Art Database
If a function f(A,C) needs to be evaluated with inputs from two different modules or chips, with the results needed in one of the two. This situation requires the splitting of the function. To minimize data transport, the data from the remote module should be preprocessed such that only a minimum of information is transmitted. The function f(A,C) is to be factorized into f(A,C)=g(A,h(C)), such that the set of images of h is minimal.
Page 01 of 1
---Diagram based method to determine the data transport in a finiteDiagram based method to determine the data transport in a finiteDiagram based method to determine the data transport in a finite
Diagram based method to determine the data transport in a finite
Description of Invention
The function f and all the following derived functions, relations are represented as a Binary Decision Diagram, or a data type which supports combination, (partial) evaluation, quantor application of functions, and determination of size of fulfilling set.
1. Convert the function into a relation-representation r: r(a,c,b) = 1
2. Create a copy of the relation with a different set of input variables for c: r2(a,c2,b)
3. combine r and r2 forming a relation s(a,b,c,c2 ).
4. Remove the inputs for a and c by forall-quantorization of variables a and c: e(c,c2 ) = FORALL a,b s(a,b,c,c2)
5. create the greater-than-or-equal function for inputs c, c2.
6. Form M(c,c2 )=(c ≥c2 ) & e(c,c2 )
7. Remove the inputs c2 from M by FORALL- quantorization, resulting in N
8. Determine the number of fulfilling inputs of N.
The individual operations in steps 1. to 7. are known for Binary Decision Diagrams and are supported by typical BDD implementations, for instance CUDD.
For the operation in step 8. algorithms are known and published for instance in Christoph Meinel, Torsten Theobald: "
Algorithms and Data Struc...