Software for generation of binary 2-separating codes

This software addresses the generation of binary 2-separating codes, and the study of the code rates that can be achieved in practice. In a separating code any two disjoint subsets (of maximum specified size) of code words have at least one position in which the sets of entries are disjoint. 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 in the literature from a theoretical point of view, but, as far as we know, it has not been tackled from a practical point of view. Here we consider two different generation algorithms. The first one is inspired by the Moser-Tardos algorithm, 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. A second algorithm has been implemented, which was designed to generate codes with rates as large as possible. The rates achieved are larger than those achieved with the first algorithm, but they still are very far form the theoretical upper bound.