Solving undetermined systems of linear boolean equations with corrupted right-hand side and low-weight true solution | Applied Discrete Mathematics. Supplement. 2019. № 12. DOI: 10.17223/2226308X/12/64

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

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.

Download file

Counter downloads: 119

Keywords

случайные системы линейных булевых уравнений, декодирование по информационным множествам, random systems of linear Boolean equations, information-set decoding

Authors

Name	Organization	E-mail
Rumenko N. Yu.	Moscow Technical University of Communications and Informatics	nrum90@yandex.ru
Kostyuk A. V.	Moscow Technical University of Communications and Informatics	av_kost@mail.ru

Всего: 2

References

Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике. М.: ТВП, 1997. T. 1. C. 1-18.

Алексейчук А. Н., Грязнухин А. Ю. Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью // Прикладная дискретная математика. 2013. Т. 20. №2. С. 59-70.

Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок // Доклады АН СССР. 1957. C. 739-741.

May A, Meurer A., and ThomaeE. Decoding random linear codes in O(2°-054n) // Proc. Asiacrypt'2011. Seoul, South Korea, December 04-08, 2011. P. 107-124.