Abstract| A CDEC gate, or a Condition Decoder, being a product of an AND and NAND of literals, has been introduced in the logic array of the high-speed EPLD CY7C361 chip from Cypress. In this paper we give an algorithm for the minimization of SUM-OF-CDEC (SOC) expressions. This algorithm produced the minimum solutions on all small single-output functions, as required by this chip. We propose also the new concept of a CDEC-PLA and show its advantage over the existing AND/OR PLAs. This structure realizes multi-output SUM-OF-CDEC (SOC) expressions, which generalize the well known SUM-OF-PRODUCT expressions of PLAs. An e.cient heuristic algorithm for the minimization of the multi-output SOC expressions is given. We also propose a new approach for solving covering/factorization problems, called Conditional Graph Coloring. This method is used to minimize SOCs, but can be used in many other applications. Comparison of several versions of the algorithm on benchmarks proves that our fast multi-output algorithm generates high-quality solutions and is especially efficient on strongly unspecifed functions.