Solution of Boolean differential equations on systolic arrays (Q1364106)

Boolean differential equations arise in the analysis of binary system dynamics, design and diagnosis of combinational networks, generation of test sequences, and determination of special properties of Boolean functions. The existing solution methods, such as the method of undetermined coefficients are intended for sequential computers, and are not suitable for implementation on homogeneous computing structures with parallel computations. This raises the question of ``translating'' the problem into the language of parallel algorithms. In this paper, we propose a method for solving Boolean differential equations that can be implemented on homogeneous computing structures, and present an example of such a structure. The proposed approach replaces the original Boolean differential equation with a system of logical equations in Reed-Muller form and solves the resulting system by fast algorithms using vector-matrix procedures.