Portal de Periódicos da CAPES

Efficient polarity conversion for large Boolean functions

1999; Volume: 146; Issue: 4 Linguagem: Inglês

10.1049/ip-cdt

1359-7027

L. Wang, A.E.A. Almaini, A. Bystrov,

Logic, programming, and type systems

The concept of polarity for canonical sum-of-products (SOP) Boolean functions is introduced. This facilitates efficient conversion between SOP and fixed polarity Reed-Muller (FPRM) forms. New algorithms are presented for the bidirectional conversion between the two paradigms. Multiple segment and multiple pointer techniques are employed to achieve fast conversion for large Boolean functions. Experimental results are given using a personal computer with Cyrix 6x86-166 CPU and 32MB RAM. The results show that the algorithm is very efficient in terms of time and space for large Boolean functions.