A Method for the Fast Approximate Solution of Large Prime Implicant Charts

A method is presented which uses easily calculated probabilities to determine complete covers of prime implicant charts. Apparently the underlying principle of incomplete branching has not been applied previously to prime implicant charts. This principle differs in that branching is not carried out to complete covers, but only to a specified level, at which point each position is evaluated. All positions are then mimimaxed to the point of branching to choose the best branch. The method is easy to program and requires relatively little computer time to determine the cover. Time savings of up to 98 percent have been realized with an increase in the cost of the cover of less than 2 percent over conventional minimization methods. The method can be applied directly to any prime implicant chart, or can be used as a substitute for complete branching in charts where the application of dominance produces a cyclic chart.