Derivation of the Complete Sum of a Switching Function with the Aid of the Variable-entered Karnaugh Map

Abstract

The complete sum (CS) of a switching function f is defined as a sum-of-products formula whose products constitute all, and nothing but, the prime implicants of f It has many useful applications including the simplification and minimization of switching functions, proving equivalence or independence, solution of Boolean equations, and transient hazard analysis. This paper presents two novel techniques for deriving the CS with the aid of the variable-entered Karnaugh map (VEKM); a map that enjoys several pictorial advantages and a doubled variable-handling capability, and hence is recommended when the number of variables ranges from 7 to 12 or even more. Only completely specified switching functions (CSSFs) are considered herein, simply because the CS of an incompletely specified function f is that of the CSSF that represents the upper bound for f. Our first technique uses the VEKM for obtaining any product-of-sums expression for the function which can be multiplied out to produce the CS after deletion of any absorbable terms. The second technique starts with a VEKM of CS entries, and after repeated folding of the VEKM ends up with the required CS provided necessary absorptions are implemented after each folding. Both techniques gain much from the use of a novel multiplication matrix that restricts the number of term comparisons needed for implementing absorptions. This matrix can be used to advantage also with some purely algebraic techniques such as Tison method. However, algebraic techniques, even after improvement, might remain inferior to VEKM techniques, obviously since the latter can combine most merits of map and algebra. Dual versions of the VEKM techniques considered can be used to obtain the dual of the complete sum, viz., the complete product.