一種新型的CBC碼.pdf

1、Batch code是在2004年由Ishai，Kushilevitz，Ostrovsky和Sahai[1]首先提出的，它的提出是為了表示一種分配方式以用來解決一個信息搜索問題，這個問題是：如何分配n個元素到m個服務(wù)器里(不同服務(wù)器可以放有同一元素)，使得當(dāng)我們需要n個元素中的任意k個時，我們可以通過從每個服務(wù)器中選擇最多t個元素來找到我們所需要的這k個元素，同時讓這些服務(wù)器總量N盡可能小。
　　 我們研究當(dāng)t=1時的情況，Is

2、hai，Kushilevitz，Ostrovsky和Sahai[1]給出了batchcode的定義，如果把每個服務(wù)器看做是這n元集的一個子集，那么如何構(gòu)造這樣的batch code就可以看成是一個組合問題，由此引入CBC碼(Combinatorial BatchCode)。Paterson，Stinson和Wei[2]給出了CBC碼的定義，同時給出了判斷CBC碼的方法以及一些最優(yōu)CBC碼的構(gòu)造。在本文章中，我們主要討論每個服務(wù)器含有相同

3、個數(shù)元素時(每個服務(wù)器含有a個元素)的CBC碼，我們稱這樣的CBC碼為ECBC碼。我們給出了最優(yōu)ECBC碼的概念，并用m(n，a，k)表示最優(yōu)時m的值。這篇文章中，我們重點介紹了當(dāng)a=2和a=3時ECBC碼的情況及構(gòu)造方法，同時給出了當(dāng)l≥2，k≥2時(m+l，m+l+k-1，k，m)-CBC碼的不存在性證明，為今后尋找最優(yōu)的一般CBC碼提供一些參考。
　　 全文共分四章，本文所用的主要符號將在第一章中給出詳細(xì)說明，并列出文中所

4、用的基本引理。
　　 第一章，綜述了CBC碼的研究背景，并給出了CBC碼的具體定義以及當(dāng)前領(lǐng)域的研究成果。同時給出了判斷CBC碼的重要引理。
　　 第二章，給出文章重點要討論的ECBC碼的定義，主要討論并給出了當(dāng)a=2時以及當(dāng)a=3，n的值比較小時最優(yōu)的ECBC碼的構(gòu)造方法，同時通過遞歸構(gòu)造方法給出了m(n，2，k)的值及m(n，3，3)的一個上界。
　　 第三章，這章主要改進(jìn)前人方法證明了l≥2，k≥2時(m+