Gpu generation of binary 2-separating codes

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