Fast Tabular Based Conversion Methods for Canonical OR-Coincidence

摘要

Two fast conversion algorithms based on tabular technique for Canonical OR-Coincidence (COC) expansions are introduced. By using bitwise operations, the Serial Tabular Technique (STT) can achieve speed of less than 2 seconds for 21 variables for randomly generated functions. The other proposed Fast Parallel Tabular Technique (FPTT) generates new terms in parallel instead of one variable at a time and achieves fast conversion speed of less than 6 seconds for 25 variables for sparse functions. Inverse method is proposed to improve the conversion speed of STT and FPTT when the number of maxterms is greater than 2ⁿ/2. The experimental results obtained by STT and FPTT are also compared to those in the literature. Our results outperform those significantly in all cases and could achieve less than 0.2 seconds for IWLS benchmark up to 17 variables.