Browse Prior Art Database

Binary-Decision-Diagram based method to determine the data transport in a finite function

IP.com Disclosure Number: IPCOM000208301D
Publication Date: 2011-Jun-30
Document File: 1 page(s) / 21K

Publishing Venue

The IP.com Prior Art Database

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 98% of the total text.

Page 01 of 1

Binary

BinaryBinary-

---DecisionDecisionDecision

Decision-

---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

function

functionfunction

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

b=f(a,c)

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...