可分組設(shè)計(jì)及其在信息科學(xué)中的應(yīng)用.pdf

1、可分組設(shè)計(jì)(GDD)在組合設(shè)計(jì)理論中有著極其重要的作用，它們被廣泛地用來構(gòu)造各類設(shè)計(jì)。例如，在組合設(shè)計(jì)理論奠基人Wilson和Hanani證明成對(duì)平衡設(shè)計(jì)存在的充分必要條件時(shí)，可分組設(shè)計(jì)是他們遞歸構(gòu)造過程中不可缺少的一部分。類似地，可分解可分組設(shè)計(jì)和frame在構(gòu)造具有可分解性質(zhì)的設(shè)計(jì)的時(shí)候同樣起著基礎(chǔ)性的作用。我們稱一個(gè)GDD是型一致的如果它所有組的大小均相同。本文研究了多類可分組設(shè)計(jì)的存在性問題，包括型不一致的4-GDD，型一致的5

2、-GDD，4-RGDD，4-frame以及G-GDD等。同時(shí)，我們也討論了可分組設(shè)計(jì)在信息科學(xué)當(dāng)中的應(yīng)用，這些應(yīng)用包括光纖網(wǎng)絡(luò)中的業(yè)務(wù)疏導(dǎo)問題以及非線性糾錯(cuò)碼。
　　在第2章中，我們研究了型為gum1的可分組設(shè)計(jì)存在性問題。當(dāng)區(qū)組大小為3時(shí)，這個(gè)問題已被Colbourn，Hoffman和Rees于1992年解決。而區(qū)組大小是4的情形還沒有被解決。目前關(guān)于此類4-GDD的存在性結(jié)果多集中于gu是偶數(shù)的情況。本文將考察此類4-GDD整

3、個(gè)存在性問題。我們證明了對(duì)任意給定的g，除了很小一部分的u外，型為gum1的4-GDD存在的必要條件（關(guān)于參數(shù)u和m）也是充分的。作為這類型不一致的GDD的應(yīng)用，我們構(gòu)造了一些其他類型的設(shè)計(jì)，包括成對(duì)平衡設(shè)計(jì)，有向成對(duì)平衡設(shè)計(jì)，Kirkman frame，以及可分組覆蓋設(shè)計(jì)。
　　在第3章中，我們繼續(xù)研究了5-GDD，4-RGDD以及4-frame的存在性問題。雖然整個(gè)問題還沒有徹底解決，但我們已取得了很大的進(jìn)展。我們的結(jié)果主要集

4、中在組相對(duì)比較大的情形。我們?nèi)〉眠@些結(jié)果要?dú)w功于兩類強(qiáng)有力的遞歸構(gòu)造，它們是“雙可分組設(shè)計(jì)構(gòu)造”和“Rees型乘積構(gòu)造”。在應(yīng)用的時(shí)候我們對(duì)這兩類構(gòu)造都做了一些改進(jìn)。此外我們還構(gòu)造了一些較小的設(shè)計(jì)，包括型為2184，944，1818和3611的4-RGDD。
　　在第4章，可分組設(shè)計(jì)的概念擴(kuò)展到了G-可分組設(shè)計(jì)。我們利用G-GDD構(gòu)造了五個(gè)頂點(diǎn)的G-設(shè)計(jì)。此類設(shè)計(jì)的存在性問題最早由Bermond，Huang，Rosa和Sottea

5、u于1980年提出，并與光纖網(wǎng)絡(luò)中的業(yè)務(wù)疏導(dǎo)問題密切相關(guān)，但至今仍未徹底解決。我們完全解決了這個(gè)問題，同時(shí)對(duì)幾乎所有的n，確定了n階C-疏導(dǎo)的最小成本，這里C≤9。
　　在第5章，我們考察了長度為n的完備的q元t-刪位糾錯(cuò)碼碼字個(gè)數(shù)所有可能的取值。由于在Levenshteǐn距離下半徑為t的球可以有不同的大小，所以完備的t-刪位糾錯(cuò)碼的碼字個(gè)數(shù)可以是不一樣的，因而確定所有可能的取值是有意義的。當(dāng)t=n-2時(shí)，t-刪位糾錯(cuò)碼和有向填

6、充問題密切相關(guān)，后者的構(gòu)造主要基于組合設(shè)計(jì)理論中的工具。在本章中，我們通過構(gòu)造大量的不完全有向填充，基本上確定了完備的(4，2)q-DCC所有可能的大小，這里還剩下大小為62的(4，2)19-DCC和大小為196的(4，2)34-DCC沒有解決。
　　第6第7兩章主要研究常重碼(CWC)和常重復(fù)合碼(CCC)。已有許多種工具被用來確定常重碼和常重復(fù)合碼碼字個(gè)數(shù)的最大值，其中包括了一些組合的手段。我們對(duì)其中的可分組碼(GDC)和完全

7、可約超單(CRSS)設(shè)計(jì)比較感興趣。Chee，Ge和Ling提出了可分組碼的概念，并用來確定重量為三的最優(yōu)常重復(fù)合碼的大小。在第6章中，我們研究了重量為四、極小距離為六的最優(yōu)三元常重復(fù)合碼的構(gòu)造問題。除了一小部分的長度外，我們基本上將這個(gè)問題解決了。完全可約超單設(shè)計(jì)與多元常重碼相關(guān)，一個(gè)(v，k，λ)-CRSS設(shè)計(jì)就是一個(gè)最優(yōu)（v，2（k-1），k）λ+1-碼。在第7章中，我們基本上解決了(v，5，2)-CRSS設(shè)計(jì)的存在性問題，除了可