一種新型的CBC碼.pdf

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

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

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

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