Non-adaptive combinatorial group testing has applications in disease screening as well as in many problems in digital security and communications. Matrices that are d-disjunct (also called d-cover-free) can be built using codes and allow for the detection of d defective items using group testing. In this paper, we study d-disjunct matrices built from Reed-Solomon codes, and design a specialized algorithm for decoding the results of group testing using these matrices. We do an experimental comparison between our method and the naive one that only uses the d-disjunct property of the matrix, and show that the former outperforms the latter as the size of the problem grows.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Decoding of Group Testing Results from Reed-Solomon d-Disjunct Matrices

  • Dongxia Luo,
  • Lucia Moura

摘要

Non-adaptive combinatorial group testing has applications in disease screening as well as in many problems in digital security and communications. Matrices that are d-disjunct (also called d-cover-free) can be built using codes and allow for the detection of d defective items using group testing. In this paper, we study d-disjunct matrices built from Reed-Solomon codes, and design a specialized algorithm for decoding the results of group testing using these matrices. We do an experimental comparison between our method and the naive one that only uses the d-disjunct property of the matrix, and show that the former outperforms the latter as the size of the problem grows.