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

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

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

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

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

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

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

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

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