Scholarlink

<p>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á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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Gpu generation of binary 2-separating codes

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月11日

查看全文
  • Marcel Fernandez,
  • F. J. Martinez-Zaldivar,
  • Victor M. Garcia-Molla,
  • M. Angeles Simarro,
  • John Livieratos,
  • Alberto Gonzalez

摘要

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á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.