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

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

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

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

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

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

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

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