This article is cited in 2 papers

Computational Methods in Discrete Mathematics

Fast algorithm for recovering the true solution with fixed weight of a system of linear Boolean equations with noised right-hand side

A. N. Alekseychuk, A. Yu. Gryaznukhin

Institute of Special Communications and Protection of Informatics, Kiev, Ukraine

Abstract: A system of linear Boolean equations with noised right-hand side is considered. It is assumed that the true solution of the system has a predetermined weight that is independent of the number of variables in the system. A probabilistic algorithm for finding this solution is proposed. The time complexity of our algorithm is less than the time complexity of maximum likelihood method, and in contrast to the known algorithms with this property, our algorithm uses only comparisons and (bitwise and arithmetic) additions of binary integers. The proposed algorithm can be used in practice in some cases when other algorithms are less efficient.

Keywords: system of Boolean linear equations with noised right-hand side, probabilistic algorithm.

UDC: 631.391+519.2