View in EDS

Low-weight superimposed codes and related combinatorial structures: Bounds and applications.

Saved in:
Bibliographic Details
Title: Low-weight superimposed codes and related combinatorial structures: Bounds and applications.
Authors: Gargano, Luisa1 (AUTHOR) lgargano@unisa.it, Rescigno, Adele Anna1 (AUTHOR) arescigno@unisa.it, Vaccaro, Ugo1 (AUTHOR) uvaccaro@unisa.it
Source: Theoretical Computer Science. Feb2020, Vol. 806, p655-672. 18p.
Subjects: Superimposed coding, Telecommunication systems, Data security, K-nearest neighbor classification
Abstract: A (k , n) -superimposed code is a well known and widely used combinatorial structure that can be represented by a t × n binary matrix such that for any k columns of the matrix and for any column c chosen among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k − 1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k , n) -superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and z -error correcting superimposed codes. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:A (k , n) -superimposed code is a well known and widely used combinatorial structure that can be represented by a t × n binary matrix such that for any k columns of the matrix and for any column c chosen among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k − 1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k , n) -superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and z -error correcting superimposed codes. [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2019.10.032