论文部分内容阅读
批量码是在2004年Ishai,Kushilevitz,Ostrovsky和Sahai首次提出的.它是一种解决数据存储问题的方法.它的实际背景是:如何分配n项数据到m个服务器里,使得当用户需要这n项中的任意k项时,可以通过从每个服务器中至多读取t项来得到,同时使得这些服务器的总存储量N尽可能的小.如果我们把批量码的每个服务器中存储的项限制成n项数据的一个子集就得到了(n,N,k,m,t)组合批量码(Combinatorial BatchCodes,以下简称为CBC).在实际应用中,一般只考虑t=1的情形.给定n,k,m,我们的目的是要找到所有(n,N,k,m)-CBC中总存储量最小的(n,N,k,m)-CBC,把此CBC称为是最优的,同时用N(n,k,m)来表示最优时N的值.在利用CBC解决实际问题时,对于给定的参数n,k,m,要求N的值越小越好. 本文的主要内容是研究最优CBC具有的单调性质和确定一类最优CBC中N的值.2008年,Paterson和Stinson给出了N(m+1,k,m)的值,Richard和Kathleen给出了N(m+2,k,m)的值,延续这个思想我们尝试着去确定N(m+3,k,m)的值.当k=1时,显然N(m+3,1,m)=m+3.同时,Paterson和Ruj等确定出了N(m+3,2,m)和N(m+3,3,m)的值.此外,他们还确定了当m+3≥(k-1)(mk-1)和(mk-2)≤m+3≤(k-1)(mk-1)时N(m+3,k,m)的值,当m+3＜(mk-2)时,N(m+3,k,m)的值还未确定.对于一般情形,确定出N(m+3,k,m)的值较为困难,本文中主要研究k=4时的特殊情形,即确定N(m+3,4,m)的值. 本文的结构如下: 第一章,给出最优CBC具有的几个单调性质,并给出了当N(n1,k,m1)=t1和N(n2,k,m2)=t2时(n1+n2,t1+t2,k,m1+m2)-CBC的存在性证明. 第二章,先利用对偶定理得出N(9,4,6)=15,然后通过结合最优CBC的单调性质和利用递推不等式得出N(m+3,4,m)=m+9(m≥6). 第三章,利用反证法得到N(8,4,5)=15.