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.

Low-weight superimposed codes and their applications

Gargano, Luisa;Rescigno, Adele A.;Vaccaro, Ugo
2018-01-01

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.
2018
9783319784540
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4713380
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
social impact