多値2入力論理関数のAND-EXOR論理式の最小化

摘要

AND-EXOR論理式はESOP（Exclusive-OR Sum-of-Products）表現とも呼ばれ，現在まで様々なクラス・条件の論理関数に対して，ESOP表現の簡単化や最小化のアルゴリズムが開発されている．本稿では，多値2入力論理関数に焦点をしぼり，最小のESOP表現を求める多項式時間アルゴリズムを与える．%There are a lot of algorithms to simplify or minimize AND-EXOR expressions, called ESOP (Exclu-sive-OR Sum-of-Products) forms, for various classes of logical functions. In this paper, focusing on the minimization of ESOP forms for multiple-valued 2-input logical functions, we give a polynomial time algorithm to find a minimum ESOP form.