论文部分内容阅读
Batch code是在2004年由Ishai,Kushilevitz,Ostrovsky和Sahai[1]首先提出的,它的提出是为了表示一种分配方式以用来解决一个信息搜索问题,这个问题是:如何分配n个元素到m个服务器里(不同服务器可以放有同一元素),使得当我们需要n个元素中的任意k个时,我们可以通过从每个服务器中选择最多t个元素来找到我们所需要的这k个元素,同时让这些服务器总量N尽可能小。
我们研究当t=1时的情况,Ishai,Kushilevitz,Ostrovsky和Sahai[1]给出了batchcode的定义,如果把每个服务器看做是这n元集的一个子集,那么如何构造这样的batch code就可以看成是一个组合问题,由此引入CBC码(Combinatorial BatchCode)。Paterson,Stinson和Wei[2]给出了CBC码的定义,同时给出了判断CBC码的方法以及一些最优CBC码的构造。在本文章中,我们主要讨论每个服务器含有相同个数元素时(每个服务器含有a个元素)的CBC码,我们称这样的CBC码为ECBC码。我们给出了最优ECBC码的概念,并用m(n,a,k)表示最优时m的值。这篇文章中,我们重点介绍了当a=2和a=3时ECBC码的情况及构造方法,同时给出了当l≥2,k≥2时(m+l,m+l+k-1,k,m)-CBC码的不存在性证明,为今后寻找最优的一般CBC码提供一些参考。
全文共分四章,本文所用的主要符号将在第一章中给出详细说明,并列出文中所用的基本引理。
第一章,综述了CBC码的研究背景,并给出了CBC码的具体定义以及当前领域的研究成果。同时给出了判断CBC码的重要引理。
第二章,给出文章重点要讨论的ECBC码的定义,主要讨论并给出了当a=2时以及当a=3,n的值比较小时最优的ECBC码的构造方法,同时通过递归构造方法给出了m(n,2,k)的值及m(n,3,3)的一个上界。
第三章,这章主要改进前人方法证明了l≥2,k≥2时(m+l,m+l+k-1,k,m)-CBC码的不存在性。为今后寻找最优的一般CBC码的构造提供一些参考。
第四章,对文章进行总结,概述文章的主要结论以及对今后工作的展望。