Group testing schemes from low-weight codewords of BCH codes

Shashanka Ubaru, Arya Mazumdar, Alexander Barg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Despite a large volume of research in group testing, explicit small-size group testing schemes are still difficult to construct, and the parameters of known combinatorial schemes are limited by the constraints of the problem. Relaxing the worst-case identification requirements to probabilistic localization of defectives enables one to expand the range of parameters, and yet the small-size practical constructions are sparse. Motivated by this question, we perform an experimental study of almost disjunct matrices constructed from low-weight codewords of binary BCH codes, and evaluate their performance in nonadaptive group testing. We observe that identification of defectives is much more stable in these schemes compared to the schemes constructed from random binary matrices. We derive an estimate of the error probability of identification in the constructed schemes which provides a partial explanation of their performance.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509018062
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2016 IEEE International Symposium on Information Theory, ISIT 2016

Bibliographical note

Funding Information:
Research supported by NSF grant CCF- 1318597. Part of the work was done when the author was at University of Minnesota. Research supported in part by NSF grants CCF1318093 and CCF1453121. Research supported by NSF grants CCF1217245 and CCF1422955

Publisher Copyright:
© 2016 IEEE.

Fingerprint Dive into the research topics of 'Group testing schemes from low-weight codewords of BCH codes'. Together they form a unique fingerprint.

Cite this