Union-free codes and disjunctive codes are two combinatorial structures, which are used in nonadaptive group testing to find a set of $d$ defective elements among $n$ samples by carrying out the minimal number of tests $t$. It is known that union-free codes have a larger rate, whereas disjunctive codes provide a more efficient decoding algorithm. In this paper we introduce a new family of codes for nonadaptive group testing with fast decoding. The rate of these codes is larger than the rate of disjunctive codes, while the decoding algorithm has the same complexity. In addition, we derive a lower bound on the rate of new codes for the case of $d=2$ defectives, which is significantly better than the bound for disjunctive codes and almost as good as the bound for union-free codes.


翻译:无工会守则和分离代码是两种组合结构,用于非适应性组别测试,通过进行最低数量的测试,在一美元样本中找到一组美元缺陷元素。众所周知,无工会守则的比例较高,而脱钩守则提供了更有效的解码算法。在本文中,我们引入了非适应性组别快速解码测试的新编码组合。这些编码的比率高于分离性编码的比率,而解码算法也具有同样的复杂性。此外,我们对美元=2美元的缺陷案例的新编码率的约束程度较低,这大大优于脱钩编码的约束,几乎与无工会守则的约束值一样好。

0
下载
关闭预览

相关内容

专知会员服务
72+阅读 · 2021年1月12日
【2020新书】数据科学与机器学习导论,220页pdf
专知会员服务
80+阅读 · 2020年9月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
计算机视觉最佳实践、代码示例和相关文档
专知会员服务
17+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
一文读懂Faster RCNN
极市平台
5+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年10月21日
Arxiv
0+阅读 · 2021年10月20日
Arxiv
0+阅读 · 2021年10月19日
Arxiv
0+阅读 · 2021年10月19日
Arxiv
0+阅读 · 2021年10月15日
VIP会员
相关VIP内容
专知会员服务
72+阅读 · 2021年1月12日
【2020新书】数据科学与机器学习导论,220页pdf
专知会员服务
80+阅读 · 2020年9月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
计算机视觉最佳实践、代码示例和相关文档
专知会员服务
17+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Top
微信扫码咨询专知VIP会员