Logic synthesis for cellular architecture FPGAs using BDDs

In this paper, an efficient approach to the synthesis of CA (Cellular Architecture)-type FPGAs is presented. To exploit the array structure of cells in CA-type FPGAs, logic expressions called Maitra terms, which can be mapped directly to the cell arrays are generated. In this approach, a BDD is modified so that each node of the BDD has another branch which is an exclusive-OR of the two branches of a node. Once the modified BDD is obtained, a traversal of the BDD is sufficient to generate the Maitra terms needed. Since a BDD can be traversed in O(n) steps, where it is the number of nodes in the BDD, Maitra terms are generated very efficiently. This also removes the need for generating minimal SOP or ESOP expressions which can be costly in some cases. The experiments show that the proposed method generates better results than existing methods.