幾類編碼問(wèn)題研究中的組合學(xué)方法.pdf

1、伴隨著以計(jì)算機(jī)科學(xué)為代表的第三次工業(yè)革命的爆發(fā)，古老的組合數(shù)學(xué)重新煥發(fā)青春，而編碼理論更是現(xiàn)代計(jì)算機(jī)科學(xué)和數(shù)字通信技術(shù)的核心。組合數(shù)學(xué)、計(jì)算機(jī)理論和數(shù)字通信技術(shù)的研究對(duì)象都具有離散性質(zhì)，三門學(xué)科之間存在著天然的聯(lián)系。在本篇論文中，我們將從組合數(shù)學(xué)的視角出發(fā)考察編碼理論中的幾類問(wèn)題，包括常用的最優(yōu)線性糾錯(cuò)碼，電力線通信中的非線性糾錯(cuò)碼，以及用于多媒體防偽和信號(hào)壓縮感知的信息編碼等。
　　在論文的第一部分，我們將研究?jī)深悆?yōu)良線性分組糾

2、錯(cuò)碼的組合構(gòu)造方法。由于線性碼具有高效的編碼算法，是在實(shí)際生活中最為常用的編碼。在第2章中，我們將展示利用差集的軌道矩陣來(lái)構(gòu)造線性碼碼鏈的想法。這一方法是受到Ding等人從差集構(gòu)造循環(huán)碼以及Lander使用關(guān)聯(lián)結(jié)構(gòu)得到子模碼等相關(guān)工作的啟發(fā)而獲得的。在這一章中，我們將從具有素?cái)?shù)階半正則自同構(gòu)群的循環(huán)差集出發(fā)，研究其關(guān)聯(lián)矩陣在同構(gòu)作用下的軌道形成的分塊陣列。利用陣列的Smith標(biāo)準(zhǔn)型中的不變因子序列分布情況，我們從軌道矩陣中選取適當(dāng)?shù)男锌?/p>

3、間序列構(gòu)造線性碼碼鏈。很多例子都顯示，這一構(gòu)造方法得到的碼鏈中包含了許多達(dá)到各種理論上界的最優(yōu)線性碼。
　　但遺憾的一點(diǎn)是，上述方法構(gòu)造的線性碼不一定保持循環(huán)性，因此其解碼復(fù)雜度可能較高。為了克服這一缺點(diǎn)，我們將在第3章中研究一類可以通過(guò)信息傳遞等迭代算法快速譯碼的分組線性糾錯(cuò)碼，即低密度奇偶校驗(yàn)碼（LDPC碼）。這是一類性能非常接近Shannon極限的好碼，已經(jīng)在當(dāng)前各種最新的通信標(biāo)準(zhǔn)中占據(jù)主導(dǎo)地位。通過(guò)對(duì)基于循環(huán)群上的差矩陣內(nèi)

4、的元素進(jìn)行二元矩陣散布，我們可以獲得正則的擬循環(huán)低密度校驗(yàn)矩陣。與文獻(xiàn)中從其它組合結(jié)構(gòu)得到的碼進(jìn)行比較后發(fā)現(xiàn)，我們的方案在性能上與前人結(jié)果非常接近，但具有更大的靈活性，可以選擇的參數(shù)更廣。
　　第4章和第5章一起構(gòu)成了論文的第二部分。我們將在其中討論在電力線通信技術(shù)中具有重要應(yīng)用的兩類非線性分組糾錯(cuò)碼，它們分別是置換碼和常重復(fù)合碼，其中后者可以看作是前者的推廣形式。當(dāng)然，這兩類編碼在其它領(lǐng)域也都具有廣泛的應(yīng)用。目前關(guān)于置換碼的研究

5、進(jìn)展非常緩慢，事實(shí)上，我們只能構(gòu)造出最小距離不超過(guò)3的最優(yōu)置換碼。而對(duì)于一般的距離條件，關(guān)于其碼字個(gè)數(shù)的上下界估計(jì)都是極其困難的。在第4章里，我們通過(guò)將置換碼對(duì)應(yīng)到Cayley圖上的頂點(diǎn)獨(dú)立集，從而利用圖論中的方法對(duì)碼字?jǐn)?shù)目的下界進(jìn)行估計(jì)。在漸近意義下，即當(dāng)碼長(zhǎng)n趨于無(wú)窮時(shí)，我們的結(jié)果將傳統(tǒng)的Gilbert-Varshamov型下界提高了Ω（In（n））倍。
　　第5章中將探討的常重復(fù)合碼，可以看作置換碼放松了每個(gè)字母只能在碼字中

6、出現(xiàn)一次這一條件后得到的推廣形式;另一方面，它也可以被看作是傳統(tǒng)的二元常重碼的一類擴(kuò)展。從二十世紀(jì)九十年代后期以來(lái)，人們才逐漸展開(kāi)關(guān)于最優(yōu)常重復(fù)合碼的系統(tǒng)性研究。其中Chee等人于2008年確定出了重量為3時(shí)，所有長(zhǎng)度和距離的最優(yōu)三元常重復(fù)合碼所含的碼字個(gè)數(shù)。在這一章中，我們將延續(xù)前人的工作，利用可分組碼以及各種組合設(shè)計(jì)中的遞歸方法，完全構(gòu)造出重量為4且最小距離為5時(shí)，所有長(zhǎng)度的最優(yōu)三元常重復(fù)合碼。
　　以上兩個(gè)部分中研究的幾類編

7、碼，都屬于信道編碼中的分組糾錯(cuò)碼。而在論文的最后一部分，即第6章和第7章中，我們將把關(guān)注點(diǎn)轉(zhuǎn)移到兩類信息編碼問(wèn)題上。為了應(yīng)對(duì)數(shù)字多媒體內(nèi)容的盜版和篡改等問(wèn)題，一種通行的方法是向這些內(nèi)容中嵌入數(shù)字指紋。但普通的指紋只能追蹤單個(gè)非法用戶，而對(duì)于合謀犯罪無(wú)能為力。第6章所考慮的可分碼就是在這一背景下由Cheng等人提出的，它可以用來(lái)抵抗合謀犯罪中最為常見(jiàn)的平均攻擊模型。本章中研究了強(qiáng)度t=2時(shí)，可分碼的上下界問(wèn)題。我們利用坐標(biāo)分組的想法，大幅

8、改進(jìn)了前人提出的上界。特別的，當(dāng)可分碼是一個(gè)線性碼時(shí)，其上界可以被進(jìn)一步降低，并且我們將利用正交表構(gòu)造出了達(dá)到這一上界的線性可分碼。另一方面，我們分別使用概率方法和Stein-Lovász定理，得到了可分碼的一些下界結(jié)果。其中，在碼長(zhǎng)固定而字母表大小趨向無(wú)窮的這一漸近意義下，由前一方法得到的可分碼的大小和我們改進(jìn)后的上界具有相同的階。
　　在第7章中，我們展示了使用代數(shù)曲線構(gòu)造壓縮感知矩陣的方法。壓縮感知理論研究如何從極少次數(shù)的測(cè)