System and method for simulating discrete functions using ordered decision arrays

Claim 3

The method of claim 1, wherein said step of generating a multi-valued decision data representation comprises the steps of: generating a first representation of a binary decision diagram (BDD), associated with one of the outputs of the discrete function circuit design, representing said effect of the two or more discrete function elements on the inputs; repeating said step of generating a first representation, for each of said outputs; combining two or more of said first representations of a BDD to create a second BDD representation, associated with two or more of said outputs of the discrete function circuit design, representing said effect of the two or more discrete function elements on the inputs; and converting said second BDD representation to said first multi-value decision diagram (MDD) representation.

Claim 4

The method of claim 2, further comprising the step of: modifying said first data array by representing the effect of the two or more discrete function elements on all but one of the inputs wherein said one input does not affect said associated two or more outputs.

Claim 5

The method of claim 2, wherein said discrete function circuit design is a logic circuit design, and wherein said discrete function element is a logic gate.

Claim 6

The method of claim 4, wherein the logic circuit design is a layout level circuit design.

Claim 7

The method of claim 4, wherein the logic circuit design is a logic level circuit design.

Claim 8

The method of claim 4, wherein the logic circuit design is an architectural level circuit design.

Claim 9

The method of claim 2, further comprising the step of: generating a simulation program, based upon said first data array, which simulates the effect of the two or more discrete function elements on the plurality of inputs.

Claim 10

The method of claim 8, wherein said step of generating said simulation program comprises the step of: performing only one or more first data array lookup operations to simulate the effect of the discrete function elements on the inputs.

Claim 11

The method of claim 1, wherein said discrete function circuit design is a logic circuit design, and wherein said discrete function element is a logic gate.

Claim 12

The method of claim 10, wherein the logic circuit design is a combinational logic circuit design.

Claim 13

The method of claim 10, wherein the logic circuit design is a sequential logic circuit design.

Claim 14

The method of claim 12, further comprising the step of: converting said sequential logic circuit into a combinational logic block having said two or more logic blocks.

Claim 15

The method of claim 13, further comprising the step of: storing a sequential logic variable wherein said sequential logic variable is one of the outputs.

Claim 16

The method of claim 14, wherein the inputs into said combinational logic block include said sequential logic variable.

Claim 17

The method of claim 14, further comprising the step of: eliminating a delay when simulating a first combinational logic block and a second combinational logic block by inputting a first plurality of inputs and said sequential logic variable into said first combinational logic block and inputting a second plurality of inputs and said sequential logic variable into said second combinational logic block.

Claim 18

The method of claim 1, further comprising the step of synthesizing and optimizing the discrete function circuit design before generating said first data array.

Claim 19

The method of claim 1, further comprising the step of: pipelineing said discrete function circuit design to form two or more design stages, and generating said first data array for each of said stages.

Claim 20

The method of claim 1, wherein said data tables include a plurality of first data tables, each of said first data tables having a plurality of pointers, each of said pointers identifying a position of another of said data tables, and a second data table including said output values.

Claim 21

The method of claim 19, wherein said step of traversing said first data array includes the steps of: (a) selecting one of said first data tables; (b) s electing a first subset of said inputs; (c) determining a first value representing said first subset of said inputs; (d) selecting one of said plurality of pointers of one of said first data tables, said selected pointer identifying the next data table; (e) repeating steps (b) through (d) until all of said inputs have been included in said first subset, wherein said pointer identifies said second table; and (f) identifying one or more of said plurality of outputs as a value of said second table.

Claim 22

The method of claim 1, wherein said step of generating a multi-valued decision data array includes the steps of: generating a plurality of binary-valued decision data arrays, each representing the value of one of said outputs from said plurality of inputs; identifying a first group including two or more of said plurality of inputs; identifying a second group including two or more of said plurality of outputs; and combining two or more of said binary-valued data arrays associated with said first group and said second group to generate said multi-valued decision data array.

Claim 23

The method of claim 21, further comprising the step of eliminating unused inputs from said multi-valued decision data array.

Claim 24

A computer based system for simulating a circuit design having a plurality of signals representative of two or more logic gates, the two or more logic gates having a plurality of input signals and a plurality of output signals, comprising: a storage device; MDD generating means, coupled to said storage device, for generating a multi-valued decision data representation having a plurality of nodes, representing the circuit design, a size of said multi-valued decision data representation is not dependent upon the number of discrete function elements, for generating a first representation of a binary decision diagram (BDD), associated with one of the outputs of the discrete function circuit design, representing said effect of the two or more discrete function elements on the inputs, for combining two or more of said first representations to create a second representation of a BDD, associated with two or more outputs, said second representation representing said effect of the two or more discrete function elements on the inputs, and for converting said second BDD representation to a first multi-value decision diagram (MDD) representation; first data array generating means, coupled to said storage device, and responsive to the logic gate signals, for generating signals representative of a first data array, wherein said first data array signals represents said MDD representation and an effect of the logic gate signals on the plurality of input signals, and wherein said first data array includes a plurality of data tables, each of said tables identified with one of said plurality of nodes, said first data array having a size that is not dependent upon the number of logic gates; and a processor, coupled to said data generating means, responsive to the input signals, wherein said processor generates an output signal based upon the effect of the first data array signals on the input signals.

Claim 25

A computer based system for simulating a circuit design having a plurality of signals representative of two or more logic gates, the two or more logic gates having a plurality of input signals and a plurality of output signals, comprising: a storage device; MDD generating means, coupled to said storage device, for generating a multi-valued decision data representation having a plurality of nodes, representing the circuit design, a size of said multi-valued decision data representation is not dependent upon the number of discrete function elements, for generating a first representation of a binary decision diagram (BDD), associated with one of the outputs of the discrete function circuit design, representing said effect of the two or more discrete function elements on the inputs, for combining two or more of said first representations to create a second representation of a BDD, associated with two or more outputs, said second representation representing said effect of the two or more discrete function elements on the inputs, and for converting said second BDD representation to a first multi-value decision diagram (MDD) representation; first data array generating means, coupled to said storage device, and responsive to the logic gate signals, for generating signals representative of a first data array, wherein said first data array signals represents said MDD representation and an effect of the logic gate signals on the plurality of input signals, and wherein said first data array includes a plurality of data tables, each of said tables identified with one of said plurality of nodes, said first data array having a size that is not dependent upon the number of logic gates; and a processor, coupled to said data generating means, responsive to the input signals, wherein said processor generates an output signal based upon the effect of the first data array signals on the input signals.

Claim 26

The system of claim 23, wherein the circuit design is a sequential circuit design, further comprising: a sequential logic converter, coupled to said storage device, for converting signals representative of the sequential circuit design into signal representative of a combinational logic block having said two or more logic gates and for storing one of the outputs corresponding to a sequential variable signal in said storage device.

Claim 27

The system of claim 23, wherein said sequential variable signal is one of the input signals.

Claim 28

The system of claim 23, further comprising: traversing means, coupled to said processor, for selecting one of said first data tables, for selecting a first subset of said inputs, for determining a first value representing said first subset of said inputs, for selecting one of said plurality of pointers of one of said first data tables, said selected pointer identifying the next data table, and for identifying one or more of said plurality of outputs as a value of said second table.

Claim 31

The method of claim 27, wherein said data tables include a plurality of first data tables, each of said first data tables having a plurality of pointers, each of said pointers identifying a position of another of said data tables, and a second data table including said output values.

Claim 32

The method of claim 30, wherein said step of traversing said first data array includes the steps of: (a) select one of said first data tables; (b) selecting a first subset of said inputs; (c) determining a first value representing said first subset of said inputs; (d) selecting one of said plurality of pointers of one of said first data tables, said selected pointer identifying the next data table; (e) repeating steps (b) through (d) until all of said inputs have been included in said first subset, wherein said pointer identifies said second table; and (f) identifying one or more of said plurality of outputs as a value of said second table.

Claim 33

The method of claim 27, further comprising the step of eliminating unused inputs from said first data array.

Claim 34

The method of claim 27, wherein said discrete function circuit design is a logic circuit design, and wherein said discrete function element is a logic gate.

Claim 35

The method of claim 31, wherein the logic circuit design is a combinational logic circuit design.

Claim 36

The method of claim 31, wherein the logic circuit design is a sequential logic circuit design.

Claim 37

The method of claim 33, further comprising the step of: converting said sequential logic circuit into a combinational logic block having said two or more logic blocks.

Claim 38

The method of claim 34, further comprising the step of: storing a sequential logic variable wherein said sequential logic variable is one of the outputs.

Claim 39

The method of claim 35, wherein the inputs into said combinational logic block include said sequential logic variable.

Claim 40

The method of claim 35, further comprising the step of: eliminating a delay when simulating a first combinational logic block and a second combinational logic block by inputting a first plurality of inputs and said sequential logic variable into said first combinational logic block and inputting a second plurality of inputs and said sequential logic variable into said second combinational logic block.

Claim 41

The method of claim 27, further comprising the step of: synthesizing and optimizing the discrete function circuit design before generating said data array.

Claim 42

The method of claim 27, further comprising the step of pipelineing said discrete function circuit design to form two or more design stages, and generating said data array for each of said stages.