Derivation of All Particular Solutions of a ‘Big’ Boolean Equation with Applications in Digital Design
Ali Muhammad Rushdi *
Department of Electrical and Computer Engineering, King Abdulaziz University, P.O.Box 80204, Jeddah 21589, Saudi Arabia.
Sultan Sameer Zagzoog
Department of Electrical and Computer Engineering, King Abdulaziz University, P.O.Box 80204, Jeddah 21589, Saudi Arabia.
*Author to whom correspondence should be addressed.
Abstract
This paper considers the problem of solving a system of Boolean equations over a finite (atomic) Boolean algebra other than the two-valued one. The paper outlines classical and novel direct methods for deriving the general parametric solution of such a system and for listing all its particular solutions. A detailed example over B256 is used to illustrate these two methods as well as a third method that starts by deriving the subsumptive solution first. The example demonstrates how the consistency condition forces a collapse of the underlying Boolean algebra to a subalgebra, and also how to list a huge number of particular solutions in a very compact space. Subsequently, the paper proposes some potential applications for the techniques of Boolean-equation solving. These techniques are very promising as useful extensions of classical techniques based on two-valued Boolean algebra.
Keywords: Big Boolean algebra, parametric solution, listing of particular solutions, digital design, direct and inverse arithmetic, integer factorization, Diophantine equations