Back to results
US 7,337,154 B2Granted
Method for solving the binary minimization problem and a variant thereof
AssigneeRaytheon Company
InventorSteven J Manson
Life of this patent
Estimating the term…
Abstract
A recursive binary splitting and recombination procedure coupled with a specially tailored genetic algorithm provides a solution to the general binary minimization problem with much lower run times than other methods. A minor modification to the procedure solves a variant of the binary minimization problem using an alternate operator logic that is crucial to solving certain combinatorial geometry problems.
Claims37
A method of digital logic circuit design, comprising:
- a) Storing a complementary pair of truth tables T and F in a computer, said truth tables representing an initial configuration of logic gates to map from logic inputs to a single bit output of a digital logic circuit;
- b) Iteratively subdividing the T truth table into pairs of sub-tables along branches at progressively lower levels until the remaining sub-tables are smaller than a threshold size;
- c) Using a genetic algorithm to solve each of the sub-tables at the lowest level independently from respective seed organisms as a sub-solution;
- d) For each pair of sub-tables at the lowest remaining level, combining their sub-solutions to form the seed organism to seed the genetic algorithm to solve the sub-table at the next higher level up the branch and refine the sub-solution;
- and
- e) Repeating step (d) at least once to generate a solution;
- and
- f) Storing the solution in the computer, said solution representing a configuration of logic gates for the digital logic circuit to map the logic inputs to the single bit output that requires fewer gates than said initial configuration.
5 more elements
A method of digital logic circuit design, comprising:
- a) Storing a complementary pair of truth tables T and F in a computer, said truth tables representing an initial configuration of logic gates to map from logic inputs to a single bit output of a digital logic circuit;
- b) Recursively bisecting the T truth table into pairs of sub-tables along branches at progressively lower levels until the remaining sub-tables are smaller than a threshold size;
- c) Using a genetic algorithm to solve the T sub-tables at the lowest level independently as a sub-solution, said genetic algorithm forming a binary seed organism from the T sub-table, creating a pool of trinary organisms by setting some of the genes in the seed organism to 0 representing either T or F, eliminating low scoring organisms and breeding the organisms until the scores stabilize, and selecting a high scoring organism for the sub-solution;
- d) For each pair of sub-tables at the lowest remaining level, combining their sub-solutions to form a trinary seed organism to seed the genetic algorithm to solve the sub-table at the next higher level up the branch and refine the sub-solution,
- e) Repeating step (d) at least once to recursively generate a solution;
- and
- f) Storing the solution in the computer, said solution representing a configuration of logic gates for the digital logic circuit to map the logic inputs to the single bit output that requires fewer gates than said initial configuration.
4 more elements
Dependencies are inferred from the claim text.