State Key Lab of ASIC and Systems, Fudan University, Shanghai, China

---

Abstract—An efficient minimisation method is presented to find the best polarity of fixed polarity canonical orcoincidence (COC) expansions. The method derives one COC fixed polarity expansion from another adjacent polarity expansion. To reduce CPU time, it utilises bitwise operation and Gray code. Furthermore, it counts the number of “0”s in the polarity matrix rather than polarity matrix multiplication. As a result, it makes minimisation for large functions within reasonable time practical. The space complexity of the proposed algorithm is O(M) and time complexity is O(2n(MlogM+M)) (n and M are the number of input variables and the number of on-set COC maxterms).

Index Terms—An efficient minimisation method is presented to find the best polarity of fixed polarity canonical orcoincidence (COC) expansions. The method derives one COC fixed polarity expansion from another adjacent polarity expansion. To reduce CPU time, it utilises bitwise operation and Gray code. Furthermore, it counts the number of “0”s in the polarity matrix rather than polarity matrix multiplication. As a result, it makes minimisation for large functions within reasonable time practical. The space complexity of the proposed algorithm is O(M) and time complexity is O(2n(MlogM+M)) (n and M are the number of input variables and the number of on-set COC maxterms).

[PDF]

Cite: Meng Yang, Jiarong Tong, and Jinmei Lai, " Optimisation of Fixed Polarity Canonical Or-Coincidence Expansions," Journal of Computers vol. 8, no. 10, pp. 2520-2526, 2013.