SOFTWARE FOR GENERATION OF BINARY 2-SEPARATING CODES

This repository contains the source code of several algorithms for generation of separating codes, written by Francisco-José Martínez-Zaldívar¹, Víctor M. García-Mollá², Marcel Fernández³, M.ª Ángeles Simarro⁴, John Livieratos⁵ and Alberto González¹.

• Overview

• Contents

• Acknowledgements

• References

¹ Department of Communications. Universitat Politècnica de València, València (Spain)
² Department of Informatics Systems and Computation. Universitat Politècnica de València, València (Spain)
³ Department of Network Engineering, Universitat Politècnica de Catalunya, Barcelona (Spain)
⁴ ITEAM, Institute of Telecommunications and Multimedia Applications, Universitat Politècnica de València, València (Spain)
⁵ Department of Mathematics. National Kapodistrian University of Athens, (Greece)

Overview

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.

Contents

• The folder version_matlab_paper has a version that only needs Matlab.

• The folder version_matlab_gpu_paper has a version that requires Matlab, a CUDA programmable GPU and the Matlab Parallel Toolbox.

• The folder version_cuda_seq_add has a CUDA version of the sequential addition algorithm. Requires a CUDA programmable GPU and the nvcc CUDA compiler.

Acknowledgements

This work was supported in part by MICIN 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.

References

[1] Y. L. Sagalovich, Separating systems, Problemy Peredachi Informatsii 30 (2) (1994) 14–35.

[2] A. Barg, G. R. Blakley, G. A. Kabatiansky, Digital fingerprinting codes: Problem statements, constructions, identification of traitors, IEEE Transactions on Information Theory 49 (4) (2003) 852–865.

[3] J. Moreira, M. Fernández, G. Kabatiansky, Almost separating and almost secure frameproof codes over q-ary alphabets, Des. Codes Cryptogr. 80 (1) (2016) 11–28.

[4] J. Körner, G. Simonyi, Separating partition systems and locally different sequences, SIAM journal on discrete mathematics 1 (3) (1988) 355–359.

[5] I. V. Vorob’ev, V. S. Lebedev, Improved upper bounds for the rate of separating and completely separating codes, Probl. Inf. Transm. 58 (3) (2022) 242–253.

[6] P. Erdös, L. Lovàsz, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets 10 (1975) 609–627.

[7] R. A. Moser, A constructive proof of the Lov´asz local lemma, in: Proceedings 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, 2009, pp. 343–350.

[8] R. A. Moser, G. Tardos, A constructive proof of the general Lovàsz local lemma, Journal of the ACM (JACM) 57 (2) (2010) 11.

[9] I. Giotis, L. Kirousis, K. I. Psaromiligkos, D. M. Thilikos, On the algorithmic Lov´asz local lemma and acyclic edge coloring, in: Proceedings of the twelfth workshop on analytic algorithmics and combinatorics, Society for Industrial and Applied Mathematics, 2015, pp. 16–25.

[10] M. Fernández, J. Livieratos, Algorithmic aspects on the construction of separating codes, in: Analysis of Experimental Algorithms - Special Event, SEA2 2019, Kalamata, Greece, June 24- 29, 2019, Revised Selected Papers, Vol. 11544 of Lecture Notes in Computer Science, Springer, 2019, pp. 513–526.

[11] NVIDIA Corporation, NVIDIA CUDA Compute Unified Device Architecture Programming Guide, NVIDIA Corporation, 2007.

[12] J. Spencer, Asymptotic lower bounds for ramsey functions, Discrete Mathematics 20 (1977) 69–76.

[13] MATLAB, version 9.8.0.1323502 (R2020a), Natick, Massachusetts, 2020.

[14] MATLAB, Parallel computing toolbox version 7.2 (r2020a) (2022).