IEE Proceedings E Computers and Digital Techniques · 1992 · 14 citations · 11 references
ComputingComputer EngineeringComputer ScienceAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisComputational ComplexityLogic SynthesisArithmetic Circuit SynthesisCommon Subexpression EliminationMinimization Of Boolean FunctionsProduct ReductionSynthesis Optimization
A new method for (quasi) minimisation of incompletely specified multiple-output mod-2 sum expressions is presented. It uses a new low-complexity algorithm for the Reed-Muller transform (RMT). Heuristically choosing a (quasi-) optimal polarity of the transform, its coefficients are combined so as to form a locally disjoint RM coefficient cover. Inverse RMT yields a (quasi)minimal exclusive-OR sum of products. To exploit common product terms, multiple-output functions are combined to form a single-output hyperfunction. ‘don't cares’ are (quasi-)optimally allotted during the procedure. Since throughout the algorithm only cubes are to be handled, the method is fast and requires only moderate storage. It compares favourably with other algorithms both in the average number of products required and in its computational complexity. The program HEALEX can handle functions of hundreds of variables on an AT personal computer.
11
Proceedings of the International Symposium
Dominique A. Vuitton, Laurence Millon, Bruno Gottstein et al. · Parasite · 2014 · 760 citations · Full text
On the complexity of mod-2l sum PLA's
T. Sasao, Philipp W. Besslich · IEEE Transactions on Computers · 1990 · 180 citations