Logic path length reduction using boolean minimization

Claim 1

A method for reducing a logic network to a specified number of gate levels, the logic network having a plurality of gates, a number of gate levels, at least one input, at least one output, and at least one worst path which represents a path through the logic network having at least as many gate levels as any other path through the logic network, the method comprising the steps of: receiving data representing the topology of the logic network; levelizing the gates of the logic network in a forward and a backward direction; determining all of the gates of the logic network which are in the at least one worst path; specifying a scoring function; selecting, in accordance with the scoring function, one of the gates in the at least one worst path; applying a local Boolean compression to the selected gate, thereby producing a compressed logic network having fewer gate levels than the number of gate levels of the logic network prior to compression; comparing the number of gate levels of the compressed logic network with the specified number of gate levels; and if the compressed logic network has a number of gate levels which is greater than the specified number of gate levels, then repeating said levelizing, determining, specifying, selecting, applying, and comparing steps on the compressed logic network until the specified number of gate levels is achieved.

Claim 2

A method for reducing a logic network to a specified number of gate levels, the logic network having a plurality of gates, a number of gate levels, at least one input, at least one output, and at least one worst path which represents a path through the logic network having at least as many gate levels as any other path through the logic network, the method comprising the steps of: receiving data representing the topology of the logic network; levelizing the gates of the logic network in a forward and a backward direction; determining all of the gates of the logic network which are in the at least one worst path; specifying a scoring function; selecting, in accordance with the scoring function, one of the gates in the at least one worst path; applying a local Boolean compression to the selected gate, thereby producing a compressed logic network having fewer gate levels than the number of gate levels of the logic network prior to compression; comparing the number of gate levels of the compressed logic network with the specified number of gate levels; and if the compressed logic network has a number of gate levels which is greater than the specified number of gate levels, then repeating said levelizing, determining, specifying, selecting, applying, and comparing steps on the compressed logic network until the specified number of gate levels is achieved.

Claim 12

A method for reducing a logic network to a specified number of gate levels, the logic network having a plurality of gates, a number of gate levels, at least one input, at least one output, and at least one worst path which represents a path through the logic network having at least as many gate levels as any other path through the logic network, the method comprising the steps of: receiving data representing the topology of the logic network; levelizing the gates in a forward and backward direction; calculating for each of the gates a worst path convergence factor which represents a number of worst paths which converge at a particular gate; calculating for each of the gates a long path convergence value which represents a number of paths through the logic network having more than the specified number of gate levels which converge at a particular gate; applying a trial local Boolean compression on those gates of the logic network having a worst path convergence factor greater than zero and which are at least two levels from the at least one input and at least one level from the at least one output; calculating a gate count increase value which represents a number of gates added to the logic network after said trial local Boolean compression is applied; calculating a connection count increase value which represents a number of input connections added to the logic network after said trial Boolean compression is applied; specifying a scoring function; selecting, in accordance with the scoring function, one of the gates in the at least one worst path; applying a local Boolean compression to the selected gate, thereby producing a compressed logic network having fewer gate levels than the number of gate levels of the logic network prior to compression; comparing the number of gate levels of the compressed logic network with the specified number of gate levels; and if the compressed logic network has a number of gate levels which is greater than the specified number of gate levels, than repeating said levelizing, worst path convergence factor calculating, long path convergence value calculating, trial Boolean compression applying, gate count increase calculating, connection count increase calculating, specifying, selecting, local Boolean compression applying, and comparing steps on the compressed logic network until the specified number of gate levels is achieved.

Claim 13

A method for reducing a logic network to a specified number of gate levels, the logic network having a plurality of gates, a number of gate levels, at least one input, at least one output, and at least one worst path which represents a path through the logic network having at least as many gate levels as any other path through the logic network, the method comprising the steps of: receiving data representing the topology of the logic network; levelizing the gates in a forward and backward direction; calculating for each of the gates a worst path convergence factor which represents a number of worst paths which converge at a particular gate; calculating for each of the gates a long path convergence value which represents a number of paths through the logic network having more than the specified number of gate levels which converge at a particular gate; applying a trial local Boolean compression on those gates of the logic network having a worst path convergence factor greater than zero and which are at least two levels from the at least one input and at least one level from the at least one output; calculating a gate count increase value which represents a number of gates added to the logic network after said trial local Boolean compression is applied; calculating a connection count increase value which represents a number of input connections added to the logic network after said trial Boolean compression is applied; specifying a scoring function; selecting, in accordance with the scoring function, one of the gates in the at least one worst path; applying a local Boolean compression to the selected gate, thereby producing a compressed logic network having fewer gate levels than the number of gate levels of the logic network prior to compression; comparing the number of gate levels of the compressed logic network with the specified number of gate levels; and if the compressed logic network has a number of gate levels which is greater than the specified number of gate levels, than repeating said levelizing, worst path convergence factor calculating, long path convergence value calculating, trial Boolean compression applying, gate count increase calculating, connection count increase calculating, specifying, selecting, local Boolean compression applying, and comparing steps on the compressed logic network until the specified number of gate levels is achieved.