Computational methods in discrete mathematics

Solving undetermined systems of linear Boolean equations with corrupted right-hand side and low-weight true solution

N. Yu. Rumenko, A. V. Kostyuk

Moscow Technical University of Communications and Informatics

Abstract: Undetermined systems of random linear Boolean equations with corrupted right-hand side and with a true solution of little Hamming weight are studied. Experimentally, we show that, for small bit-error rates, these systems can be efficiently solved by decoding algorithms with regard to information symbols.

Keywords: random systems of linear Boolean equations, information-set decoding.

UDC: 519.6

DOI: 10.17223/2226308X/12/64

Bibliographic databases:

•