RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication
Artículo científico (JournalArticle)
Gpu generation of binary 2-separating codes
[EN] This paper addresses the generation of binary 2-separating codes and the study of the code rates that can be achieved in practice. In the case of binary 2-separating codes, there exist lower and upper theoretical bounds in the rates that can be achieved. The generation of 2-separating codes has been studied from a theoretical point of view, but, as far as we know, it has not been tackled from a practical point of view. In this paper, we consider and analyze two different generation algorithms. Both algorithms were implemented in CUDA and executed in GPUs, for the sake of efficiency. The first algorithm is inspired by the Moser-Tardos algorithm, which is based on the Local Lov & aacute;sz Lemma. This algorithm has a strong theoretical appeal; codes obtained through this first algorithm can be shown to match the best known lower bound. To generate codes with rates as large as possible, a second algorithm has been implemented. The rates achieved are larger than those achieved with the first algorithm, but they still are very far from the theoretical upper bound. The results obtained suggest that the theoretical upper bound can probably be improved., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work was supported in part by the Spanish Ministery of Science and Innovation under grant
PID2021-125736OB-I00 (MCIN/AEI /10.13039/501100011033/, ERDF A way of making
Europe ), and by GVA under grant CIPROM/2022/20. The work of Marcel Fernández has been
supported by TCO-RISEBLOCK (PID2019-110224RB-I00) MINECO.
Project:
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2019-110224RB-I00
,
Agencia Estatal de Investigación / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-125736OB-I00
,
Generalitat Valenciana CIPROM/2022/20