Optimisation of Reed–Muller PLA implementations

Decomposition techniques are utilised for mixed polarity Reed–Muller minimisation, which lead to Reed–Muller programmable logic array implementations for Boolean functions. The proposed algorithm produces a simplified mixed polarity Reed–Muller format from the conventional sum-of-products input based on a top-down strategy. The output format belongs to the most general class of AND/XOR forms, namely exclusive-OR sum-of-products. This method is further generalised to very large multiple output Boolean functions. The developed decomposition method is implemented in the C language and tested with MCNC and IWLS’93 benchmarks. Experimental results show that the decomposition method can produce much better results than Espresso for many test cases. This efficient method offers compact Reed–Muller programmable logic array implementations with the added advantage of easy testability, in contrast to the conventional programmable logic array realisations.